Improving Entry API to get the keys back when they are unused

[matthieu-m]

First of all, I would like to congratulate Gankro on the Entry API, it really simplified the interface of associative containers.

If I had one nit, however, it is that the entry methods available always consume the key.

Now, said key is taken by value so of course it is consumed, and the key is actually inserted in the container via the call to VacantEntry::insert, so it seems reasonable. However, in the case the key slot in the container is already occupied, and we get an OccupiedEntry as a result, there seems to be little reason not to return the key to the user.

For completeness, one could actually also improve VacantEntry so that is possible for it to hand over the key it had consumed, although why would one use the Entry API for look-up without any wish to insert is for now a mystery to me.

The main benefit of returning the un-consumed key is allowing reusing it. When the key is a simple integer, this has little appeal, however when the key owns heap-allocated memory (such as String) then the ability to re-use the buffer rather than continuously allocating/deallocating seems like a huge boon.

---

I prototyped the idea of an improved Occupied below, the modification is simple, and casual perusal of http://doc.rust-lang.org/src/std/collections/hash/map.rs.html#1150-1195 seems to show that simply modifying the lines 1175-1177 to:

return Occupied(OccupiedEntry{ elem: bucket, }, k); // Note the ", k"

would be the only change to HashMap implementation; likewise the entry change at lines 1366-1371 is simple enough:

pub enum Entry<'a, K: 'a, V: 'a> {
    /// An occupied Entry, and the unconsumed key
    Occupied(OccupiedEntry<'a, K, V>, K), // Note the ", K"
    /// A vacant Entry
    Vacant(VacantEntry<'a, K, V>),
}

I suspect, but have not verified, that other associative containers would likely be as easily modified. And of course, it would impact all consumers...

The example below show cases achieving buffer re-use through such an improved API, note how easy it is.

#![allow(unstable)]

use std::default::Default;

struct OccupiedEntry<K, V>;

struct VacantEntry<K, V> {
    entry: K,
}

enum Entry<K, V> {
    Occupied(OccupiedEntry<K, V>, K), // Simply add one more element to Occupied.
    Vacant(VacantEntry<K, V>),
}

impl<K, V> Entry<K, V> {
    fn new(key: K, really: bool) -> Entry<K, V> {
        if really {
            Entry::Occupied(OccupiedEntry, key)
        } else {
            Entry::Vacant(VacantEntry{entry: key})
        }
    }
}

fn main() {
    let mut acc: Vec<String> = vec!();

    let mut word: String = Default::default();
    for i in "Lorem iipsum and all that".split_str(" ") {
        word.clear();
        word.push_str(i);

        word = match Entry::<String, i32>::new(word, i.len() % 2 == 0) {
            Entry::Occupied(_, key) => { key }
            Entry::Vacant(v) => { acc.push(v.entry); Default::default() }
        };

        println!("{}\t{}", word, i);
    }

    println!("{:?}", acc);
}

[jdm]

cc @gankro

[Gankra]

Interesting! I agree wtih all the points made here.

Although I don't see how your example at all re-uses a buffer?

[matthieu-m]

Oh right, in this example in does not! Let met get back to the original situation iterating over &str.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#690