如何在不烦扰借用检查器的情况下建模双向地图？

Question

从Why can't I store a value and a reference to that value in the same struct?我了解到我无法在同一个结构中存储值和引用。

建议的解决方案是：

最简单和最推荐的解决方案是不要试图将这些项目放在同一个结构中。通过这样做，您的结构嵌套将模仿代码的生命周期。将拥有数据的类型放在一起放在一个结构中，然后提供允许您根据需要获取包含引用的引用或对象的方法。

但是，我不知道如何在我的具体案例中应用这个：

我想构建双向映射，由两个内部HashMaps实现。显然，其中一个人必须拥有这些数据。但是，另一部分对双向映射也很重要，所以我看不出如何在保持双向映射接口的同时将这两者分开。

struct BidiMap<'a, S: 'a, T: 'a> { ? }
fn put(&mut self, s: S, t: T) -> ()
fn get(&self, s: &S) -> T
fn get_reverse(&self, t: &T) -> S

Answer 1

在这种情况下，最简单的解决方案是像垃圾收集器的语言一样工作：

use std::collections::HashMap;
use std::rc::Rc;
use std::hash::Hash;
use std::ops::Deref;

struct BidiMap<A, B> {
    left_to_right: HashMap<Rc<A>, Rc<B>>,
    right_to_left: HashMap<Rc<B>, Rc<A>>,
}

impl<A, B> BidiMap<A, B>
where
    A: Eq + Hash,
    B: Eq + Hash,
{
    fn new() -> Self {
        BidiMap {
            left_to_right: HashMap::new(),
            right_to_left: HashMap::new(),
        }
    }

    fn put(&mut self, a: A, b: B) {
        let a = Rc::new(a);
        let b = Rc::new(b);
        self.left_to_right.insert(a.clone(), b.clone());
        self.right_to_left.insert(b, a);
    }

    fn get(&self, a: &A) -> Option<&B> {
        self.left_to_right.get(a).map(Deref::deref)
    }

    fn get_reverse(&self, b: &B) -> Option<&A> {
        self.right_to_left.get(b).map(Deref::deref)
    }
}

fn main() {
    let mut map = BidiMap::new();
    map.put(1, 2);
    println!("{:?}", map.get(&1));
    println!("{:?}", map.get_reverse(&2));
}

当然，您希望拥有更严格的代码，因为这样可以打破双向映射。这只是向您展示解决问题的一种方法。

显然，其中一个人必须拥有这些数据

显然，那不是真的^ _ ^。在这种情况下，两张地图都使用Rc共享所有权。

对此解决方案进行基准测试，以了解它是否足够有效。

做更有效的事情需要更多地考虑所有权。例如，如果left_to_right映射拥有数据并且您在另一个映射中使用了原始指针，则只要第一个映射重新分配，该指针就会失效。