set_recovery

Summary

Add element-recovery methods to the set types in std.

Motivation

Sets are sometimes used as a cache keyed on a certain property of a type, but programs may need to access the type's other properties for efficiency or functionality. The sets in std do not expose their elements (by reference or by value), making this use-case impossible.

Consider the following example:

use std::collections::HashSet;
use std::hash::{Hash, Hasher};

// The `Widget` type has two fields that are inseparable.
#[derive(PartialEq, Eq, Hash)]
struct Widget {
    foo: Foo,
    bar: Bar,
}

#[derive(PartialEq, Eq, Hash)]
struct Foo(&'static str);

#[derive(PartialEq, Eq, Hash)]
struct Bar(u32);

// Widgets are normally considered equal if all their corresponding fields are equal, but we would
// also like to maintain a set of widgets keyed only on their `bar` field. To this end, we create a
// new type with custom `{PartialEq, Hash}` impls.
struct MyWidget(Widget);

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

impl Eq for MyWidget {}

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

fn main() {
    // In our program, users are allowed to interactively query the set of widgets according to
    // their `bar` field, as well as insert, replace, and remove widgets.

    let mut widgets = HashSet::new();

    // Add some default widgets.
    widgets.insert(MyWidget(Widget { foo: Foo("iron"), bar: Bar(1) }));
    widgets.insert(MyWidget(Widget { foo: Foo("nickel"), bar: Bar(2) }));
    widgets.insert(MyWidget(Widget { foo: Foo("copper"), bar: Bar(3) }));

    // At this point, the user enters commands and receives output like:
    //
    // ```
    // > get 1
    // Some(iron)
    // > get 4
    // None
    // > remove 2
    // removed nickel
    // > add 2 cobalt
    // added cobalt
    // > add 3 zinc
    // replaced copper with zinc
    // ```
    //
    // However, `HashSet` does not expose its elements via its `{contains, insert, remove}`
    // methods,  instead providing only a boolean indicator of the elements's presence in the set,
    // preventing us from implementing the desired functionality.
}

Detailed design

Add the following element-recovery methods to std::collections::{BTreeSet, HashSet}:

impl<T> Set<T> {
    // Like `contains`, but returns a reference to the element if the set contains it.
    fn get<Q: ?Sized>(&self, element: &Q) -> Option<&T>;

    // Like `remove`, but returns the element if the set contained it.
    fn take<Q: ?Sized>(&mut self, element: &Q) -> Option<T>;

    // Like `insert`, but replaces the element with the given one and returns the previous element
    // if the set contained it.
    fn replace(&mut self, element: T) -> Option<T>;
}

Drawbacks

This complicates the collection APIs.

Alternatives

Do nothing.