只實現IndexMut而不實現索引

Question

我試圖創建一個DefaultHashMap結構，它基本上是一個圍繞HashMap的包裝，區別在於，當獲取一個不在映射中的鍵時，默認值被放入該鍵中，並且回。

我做了一個get和一個get_mut方法，這工作正常。現在我試圖執行Index和IndexMut作爲這些方法的包裝。在這裏我遇到了兩個問題。

第一個問題是由於get在密鑰不存在時必須對結構進行變異，它需要一個可變引用。但是，index方法Index的簽名有&self而不是&mut self，所以我無法實現它。

這會導致第二個問題，IndexMut需要執行一個Index。因此，即使IndexMut將不會實施問題，我不能這樣做，因爲Index無法實施。

第一個問題很煩人，但可以理解。對於第二個，我不明白爲什麼要求甚至在那裏。我想有辦法解決它。現在，我做以下，但我希望有人有更好的解決辦法：

impl<K: Eq + Hash, V: Clone> Index<K> for DefaultHashMap<K, V> { 
    type Output = V; 

    fn index(&self, _: K) -> &V { 
     panic!("DefautHashMap doesn't implement indexing without mutating") 
    } 
} 

impl<K: Eq + Hash, V: Clone> IndexMut<K> for DefaultHashMap<K, V> { 
    #[inline] 
    fn index_mut(&mut self, index: K) -> &mut V { 
     self.get_mut(index) 
    } 
} 

Answer 1

首先，我懷疑你的要求「得到一個關鍵，是不是在地圖中的默認值被放入時該密鑰「並不是完全必需的！

考慮一個不可變的訪問let foo = default_hash_map[bar] + 123;。除非你打算在地圖上使用具有內部可變性的值，否則default_hash_map[bar]是否實際上創建密鑰或者只是返回對單個默認值的引用。

現在，如果您確實需要在訪問期間創建新條目，那麼有一種方法可以實現。借用檢查器限制只允許您添加具有可變訪問權限的新條目，這樣可以阻止您創建懸掛指針，這些指針在您將引用保存在其中時每次修改映射時都會發生。但是，如果您使用的是具有穩定引用的結構，那麼穩定意味着在向結構中輸入新條目時引用不會失效，那麼借用檢查器試圖阻止的問題將會消失。

在C++中，我會考慮使用deque，這是由標準保證，當您添加新條目時不會使其引用無效。不幸的是，Rust deques是不同的（儘管你可能會發現競技場分配器板條箱的屬性類似於C++ deque），所以在這個例子中我使用Box。盒裝值分別位於堆上，並且在將新條目添加到HashMap時不會移動。

現在，您的正常訪問模式可能會是修改新的條目，然後訪問該地圖的現有條目。因此在Index::index中創建新條目是一個例外，不應拖慢地圖的其他部分。這可能是有道理的，因此只支付Index::index訪問的拳擊價格。要做到這一點，我們可以使用第二個結構，它只保留盒裝的Index::index值。

明知HashMap<K, Box<V>>可插入，而不存在V refereces無效允許我們使用它作爲一個臨時緩衝區，持有Index::index -created值，直到我們有機會向他們的主要HashMap同步。

use std::borrow::Borrow; 
use std::cell::UnsafeCell; 
use std::collections::HashMap; 
use std::hash::Hash; 
use std::ops::Index; 
use std::ops::IndexMut; 

struct DefaultHashMap<K, V>(HashMap<K, V>, UnsafeCell<HashMap<K, Box<V>>>, V); 

impl<K, V> DefaultHashMap<K, V> 
    where K: Eq + Hash 
{ 
    fn sync(&mut self) { 
     let buf_map = unsafe { &mut *self.1.get() }; 
     for (k, v) in buf_map.drain() { 
      self.0.insert(k, *v); 
     } 
    } 
} 

impl<'a, K, V, Q: ?Sized> Index<&'a Q> for DefaultHashMap<K, V> 
    where K: Eq + Hash + Clone, 
      K: Borrow<Q>, 
      K: From<&'a Q>, 
      Q: Eq + Hash, 
      V: Clone 
{ 
    type Output = V; 

    fn index(&self, key: &'a Q) -> &V { 
     if let Some(v) = self.0.get(key) { 
      v 
     } else { 
      let buf_map: &mut HashMap<K, Box<V>> = unsafe { &mut *self.1.get() }; 
      if !buf_map.contains_key(key) { 
       buf_map.insert(K::from(key), Box::new(self.2.clone())); 
      } 
      &*buf_map.get(key).unwrap() 
     } 
    } 
} 

impl<'a, K, V, Q: ?Sized> IndexMut<&'a Q> for DefaultHashMap<K, V> 
    where K: Eq + Hash + Clone, 
      K: Borrow<Q>, 
      K: From<&'a Q>, 
      Q: Eq + Hash, 
      V: Clone 
{ 
    fn index_mut(&mut self, key: &'a Q) -> &mut V { 
     self.sync(); 
     if self.0.contains_key(key) { 
      self.0.get_mut(key).unwrap() 
     } else { 
      self.0.insert(K::from(key), self.2.clone()); 
      self.0.get_mut(key).unwrap() 
     } 
    } 
} 

fn main() { 
    { 
     let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), 
                 UnsafeCell::new(HashMap::new()), 
                 "bar".into()); 
     for i in 0..10000 { 
      dhm[&format!("{}", i % 1000)[..]].push('x') 
     } 
     println!("{:?}", dhm.0); 
    } 

    { 
     let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), 
                 UnsafeCell::new(HashMap::new()), 
                 "bar".into()); 
     for i in 0..10000 { 
      let key = format!("{}", i % 1000); 
      assert!(dhm[&key].len() >= 3); 
      dhm[&key[..]].push('x'); 
     } 
     println!("{:?}", dhm.0); 
    } 

    { 
     #[derive(Eq, PartialEq, Clone, Copy, Hash, Debug)] 
     struct K(u32); 
     impl<'a> From<&'a u32> for K { 
      fn from(v: &u32) -> K { 
       K(*v) 
      } 
     } 
     impl<'a> Borrow<u32> for K { 
      fn borrow(&self) -> &u32 { 
       &self.0 
      } 
     } 
     let mut dhm = DefaultHashMap::<K, K>(HashMap::new(), 
              UnsafeCell::new(HashMap::new()), 
              K::from(&123)); 
     for i in 0..10000 { 
      let key = i % 1000; 
      assert!(dhm[&key].0 >= 123); 
      dhm[&key].0 += 1; 
     } 
     println!("{:?}", dhm.0); 
    } 
} 

（playground）

注意拳擊只有穩定的新條目的插入。到刪除盒裝條目你仍然需要可變（&mut self）訪問DefaultHashMap。