I’ve had this conversation a lot lately, so I’m just going to post this here and hope we can settle it once and for all.
So currently, Maps treat keys like trash. These are the two main MutableMap fns:
fn swap(&mut self, k: K, v: V) -> Option<V>; fn pop(&mut self, k: &K) -> Option<V>;
swap takes a key by value, and in the case of a key-match returns a value, and just drops one of the keys.
pop meanwhile removes a key, but never gives it back. The search methods are a similar story, they only yield values. As a consequence, Sets (which are just a
Map<T, ()>) can’t tell you at all about what’s happening inside them:
fn insert(&mut self, value: T) -> bool; fn remove(&mut self, value: &T) -> bool;
They just know if something was there, and nothing else.
Now, on one hand, this all makes sense. The current convention in Rust is that if two objects are Eq, they’re basically byte-wise equal (ignoring actual memory addresses). Similarly, the two biggest keys are integers and strings, objects which are completely indistinguishable when equal. Therefore, information about keys would just be noise when we really do generally only care about values. If we accept this, then this opens up room for some internal optimizations. On key collisions, the implementation can keep whichever key is easiest (probably the old one, to avoid a write). In fact, this is actually basically the case right now.
HashMap keeps the old key, and
TreeMap keeps the new key. The behavior of a generic Map is basically undefined with respect to which keys are kept or lost.
On the other hand, there’s no fundamental reason why
Eq keys should be considered indistinguishable. It’s arbitrary code, the user can make it work how they want. Further, the keys could implement Drop, and therefore which does or doesn’t survive could really matter. Sets, which consist only of Keys, are exceptional minimal because of this behavior. All you can do is ask yes/no questions or get an iterator. Also, with tuple indexing, returning a “useless” key wouldn’t be a huge ergonomic loss.
So there’s the issue. We have Maps and Sets which basically assert that keys are uninteresting as actual values. This provides room for optimization, and keeps the API simple. However this constrains some niche hypothetical use cases. At very least, the current behavior is undocumented and inconsistent. I’d like to at least have a documented convention for how keys should be treated.