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.


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).


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.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.