如果您尝试显式地表达隐式生命周期,您将得到以下
get_common_prefix
签名:
fn get_common_prefix<'a, 'b>(s1: &'a String, s2: &'b String) -> String {
...
}
特别地,您不能交换这两个值,因为两个借用的持续时间不同。相反,您可以执行以下操作
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
)。
一种解决方法是实际上使用
swap_remove
获取
strs[0]
(它非常高效地从向量中移除元素,假设我们不关心元素的顺序):
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
基本相同(因为你可以将
String
看作指向
str
的指针)。因此,我们应该直接写出
&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]
}
请注意,我更改了返回类型和最后一行。
现在,为了使其工作,我们还需要调整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();
}
我们回到了只是引用第一个元素strs
的方式,而不是获取它。此外,我们只在需要返回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]
}
注意:正如@SebastianRedi所指出的那样,idx
不应该增加1
,而应该增加c1.len_utf8()
,因为在索引字符串时,索引是以字节而不是字符表示的,并且某些字符超过一个字节长。
&str
参数而不是&String
。参见:https://dev59.com/W1kS5IYBdhLWcg3wV1Zy - Jmbfn get_common_prefix<'a> (s1: &'a String, s2: 'a String) -> String
。 - Jmb