Expose a HashMap entry's key

[dstu]

At present, HashMap's OccupiedEntry and VacantEntry don't expose their associated keys. It would be useful to have a method (say, key()) which exposes a reference to the key. The relevant use case I have run into is when performing a get-or-insert operation on a HashMap, when the value that is inserted is a function of the key. If you want to compute the value to insert only when there is not already an entry in the map, the current API forces you to clone the key so that its value is still available after pulling an Entry out of the map. For example:

pub fn get_or_insert<K: Clone + Eq + Hash, V, F: FnOnce(&K) -> V>(
        table: &mut HashMap<K, V>, key: K, f: F) -> bool {
    // table.entry() moves out of key, so we need to clone it,
    // regardless of our need for it later.
    match table.entry(key.clone()) {
        Entry::Occupied(_) => false,
        Entry::Vacant(e) => {
            e.insert(f(&key));
            true
        }
    }
}

It appears simple to add methods which return a reference to the keys of OccupiedEntry and VacantEntry. I would be happy to provide a pull request doing so.

[sfackler]

This seems pretty reasonable - I think the right way to move forward here would be to open a PR adding the methods (marked unstable of course). We'll want to cover both BTreeMap and HashMap for consistency.

cc @rust-lang/libs.

[comex]

It's not too relevant, but I just thought I'd mention - a somewhat related case is if you have, say, a HashMap<String, X> and want to perform a get-or-insert with an &str key, without wasting time copying it into a String if there is already an entry for it. Today you can't use the entry API for this as you need to give it an owned key up front. If hypothetically there were an alternate form of Entry that only required a reference to obtain, and its insert-vacant method allowed explicitly specifying a replacement key (which is, of course, a big potential footgun if the new key doesn't have the same hash - it would probably be better to use ToOwned or a new trait, that is if this is worth doing at all - but just supposing), then you could also avoid the clone in the OP's example case with that.

[dstu]

@comex, I was thinking along similar lines with an alternate form of Entry, but specialized for when the key type implements Clone. It would make sense to have an Entry analogue with a variant for vacancy, which wraps around a reference to a key and clones it if/when you want to do an insertion, and a variant for occupancy, which simply provides access to the key that is in the map. I haven't yet prototyped things to demonstrate that the API won't explode into a bifurcated mess and that the lifetimes work out properly.

If this seems worth pursuing, does it make sense to get in a PR for the simpler case of modifying the current API first?

[codyps]

Related: #1533

[dstu]

Point of order: when should this issue and #32281 in rust-lang/rust be closed? With the PR accepted, I'm not sure if it's my responsibility to close them. (Does that happen if/when the map_entry_keys feature is accepted/dropped?)

I'd like to follow up with additional discussion about how to improve the entry API. I'm currently considering how to expose (K, V) pairs after insertion instead of just a reference to the value that was inserted. This can be done by adding another insertion method to VacantEntry, but it might be better to consider such changes more holistically.

#1533 is host to discussion about handling cloneable key types better. Is it time to try writing a more general RFC on the entry API (cf. Head-Desking on Entry API 4.0)?

[mbrubeck]

Entry::key is now implemented and stabilized. Closing.