如何在不烦扰借用检查器的情况下建立双向映射？

Question

从为什么不能在同一结构体中存储值和对该值的引用？中得知，我不能同时在同一结构体中存储值和对该值的引用。

提出的解决方案是：

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

然而，我不知道如何应用到我的具体情况中：

我想建立双向映射，由两个内部的HashMap实现。显然，其中之一必须拥有数据。然而，另一部分对于双向映射也是至关重要的，所以我不知道如何将这两个分开，同时仍维护双向映射接口。

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

- knub

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 映射拥有数据，并且在另一个映射中使用原始指针，那么该指针将在第一个映射重新分配内存时失效。

- Shepmaster

---

如果您需要修改其中一个值，想要获取可变引用怎么办？ - khc

@khc 那么你需要 内部可变性。 - Shepmaster