How do I use the Entry API with an expensive key that is only constructed if the Entry is Vacant?

Question

Is it possible to use the Entry API to get a value by a AsRef<str>, but inserting it with Into<String>?

This is the working example:

use std::collections::hash_map::{Entry, HashMap};

struct Foo;

#[derive(Default)]
struct Map {
    map: HashMap<String, Foo>,
}

impl Map {
    fn get(&self, key: impl AsRef<str>) -> &Foo {
        self.map.get(key.as_ref()).unwrap()
    }

    fn create(&mut self, key: impl Into<String>) -> &mut Foo {
        match self.map.entry(key.into()) {
            Entry::Vacant(entry) => entry.insert(Foo {}),
            _ => panic!(),
        }
    }

    fn get_or_create(&mut self, key: impl Into<String>) -> &mut Foo {
        match self.map.entry(key.into()) {
            Entry::Vacant(entry) => entry.insert(Foo {}),
            Entry::Occupied(entry) => entry.into_mut(),
        }
    }
}

fn main() {
    let mut map = Map::default();
    map.get_or_create("bar");
    map.get_or_create("bar");
    assert_eq!(map.map.len(), 1);
}

playground

My problem is that in get_or_create a String will always be created, incurring unneeded memory allocation, even if it's not needed for an occupied entry. Is it possible to fix this in any way? Maybe in a neat way with Cow?

Answer 1

You cannot, safely. This is a limitation of the current entry API, and there's no great solution. The anticipated solution is the "raw" entry API. See Stargateur's answer for an example of using it.

The only stable solution using the Entry API is to always clone the key:

map.entry(key.clone()).or_insert(some_value);

Outside of the Entry API, you can check if the map contains a value and insert it if not:

if !map.contains_key(&key) {
    map.insert(key.clone(), some_value);
}

map.get(&key).expect("This is impossible as we just inserted a value");

See also:

• [Pre-RFC] Abandonning Morals In The Name Of Performance: The Raw Entry API
• WIP: add raw_entry API to HashMap (50821)
• Extend entry API to work on borrowed keys. (1769)
• Add HashMap.entry_or_clone() method (1203)

For non-entry based solutions, see:

• How to avoid temporary allocations when using a complex key for a HashMap?
• How to implement HashMap with two keys?

Answer 2

In nightly Rust, you can use the unstable raw_entry_mut() feature that allows this:

Creates a raw entry builder for the HashMap.

[...]

Raw entries are useful for such exotic situations as:

• Deferring the creation of an owned key until it is known to be required

In stable Rust, you can add the hashbrown crate which has the same API but stable. The hashbrown crate is actually the underlying implementation of the standard library's hashmap.

Example:

#![feature(hash_raw_entry)]
use std::collections::HashMap;

#[derive(Hash, PartialEq, Eq, Debug)]
struct NoCopy {
    foo: i32,
}

impl Clone for NoCopy {
    fn clone(&self) -> Self {
        println!("Clone of: {:?}", self);
        Self { foo: self.foo }
    }
}

fn main() {
    let no_copy = NoCopy { foo: 21 };

    let mut map = HashMap::new();

    map.raw_entry_mut()
        .from_key(&no_copy)
        .or_insert_with(|| (no_copy.clone(), 42));

    map.raw_entry_mut()
        .from_key(&no_copy)
        .or_insert_with(|| (no_copy.clone(), 84));

    println!("{:#?}", map);
}

Applied to your original example:

fn get_or_create<K>(&mut self, key: K) -> &mut Foo
where
    K: AsRef<str> + Into<String>,
{
    self.map
        .raw_entry_mut()
        .from_key(key.as_ref())
        .or_insert_with(|| (key.into(), Foo))
        .1
}

Answer 3

The hashbrown crate (it's the same implementation that powers std's HashMap) provides the entry_ref() API for that:

use hashbrown::hash_map::{EntryRef, HashMap};

struct Foo;

#[derive(Default)]
struct Map {
    map: HashMap<String, Foo>,
}

impl Map {
    fn get(&self, key: impl AsRef<str>) -> &Foo {
        self.map.get(key.as_ref()).unwrap()
    }

    fn create(&mut self, key: impl AsRef<str>) -> &mut Foo {
        match self.map.entry_ref(key.as_ref()) {
            EntryRef::Vacant(entry) => entry.insert(Foo {}),
            _ => panic!(),
        }
    }

    fn get_or_create(&mut self, key: impl AsRef<str>) -> &mut Foo {
        match self.map.entry_ref(key.as_ref()) {
            EntryRef::Vacant(entry) => entry.insert(Foo {}),
            EntryRef::Occupied(entry) => entry.into_mut(),
        }
        // Or:
        // self.map.entry_ref(key.as_ref()).or_insert(Foo {})
    }
}