Draft: Map `replace`, which is like `insert`, but returns previous value (or entry?)

[anko]

This PR is a rough first draft to gather feedback, and just to have "something on the wall to point at". It runs and illustrates the idea, but does not have tests, and currently only implements for HashTrieMap.

Motivation

In std, HashMap<K, V>::insert returns Option<V>, which contains the previous value if any. BTreeMap::insert too. It can avoid having to do an additional get before the insert.

I have a use-case where a similar method on rpds map types would help.

Observations

I found these complications, and options for tackling them:

1. Being a persistent data structure, insert currently returns the new version of the map type. So it would have to return a tuple instead, which results in an annoying interface at the call site whenever you don't intend to use the old value (which I imagine is quite often);

   let (map, _old_value) = map.insert(k, v);

   Options:

   • Accept the crappier API, which also requires major semver bump, because it changes the interface of insert.
   • Leave insert/insert_mut as-is, and name the new methods replace/replace_mut instead. (I think this is better. It's what the PR currently does, with insert/insert_mut delegating to replace/replace_mut but discarding their other return value.)

2. Unless V is Copy, there's no way to get literally Option<V>, as other versions of the map may be holding references to the relevant refcounted Entry structs. So it would have to return Option<SharedPointer<V, _>> or similar, which is fine too; it's the equivalent for a persistent data structure.

   However, V is held inside an Entry<K, V>.

   Options:

   • From an implementation perspective, the simplest thing would be to just return a refcounted pointer to the whole Entry, since it and its fields are pub; -> Option<SharedPointer<Entry<K, V>, P>>. This adds cruft to the call site though, since the caller obviously already has the key;

     let (map, old_entry) = map.replace(k, v);
     let old_value = old_entry.value;

     On the other hand, it's possible that the user's type K has distinct values that still deliberately Hash/Ord as equal for some reason, in which case being able to fetch the key too could be useful. (Though that should probably be the realm of another future method addition, akin to std::HashMap::entry.)

     (This what the PR does currently.)

   • Invent a new struct like SharedValue<V>(SharedPointer<Entry<K, V>, P>), which implements Deref<Target = V>. Then return Option<SharedValue<V>>.

     That's cleaner for the user, but feels weird to implement since it's so single-use. (I think this is better though, and would lean toward this being the API if this is added.)

Opinions?

[anko]

It also occurs to me now that approximately the same thing could be done for remove/remove_mut. I can't think of a neat alternative to that wording that implies the same as replace does for insert.

Perhaps insert_get/insert_mut_get and remove_get/remove_mut_get? Trying to avoid confusing overlap with get_mut, which gets a mutable reference, when these get an immutable reference, after a mutable operation.

Naming is hard. :sweat_smile:

[orium]

Sorry, I rename the master branch to main. Feel free to re-open the PR.