Why does Rust's BTreeSet not have a pop()?

1

I've given up on using the BinaryHeap because I need to be able to update and view into the contents of the queue. I've replaced it with BTreeMap and other than my Ord implementation being a bit weird, it's working great.

This is the minimal code as a proof-of-concept:

use std::collections::BTreeSet;
 
fn main() {
    let mut pq = BTreeSet::new();

    pq.insert(3);
    pq.insert(1);
    pq.insert(0);
    pq.insert(2);
    pq.insert(4);

    loop {
        // My pretend 'pop' function looks up the element, then calls take() below.
        let item = match pq.iter().next() {
            None => return,
            Some(x) => x.clone()
        };

        let item = pq.take(&item)
            .expect("Should be covered by match arm above");

        println!("Value: {}", item);
    }
}

This is bad code for multiple reasons, but it begs the question: Why isn't pop() on BTreeMap part of the standard library? It should be more useful and efficient than the BinaryHeap implementation presuming the BinaryHeap is in fact a binary heap underneath.

If I were to implement pop(), what needs to happen?

1 Like
3

pop_first and pop_last were recently added, and are currently available in nightly Rust as an unstable feature:

https://doc.rust-lang.org/nightly/std/collections/struct.BTreeSet.html#method.pop_first

12 Likes
4

Well that’s perfect then! Thanks!

5

Just a little update here for those who stumble upon it: I did try using pop_first as opposed to my solution above but it provided different results. I didn't dive deeply into it, but for those who might give it a try I'd make sure you're getting the results you expect from both methods.

6

.iter().next() doesn't remove the element, but .pop_first() does.

7

No, but take does, which is part of the alternative pop_first implementation.

1 Like
8

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