Tracking Issue for {BTreeMap,BTreeSet}::extract_if

[ssomers]

This is a tracking issue for the Implementation of a extract_if method on BTreeMap and BTreeSet, similar to the one in LinkedList and in Vec (#43244).
The feature gate for the issue is #![feature(btree_extract_if)] (previously btree_drain_filter)

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also uses as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• Implement suboptimally, relying on an Ord bound: efficient for simple and common cases, but falling back on a coarse restart after complicated removals.
• Possibly adjust the underlying tree representation (using Cells).
• Implement all cases without relying on an Ord bound, tracking every adjustment
• Adjust documentation (see instructions on rustc-dev-guide)
• Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

• Do we want the Ord bound on drain_filter (that is currently not required)?
• Do we need to implement some post-panic guarantees beyond memory leaks, like the undocumented guarantees that Vec::drain_filter and LinkedList::drain_filter provide, as I tried to discuss in Audit liballoc for leaks in Drop impls when user destructor panics #67290?
• The unstable book seems abandoned - the other drain_filter is listed but generated from somewhere.

Implementation history

• Remove the Ord bound on DrainFilter (not on drain_filter) (Remove the Ord bound that was plaguing drain_filter #70843)
• Keep track of position when deleting from a BTreeMap (Keep track of position when deleting from a BTreeMap #70795)
• Initial suboptimal implementation (BTreeMap/BTreeSet: implement drain_filter  #68770)
• Related attempt to implement drain and retain (BTreeMap/BTreeSet drain & retain #66747)
• Don't drain-on-drop in DrainFilter impls of various collections. #104455

[droundy]

Is there another issue for adding these to HashSet and HashMap?

[mbrubeck]

Is there another issue for adding these to HashSet and HashMap?

That is #59618.

[simias]

I stumbled upon this issue from the docs and I must say that I'm a bit confused: I wanted to replace a HashMap with a BTreeMap in my code, but then I noticed that it didn't have a retain method unlike the hash counterpart. Then I noticed this experimental drain_filter method.

As far as I can tell isn't this method the same thing as HashMap's retain, just with the boolean result of the predicate complemented?

Looking at the APIs of BTreeMap, Vec and HashMap I find the following methods that all deal with filtering the contents of the collection:

Vec::retain: predicate that gets passed an &T
HashMap::retain: predicate that gets passed an &K, &mut V

Vec::drain_filter: predicate that gets passed an &mut T
BTreeMap::drain_filter (this issue): predicate that gets passed a &K, &mut V

LinkedList has drain_filter (taking a &mut T) but no retain. And then there's this old RFC from 2015 that proposes BTreeMap::retain: rust-lang/rfcs#1338

I genuinely don't get the logic behind these choices of mutability and naming.

In particular I really think that the APIs of HashMap and BTreeMap should match as much as practically possible since they are so conceptually similar and it's not uncommon to want to replace one by the other in hindsight (in particular if your ordering requirements change).

[simias]

Oh, I noticed an obvious difference between retain and drain_filter: the later returns an iterator. So now I understand the need for both, but I'm still surprised by the lack of consistency between collections when it comes to mutability and the lack of drain_filter for HashMaps.

[ssomers]

When I first looked into it, I remember a drain_filter where the predicate had the opposite meaning. I liked the current one better: true means "yes, drain".

now I understand the need for both

If you really do, please explain, but I think you mean you understand why someone made retain and later someone made a more general drain_filter, probably for another container. At least that's how I hope it went.

[fogti]

I think if we could replace retain with an implementation solely based upon drain_filter, this would prove that retain is therefore redundant.

[simias]

Right, I meant that I understand why drain_filter is effectively a more powerful retain. I assumed that either retain came first and was kept for compatibility or that it was somehow more efficient.

I also found this issue in the meantime: #59618 so apparently HashMap is going to get a drain_filter too, which means that eventually the APIs will be less confusing and less weirdly incompatible between the two *Maps.

In the meantime it's a real hard scratcher, for me at least.

[mbrubeck]

HashMap::drain_filter is already available in the nightly toolchain. It's behind a feature flag, like the other drain_filter methods. On stable Rust, you can use HashMap::drain_filter via hashbrown.

For the status of drain_filter in all the standard collection types, see rust-lang/rfcs#2140. For discussion of the naming and API design for drain_filter, see #43244, especially this comment.

[simias]

Thank you @mbrubeck, this was the context I lacked.

[mbrubeck]

I submitted #79026 to add BTreeMap::retain and BTreeSet::retain, implemented in terms of drain_filter as suggested above.

[ssomers]

if we could replace retain with an implementation solely based upon drain_filter

I think retain is the same as drain_filter with the predicate inverted and the result dropped, as in this playground demo, or even better, in a playground demo that isn't spectacularly wrong. But in the hashbrown code they are unrelated. Maybe that's to improve performance, because drain_filter does add some overhead for setting up and using an iterator. Either way, it's pretty easy to implement retain in BTreeMap/Set.

[ssomers]

Note that this (nightly only) drain_filter in BTreeMap/Set is as optimal as I can imagine when you drain only a few elements, but definitely not when you drain a lot of elements. Of course, if you typically drain all but a few elements, you shouldn't be using drain_filter at all - better into_iter, into_keys or into_values the whole lot and divert the few ones you want to retain to a new map/set. But if you drain say half the elements, it's nowhere near as efficient as something like split_off. So I'm not sure this is good enough to become stable at all.

[maboesanman]

As it is now the documentation makes no claims about the order of the events returned from the iterator. Is this intended? having this iterator return in sorted order, or even returning a double ended iterator similar to range could be pretty useful.

[ssomers]

It's not intended not to be made, this claim… I mean, I forgot to mention that, because it's guaranteed to come in ascending order. PS ⇒ #81434

[maboesanman]

it's certainly worth documenting that, but I also think it's worth making this into a double ended iterator.

[ssomers]

It's definitely not easy to make drain_filter double-ended, and almost definitely possible. I wonder why though. Unlike iterators and range, drain_filter does not allow shortcutting, stopping when you've reached the elements you were interested in. You have to see the whole collection through, front to back. So by querying the length up front, it seems to me you can easily do the same thing you could do with a double-ended iterator.

[KonradHoeffner]

This feature stopped working for me with the newest nightly version as of 2023-06-16.

[Nemo157]

The feature was renamed in #104455.

[KonradHoeffner]

Thanks! After replacing "btree_drain_filter" with "btree_extract_if" and "drain_filter" with "extract_if" the code compiles as before.

[QuineDot]

The ExtractIf definitions have lifetime bounds on the F parameter which, as far as I can tell, are unnecessary.

// BTreeMap version
pub struct ExtractIf<'a, K, V, F, A: Allocator + Clone = Global> where
    F: 'a + FnMut(&K, &mut V) -> bool,

Which causes this to fail without extra bounds, for example.

Edit: Eh, that was a bad example since it type-erased F and would thus need the bound anyway. (The outer covariance of &mut _ makes it hard to observe the bound in an uncontrived way.)

The T: 'a on BTreeSet can also probably be removed (it's implied on the extract_if method anyway).

The same is probably also true for linked_list::ExtractIf.

Inspired by this conversation.

[Amanieu]

We discussed this in the libs-api meeting today. As with Vec::extract_if in #43244, this should take a range argument to limit the extraction to a subset of the tree. It is often desirable to only scan or extract only a subset of elements in a tree.