pre-RFC: HashSet::pop()

[joshtriplett]

I'd like to have a pop() method available for HashSet, which removes an item from the set if any, and returns an Option<T> (returning None if empty). That would make it easy to iterate over a set with while let element = set.pop() { ... }, without holding a mutable reference to the set as HashSet::drain() does, so you can insert more items into the set as you iterate.

Does that seem like a reasonable method to add to HashSet? Does this need an RFC, or just a patch to std?

[jonas-schievink]

The more interesting question is how you'd implement this without quadratic behaviour

[nagisa]

Duplicate-ish to #33549

[sfackler]

I believe these kinds of issues should also be filed on the RFCs repo rather than here.

[joshtriplett]

@jonas-schievink You could keep a "hint" in the set for the next bucket to check for an element, and increment that after popping out an element. That would avoid traversing all the empty buckets every time. So, unless you had a loop where every insert happened to put a new element at the point directly behind the current hint, you shouldn't get quadratic behavior.

@nagisa Not quite, I think. An iterator over the entries wouldn't allow mutating the set at the same time.

@sfackler You're right, I should have filed this on the RFCs repository.

[bluss]

OrderMap has an O(1) (average) .pop() because its implementation allows it.

Like jonas said, needs shrewd plan for how to do it in HashSet/HashMap if they don't change implementation.

[sfackler]

Closing in favor of the RFCs issue.