Repository navigation
Tracking Issue for {BTreeMap,BTreeSet}::extract_if #70530
Description
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
Ordbound: efficient for simple and common cases, but falling back on a coarse restart after complicated removals. -
Possibly adjust the underlying tree representation (usingCells). - Implement all cases without relying on an
Ordbound, 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
Ordbound ondrain_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_filterandLinkedList::drain_filterprovide, as I tried to discuss in Audit liballoc for leaks inDropimpls when user destructor panics #67290? - The unstable book seems abandoned - the other drain_filter is listed but generated from somewhere.
Implementation history
- Remove the
Ordbound onDrainFilter(not ondrain_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
drainandretain(BTreeMap/BTreeSet drain & retain #66747) - Don't drain-on-drop in DrainFilter impls of various collections. #104455
Activity
droundy commentedon Jul 8, 2020
Is there another issue for adding these to HashSet and HashMap?
mbrubeck commentedon Jul 8, 2020
That is #59618.
simias commentedon Nov 13, 2020
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
retainmethod unlike the hash counterpart. Then I noticed this experimentaldrain_filtermethod.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&THashMap::retain: predicate that gets passed an&K, &mut VVec::drain_filter: predicate that gets passed an&mut TBTreeMap::drain_filter(this issue): predicate that gets passed a&K, &mut VLinkedList has
drain_filter(taking a&mut T) but noretain. And then there's this old RFC from 2015 that proposesBTreeMap::retain: rust-lang/rfcs#1338I genuinely don't get the logic behind these choices of mutability and naming.
In particular I really think that the APIs of
HashMapandBTreeMapshould 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 commentedon Nov 13, 2020
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_filterfor HashMaps.ssomers commentedon Nov 13, 2020
When I first looked into it, I remember a
drain_filterwhere the predicate had the opposite meaning. I liked the current one better: true means "yes, drain".If you really do, please explain, but I think you mean you understand why someone made
retainand later someone made a more generaldrain_filter, probably for another container. At least that's how I hope it went.fogti commentedon Nov 13, 2020
I think if we could replace
retainwith an implementation solely based upondrain_filter, this would prove thatretainis therefore redundant.simias commentedon Nov 13, 2020
Right, I meant that I understand why
drain_filteris effectively a more powerfulretain. 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_filtertoo, 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 commentedon Nov 13, 2020
HashMap::drain_filteris already available in the nightly toolchain. It's behind a feature flag, like the otherdrain_filtermethods. On stable Rust, you can useHashMap::drain_filtervia hashbrown.For the status of
drain_filterin all the standard collection types, see rust-lang/rfcs#2140. For discussion of the naming and API design fordrain_filter, see #43244, especially this comment.simias commentedon Nov 13, 2020
Thank you @mbrubeck, this was the context I lacked.
mbrubeck commentedon Nov 13, 2020
I submitted #79026 to add
BTreeMap::retainandBTreeSet::retain, implemented in terms ofdrain_filteras suggested above.57 remaining items
rfcbot commentedon Aug 15, 2025
The final comment period, with a disposition to merge, as per the review above, is now complete.
As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.
This will be merged soon.
the8472 commentedon Aug 15, 2025
Uh, a bit late in the process, but the tracking issue doesn't have an API signature overview.
Soo...
but
Can/should we add support for the K: Borrow indirection to the range argument?
rs-sac commentedon Aug 15, 2025
@the8472 I posted an updated pair of patches, one of which addresses the Borrow issue you pointed out. If it's not appropriate to post them together or if anything else is bureaucratically amiss, please let me know.
Unfortunately I cannot edit the issue to add the API signature.
rs-sac commentedon Aug 15, 2025
(In review, it was decided that due to an inability to infer the type of Q when the range is .., this idea is too high friction.)
Auto merge of #145471 - rs-sac:extr, r=the8472
Rollup merge of rust-lang#145471 - rs-sac:extr, r=the8472
Unrolled build for #145471
Rollup merge of #145471 - rs-sac:extr, r=the8472
Rollup merge of rust-lang#145471 - rs-sac:extr, r=the8472