logo
pub struct VecDeque<T, A = Global> where
    A: Allocator
{ /* private fields */ }
Available on crate feature mtls only.
Expand description

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]);

Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory. If you want to access the elements as a single slice, such as for efficient sorting, you can use make_contiguous. It rotates the VecDeque so that its elements do not wrap, and returns a mutable slice to the now-contiguous element sequence.

Implementations

Creates an empty deque.

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::new();

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

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::with_capacity(10);
🔬 This is a nightly-only experimental API. (allocator_api)

Creates an empty deque.

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::new();
🔬 This is a nightly-only experimental API. (allocator_api)

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

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::with_capacity(10);

Provides a reference to the element at the given index.

Element at index 0 is the front of the queue.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf.get(1), Some(&4));

Provides a mutable reference to the element at the given index.

Element at index 0 is the front of the queue.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
if let Some(elem) = buf.get_mut(1) {
    *elem = 7;
}

assert_eq!(buf[1], 7);

Swaps elements at indices i and j.

i and j may be equal.

Element at index 0 is the front of the queue.

Panics

Panics if either index is out of bounds.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf, [3, 4, 5]);
buf.swap(0, 2);
assert_eq!(buf, [5, 4, 3]);

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

Examples
use std::collections::VecDeque;

let buf: VecDeque<i32> = VecDeque::with_capacity(10);
assert!(buf.capacity() >= 10);

Reserves the minimum capacity for exactly additional more elements to be inserted in the given deque. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

Panics

Panics if the new capacity overflows usize.

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);

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

Panics

Panics if the new capacity overflows usize.

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve(10);
assert!(buf.capacity() >= 11);

Tries to reserve the minimum capacity for exactly additional more elements to be inserted in the given deque. After calling try_reserve_exact, capacity will be greater than or equal to self.len() + additional. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal. Prefer try_reserve if future insertions are expected.

Errors

If the capacity overflows usize, or the allocator reports a failure, then an error is returned.

Examples
use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve_exact(data.len())?;

    // Now we know this can't OOM(Out-Of-Memory) in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}

Tries to reserve capacity for at least additional more elements to be inserted in the given deque. The collection may reserve more space to avoid frequent reallocations. After calling try_reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

Errors

If the capacity overflows usize, or the allocator reports a failure, then an error is returned.

Examples
use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve(data.len())?;

    // Now we know this can't OOM in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}

Shrinks the capacity of the deque as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the deque that there is space for a few more elements.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to_fit();
assert!(buf.capacity() >= 4);

Shrinks the capacity of the deque with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to(6);
assert!(buf.capacity() >= 6);
buf.shrink_to(0);
assert!(buf.capacity() >= 4);

Shortens the deque, keeping the first len elements and dropping the rest.

If len is greater than the deque’s current length, this has no effect.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);
buf.truncate(1);
assert_eq!(buf, [5]);
🔬 This is a nightly-only experimental API. (allocator_api)

Returns a reference to the underlying allocator.

Returns a front-to-back iterator.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
let b: &[_] = &[&5, &3, &4];
let c: Vec<&i32> = buf.iter().collect();
assert_eq!(&c[..], b);

Returns a front-to-back iterator that returns mutable references.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
for num in buf.iter_mut() {
    *num = *num - 2;
}
let b: &[_] = &[&mut 3, &mut 1, &mut 2];
assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);

Returns a pair of slices which contain, in order, the contents of the deque.

If make_contiguous was previously called, all elements of the deque will be in the first slice and the second slice will be empty.

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);
deque.push_back(2);

assert_eq!(deque.as_slices(), (&[0, 1, 2][..], &[][..]));

deque.push_front(10);
deque.push_front(9);

assert_eq!(deque.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));

Returns a pair of slices which contain, in order, the contents of the deque.

If make_contiguous was previously called, all elements of the deque will be in the first slice and the second slice will be empty.

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);

deque.push_front(10);
deque.push_front(9);

deque.as_mut_slices().0[0] = 42;
deque.as_mut_slices().1[0] = 24;
assert_eq!(deque.as_slices(), (&[42, 10][..], &[24, 1][..]));

Returns the number of elements in the deque.

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert_eq!(deque.len(), 0);
deque.push_back(1);
assert_eq!(deque.len(), 1);

Returns true if the deque is empty.

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert!(deque.is_empty());
deque.push_front(1);
assert!(!deque.is_empty());

Creates an iterator that covers the specified range in the deque.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Examples
use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3].into();
let range = deque.range(2..).copied().collect::<VecDeque<_>>();
assert_eq!(range, [3]);

// A full range covers all contents
let all = deque.range(..);
assert_eq!(all.len(), 3);

Creates an iterator that covers the specified mutable range in the deque.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<_> = [1, 2, 3].into();
for v in deque.range_mut(2..) {
  *v *= 2;
}
assert_eq!(deque, [1, 2, 6]);

// A full range covers all contents
for v in deque.range_mut(..) {
  *v *= 2;
}
assert_eq!(deque, [2, 4, 12]);

Removes the specified range from the deque in bulk, returning all removed elements as an iterator. If the iterator is dropped before being fully consumed, it drops the remaining removed elements.

The returned iterator keeps a mutable borrow on the queue to optimize its implementation.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Leaking

If the returned iterator goes out of scope without being dropped (due to mem::forget, for example), the deque may have lost and leaked elements arbitrarily, including elements outside the range.

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<_> = [1, 2, 3].into();
let drained = deque.drain(2..).collect::<VecDeque<_>>();
assert_eq!(drained, [3]);
assert_eq!(deque, [1, 2]);

// A full range clears all contents, like `clear()` does
deque.drain(..);
assert!(deque.is_empty());

Clears the deque, removing all values.

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
deque.push_back(1);
deque.clear();
assert!(deque.is_empty());

Returns true if the deque contains an element equal to the given value.

This operation is O(n).

Note that if you have a sorted VecDeque, binary_search may be faster.

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<u32> = VecDeque::new();

deque.push_back(0);
deque.push_back(1);

assert_eq!(deque.contains(&1), true);
assert_eq!(deque.contains(&10), false);

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

Examples
use std::collections::VecDeque;

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

d.push_back(1);
d.push_back(2);
assert_eq!(d.front(), Some(&1));

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

Examples
use std::collections::VecDeque;

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

d.push_back(1);
d.push_back(2);
match d.front_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.front(), Some(&9));

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

Examples
use std::collections::VecDeque;

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

d.push_back(1);
d.push_back(2);
assert_eq!(d.back(), Some(&2));

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

Examples
use std::collections::VecDeque;

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

d.push_back(1);
d.push_back(2);
match d.back_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.back(), Some(&9));

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

Examples
use std::collections::VecDeque;

let mut 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 mut buf = VecDeque::new();
assert_eq!(buf.pop_back(), None);
buf.push_back(1);
buf.push_back(3);
assert_eq!(buf.pop_back(), Some(3));

Prepends an element to the deque.

Examples
use std::collections::VecDeque;

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

Appends an element to the back of the deque.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(1);
buf.push_back(3);
assert_eq!(3, *buf.back().unwrap());

Removes an element from anywhere in the deque and returns it, replacing it with the first element.

This does not preserve ordering, but is O(1).

Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples
use std::collections::VecDeque;

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

assert_eq!(buf.swap_remove_front(2), Some(3));
assert_eq!(buf, [2, 1]);

Removes an element from anywhere in the deque and returns it, replacing it with the last element.

This does not preserve ordering, but is O(1).

Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples
use std::collections::VecDeque;

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

assert_eq!(buf.swap_remove_back(0), Some(1));
assert_eq!(buf, [3, 2]);

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 mut vec_deque = VecDeque::new();
vec_deque.push_back('a');
vec_deque.push_back('b');
vec_deque.push_back('c');
assert_eq!(vec_deque, &['a', 'b', 'c']);

vec_deque.insert(1, 'd');
assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);

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 mut 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]);

Splits the deque into two at the given index.

Returns a newly allocated VecDeque. self contains elements [0, at), and the returned deque contains elements [at, len).

Note that the capacity of self does not change.

Element at index 0 is the front of the queue.

Panics

Panics if at > len.

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = [1, 2, 3].into();
let buf2 = buf.split_off(1);
assert_eq!(buf, [1]);
assert_eq!(buf2, [2, 3]);

Moves all the elements of other into self, leaving other empty.

Panics

Panics if the new number of elements in self overflows a usize.

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = [1, 2].into();
let mut buf2: VecDeque<_> = [3, 4].into();
buf.append(&mut buf2);
assert_eq!(buf, [1, 2, 3, 4]);
assert_eq!(buf2, []);

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain(|&x| x % 2 == 0);
assert_eq!(buf, [2, 4]);

Because the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..6);

let keep = [false, true, true, false, true];
let mut iter = keep.iter();
buf.retain(|_| *iter.next().unwrap());
assert_eq!(buf, [2, 3, 5]);

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain_mut(|x| if *x % 2 == 0 {
    *x += 1;
    true
} else {
    false
});
assert_eq!(buf, [3, 5]);

Modifies the deque in-place so that len() is equal to new_len, either by removing excess elements from the back or by appending elements generated by calling generator to the back.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize_with(5, Default::default);
assert_eq!(buf, [5, 10, 15, 0, 0]);

buf.resize_with(2, || unreachable!());
assert_eq!(buf, [5, 10]);

let mut state = 100;
buf.resize_with(5, || { state += 1; state });
assert_eq!(buf, [5, 10, 101, 102, 103]);

Rearranges the internal storage of this deque so it is one contiguous slice, which is then returned.

This method does not allocate and does not change the order of the inserted elements. As it returns a mutable slice, this can be used to sort a deque.

Once the internal storage is contiguous, the as_slices and as_mut_slices methods will return the entire contents of the deque in a single slice.

Examples

Sorting the content of a deque.

use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

// sorting the deque
buf.make_contiguous().sort();
assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));

// sorting it in reverse order
buf.make_contiguous().sort_by(|a, b| b.cmp(a));
assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));

Getting immutable access to the contiguous slice.

use std::collections::VecDeque;

let mut buf = VecDeque::new();

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

buf.make_contiguous();
if let (slice, &[]) = buf.as_slices() {
    // we can now be sure that `slice` contains all elements of the deque,
    // while still having immutable access to `buf`.
    assert_eq!(buf.len(), slice.len());
    assert_eq!(slice, &[3, 2, 1] as &[_]);
}

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 mut buf: VecDeque<_> = (0..10).collect();

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]);

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 mut buf: VecDeque<_> = (0..10).collect();

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]);

Binary searches this VecDeque for a given element. This behaves similarly to contains if this VecDeque is sorted.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search_by, binary_search_by_key, and partition_point.

Examples

Looks up a series of four elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search(&13),  Ok(9));
assert_eq!(deque.binary_search(&4),   Err(7));
assert_eq!(deque.binary_search(&100), Err(13));
let r = deque.binary_search(&1);
assert!(matches!(r, Ok(1..=4)));

If you want to insert an item to a sorted deque, while maintaining sort order, consider using partition_point:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
// The above is equivalent to `let idx = deque.binary_search(&num).unwrap_or_else(|x| x);`
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

Binary searches this VecDeque with a comparator function. This behaves similarly to contains if this VecDeque is sorted.

The comparator function should implement an order consistent with the sort order of the deque, returning an order code that indicates whether its argument is Less, Equal or Greater than the desired target.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search, binary_search_by_key, and partition_point.

Examples

Looks up a series of four elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search_by(|x| x.cmp(&13)),  Ok(9));
assert_eq!(deque.binary_search_by(|x| x.cmp(&4)),   Err(7));
assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
let r = deque.binary_search_by(|x| x.cmp(&1));
assert!(matches!(r, Ok(1..=4)));

Binary searches this VecDeque with a key extraction function. This behaves similarly to contains if this VecDeque is sorted.

Assumes that the deque is sorted by the key, for instance with make_contiguous().sort_by_key() using the same key extraction function.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search, binary_search_by, and partition_point.

Examples

Looks up a series of four elements in a slice of pairs sorted by their second elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [(0, 0), (2, 1), (4, 1), (5, 1),
         (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
         (1, 21), (2, 34), (4, 55)].into();

assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
let r = deque.binary_search_by_key(&1, |&(a, b)| b);
assert!(matches!(r, Ok(1..=4)));

Returns the index of the partition point according to the given predicate (the index of the first element of the second partition).

The deque is assumed to be partitioned according to the given predicate. This means that all elements for which the predicate returns true are at the start of the deque and all elements for which the predicate returns false are at the end. For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 (all odd numbers are at the start, all even at the end).

If the deque is not partitioned, the returned result is unspecified and meaningless, as this method performs a kind of binary search.

See also binary_search, binary_search_by, and binary_search_by_key.

Examples
use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
let i = deque.partition_point(|&x| x < 5);

assert_eq!(i, 4);
assert!(deque.iter().take(i).all(|&x| x < 5));
assert!(deque.iter().skip(i).all(|&x| !(x < 5)));

If you want to insert an item to a sorted deque, while maintaining sort order:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

Modifies the deque in-place so that len() is equal to new_len, either by removing excess elements from the back or by appending clones of value to the back.

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize(2, 0);
assert_eq!(buf, [5, 10]);

buf.resize(5, 20);
assert_eq!(buf, [5, 10, 20, 20, 20]);

Trait Implementations

Returns the number of bytes between the current position and the end of the buffer. Read more

Returns a slice starting at the current position and of length between 0 and Buf::remaining(). Note that this can return shorter slice (this allows non-continuous internal representation). Read more

Advance the internal cursor of the Buf Read more

Fills dst with potentially multiple slices starting at self’s current position. Read more

Returns true if there are any more bytes to consume Read more

Copies bytes from self into dst. Read more

Gets an unsigned 8 bit integer from self. Read more

Gets a signed 8 bit integer from self. Read more

Gets an unsigned 16 bit integer from self in big-endian byte order. Read more

Gets an unsigned 16 bit integer from self in little-endian byte order. Read more

Gets a signed 16 bit integer from self in big-endian byte order. Read more

Gets a signed 16 bit integer from self in little-endian byte order. Read more

Gets an unsigned 32 bit integer from self in the big-endian byte order. Read more

Gets an unsigned 32 bit integer from self in the little-endian byte order. Read more

Gets a signed 32 bit integer from self in big-endian byte order. Read more

Gets a signed 32 bit integer from self in little-endian byte order. Read more

Gets an unsigned 64 bit integer from self in big-endian byte order. Read more

Gets an unsigned 64 bit integer from self in little-endian byte order. Read more

Gets a signed 64 bit integer from self in big-endian byte order. Read more

Gets a signed 64 bit integer from self in little-endian byte order. Read more

Gets an unsigned 128 bit integer from self in big-endian byte order. Read more

Gets an unsigned 128 bit integer from self in little-endian byte order. Read more

Gets a signed 128 bit integer from self in big-endian byte order. Read more

Gets a signed 128 bit integer from self in little-endian byte order. Read more

Gets an unsigned n-byte integer from self in big-endian byte order. Read more

Gets an unsigned n-byte integer from self in little-endian byte order. Read more

Gets a signed n-byte integer from self in big-endian byte order. Read more

Gets a signed n-byte integer from self in little-endian byte order. Read more

Gets an IEEE754 single-precision (4 bytes) floating point number from self in big-endian byte order. Read more

Gets an IEEE754 single-precision (4 bytes) floating point number from self in little-endian byte order. Read more

Gets an IEEE754 double-precision (8 bytes) floating point number from self in big-endian byte order. Read more

Gets an IEEE754 double-precision (8 bytes) floating point number from self in little-endian byte order. Read more

Consumes len bytes inside self and returns new instance of Bytes with this data. Read more

Creates an adaptor which will read at most limit bytes from self. Read more

Creates an adaptor which will chain this buffer with another. Read more

Creates an adaptor which implements the Read trait for self. Read more

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Creates an empty deque.

Deserialize this value from the given Serde deserializer. Read more

Executes the destructor for this type. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Converts a [T; N] into a VecDeque<T>.

use std::collections::VecDeque;

let deq1 = VecDeque::from([1, 2, 3, 4]);
let deq2: VecDeque<_> = [1, 2, 3, 4].into();
assert_eq!(deq1, deq2);

Turn a Vec<T> into a VecDeque<T>.

This avoids reallocating where possible, but the conditions for that are strict, and subject to change, and so shouldn’t be relied upon unless the Vec<T> came from From<VecDeque<T>> and hasn’t been reallocated.

Turn a VecDeque<T> into a Vec<T>.

This never needs to re-allocate, but does need to do O(n) data movement if the circular buffer doesn’t happen to be at the beginning of the allocation.

Examples
use std::collections::VecDeque;

// This one is *O*(1).
let deque: VecDeque<_> = (1..5).collect();
let ptr = deque.as_slices().0.as_ptr();
let vec = Vec::from(deque);
assert_eq!(vec, [1, 2, 3, 4]);
assert_eq!(vec.as_ptr(), ptr);

// This one needs data rearranging.
let mut deque: VecDeque<_> = (1..5).collect();
deque.push_front(9);
deque.push_front(8);
let ptr = deque.as_slices().1.as_ptr();
let vec = Vec::from(deque);
assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
assert_eq!(vec.as_ptr(), ptr);

Creates a value from an iterator. Read more

Feeds this value into the given Hasher. Read more

Feeds a slice of this type into the given Hasher. Read more

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

Performs the mutable indexing (container[index]) operation. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

Consumes the deque into a front-to-back iterator yielding elements by value.

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

Restrict a value to a certain interval. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

Serialize this value into the given Serde serializer. Read more

The type of value produced by the sink when an error occurs.

Attempts to prepare the Sink to receive a value. Read more

Begin the process of sending a value to the sink. Each call to this function must be preceded by a successful call to poll_ready which returned Poll::Ready(Ok(())). Read more

Flush any remaining output from this sink. Read more

Flush any remaining output and close this sink, if necessary. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Compare self to key and return true if they are equal.

Returns the argument unchanged.

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more

Instruments this type with the current Span, returning an Instrumented wrapper. Read more

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Converts self into a collection.

Should always be Self

Composes a function in front of the sink. Read more

Composes a function in front of the sink. Read more

Transforms the error returned by the sink.

Map this sink’s error to a different error type using the Into trait. Read more

Adds a fixed-size buffer to the current sink. Read more

Close the sink.

Fanout items to multiple sinks. Read more

Flush the sink, processing all pending items. Read more

A future that completes after the given item has been fully processed into the sink, including flushing. Read more

A future that completes after the given item has been received by the sink. Read more

A future that completes after the given stream has been fully processed into the sink, including flushing. Read more

Wrap this sink in an Either sink, making it the left-hand variant of that Either. Read more

Wrap this stream in an Either stream, making it the right-hand variant of that Either. Read more

A convenience method for calling [Sink::poll_ready] on Unpin sink types. Read more

A convenience method for calling [Sink::start_send] on Unpin sink types. Read more

A convenience method for calling [Sink::poll_flush] on Unpin sink types. Read more

A convenience method for calling [Sink::poll_close] on Unpin sink types. Read more

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into)

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more