Retain for btree_map::RangeMut

BTreeMap currently has a useful retain function

However (unless I am missing something) there is no equivalent if you want to process a range and retain some elements of the range.

returns

which doesn't have a retain function.

I think this would be a useful addition to BTreeMap (I have needed it), and given that retain is already implemented, I imagine ( without having looked at the code ) it would not be too difficult to implement. Thoughts?

I think you' re looking for BTreeMap::drain_filter. In general this kind of operation is called "drain".

However I think it lacks a faster variant for ranges. That is, drain_filter (and retain) will always call the closure for each element (which is linear in the total number of values) even though you might be interested in removing only a specific range (which is logarithmic in the total number of values).

2 Likes

It might make sense to add some kind of fast-forward method to the various BTree iterators which can skip past entire subtrees without iterating into them— Like Iterator::find, but that takes something less general than FnMut.

Yes. I am not quite how the API would work, but the requirement is to have a version of retain that operates over a specified range of the Map, a combination of range_mut and retain. Currently I have to call remove for each element that is to be removed ( after saving the key values in an auxiliary Vec ). Which is not very elegant or efficient.