在 Rust 中实现 Trie 数据结构的更好方法

Question

最近我自学 Rust，并尝试编写 Trie 数据结构。我已经用 C++ 编写了 Trie 代码，如下所示。

struct node_t
{
    bool is_end = false;
    std::vector<std::pair<char, node_t>> children;

    void push(std::string str)
    {
        node_t* curr = this;

        for (size_t i = 0; i < str.size(); i++)
        {
            char curr_char = str[i];
            std::vector<std::pair<char, node_t>>::iterator iter = std::find_if(curr->children.begin(), curr->children.end(), [&](std::pair<char, node_t>& e) { return e.first == curr_char; });

            curr = iter != curr->children.end() ?
                   &iter->second :
                   (curr->children.push_back(std::make_pair(curr_char, node_t{ false, std::vector<std::pair<char, node_t>>() })), &(curr->children.end() - 1)->second);

        }

        curr->is_end = true;
    }

    bool has(std::string str)
    {
        node_t* curr = this;

        for (size_t i = 0; i < str.size(); i++)
        {
            char curr_char = str[i];
            std::vector<std::pair<char, node_t>>::iterator iter = std::find_if(curr->children.begin(), curr->children.end(), [&](std::pair<char, node_t>& e) { return e.first == curr_char; });

            if (iter == curr->children.end())
                return false;

            curr = &iter->second;
        }

        return curr->is_end;
    }
};

正如你所看到的，函数“push”和“has”使用自己的引用变量“self”作为名为“curr”的指针。
并且指针“curr”在遍历名为“str”的给定字符串时保持链接。

如果下一个字符在子向量中，“curr”将更改为该子向量。
否则，“curr”将被更改为具有新字符的新孩子，新推送。

我用 Rust 编写了类似于下面的代码。

fn push(&mut self, string: &str) {
    let mut curr = self;

    for c in string.chars() {
        curr = match curr.children.iter_mut().find(|e| e.0 == c) {
            Some(e) => &mut e.1,
            None => {
                curr.children.push((c, Node { is_end: false, children: Vec::new() }));
                &mut curr.children.last_mut().unwrap().1
            }
        }
    }

    curr.is_end = true;
}

上面的代码使用 C++ 代码使用的技术。
但是，这里有一个问题。

C++ 中的“curr”指针有两种用途。

首先，要跟踪给定的字符串，这意味着“curr”本身不断变化，因此“curr”必须是 mut 变量。其次，要在给定字符串中推送新字符，这意味着“curr”必须引用 mut 变量。

由于我们必须将“curr”推理为 mut 和 &mut，并且需要将“curr”与 mut 一起使用两次，编译器会对此抱怨。

error[E0499]: cannot borrow `curr.children` as mutable more than once at a time
  --> C:\Users\first\Developments\Temp\trie.rs:44:17
   |
41 |         curr = match curr.children.iter_mut().find(|e| e.0 == c) {
   |                      ------------------------ first mutable borrow occurs here
...
44 |                 curr.children.push((c, Node { is_end: false, children: Vec::new() }));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                 |
   |                 second mutable borrow occurs here
   |                 first borrow later used here

error[E0499]: cannot borrow `curr.children` as mutable more than once at a time
  --> C:\Users\first\Developments\Temp\trie.rs:45:22
   |
41 |         curr = match curr.children.iter_mut().find(|e| e.0 == c) {
   |                      ------------------------ first mutable borrow occurs here
...
45 |                 &mut curr.children.last_mut().unwrap().1
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^
   |                      |
   |                      second mutable borrow occurs here
   |                      first borrow later used here

error: aborting due to 2 previous errors; 1 warning emitted

问题是：有什么方法可以解决这个问题，使代码类似于上面的 C++ 代码吗？或者，如果我应该想出一个全新的代码，它会是什么样子？

如果问题无效或“curr”的解释不正确，请纠正我。

Answer 1

您的代码是正确的，应该已被接受。事实上并非如此，因为借用检查器存在已知缺陷（下一代Polonius借用检查器已接受该缺陷）。

问题在于，借用检查员认为案例中的引用在案例Some中处于活动状态None，即使事实并非如此。解决方案是不保留引用，例如使用position()：

pub fn push(&mut self, string: &str) {
    let mut curr = self;

    for c in string.chars() {
        curr = match curr.children.iter_mut().position(|e| e.0 == c) {
            Some(idx) => &mut curr.children[idx].1,
            None => {
                curr.children.push((
                    c,
                    Node {
                        is_end: false,
                        children: Vec::new(),
                    },
                ));
                &mut curr.children.last_mut().unwrap().1
            }
        }
    }

    curr.is_end = true;
}