如何使用Vec支持HashMap

我尝试实现通用的A *树搜索算法 . 重要的部分是在标有TODO的函数_469528中：

use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::cmp::Ordering;

pub trait SearchTree<A> {
    fn available_actions(&self) -> Vec<A>;
    fn apply_action(&self, act: &A) -> Self;
}

pub trait CostSearchTree<A>: SearchTree<A> + Eq {
    fn action_cost(&self, act: &A) -> f64;
}

/// Node in the expanded search tree for uniform cost search with heuristic
struct HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    cost: f64,
    heuristic_cost: f64,
    parent_index: usize,
    action: Option<A>,
    tree: T,
}

impl<A, T> PartialEq for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn eq(&self, other: &HucsNode<A, T>) -> bool {
        // Can be used for closed list checking if we just compare the trees
        return self.tree == other.tree;
    }
}

impl<A, T> Eq for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
}

impl<A, T> PartialOrd for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn partial_cmp(&self, other: &HucsNode<A, T>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<A, T> Ord for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn cmp(&self, other: &HucsNode<A, T>) -> Ordering {
        let self_cost = self.cost + self.heuristic_cost;
        let other_cost = other.cost + other.heuristic_cost;

        // Flip for min-heap
        match other_cost.partial_cmp(&self_cost) {
            Some(order) => order,
            _ => Ordering::Equal,
        }
    }
}

/// Perform a uniform cost search with a monotonous heuristic function on a search tree.
/// Returns a sequence of actions if a state is found that satisfies the predicate or None if the search terminates before.
pub fn hucs<A, T: CostSearchTree<A> + Hash>(
    tree: T,
    predicate: &Fn(&T) -> bool,
    heuristic: &Fn(&T) -> f64,
) -> Option<Vec<A>> {

    let mut node_heap = BinaryHeap::new() as BinaryHeap<HucsNode<A, T>>;

    // Push the initial node onto the tree
    node_heap.push(HucsNode {
        action: None,
        parent_index: usize::max_value(),
        cost: 0.0,
        heuristic_cost: heuristic(&tree),
        tree: tree,
    });

    let mut old_nodes = Vec::new();
    let mut last_node_index = 0 as usize;

    'outer: while let Some(current_node) = node_heap.pop() {
        // Break borrows with scope so current_node can be moved out
        {
            if predicate(&current_node.tree) {
                return Some(form_action_sequence(current_node, old_nodes));
            }

            // Check if visited nodes already contains this tree with less cost
            // TODO: Time complexity is hardly ideal
            for old_node in old_nodes.iter() {
                if old_node.tree == current_node.tree && old_node.cost <= current_node.cost {
                    continue 'outer;
                }
            }

            let ref current_tree = current_node.tree;

            for action in current_tree.available_actions() {

                let action_cost = current_tree.action_cost(&action);
                let new_tree = current_tree.apply_action(&action);
                let new_cost = current_node.cost + action_cost;

                let new_node = HucsNode {
                    action: Some(action),
                    cost: new_cost,
                    parent_index: last_node_index,
                    heuristic_cost: heuristic(&new_tree),
                    tree: new_tree,
                };

                node_heap.push(new_node);
            }
        }

        old_nodes.push(current_node);
        last_node_index += 1;
    }

    return None;
}

/// Restore the sequence of actions that was used to get to this node by climbing the tree of expanded nodes
fn form_action_sequence<A, T: CostSearchTree<A>>(
    leaf: HucsNode<A, T>,
    mut older_nodes: Vec<HucsNode<A, T>>,
) -> Vec<A> {

    let mut action_vector = Vec::new();

    let mut current = leaf;

    while let Some(action) = current.action {
        action_vector.insert(0, action);

        // Safe to swap as nodes' parents are always before them
        current = older_nodes.swap_remove(current.parent_index);
    }

    return action_vector;
}

问题是通过扫描旧节点来查找当前节点是否在旧节点中需要太长时间 . 因此我想添加一个 HashMap . 因为我还需要能够通过索引访问旧节点以在最后形成解决方案动作序列，所以我还需要保留 Vec . 为了解决这个问题，我尝试添加一个包装器，我可以将其插入到 HashMap 作为一个键，只需在Vec中查找其内容，如下所示：

use std::hash::Hash;
use std::hash::Hasher;

struct BackedHashWrapper<'a, T: 'a + Hash + Eq> {
    source: &'a Vec<T>,
    index: usize,
}

impl<A, T> Hash for HucsNode<A, T>
where
    T: CostSearchTree<A> + Hash,
{
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.tree.hash(state);
    }
}

impl<'a, T> Hash for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.source[self.index].hash(state);
    }
}

impl<'a, T> PartialEq for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
    fn eq(&self, other: &BackedHashWrapper<T>) -> bool {
        self.source[self.index] == other.source[other.index]
    }
}

impl<'a, T> Eq for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
}

我无法弄清楚如何在 hucs 方法中实现这一点，我尝试了以下只是为了向hashmap添加元素

...
let mut old_nodes = Vec::new();
let mut hash_map = HashMap::new();
...

    ...
    hash_map.insert(BackedHashWrapper {source: &old_nodes, index: last_node_index}, current_node.cost);
    old_nodes.push(current_node);
    last_node_index += 1;
    ...

但借用检查器不允许我创建这样的 BackedHashWrapper 而源向量是可变的 . 很明显，我这样做是完全错误的，所以我怎么能在不克隆树或任何动作的情况下完成这个？