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.

Public API

impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
    pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, K, V, R, F, A>
    where
        K: Ord,
        R: RangeBounds<K>,
        F: FnMut(&K, &mut V) -> bool
}

pub struct ExtractIf<'a, K,  V, R, F>

impl<K, V, R, F, A: Allocator + Clone> Iterator for ExtractIf<'_, K, V, R, F, A> {}

/// ditto for BTreeSet

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.