[Pre-RFC] HashMap/BTreeMap Entry method or_insert_with_key

libs
1

Both HashMap and BTreeMap have an idiom like this:

let value = map.entry(key).or_insert(value_if_empty)

let value = map.entry(key).or_insert_with(|| expensive_value_if_empty)

The problem is that or_insert_with doesn't provide the lambda with the map key you're currently dealing with. This is sometimes desirable. For example, the Rust book has a Cacher type that takes an expensive-to-compute lambda and later allows you to provide an argument to the lambda and receive either the cached or newly-computed result value.

It would be nice to be able to make a Cacher method like this:

    fn value(&mut self, arg: K) -> &V {
        let calculation = self.calculation;
        self.cache.entry(arg).or_insert_with_key(|key| calculation(key))
    }

As it is, you either have to clone the key or replicate the following uglier implementation of the or_insert_with_key method:

    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => {
                let value = default(entry.key());
                entry.insert(value)
            },
        }
    }

I propose inserting that code into both the HashMap and BTreeMap Entry modules. Is this a good idea? Are there any better names or implementations or other suggestions?

2

It seems like a reasonable idea to me, however in your example:

I don't expect this will work, because self.cache is mutably borrowed for the entry -- that will make self methods inaccessible for your calculation. You could only use distinct fields of self, and you'd have to pre-borrow them outside of your closure so it doesn't try to capture self. The explicit match would also have a problem with self methods, but would have no problem with distinct self fields.

3

Yeah, this is a standard problem I run into regularly: I want to use things like the entry API, but I can't when the table lives in self and filling the table requires touching other bits of self. I tend to end up either doing two lookups (self.sometable.get then self.sometable.insert), or open-coding things I would otherwise have put in a helper function because Rust can't see inside the helper function to see that it doesn't touch self.sometable.

I wish that Rust's borrow checker didn't mind "peering inside" other methods of Self and doing cross-function analysis in that specific case to see which members the called method uses. I can understand not peering inside arbitrary other functions, but this issue primarily comes up with struct methods and struct fields, and those seem like the most justifiable cases for the borrow checker to peer inside.

1 Like
4

Thanks for the heads up. With a modified hashbrown crate, I got the code to work and edited my original post.

5

I was advised to submit this as a pull request rather than as an RFC, and I've done so at https://github.com/rust-lang/rust/pull/70996

1 Like
6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.