Remove elements from the beginning of a sorted set

help
1

Hi guys, could you please tell what is the efficient way to do the the following:

I want to remove some of the elements from the beginning of a sorted set based on some condition (let's say some smaller than a given value). In Java I'll do:

SortedSet<Integer> set = new TreeSet<>();
set.add(1);
set.add(3);
set.add(5);
set.add(7);
set.add(9);
set.add(10);
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
  if(it.next() < 7){
    it.remove();
  }else{
    break;  
 }
}

I have no good idea, how I can do this efficiently in rust(e.g. without having to go over the whole collection and filter)
Thank you!

2

What collection are you using for the sorted set?

With BTreeSet, you can split_off and drop the part you don't want.

With a sorted Vec, you can binary_search the cut point and then drain(..i).

3

I am using a BTreeSet and my collection could be large(let's say 30k elements).
Is it split_of going to work if I split by an element which does not exist in the set? E.g if in my previous example I want to remove all elements less than 6?
Also, I need an efficient solution, by splitting, I'll create a new collection and basically I will go over each element I want to remove twice which is something I do not like.

I am very surprise that a solution similar with the one in java is neither available neither easy to code..

4

Yes, split_off works for splitting on an element that is not in the set. Example.

5

Thank you, looks, like split_of is my best bet.

6

An equivalent to the Java code could be:

    while let Some(&x) = set.iter().next() {
        if x < 7 {
            set.remove(&x);
        } else {
            break;
        }
    }

Full example

7

Plus an advantage to tree structures is that splitting them is usually not an expensive endeavor, since they don't have to copy all the split elements like you would if you split a Vec. I'm not exactly sure what BTreeMap/BTreeSet does but I'd be surprised if it had to reallocate every node.

8

That should work, since they're always removing the beginning, but we'd really need a Cursor API to replicate what Java is able to do.

9

Thank you, I am familiar with this solution, but it's ugly. It creates an iterator every loop step.