0

I need to implement a function similar to the unstable BTreeSet::pop_first().

It is not a duplicate of Getting first member of a BTreeSet, since I ask for a way get the first element of a BTreeSet without making a copy.

fn pop<O:Ord>(set: &mut std::collections::BTreeSet<O>) -> O

Based on a previous question (Getting first member of a BTreeSet), I get a compiler error about a mutable use after an inmutable one:

pub fn pop<O:Ord>(set: &mut std::collections::BTreeSet<O>) -> O {

    let n = {
        let mut start_iter = set.iter();
        start_iter.next().unwrap()
    };

    set.take(n).unwrap()
}

error[E0502]: cannot borrow `*set` as mutable because it is also borrowed as immutable
   --> src/main.rs:493:5
    |
489 |         let mut start_iter = set.iter();
    |                              --- immutable borrow occurs here
...
493 |     set.take(n).unwrap()
    |     ^^^^----^^^
    |     |   |
    |     |   immutable borrow later used by call
    |     mutable borrow occurs here

If I replace set.iter() with set.iter().clone() the code works, but I would like to not make copies of the elements of the set because it will be a costly operation.

How can I implement such a pop function?

rustc version 1.41.0

E_net4
  • 27,810
  • 13
  • 101
  • 139
Alvaro González Sotillo
  • 48
  • 5
  • The elements of the iterator are borrowed from the set, so `n` is borrowed from the set as well. Have you considered using a `BinaryHeap` as suggested in the linked question? – nnnmmm Mar 14 '20 at 18:00
  • I need an ordered data type that removes duplicates. It seems a `BinaryHeap` can not remove duplicates. – Alvaro González Sotillo Mar 14 '20 at 18:52
  • I don't agree with https://stackoverflow.com/users/155423/shepmaster. The linked question doesn't solve my problem: I what to remove the first element and get it *without* a copy, like `pop_first` seems to do. – Alvaro González Sotillo Mar 19 '20 at 17:00

1 Answers1

2

It is not possible to implement that function like you ask without access to the internals of BTreeSet: The elements of the iterator are borrowed from the set, so n is borrowed from the set as well. While you have borrowed something from the set, you cannot modify it.

You could:

  • Use clone()/cloned(), like you mentioned. If you were worried it would clone all elements in the iterator when calling pop_first(), that's not the case. It would clone only the one element since iterators are lazy.
  • Keep both a BinaryHeap and a HashSet of your elements. Before inserting an element into the BinaryHeap, check whether it is already in the HashSet.
  • Find/implement an extended BTreeSet from scratch that has this functionality.
nnnmmm
  • 7,964
  • 4
  • 22
  • 41