rust - 在 Rust 中取消引用引用向量

Question

我在 Rust 中有以下 DFS 实现，但现在存在类型不一致错误。

fn dfs<T: Hash + Eq>(
    initial_state: T,
    is_final: &dyn Fn(&T) -> bool,
    next_states: &dyn Fn(&T) -> Vec<T>,
) -> Vec<T> {

    let mut final_states = Vec::new();

    {
        let mut stack = Vec::new();
        let mut seen = HashSet::new();
        stack.push(&initial_state);
        seen.insert(&initial_state);

        while let Some(node) = stack.pop() {
            if is_final(node) {
                final_states.push(node);
            }

            for ns in next_states(node) {
                if !seen.contains(&ns) {
                    seen.insert(&ns);
                    stack.push(&ns);
                }
            }
        }
    }
    final_states
}

编译器当前提示是因为 final_states类型为Vec<&T>而不是Vec<T> 。如果我更新函数签名以返回 Vec<T> ，编译器提示错误 returns a value referencing data owned by the current function并指向stack.push(&ns);以及其他带有 stack 的行和seen .

有没有办法更新Vec<&T>类型的final_states至Vec<T> ？

如果不行，有什么方法可以解决这个问题？

编辑:如果将 Copy 特征添加到 T(除非确实必要，否则我不喜欢这样做)， for ns next_states(node) 会出现另一个编译器问题。这就是说“借来的值(value)活得不够久”。 ns不在循环之外。

Link to the playground

Answer 1

这是您 self 回答的延伸。

• 您应该使用 Clone而不是Copy因为它的限制较少。许多类型是 Clone但少得多 Copy 。这还公开了通过 final_states.push(node) 完成的额外副本如果没有.clone()，这并不明显.

• 你做了一些不必要的克隆。唯一.clone()将元素放入 seen 时应该进行必要的调用设置，否则状态可以移动到 stack 。您可以将状态移出next_states通过迭代 nss 得到结果而不是&nss .

• 移动is_final检查next_states后步骤允许node 移动至 final_states而不是克隆。由于它不再使用并且已被移出 stack .

更新后的代码:

fn dfs<T: Clone + Eq + Hash>(
    initial_state: T,
    is_final: &dyn Fn(&T) -> bool,
    next_states: &dyn Fn(&T) -> Vec<T>,
) -> Vec<T> {
    let mut final_states = Vec::new();
    let mut stack = Vec::new();
    let mut seen = HashSet::new();
    seen.insert(initial_state.clone());
    stack.push(initial_state);

    while let Some(node) = stack.pop() {
        let nss = next_states(&node);
        for ns in nss {
            if !seen.contains(&ns) {
                seen.insert(ns.clone());
                stack.push(ns);
            }
        }
        
        if is_final(&node) {
            final_states.push(node);
        }
    }

    final_states
}

---

如果克隆 Not Acceptable ，您可以 seen和stack/final_states通过使用Rc共享所有权s。尽管将最终状态拉入Vec<T>需要更多的工作。在最后。

use std::rc::Rc;
use std::fmt::Debug;

fn dfs<T: Debug + Eq + Hash>(
    initial_state: T,
    is_final: &dyn Fn(&T) -> bool,
    next_states: &dyn Fn(&T) -> Vec<T>,
) -> Vec<T> {
    let mut final_states = Vec::new();
    let mut stack = Vec::new();
    let mut seen = HashSet::new();
    
    let initial_state = Rc::new(initial_state);
    seen.insert(Rc::clone(&initial_state));
    stack.push(initial_state);

    while let Some(node) = stack.pop() {
        let nss = next_states(&node);
        for ns in nss {
            if !seen.contains(&ns) {
                let ns = Rc::new(ns);
                seen.insert(Rc::clone(&ns));
                stack.push(ns);
            }
        }
        
        if is_final(&node) {
            final_states.push(node);
        }
    }
    
    // Ensure stack and seen are dropped early so that
    // final_states has unique ownership.
    std::mem::drop(stack);
    std::mem::drop(seen);
    
    final_states
        .into_iter()
        .map(|state| Rc::try_unwrap(state).unwrap())
        .collect()
}