Implementing only IndexMut without implementing Index

Question

I'm trying to create a DefaultHashMap struct which is basically a wrapper around HashMap, with the difference that when getting a key that is not in the map the default value is put in that key and is returned.

I made a get and a get_mut method and this works fine. Now I'm trying to implement Index and IndexMut as wrappers around those methods. Here I'm running into two problems.

The first problem is caused by the fact that get has to mutate the struct when the key is not present it requires a mutable reference. However, the signature for the index method of Index has &self instead of &mut self, so I cannot implement it.

This causes a second problem, IndexMut requires an Index implementation. So even though IndexMut would have no problems being implemented I cannot do this because Index cannot be implemented.

The first problem is annoying but understandable. For the second one, I don't get why the requirement is even there. I would like to have a way to work around it. Right now I'm doing the following, but I hope someone has a better solution:

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

First, I suspect that your requirement "when getting a key that is not in the map the default value is put in that key" is not exactly required!

Consider an immutable access let foo = default_hash_map[bar] + 123;. Unless you're going to use values with interior mutability with the map it might be inconsequential whether default_hash_map[bar] is actually creating a key or just returns a reference to a single default value.

Now, if you really need to create new entries during access then there is a way to do this. The borrow checker restriction that only allows you to add new entries with a mutable access is here to stop you from creating the dangling pointers that would occur whenever you modify the map while holding the references in there. But if you were using a structure with stable references, where stable means that the references are not invalidated when you enter new entries into the structure, then the problem the borrow checker is trying to prevent will go away.

In C++ I would've considered using a deque which is guaranteed by the standard not to invalidate its references when you add new entries to it. Unfortunately, Rust deques are different (though you can probably find arena allocator crates with properties similar to the C++ deque) and so for this example I'm using Box. The boxed values reside separately on the heap and aren't moved when you add new entries into HashMap.

Now, your normal access pattern is probably going to be modifying the new entries and then accessing the existing entries of the map. Thus making new entries in Index::index is an exception and shouldn't slow down the rest of the map. It might make sense therefore to pay the boxing price only for the Index::index access. To do that we might use a second structure, that keeps just the boxed Index::index values.

Knowing that HashMap<K, Box<V>> can be inserted into without invalidating the existing V refereces allows us to use it as a temporary buffer, holding the Index::index-created values until we get a chance to synchronize them with the primary 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)

Note that boxing only stabilizes the insertion of new entries. To remove the boxed entries you still need the mutable (&mut self) access to DefaultHashMap.