具有 str 键的 HashMap 的 Rust lang 生命周期不匹配

Question

我正在尝试在 Rust 中实现一个有效的现有 C++ 算法，以了解生命周期是如何工作的。我们应该使用什么模式来进行以下...作为背景，该算法尝试求最长回文子序列的长度。

use std::cmp::{max, min};
use std::collections::HashMap;
use std::str;

fn main() {
    let mut m = HashMap::new();
    println!(
        "Longest palin size: {}",
        longest_palin_substring("abdbca".as_bytes(), &mut m)
    );
}
    
    
    pub fn longest_palin_substring(is_palin: &[u8], map: &mut HashMap<&str, usize>) -> usize {
    println!("current string : {}", str::from_utf8(is_palin).unwrap());
    if is_palin.len() == 0 || is_palin.len() == 1 {
        return is_palin.len();
    }

    if let Some(len) = map.get(str::from_utf8(is_palin).unwrap()) {
        *len
    } else {
        let c1 = if is_palin[0] == is_palin[is_palin.len() - 1] {
            let r = longest_palin_substring(&is_palin[1..is_palin.len() - 1], map);
            if r == is_palin.len() - 2 {
                2 + r
            } else {
                0
            }
        } else {
            0
        };

        let c2 = longest_palin_substring(&is_palin[1..], map);
        let c3 = longest_palin_substring(&is_palin[..is_palin.len() - 1], map);

        let c = max(c1, max(c2, c3));
        map.insert(str::from_utf8(is_palin).unwrap(), c);
        c
    }
}

error[E0623]: lifetime mismatch
  --> src/main.rs:38:20
   |
14 |     pub fn longest_palin_substring(is_palin: &[u8], map: &mut HashMap<&str, usize>) -> usize {
   |                                              -----                    ----
   |                                              |
   |                                              these two types are declared with different lifetimes...
...
38 |         map.insert(str::from_utf8(is_palin).unwrap(), c);
   |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...but data from `is_palin` flows into `map` here

error: aborting due to previous error; 1 warning emitted

For more information about this error, try `rustc --explain E0623`.
error: could not compile `playground`

To learn more, run the command again with --verbose.

我尝试为所有引用添加 &'a 生命周期，但随后它抱怨多次发生可变借用。

 pub fn longest_palin_substring<'a>(                                                                                                                 
     is_palin: &'a [u8],                                                                                                                             
     map: &'a mut HashMap<&'a str, usize>,                                                                                                           
 ) -> usize {

错误：

error[E0499]: cannot borrow `*map` as mutable more than once at a time

我的问题如下：

首先，很明显，我应该如何继续修复这个编译错误
一些状态要遵循什么模式，将用于memoize导致递归实现，比如说，动态编程。

任何可以让我了解更多关于 Rust 模式的指示都将不胜感激。

谢谢。

Answer 1

你很接近。首先，hashmap 的生命周期将与其键类型的生命周期不同。

编译错误可以这样修复：

pub fn longest_palin_substring<'a>(is_palin: &'a [u8], map: &mut HashMap<&'a str, usize>) -> usize {

作为一般规则，如果您不存储传递给函数的引用，您不希望类型上有任何生命周期注释，编译器会使用函数签名来确定引用的使用方式，而无需检查函数的内容。

其次，为了记忆事物，我会使用一些内部可变性原语。如果算法是单线程的，那么 Cell 或 RefCell 就可以，如果不是 Mutex 将允许您改变内部状态。

如果事情只被记忆一次，你可能会对 once_cell 感兴趣（它仍然是夜间专用的，但在 stable 中有一个板条箱 usabe）。

具有 str 键的 HashMap 的 Rust lang 生命周期不匹配

Rust lang lifetime mismatch for HashMap with str key

lifetime

rust

borrow-checker