Is anyone interested in adding a "pop" method to the standard sets and maps (HashMap, HashSet, BTreeMap, BTreeSet)? I mean something that removes an arbitrary element (for sets) or a key/value pair (for maps), and returns Some if one was found and None if the map was empty.
It's possible to work around it: you can do something like
if let &x = myset.iter().next() {
myset.remove(&x);
do_what_you_wanted_to();
}
However, this seems undesirable: it accesses the tree twice (once to find the element, once again to remove it), and I don't seem to see a way of doing it that doesn't have that property.
It's quite a useful piece of functionality: lots of algorithms have the flavour of maintaining a set of things to do, and repeatedly drawing things out of it until there are none left.
Yes please, and especially if it's an iterator that removes the individual items (rather that consumes the whole set, like into_iter does). Then you could do stuff like .take(2) on it to get a "random" pair. Maybe remove_iter or iter_remove
Hmm, @scottmcm, is it likely that there would be a faster implementation of pop_something() than of pop_last()? If so, then it does seem like a good idea!
@dcarosone, provided the pop() method existed, we'd be able to implement that ourselves if necessary: we just create a struct that holds a mutable reference to a set, and implements Iterator by popping it repeatedly. Once that no longer existed, we'd have access to our set again.
I don't know for sure, but given that always popping from the same side is inherently imbalancing, I'd suspect that giving the method extra leeway on what to pop would let it pull things out in a way that reduced the overall work.
(Could even be a good reason to make the destructive iterator be the way to expose it, as that could explicitly suspend rebalancing activities until you've stopped popping things.)
I would suggest that the implementation is free to pick an element 'at random', and could in theory pick the least-balanced leaf. In practice, figuring out which one is 'optimal' might be as much work as re-balancing, at least for some data structures, but at least the option is there.
How would it know when you've stopped? Hold a guard from the collection object in the iterator that's released on drop?
While I'm sure that's true in general, there are at least some where it's easy -- the balance factor in an AVL tree leads directly to the deepest node, for example.
Yes, borrow it mutably in the iterator, and fix it in iterator's Drop::drop (very, very carefully, including actually making it look empty on creation of the iterator).
Basically the same idea as how Vec::drain is more efficient that calling Vec::remove repeatedly.