无法端口C++其插入到一个字典树来锈病由于多个可变代码借用

Question

我有以下C++代码：

#include <vector> 
#include <string> 
using namespace std; 

struct Trie { 
    bool eow;   //end of word 
    char val; 
    vector<Trie> chd; //children 

    void push_word(const string& word){ 
    Trie& trie = *this; 
    for (char c: word){ 
     if (trie.chd.empty() || trie.chd.back().val != c) { 
     trie.chd.push_back(Trie{false, c, vector<Trie>{}}); 
     } 
     trie = trie.chd.back(); 
    } 
    trie.eow = true; 
    } 
}; 

这对串的线索。 push_word应该只接受按字典顺序大于trie中已经包含的任何单词的字符串;这样可以在每个节点上跳过搜索正确的孩子。换句话说，这使我们能够有效地从字的排序矢量构建特里结构：

Trie from_sorted_vector(const vector<string>& words){ 
    Trie trie{false, '\0', vector<Trie>{}}; 
    for (const auto& word: words) { 
    trie.push_word(word); 
    } 
    return trie; 
} 

在锈病我有以下：

#[derive(Eq, PartialEq, Debug, Clone)] 
struct Trie { 
    eow: bool, 
    val: char, 
    chd: Vec<Trie>, 
} 

impl Trie { 
    fn new(eow: bool, val: char, chd: Vec<Trie>) -> Trie { 
     Trie { 
      eow: eow, 
      val: val, 
      chd: chd, 
     } 
    } 

    fn push_word(&mut self, word: &String) { 
     let mut trie = self; 
     for c in word.chars() { 
      // ??? 
     } 
    } 
} 

我不能以类似的方式实现push_word到C++。对于trie或trie.chd或trie.chd的最后一个元素，我总是得到两个可变借入或一个不可变和一个可变借入。我想知道如何完成这个任务。

Answer 1

看到这一个奇怪的伎俩击败借位检查器：编译器恨它。

#[derive(Eq, PartialEq, Debug, Clone)] 
struct Trie { 
    eow: bool, 
    val: char, 
    chd: Vec<Trie>, 
} 

impl Trie { 
    fn new(eow: bool, val: char, chd: Vec<Trie>) -> Trie { 
     Trie { 
      eow: eow, 
      val: val, 
      chd: chd, 
     } 
    } 

    fn push_word(&mut self, word: &String) { 
     let mut trie = self; 
     for c in word.chars() { 
      if trie.chd.last().map_or(true, |t| t.val != c) { 
       trie.chd.push(Trie::new(false, c, vec![])) 
      } 

      let tmp = trie; // * 
      trie = tmp.chd.last_mut().unwrap(); 
     } 

     trie.eow = true; 
    } 
} 

fn main() {} 

这是引进线的标记*，使这项工作。编译器还不够聪明，看到trie通过last_mut的可变子借项是替代trie的可变借款。如果它理解了这一点，它会接受显而易见的代码trie = trie.chd.last_mut().unwrap();，但是现在程序员必须通过首先将借出移出trie来手动作出保证，然后可以自由重新分配。这以一种编译器可以理解的方式移动了借用的所有权。

这覆盖了issue #10520。

Answer 2

有是完成同huon's answer一个稍微精简的方法，但无需明确的临时变量：

fn push_word(&mut self, word: &String) { 
    let mut trie = self; 
    for c in word.chars() { 
     if trie.chd.last().map_or(true, |t| t.val != c) { 
      trie.chd.push(Trie::new(false, c, vec![])) 
     } 

     trie = { trie }.chd.last_mut().unwrap(); // Here 
    } 

    trie.eow = true; 
} 

我们附上了“老”特里在一个块，其中转移所有权，创建一个未命名的临时文件。