Add a `take_any` method

[timothee-haudebourg]

It is not the first time I'm missing a method to remove an arbitrary element from a set or map. This issue has been solved in the standard library for BTreeSet and BTreeMap with the recent introduction of the pop_first and pop_last methods, but there is no equivalent for HashMap/HashSet.

What I'm looking for is as simple as that:

/// Removes an arbitrary element from the set.
fn take_any(&mut self) -> Option

It is currently impossible to remove an element from a HashMap/HashSet through remove or take without a preexisting reference to an element/key of the set/map. So to have such reference the only way is to clone one beforehand:

fn take_any<T: Clone>(set: &mut HashSet<T>) -> Option<T> {
  let result = set.iter().next()?.clone();
  set.remove(&result);
  result
}

It is possible without the Clone bound with the drain_filter that allows to drain the first item and keep the rest, but it seems expansive to me.

fn take_any<T>(set: &mut HashSet<T>) -> Option<T> {
  let mut taken = false;
  set.drain_filter(|_| {
    let take = !taken;
    taken = true;
    take
  }).next()
}

As for the name, it could also be named pop_any to reflect the pop_first and pop_last methods on BTreeSet and BTreeMap.

[timothee-haudebourg]

Following the related thread on the internals forum it appears that it would be a O(n) operation, which removes the advantages of using a HashSet/HashMap. But on the eventual case where it cannot be avoided, I still think it would be nice to have this function to avoid the Clone bound and the cost of using drain_filter that iterates over the whole map/set.

[Amanieu]

My recommendation in these cases is to use IndexMap instead, where the pop operation is guaranteed to be O(1).

[timothee-haudebourg]

I understand there are more fitted libraries for that, but sometimes the choice isn't ours to make and we have to work with what we have. Even then, the additional cost induced by IndexMap may be too much if take_any is only used rarely. Whatever the case, there is currently no way of removing an arbitrary element from a map or set without cloning, regardless of the complexity of the operation. You could still provide the operation with a complexity warning and let the user choose, if they can, what is better in their situation. Not all operations have to be O(1), O(n) is not so bad either.