Document replacement behavior of map and set insertion methods

[apasel422]

The behavior of the following methods is undocumented when the key/item being inserted is equivalent to one already in the collection:

• BTreeMap::insert
• BTreeSet::insert
• HashMap::insert
• HashSet::insert

The following program demonstrates that the maps and sets do not replace their keys/items in this scenario:

use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Foo {
    a: u32,
    b: &'static str,
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool { self.a == other.a }
}

impl Eq for Foo {}

impl Hash for Foo {
    fn hash<H: Hasher>(&self, h: &mut H) { self.a.hash(h); }
}

impl PartialOrd for Foo {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.a.partial_cmp(&other.a) }
}

impl Ord for Foo {
    fn cmp(&self, other: &Self) -> Ordering { self.a.cmp(&other.a) }
}

fn main() {
    println!("BTreeMap:");
    let mut map = BTreeMap::new();
    map.insert(Foo { a: 1, b: "baz" }, ());
    map.insert(Foo { a: 1, b: "xyz" }, ());
    for foo in map.keys() { println!("{:?}", foo); }

    println!("HashMap:");
    let mut map = HashMap::new();
    map.insert(Foo { a: 1, b: "baz" }, ());
    map.insert(Foo { a: 1, b: "xyz" }, ());
    for foo in map.keys() { println!("{:?}", foo); }

    println!("BTreeSet:");
    let mut set = BTreeSet::new();
    set.insert(Foo { a: 1, b: "baz" });
    set.insert(Foo { a: 1, b: "xyz" });
    for foo in &set { println!("{:?}", foo); }

    println!("HashSet:");
    let mut set = HashSet::new();
    set.insert(Foo { a: 1, b: "baz" });
    set.insert(Foo { a: 1, b: "xyz" });
    for foo in &set { println!("{:?}", foo); }
}

Output:

BTreeMap:
Foo { a: 1, b: "baz" }
HashMap:
Foo { a: 1, b: "baz" }
BTreeSet:
Foo { a: 1, b: "baz" }
HashSet:
Foo { a: 1, b: "baz" }

[reem]

This is... unexpected.

[steveklabnik]

/cc @rust-lang/libs @gankro

is this behavior intentional and should it be documented?

[Gankra]

It's intentional. The justification being "our API says you're not allowed to care about keys, and swapping keys is more expensive, so do the less expensive thing".

It's not necessarily the right choice, but at very least it's not an accident. It's unclear if anyone is relying on this (we settled on a uniform behaviour in case anyone did).

[apasel422]

I think we should document that they don't replace the key. rust-lang/rfcs#1194 provides an additional replace method that does replace them, and it's most flexible to provide both forms.