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

Question

我正在学习 Rust 中的字符串。我想实现函数来计算字符串列表中的长公共前缀。

我的代码

impl Solution {
    pub fn get_common_prefix(s1: &String, s2: &String) -> String {
        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].to_string();
        
        
    }
    pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
        strs.sort();
        let mut longest_pref = strs[0];
        for i in 0..strs.len() {
            longest_pref = Self::get_common_prefix(&longest_pref, &strs[i]);
        }
        return longest_pref;
    }
}

我有一个错误。您能帮忙修复一下吗？

Line 5, Char 37: lifetime mismatch (solution.rs)
  |
2 |     pub fn get_common_prefix(s1: &String, s2: &String) -> String {
  |                                  -------      ------- these two types are declared with different lifetimes...
...
5 |             std::mem::swap(&mut s1, &mut s2);
  |                                     ^^^^^^^ ...but data from `s2` flows into `s1` here

我在这里阅读有关生命周期的内容https://doc.rust-lang.org/rust-by-example/scope/lifetime.html但没有成功

Answer 1

如果您尝试显式隐式生命周期，您将获得以下签名get_common_prefix：

\n

fn get_common_prefix<\'a, \'b>(s1: &\'a String, s2: &\'b String) -> String { \n    ...\n}\n

\n

特别是，您不能交换这两个值，因为两个借用的持续时间都不一样长。相反，你可以这样做

\n

fn get_common_prefix<\'a>(s1: &\'a String, s2: &\'a String) -> String { \n    ...\n}\n

\n

这样做可以解决问题，但也会引发很多其他错误，因为您的代码还存在其他问题。让我们一一分析一下。

\n

首先，它现在会抱怨这std::mem::swap(&mut s1, &mut s2);是非法的，因为

\n

error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable\n --> src/main.rs:4:24\n  |\n4 |         std::mem::swap(&mut s1, &mut s2);\n  |                        ^^^^^^^ cannot borrow as mutable\n  |\nhelp: consider changing this to be mutable\n  |\n1 | pub fn get_common_prefix<\'a>(mut s1: &\'a String, s2: &\'a String) -> String {\n  |                              +++\n\nerror[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable\n --> src/main.rs:4:33\n  |\n4 |         std::mem::swap(&mut s1, &mut s2);\n  |                                 ^^^^^^^ cannot borrow as mutable\n  |\nhelp: consider changing this to be mutable\n  |\n1 | pub fn get_common_prefix<\'a>(s1: &\'a String, mut s2: &\'a String) -> String {\n  |                                              +++\n

\n

然而，Rust 非常好，它告诉你在这种情况下该怎么做，将s1和s2声明为可变的：

\n

fn get_common_prefix<\'a>(mut s1: &\'a String, mut s2: &\'a String) -> String { \n    ...\n}\n

\n

该函数get_common_prefix现在是正确的，但仍然存在错误longest_common_prefix：

\n

error[E0507]: cannot move out of index of `Vec<String>`\n  --> src/main.rs:16:28\n   |\n16 |     let mut longest_pref = strs[0];\n   |                            ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait\n   |\nhelp: consider borrowing here\n   |\n16 |     let mut longest_pref = &strs[0];\n   |                            +\n

\n

问题是您正在strs[0]从获取strs，但没有删除它，这是非法的，因为第一个字符串现在将被拥有两次（一次由longest_pref，一次由strs）。

\n

一种解决方案是实际采用strs[0], with swap_remove（这对于从向量中删除元素非常有效，假设我们不关心元素的顺序）：

\n

error[E0507]: cannot move out of index of `Vec<String>`\n  --> src/main.rs:16:28\n   |\n16 |     let mut longest_pref = strs[0];\n   |                            ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait\n   |\nhelp: consider borrowing here\n   |\n16 |     let mut longest_pref = &strs[0];\n   |                            +\n

\n\n

这可行，但是......由于多种原因，效率很低。首先，即使这不是一个可怕的性能损失，但&String在函数签名中使用 a 几乎总是错误的，因为你可以用它做所有的事情（实际上，Rust 会为你做这件事，所以也许你没有意识到）是Deref它到 a &str，这基本上与少一个间接寻址相同（因为你可以将其视为String指向 的指针str）。所以我们应该直接写成

\n

pub fn longest_common_prefix(mut strs: Vec<String>) -> String {\n    strs.sort();\n    let mut longest_pref = strs.swap_remove(0);\n    for i in 1..strs.len() {\n        longest_pref = get_common_prefix(&longest_pref, &strs[i]);\n    }\n    return longest_pref;\n}\n

\n

此外，当我们可以只返回该字符串的切片时（因为我们正在获取子字符串），返回需要分配的 a 是没有意义的String：

\n

fn get_common_prefix<\'a>(s1: &\'a str, s2: &\'a str) -> String { \n    ...\n}\n

\n

请注意，我更改了返回类型和最后一行。

\n

现在，为了使其发挥作用，我们还需要适应longest_common_prefix字符串切片的使用：

\n

pub fn get_common_prefix<\'a>(mut s1: &\'a str, mut s2: &\'a str) -> &\'a str {\n    let mut idx: usize = 0;\n    if s1.len() > s2.len() {\n        std::mem::swap(&mut s1, &mut s2);\n    }\n    \n    while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {\n        idx += 1;    \n    }\n    return &s1[0..idx]\n}\n

\n

我们回到只引用 的第一个元素strs，而不是接受它。String另外，当我们实际上必须返回 a 时，我们只对 a 执行一次分配String。

\n

还有一些其他优化需要完成。首先，排序strs是没有用的，它不会改变 的结果longest_common_prefix，所以我们可以删除它

\n

pub fn longest_common_prefix(mut strs: Vec<String>) -> String {\n    strs.sort();\n    let mut longest_pref: &str = &strs[0];\n    for i in 1..strs.len() {\n        longest_pref = get_common_prefix(&longest_pref, &strs[i]);\n    }\n    return longest_pref.to_string();\n}\n

\n

接下来，s1.chars().nth(i)非常慢（\xce\x98(i)）。更有效的方法是重用相同的迭代器 ( s1.chars())，并在每个步骤中推进它，如下所示

\n

pub fn longest_common_prefix(strs: Vec<String>) -> String {\n    let mut longest_pref: &str = &strs[0];\n    for i in 1..strs.len() {\n        longest_pref = get_common_prefix(&longest_pref, &strs[i]);\n    }\n    return longest_pref.to_string();\n}\n

\n

.zip()不会从最长的字符串中取出任何剩余的字符，所以我们实际上可以swap完全删除，得到

\n

for (c1, c2) in s1.chars().zip(s2.chars()) {\n    if c1 != c2 {\n        break;\n    }\n    idx += 1;    \n}\n

\n

注意：正如@SebastianRedi所指示的，idx不应该增加而是增加1，c1.len_utf8()因为在索引字符串时，索引以字节表示，而不是以字符表示，并且某些字符的长度超过一个字节。

\n