如果您try 显式的隐式生存期,您将得到get_common_prefix
的以下签名:
fn get_common_prefix<'a, 'b>(s1: &'a String, s2: &'b String) -> String {
...
}
特别是,您不能交换这两个值,因为这两个borrow 彼此的持续时间都不长.相反,你可以这样做
fn get_common_prefix<'a>(s1: &'a String, s2: &'a String) -> String {
...
}
这样做可以解决问题,但也会引发许多其他错误,因为您的代码还有其他问题.让我们一个接一个地看一遍.
首先,它现在会抱怨std::mem::swap(&mut s1, &mut s2);
是非法的,因为
error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable
--> src/main.rs:4:24
|
4 | std::mem::swap(&mut s1, &mut s2);
| ^^^^^^^ cannot borrow as mutable
|
help: consider changing this to be mutable
|
1 | pub fn get_common_prefix<'a>(mut s1: &'a String, s2: &'a String) -> String {
| +++
error[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable
--> src/main.rs:4:33
|
4 | std::mem::swap(&mut s1, &mut s2);
| ^^^^^^^ cannot borrow as mutable
|
help: consider changing this to be mutable
|
1 | pub fn get_common_prefix<'a>(s1: &'a String, mut s2: &'a String) -> String {
| +++
但是,Rust相当不错,它告诉您在本例中要做什么,将s1
和s2
都声明为可变的:
fn get_common_prefix<'a>(mut s1: &'a String, mut s2: &'a String) -> String {
...
}
功能get_common_prefix
现在是正确的,但longest_common_prefix
中仍然有错误:
error[E0507]: cannot move out of index of `Vec<String>`
--> src/main.rs:16:28
|
16 | let mut longest_pref = strs[0];
| ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait
|
help: consider borrowing here
|
16 | let mut longest_pref = &strs[0];
| +
问题是您将从strs
中提取strs[0]
,但不删除它,这是非法的,因为第一个字符串现在将被拥有两次(一次由longest_pref
拥有,一次由strs
拥有).
一种解决方案是实际取strs[0]
和swap_remove
(假设我们不关心元素的顺序,这在从向量中删除元素时非常有效):
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
strs.sort();
let mut longest_pref = strs.swap_remove(0);
for i in 1..strs.len() {
longest_pref = get_common_prefix(&longest_pref, &strs[i]);
}
return longest_pref;
}
这行得通但是...由于几个原因,这是相当低效的.首先,即使它不是一个糟糕的性能冲击,在函数签名中使用&String
几乎总是错误的,因为您可以用它做的所有事情(实际上,Rust会为您做这件事,所以您可能没有意识到这一点)是从Deref
到&str
,这基本上是相同的,但减少了一个间接数(因为您可以将String
视为指向str
的指针).所以我们应该直接写出来
fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> String {
...
}
此外,返回String
是没有意义的,这需要分配,而我们只需在该字符串上返回一个片段(因为我们是在取子字符串):
pub fn get_common_prefix<'a>(mut s1: &'a str, mut s2: &'a str) -> &'a str {
let mut idx: usize = 0;
if s1.len() > s2.len() {
std::mem::swap(&mut s1, &mut s2);
}
while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {
idx += 1;
}
return &s1[0..idx]
}
Notice that I changed both the return type and the last line.个
现在,要使其发挥作用,我们还需要调整longest_common_prefix
以使用字符串片:
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
strs.sort();
let mut longest_pref: &str = &strs[0];
for i in 1..strs.len() {
longest_pref = get_common_prefix(&longest_pref, &strs[i]);
}
return longest_pref.to_string();
}
我们回到了referencing,strs
的第一个元素,而不是takingit.此外,我们只执行一次分配到String
,而实际上我们必须返回String
.
还有一些其他的优化工作要做.首先,排序strs
是没有用的,它不会改变longest_common_prefix
的结果,所以我们可以删除它
pub fn longest_common_prefix(strs: Vec<String>) -> String {
let mut longest_pref: &str = &strs[0];
for i in 1..strs.len() {
longest_pref = get_common_prefix(&longest_pref, &strs[i]);
}
return longest_pref.to_string();
}
接下来,s1.chars().nth(i)
是非常慢的(Θ(i)
).要做到这一点,更有效的方法是重用相同的迭代器(s1.chars()
),并在每一步推进它
for (c1, c2) in s1.chars().zip(s2.chars()) {
if c1 != c2 {
break;
}
idx += 1;
}
.zip()
不会从最长的字符串中提取任何剩余的字符,所以我们实际上可以完全删除swap
,得到
pub fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> &'a str {
let mut idx: usize = 0;
for (c1, c2) in s1.chars().zip(s2.chars()) {
if c1 != c2 {
break;
}
idx += c1.len_utf8();
}
return &s1[0..idx]
}
Note:正如@SebastianRedi所指出的,idx
不应该增加1
,而应该增加c1.len_utf8()
,因为当索引字符串时,索引以字节表示,而不是以字符表示,并且有些字符的长度超过一个字节.