Add drain_filter for BinaryHeap

[RalfJung]

std::collections::BinaryHeap is missing a drain_filter method (rust-lang/rfcs#2140).

[dtolnay]

Sounds good to me. I agree that this part of the API would be good to keep consistent between HashMap/HashSet and BTreeMap/BTreeSet. Please submit a PR.

[Ryan1729]

If someone ever gets around to this, it would be a shame to repeat the mistake of passing &T like in the Vec retain implementation. These methods should pass &mut T to the closure, like the HashMap implementation does.

[jq-rs]

Getting nowhere so far, so I'll pass this to future volunteers.

[jonhoo]

BinaryHeap now has drain, although for some reason it removes elements in arbitrary order (#59278) :/

[hellow554]

[...] it removes elements in arbitrary order (#59278) :/

Is that really a problem? I can't think of a situation where you want to remove elements in order.

Ah sure, it's about iterating in a specific order, not removing (was confused with retain)

[jonhoo]

I mean, it's a heap... If I want to re-use the heap, it seems pretty reasonable to use .drain to walk the heap rather than a while let Some(_) = heap.pop loop. I think this is especially surprising for IntoIterator -- it'd be like a BTreeMap yielding elements in a random order when you do for (k, v) in btreemap.

[czipperz]

Is it acceptable to implement this using brute force and then redo it later for performance gains? Just do something like:

let this = mem::replace(self, Default::default());
*self = this.into_iter().filter(...).collect();

[ssomers]

It turns out that a drain without range is trivial. An excerpt from simple code on playground comparing to an existing drain:

        for i in v[0].drain(..) {}
        for i in std::mem::replace(&mut m[0], BTreeSet::new()).into_iter() {}

So I think it's only worth the trouble if it operates on a range.

Secondly, I wondered why retain doesn't take a range either, but that's what drain_filter is for (the #59618 mentioned above). It might die like #1353 did, but more likely it means retain will be useless and we want drain_filter instead.

[mbrubeck]

All but two of the methods originally requested here have since been implemented. I'm splitting this issue so that we have one ticket for per method. This ticket is for BinaryHeap::drain_filter.

BTreeMap/BTreeSet::drain_filter are tracked at #70530. BinaryHeap::retain is tracked at #71503. BTreeMap/BTreeSet::retain are part of rust-lang/rfcs#1338.

[inquisitivecrystal]

Should BinaryHeap::drain_filter be sorted or not? BinaryHeap::drain isn't sorted, but there's an equivalent, BinaryHeap::drain_sorted, which is.

[mikeleany]

@rustbot claim

[dis-da-moe]

@rustbot claim

[dis-da-moe]

Some questions from implementing this feature:

1. Should the closure also accept an &mut T? An item could be mutated to violate the heap order. Two possible solutions:
   1. Change the closure to accept an & T. This would mean one less feature and make this implementation inconsistent with others. But it would avoid the complexity of 2.
   2. Change the closure to accept a struct that behaves similarly to PeekMut<T>. If the struct is deref'd mut to an &mut T then on drop it will ensure the item is sorted correctly on the heap. This increases potential complexity in implementation and for the end user, as instead of accessing the value directly they need to deref it.
2. Should the items be given to the closure in order or out of order? Or should we follow the route of drain and have drain_filter and drain_filter_sorted?