最近我自学了Rust,并try 编写Trie数据 struct . 我已经用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;
    }
};

As you can see, function "push" and "has" uses its own reference variable "self" as a pointer named "curr".
And the pointer "curr" keep chainging while go through the given string named "str".

If next character is in the children vector "curr" is changed to that child.
Else, "curr" is changed to new child with new character, which pushed newly.

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

Code above uses technic as C++ code uses.
But, here's the catch.

C++中的"curr"指针有两种用途.

首先,跟踪给定的字符串,这意味着"curr"本身不断变化,因此"curr"必须是mut变量. 其次,要在给定的字符串中推送一个新字符,这意味着"Curr"必须引用mut变量.

因为我们必须将"curr"解释为mut和&amp;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"的解释不正确,请纠正我.

推荐答案

您的代码是正确的,应该被接受.事实上,它不是因为借入判断器的一个已知缺陷(它被下一代Polonius借入判断器接受).

问题是borrow 判断器认为Some case 中的引用在None case 中处于活动状态,即使它不是活动的.解决方案是不保留引用,例如使用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;
}

Rust相关问答推荐

如何在rust中有条件地分配变量?

空字符串转换为Box字符串时是否分配?<>

当第二个`let`依赖于第一个`let()`时,如何在一行中有多个`let()`?

如何高效地将 struct 向量中的字段收集到单独的数组中

如何在Rust中将选项<;选项<;字符串>;转换为选项<;选项&;str>;?

为什么铁 rust S的默认排序功能比我对小数组的 Select 排序稍微慢一些?

在复制类型中使用std::ptr::WRITE_VILAR进行内部可变性的安全性(即没有UnSafeCell)

为什么&;mut buf[0..buf.len()]会触发一个可变/不可变的borrow 错误?

由于生存期原因,返回引用的闭包未编译

Rust 生命周期:这两种类型声明为不同的生命周期

为什么可以在迭代器引用上调用 into_iter?

我的 Axum 处理程序无法编译:未实现 IntoResponse 特征

在 Rust 中,将可变引用传递给函数的机制是什么?

当 `T` 没有实现 `Debug` 时替代 `unwrap()`

Cargo:如何将整个目录或文件包含在功能标志中?

为什么可以从闭包中返回私有 struct

将 (T, ()) 转换为 T 安全吗?

为什么这个 Trait 无效?以及改用什么签名?

如何迭代调用可能会失败的函数?操作员?

为什么一个整型变量赋值给另一个变量后仍然可以使用?