由于多个可变借用而无法移植插入到trie中的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:

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;
}

我在Rust中有以下内容:

#[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() {}

标记的线条的引入*使这项工作成功.编译器还不够聪明,看不到trievia 的可变子借用last_mut正在取代可变借用trie.如果它理解了这一点,它就会接受明显的代码trie = trie.chd.last_mut().unwrap();,但是目前程序员必须通过先移出借用来手动进行这种保证trie,然后可以自由地重新分配.这会以编译器可以理解的方式移动借用的所有权.

问题#10520涵盖了这一点.

Answer 2

一旦启用了非词法生命周期,原始代码就可以工作:

#![feature(nll)]

#[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, val, chd }
    }

    fn push_word(&mut self, word: &str) {
        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();
        }

        trie.eow = true;
    }
}

fn main() {}

NLL提高了编译器借用检查器的精度,使其能够看到不再使用可变借位.

在默认情况下启用NLL之前,有一个稍微简化的方法可以完成与huon的答案相同的方法,但不需要显式的临时变量:

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;
}

我们将"旧"特里放在一个区块中,该区块转移所有权,创建一个未命名的临时区.