pre-RFC: HashSet::pop()

[joshtriplett]

(Originally filed as rust-lang/rust#37986, but a pre-RFC belongs in the RFC repo, not the rust repo. Re-filing it here.)

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?

[comex]

Only issue is that it'd have to search linearly through the table for a non-empty bucket, so calling it in a loop would be O(n^2)ish.

[joshtriplett]

@comex If you stored a "hint" index for the last location with an item, you should get O(n) amortized time to pop every item out of a set.

If you had a loop that also inserted new items, you should still avoid quadratic behavior, as long as the hash doesn't place items immediately behind the hint index every time.

[eddyb]

@joshtriplett Sounds more like what a draining iterator might do.

[clarfonthey]

@eddyb, @joshtriplett specifically requested this so that they can add more items into the set during iteration, so, drain is out for this use case

[bluss]

This is efficient (O(1) average) with a hashmap implementation like OrderMap's, but not with Rust's current HashMap.

crates.io already provides ordermap and linked-hash-map for two different use cases, but both have O(1) pop.

[joshtriplett]

@bluss An OrderSet would solve this for me. It'd be nice to have those in core Rust, but I don't mind pulling in another crate.

[clarfonthey]

@joshtriplett These are all part of the contain-rs organisation, so, I'd talk to them about that. A lot of these data structures are deemed as non-essential and many were actually removed from libstd, but if you can make a compelling case otherwise you could probably write up an RFC for it.

I don't know where the original discussion on this was but you could probably search for it.

[Centril]

Triage ping @joshtriplett

[joshtriplett]

I'm still interested in this and would still like to see such a method exist, or some other alternative that allows iteration without holding a reference.

[Centril]

@joshtriplett What I mean is: do you have any plans on making a PR / writing an RFC? 😃

[joshtriplett]

@Centril Making a PR, no. Writing an RFC, maybe; depends heavily on whether one would be welcomed or not, and based on this pre-RFC I'm not sure.

[Centril]

@joshtriplett Personally I like the idea. cc @rust-lang/libs -- what do you think?

[joshtriplett]

Does the switch to hashbrown affect this at all? Would that make this easier/harder?