Repository navigation
Tracking Issue for BinaryHeap::contains and BinaryHeap::remove #82001
Description
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::containsandBinaryHeap::remove#82002 - Final commenting period (FCP)
- Stabilization PR
Unresolved Questions
- What is the best way to check if an item exists in a
BinaryHeap?
Activity
goffrie commentedon Feb 13, 2021
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::removealso exists and takes linear time.est31 commentedon Feb 17, 2021
@goffrie good point. Maybe the docs added by #82002 should include this as a caveat and point to using a
BTreeSetif you need to do such an operation more often?m-ou-se commentedon Mar 3, 2021
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!)