BTreeMap::drain with a range

It's really unfortunate that BTreeMap doesn't have a drain method that takes a RangeBounds - the only real alternative I have right now is to iterate over all the keys in drain_filter testing if they're in the range - taking what could ostensibly be an O(log(n)) operation and turning it into an O(n).

As someone who hasn't contributed to rust in the past - is there anything I can do to help make this happen? Do I need to submit an RFC?

2 Likes

I don't think that this needs an RFC, because there isn't much design space. You could just submit a PR with the change and have soneone sign off on it to get it in nightly. Stabilizing will require a full team signoff, but that should be fine. (Disclaimer: I'm not on any teams that could sign off on stdlib changes)

Probably make a new function drain that takes a range

3 Likes

I have the impression that the hard part is just the implementation here - so if you have that it should be all good. A drain range has to handle partially emptying nodes, even below their minimum and then rebalancing (progressively?)

If I see it right it shouldn't be impossible, it should be possible to break down the tree - because we're draining a range - into large chunks that are untouched and then there's some slivers of nodes that need to be reassembled. Something like (the-before-the-range-tree) (boundary) (all the nodes that we drain fully) (boundary) (the after-the-range-tree)

I have the impression that the hard part is just the implementation here - so if you have that it should be all good.

I don't, unfortunately. Help here would be hugely appreciated.

I must have missed that drain_filter already exists. So the hard parts should already have been implemented, then.