Struct ::std::collections::VecDeque

Overview

A double-ended queue implemented with a growable ring buffer.

The "default" usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from the queue. extend and append push onto the back in this manner, and iterating over VecDeque goes front to back.

A VecDeque with a known list of items can be initialized from an array:

use std::collections::VecDeque;

let deq = VecDeque::from([-1, 0, 1]);

Methods

fn new() -> VecDeque

Creates an empty deque.

Examples

use std::collections::VecDeque;

let deque = VecDeque::new();
fn with_capacity(count: i64) -> VecDeque

Creates an empty deque with space for at least capacity elements.

Examples

use std::collections::VecDeque;

let deque = VecDeque::with_capacity(10);
assert!(deque.capacity() >= 10);
fn from(value) -> VecDeque

Construct a VecDeque from a value.

Examples

use std::collections::VecDeque;

let buf = VecDeque::from([1, 2, 3]);
fn extend(self, value) -> Tuple

Extend this VecDeque with something that implements the [INTO_ITER] protocol.

Examples

use std::collections::VecDeque;

let deque = VecDeque::new();
deque.extend([1, 2, 3]);

assert_eq!(Some(1), deque.pop_front());
assert_eq!(Some(3), deque.pop_back());
fn insert(self, index: i64, value) -> Tuple

Inserts an element at index within the deque, shifting all elements with indices greater than or equal to index towards the back.

Element at index 0 is the front of the queue.

Panics

Panics if index is greater than deque's length

Examples

use std::collections::VecDeque;

let buf = VecDeque::new();
buf.push_back('a');
buf.push_back('b');
buf.push_back('c');
assert_eq!(buf, ['a', 'b', 'c']);

buf.insert(1, 'd');
assert_eq!(buf, ['a', 'd', 'b', 'c']);
fn iter(self) -> Iterator

Returns a front-to-back iterator.

Examples

use std::collections::VecDeque;

let buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);

assert_eq!([5, 3, 4], buf.iter());
assert_eq!([4, 3, 5], buf.iter().rev());
fn reserve(self, index: i64) -> Tuple

Reserves capacity for at least additional more elements to be inserted in the given deque. The collection may reserve more space to speculatively avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

use std::collections::VecDeque;

let buf = VecDeque::from([1]);
buf.reserve(10);
assert!(buf.capacity() >= 11);
fn len(self) -> i64

Returns the number of elements in the deque.

Examples

use std::collections::VecDeque;

let deque = VecDeque::new();
assert_eq!(deque.len(), 0);
deque.push_back(1);
assert_eq!(deque.len(), 1);
fn capacity(self) -> i64

Returns the number of elements the deque can hold without reallocating.

Examples

use std::collections::VecDeque;

let buf = VecDeque::with_capacity(10);
assert!(buf.capacity() >= 10);
fn front(self) -> Option

Provides a reference to the front element, or None if the deque is empty.

Examples

use std::collections::VecDeque;

let d = VecDeque::new();
assert_eq!(d.front(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.front(), Some(1));
fn back(self) -> Option

Provides a reference to the back element, or None if the deque is empty.

Examples

use std::collections::VecDeque;

let d = VecDeque::new();
assert_eq!(d.back(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.back(), Some(2));
fn push_back(self, value) -> Tuple

Appends an element to the back of the deque.

Examples

use std::collections::VecDeque;

let buf = VecDeque::new();
buf.push_back(1);
buf.push_back(3);
assert_eq!(Some(3), buf.back());
fn push_front(self, value) -> Tuple

Prepends an element to the deque.

Examples

use std::collections::VecDeque;

let d = VecDeque::new();
d.push_front(1);
d.push_front(2);
assert_eq!(d.front(), Some(2));

Removes the first element and returns it, or None if the deque is empty.

Examples

use std::collections::VecDeque;

let d = VecDeque::new();
d.push_back(1);
d.push_back(2);

assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

Removes the last element from the deque and returns it, or None if it is empty.

Examples

use std::collections::VecDeque;

let buf = VecDeque::new();
assert_eq!(buf.pop_back(), None);
buf.push_back(1);
buf.push_back(3);
assert_eq!(buf.pop_back(), Some(3));
fn remove(self, index: i64) -> Option

Removes and returns the element at index from the deque. Whichever end is closer to the removal point will be moved to make room, and all the affected elements will be moved to new positions. Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples

use std::collections::VecDeque;

let buf = VecDeque::new();
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.remove(1), Some(2));
assert_eq!(buf, [1, 3]);
fn rotate_left(self, mid: i64) -> Tuple

Rotates the double-ended queue mid places to the left.

Equivalently,

  • Rotates item mid into the first position.
  • Pops the first mid items and pushes them to the end.
  • Rotates len() - mid places to the right.

Panics

If mid is greater than len(). Note that mid == len() does not panic and is a no-op rotation.

Complexity

Takes *O*(min(mid, len() - mid)) time and no extra space.

Examples

use std::collections::VecDeque;

let buf = (0..10).iter().collect::<VecDeque>();

buf.rotate_left(3);
assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);

for i in 1..10 {
   assert_eq!(i * 3 % 10, buf[0]);
   buf.rotate_left(3);
}

assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
fn rotate_right(self, mid: i64) -> Tuple

Rotates the double-ended queue k places to the right.

Equivalently,

  • Rotates the first item into position k.
  • Pops the last k items and pushes them to the front.
  • Rotates len() - k places to the left.

Panics

If k is greater than len(). Note that k == len() does not panic and is a no-op rotation.

Complexity

Takes *O*(min(k, len() - k)) time and no extra space.

Examples

use std::collections::VecDeque;

let buf = (0..10).iter().collect::<VecDeque>();

buf.rotate_right(3);
assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);

for i in 1..10 {
   assert_eq!(0, buf[i * 3 % 10]);
   buf.rotate_right(3);
}

assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

Protocols

protocol index_get 
let output = value[index]

Allows an indexing get operation to work.

protocol index_set 
value[index] = input

Allows an indexing set operation to work.

protocol into_iter 
for item in value { }

Allows the value to be converted into an iterator in a for-loop.

protocol string_debug 
println("{:?}", value)

Write a debug representation to a string.

This calls the [STRING_DEBUG] protocol over all elements of the collection.

Examples

use std::collections::VecDeque;

let deque = VecDeque::from([1, 2, 3]);
assert_eq!(format!("{:?}", deque), "[1, 2, 3]");
protocol partial_eq 
if value == b { }

Perform a partial equality check with this deque.

This can take any argument which can be converted into an iterator using [INTO_ITER].

Examples

use std::collections::VecDeque;

let deque = VecDeque::from([1, 2, 3]);

assert!(deque == [1, 2, 3]);
assert!(deque == (1..=3));
assert!(deque != [2, 3, 4]);
protocol eq 
if value == b { }

Perform a total equality check with this deque.

Examples

use std::collections::VecDeque;
use std::ops::eq;

let deque = VecDeque::from([1, 2, 3]);

assert!(eq(deque, VecDeque::from([1, 2, 3])));
assert!(!eq(deque, VecDeque::from([2, 3, 4])));
protocol partial_cmp 
if value < b { }

Perform a partial comparison check with this deque.

Examples

use std::collections::VecDeque;

let deque = VecDeque::from([1, 2, 3]);

assert!(deque > VecDeque::from([0, 2, 3]));
assert!(deque < VecDeque::from([2, 2, 3]));
protocol cmp 
if value < b { }

Perform a total comparison check with this deque.

Examples

use std::collections::VecDeque;
use std::cmp::Ordering;
use std::ops::cmp;

let deque = VecDeque::from([1, 2, 3]);

assert_eq!(cmp(deque, VecDeque::from([0, 2, 3])), Ordering::Greater);
assert_eq!(cmp(deque, VecDeque::from([2, 2, 3])), Ordering::Less);