Как смоделировать двунаправленную карту, не раздражая проверку чека?

Question

От Why can't I store a value and a reference to that value in the same struct? Я узнал, что не могу сохранить значение и ссылку в той же структуре.

Предлагаемое решение:

Самый простой и наиболее рекомендуемым решением является не пытаться поместить эти элементы в одной и той же структуры вместе. Делая это, ваша структура вложенности будет имитировать время жизни вашего кода. Поместите типы, которые содержат данные в структуру вместе, а затем предоставит методы, которые позволят вам получить ссылки или объекты, содержащие ссылки по мере необходимости.

Однако, я не знаю, как применить это в моем конкретном случае:

Я хочу построить двунаправленную карту, реализованную два внутренних 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 

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.

Benchmark это решение, если оно достаточно эффективно.

Выполнение чего-либо более эффективного требует гораздо более тяжелого мышления о собственности. Например, если карта left_to_right владела данными, и вы использовали необработанный указатель на другой карте, этот указатель станет недействительным, как только первая карта будет перераспределена.