Best Way to Drop Range of Elements From Front of VecDeque

1

Hi Guys,
I am wondering what is the most efficient or idiomatic way to drop a range of elements from the front of a VecDeque and keep the last N elements?

I see that truncate() drops elements nice and cleanly from the back but what is the equivalent to doing this at the front?

It looks like I could use drain(), split_off() or retain().

From reading the documentation drain involves some iteration and yields the removed items (I want to discard these).

Retain looks useful for "cherry-picking" which elements to keep that might not be contiguous in memory.

Since I am not aware of any equivalent to truncate for removing a range of elements from the front, I suspect that split_off() might be the most efficient way to do this?

I'll experiment with the various methods but perhaps someone in will have a definitive, best known answer.

Thanks,
djme.

2

I think drop(vecdeque.drain(..hi)) should be the most efficient and idiomatic: unlike split off, it wouldn’t do an allocation.

3

Calling pop_back in a loop should also be a fine solution.

4

@matklad's answer is the right option for now, but consider opening a PR to add truncate_front and seeing what the libs team has to say. It seems to me like a plausible thing to have.

5

Thanks for the replies guys. I have been away from my PC for the past few days but had a few mins to do a quick test today to compare the split_off() method verses the drop/drain method.

I am not sure how accurate the test below is but from repeated testing, the split_off() method was about 23 times faster to drop half of the 100 million values compared to the drop/drain method. On my PC the split_off() method completed the task in 270ms compared to 6300ms for the drop/drain method.

Again, I am not too sure how scientific this test is and haven't tested it with different values such as strings etc. but for now I'll be happy to use the split_off() method to truncate the front of a vec deque.

Thanks for your inputs.
djme.

use std::collections::VecDeque;
use std::time;

fn main() {
    let mut vd = VecDeque::new();
    let max_num = 100_000_000; 
    let keep_last_n = max_num / 2 ;
    
    //populate vec deque
    vd.extend(0..max_num);
    println!("vec deque initialized. Size is {}", vd.len());
    
    //take starting time
    let now = time::Instant::now();
    
    //Method 1: keep the last n elements - split method
    vd = vd.split_off(vd.len() - keep_last_n);
    
    //Method 2: keep the last n elements - drop/drain 
    //drop(vd.drain(0..keep_last_n));
    
    println!("Done in {} milliseconds", now.elapsed().as_millis());
    println!("{:?}", vd.len());
}
6

Please make a benchmark with criterion - Rust to see for sure.

Are you running with --release? Those numbers seem off by at least an order of magnitude...

1 Like
7

Thanks matklad/All,
The drain method does seem like the best method to truncate the front of a deque. This was not the case when I had completed some initial testing (in debug mode) but, as recommended by scottmcm, I retested with --release and using drain was indeed much quicker.
PS. Apologies for the delay in reply...I have not had much of a chance to do any Rust programming recently!
Regards,
djme.

1 Like
8

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