Tracking Issue for BinaryHeap::contains and BinaryHeap::remove

[billyrieger]

Feature gate: #![feature(binary_heap_contains_remove)]

This is a tracking issue for BinaryHeap::contains and BinaryHeap::remove. These methods are missing from the BinaryHeap API and both are common operations that one would expect to have for any general-purpose container.

Previous discussion: #66724.

Public API

impl<T: Ord> BinaryHeap<T> {
    pub fn contains<Q: ?Sized>(&self, item: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: PartialEq;

    pub fn remove<Q: ?Sized>(&self, item: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: PartialEq;
}

Steps / History

• Implementation: Add BinaryHeap::contains and BinaryHeap::remove #82002
• Final commenting period (FCP)
• Stabilization PR

Unresolved Questions

• What is the best way to check if an item exists in a BinaryHeap?

[goffrie]

This seems like a trap in that you would usually want these to run in less-than-linear time, but they don't. e.g. the standard Dijkstra/A* applications (as in the linked discussion) definitely want sublinear access, otherwise it defeats the point.

That being said Vec::remove also exists and takes linear time.

[est31]

@goffrie good point. Maybe the docs added by #82002 should include this as a caveat and point to using a BTreeSet if you need to do such an operation more often?

[m-ou-se]

I'm closing this for now since it's not clear #82002 will be merged. We can re-open it later if needed.

(Next time please open a tracking issue only after the addition was approved by a libs reviewer. Thanks!)