How can I model a bidirectional map without annoying the borrow checker?

Question

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 proposed solution is:

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:

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

Answer 1

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

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.

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.