最近我自学了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和&;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"的解释不正确,请纠正我.