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