由于多个可变借用，无法将插入到 Rust 中的 C++ 代码移植到 Rust [英] Unable to port C++ code that inserts into a trie to Rust due to multiple mutable borrows

问题描述

我有以下 C++ 代码:

I have the following C++ code:

#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:

It's a trie for strings. push_word is supposed to only accept strings that are lexicographically greater than any word already contained in the trie; this way the search for the correct child can be skipped at each node. In other words, this allows us to efficiently construct a trie from a sorted vector of words:

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 中有以下内容:

I have the following in 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() {
            // ???
        }
    }
}

我无法以类似于 C++ 的方式实现 push_word.对于 trie 或 trie.chd 或 trie.chd 的最后一个元素，我总是得到两个可变借用或一个不可变和一个可变借用.我想获得一些有关如何完成此操作的说明.

I can't implement push_word in an analogous manner to C++. I always get two mutable borrows or one immutable and one mutable borrow, for trie or trie.chd, or the last element of trie.chd. I'd like to get some directions as to how this should be done.

推荐答案

看看这个打败借用检查器的奇怪技巧:编译器讨厌它.

See This One Weird Trick To Beat The Borrow Checker: Compilers Hate It.

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

是引入了标记为 * 的行，使这项工作得以实现.编译器还不够聪明，无法看到通过 last_mut 的 trie 的可变子借用 替换 的可变借用试试.如果它理解这一点，它将接受明显的代码 trie = trie.chd.last_mut().unwrap();，但目前程序员必须通过首先移动借用来手动做出此保证从 trie 出来，然后可以自由地重新分配.这以编译器可以理解的方式移动了借用的所有权.

It is the introduction of the line marked * that makes this work. The compiler isn't yet smart enough to see that the mutable sub-borrow of trie via last_mut is replacing the mutable borrow of trie. If it understood this, it would accept the obvious code trie = trie.chd.last_mut().unwrap();, but for the moment the programmer has to manually make this guarantee by first moving the borrow out of trie and then one is free to reassign. This moves the ownership of the borrow around in a way the compiler can understand.

问题 #10520 涵盖了这一点.

这篇关于由于多个可变借用，无法将插入到 Rust 中的 C++ 代码移植到 Rust的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！