add insert_get() function to BTreeSet and HashSet

[Robbepop]

I am missing a method which I just call insert_get(...) in the interface of Set.

The method is a combination of insert(...) and the proposed get(...) (#21234).

So with insert_get(...) I could add a new item to the Set if it isn't already contained and return a reference to it.

However, contrary to the combined calls to insert(...) and get(...) this function would only calculate the hash of the given item once and also only perform the look-up once.

Besides that, given the certainty that the given item is inserted into the Set before we return the reference this method can return a &T instead of an Option<T> as in get(...).

I am in need of this method since I am trying to create a string cache and want to use this data structure as the owner of all strings within my application. This is not possible with the current API for sets.

Signature (fixed: thanks to apasel422)

fn insert_get(&mut self, value: T) -> &T;

or (linked RFC)

fn get_or_insert(&mut self, value: T) -> &T;

A Problem ...
I am not sure if it is possible to implement references out of containers easily since iterator invalidation could happen during insertion of new items deleting all references to items within the set stored outside ...

A Solution ...
To avoid iterator invalidation one could use indirections e.g. by using Box<T> instead of Tas item type for the HashSet.
An implementation could use this in order to provide methods that return references to its owned elements and forbid access to these methods otherwise.

[apasel422]

This would likely be covered by rust-lang/rfcs#1490.

Note that the signature you gave doesn't work, because you need to insert an item of type T. I assume you mean:

fn insert_get(&mut self, value: T) -> &T;

[apasel422]

Closing in favor of rust-lang/rfcs#1490.