如何在不烦恼借阅检查器的情况下为双向地图建模? [英] How can I model a bidirectional map without annoying the borrow checker?

问题描述

来自

From Why can't I store a value and a reference to that value in the same struct? I learned that I cannot store a value and a reference in the same struct.

建议的解决方案是:

最简单，最推荐的解决方案是不要尝试将这些项目放在相同的结构中.这样，您的结构嵌套将模仿代码的生命周期. 将拥有数据的类型放到一个结构中，然后提供一些方法，使您可以根据需要获取引用或包含引用的对象.

The easiest and most recommended solution is to not attempt to put these items in the same structure together. By doing this, your structure nesting will mimic the lifetimes of your code. Place types that own data into a structure together and then provide methods that allow you to get references or objects containing references as needed.

但是，我不知道如何在我的具体案例中应用此方法:

However, I do not know how to apply this in my concrete case:

我想构建由两个内部HashMap实现的双向地图. 显然，其中之一必须拥有数据.但是，另一部分对于双向地图也是必不可少的，因此我看不到如何在保持双向地图接口的同时将两者分开.

I want to build bidirectional map, implemented by two internal HashMaps. Clearly, one of them has to own the data. However, the other part is also essential to the bidirectional map, so I don't see how I could separate these two while still maintaining a bidirectional map interface.

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

推荐答案

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

In this case, the easiest solution is to act like a language with a garbage collector would work:

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));
}

当然，您想要更严格的代码，因为这使您可以打破双向映射.这只是向您显示解决问题的一种方法.

Of course, you'd want to have much more rigorous code as this allows you to break the bidirectional mapping. This just shows you one way of solving the problem.

显然，其中之一必须拥有数据

Clearly, one of them has to own the data

很显然，这不是真的^ _ ^.在这种情况下，两个地图都使用share 所有权> Rc .

Clearly, that's not true ^_^. In this case, both maps share the ownership using Rc.

基准此解决方案可以知道它是否足够有效.

Benchmark this solution to know if it's efficient enough.

做任何更有效的事情都需要对所有权进行更多的思考.例如，如果left_to_right映射拥有数据，而您在另一个映射中使用了原始指针，则该指针将在重新分配第一个映射后立即失效.

Doing anything more efficient would require much heavier thinking about ownership. For example, if the left_to_right map owned the data and you used a raw pointer in the other map, that pointer would become invalidated as soon as the first map reallocated.

这篇关于如何在不烦恼借阅检查器的情况下为双向地图建模?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！