rust - 只实现 IndexMut 不实现 Index

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

首先，我怀疑您的要求“当获取不在 map 中的键时，将默认值放入该键中”并不是完全必需的!

考虑一个不可变访问 let foo = default_hash_map[bar] + 123; .除非您打算在 map 中使用具有内部可变性的值，否则 default_hash_map[bar] 是否无关紧要。实际上是在创建一个键或只是返回对单个默认值的引用。

现在，如果您确实需要在访问期间创建新条目，那么有一种方法可以做到这一点。仅允许您添加具有可变访问权限的新条目的借用检查器限制在这里阻止您创建悬空指针，这种悬空指针在您修改 map 时会在其中保存引用时出现。但是，如果您使用的是具有稳定引用的结构，其中稳定意味着当您向结构中输入新条目时引用不会失效，那么借用检查器试图防止的问题就会消失。

在 C++ 中，我会考虑使用 deque当您向其中添加新条目时，标准保证不会使其引用无效。不幸的是，Rust 双端队列是不同的(尽管您可能会找到具有类似于 C++ 双端队列的属性的 arena allocator crates)所以对于这个例子我使用了 Box .盒装值单独驻留在堆上，当您将新条目添加到 HashMap 时不会移动。 .

现在，您的正常访问模式可能是修改 新条目，然后访问 map 的现有 条目。因此在 Index::index 中创建新条目是一个异常(exception)，不应减慢 map 的其余部分。因此，只为 Index::index 支付装箱价格可能是有意义的。使用权。为此，我们可能会使用第二个结构，它只保留盒装的 Index::index。值(value)观。

知道HashMap<K, Box<V>>可以在不使现有 V 失效的情况下插入refereces 允许我们将它用作临时缓冲区，保存 Index::index -创建值，直到我们有机会将它们与主要 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) 访问权限.