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

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

Errors

Returns an error if the capacity exceeds isize::MAX bytes, or if the allocator reports allocation failure.

Examples

# #![feature(try_with_capacity)]
# #[allow(unused)]
# fn example() -> Result<(), std::collections::TryReserveError> {
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::try_with_capacity(10)?;
# Ok(()) }

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

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);
buf.push_back(6);
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);
buf.push_back(6);
assert_eq!(buf[1], 4);
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 at least 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 speculatively 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 at least 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 if it returns Ok(()). 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)
}
# process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");

Tries to reserve 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. After calling try_reserve, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if capacity is already sufficient. This method preserves the contents even if an error occurs.

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)
}
# process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");

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 or equal to 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]);

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

If len is greater or equal to the deque's current length, this has no effect.

Examples

# #![feature(vec_deque_truncate_front)]
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_front(5);
buf.push_front(10);
buf.push_front(15);
assert_eq!(buf, [15, 10, 5]);
assert_eq!(buf.as_slices(), (&[15, 10, 5][..], &[][..]));
buf.truncate_front(1);
assert_eq!(buf.as_slices(), (&[5][..], &[][..]));

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. Otherwise, the exact split point depends on implementation details and is not guaranteed.

Examples

use std::collections::VecDeque;

let mut deque = VecDeque::new();

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

let expected = [0, 1, 2];
let (front, back) = deque.as_slices();
assert_eq!(&expected[..front.len()], front);
assert_eq!(&expected[front.len()..], back);

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

let expected = [9, 10, 0, 1, 2];
let (front, back) = deque.as_slices();
assert_eq!(&expected[..front.len()], front);
assert_eq!(&expected[front.len()..], back);

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. Otherwise, the exact split point depends on implementation details and is not guaranteed.

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

// Since the split point is not guaranteed, we may need to update
// either slice.
let mut update_nth = |index: usize, val: u32| {
    let (front, back) = deque.as_mut_slices();
    if index > front.len() - 1 {
        back[index - front.len()] = val;
    } else {
        front[index] = val;
    }
};

update_nth(0, 42);
update_nth(2, 24);

let v: Vec<_> = deque.into();
assert_eq!(v, [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 range has start_bound > end_bound, or, if the range is bounded on either end and past 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 range has start_bound > end_bound, or, if the range is bounded on either end and past 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 range has start_bound > end_bound, or, if the range is bounded on either end and past 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());

Creates a splicing iterator that replaces the specified range in the deque with the given replace_with iterator and yields the removed items. replace_with does not need to be the same length as range.

range is removed even if the Splice iterator is not consumed before it is dropped.

It is unspecified how many elements are removed from the deque if the Splice value is leaked.

The input iterator replace_with is only consumed when the Splice value is dropped.

This is optimal if:

• The tail (elements in the deque after range) is empty,
• or replace_with yields fewer or equal elements than range's length
• or the lower bound of its size_hint() is exact.

Otherwise, a temporary vector is allocated and the tail is moved twice.

Panics

Panics if the range has start_bound > end_bound, or, if the range is bounded on either end and past the length of the deque.

Examples

# #![feature(deque_extend_front)]
# use std::collections::VecDeque;

let mut v = VecDeque::from(vec![1, 2, 3, 4]);
let new = [7, 8, 9];
let u: Vec<_> = v.splice(1..3, new).collect();
assert_eq!(v, [1, 7, 8, 9, 4]);
assert_eq!(u, [2, 3]);

Using splice to insert new items into a vector efficiently at a specific position indicated by an empty range:

# #![feature(deque_extend_front)]
# use std::collections::VecDeque;

let mut v = VecDeque::from(vec![1, 5]);
let new = [2, 3, 4];
v.splice(1..1, new);
assert_eq!(v, [1, 2, 3, 4, 5]);

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

Removes and returns the first element from the deque if the predicate returns true, or None if the predicate returns false or the deque is empty (the predicate will not be called in that case).

Examples

use std::collections::VecDeque;

let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(deque.pop_front_if(pred), Some(0));
assert_eq!(deque, [1, 2, 3, 4]);
assert_eq!(deque.pop_front_if(pred), None);

Removes and returns the last element from the deque if the predicate returns true, or None if the predicate returns false or the deque is empty (the predicate will not be called in that case).

Examples

use std::collections::VecDeque;

let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(deque.pop_back_if(pred), Some(4));
assert_eq!(deque, [0, 1, 2, 3]);
assert_eq!(deque.pop_back_if(pred), None);

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

Prepends an element to the deque, returning a reference to it.

Examples

#![feature(push_mut)]
use std::collections::VecDeque;

let mut d = VecDeque::from([1, 2, 3]);
let x = d.push_front_mut(8);
*x -= 1;
assert_eq!(d.front(), Some(&7));

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

Appends an element to the back of the deque, returning a reference to it.

Examples

#![feature(push_mut)]
use std::collections::VecDeque;

let mut d = VecDeque::from([1, 2, 3]);
let x = d.push_back_mut(9);
*x += 1;
assert_eq!(d.back(), Some(&10));

Prepends all contents of the iterator to the front of the deque. The order of the contents is preserved.

To get behavior like [append][VecDeque::append] where elements are moved from the other collection to this one, use self.prepend(other.drain(..)).

Examples

#![feature(deque_extend_front)]
use std::collections::VecDeque;

let mut deque = VecDeque::from([4, 5, 6]);
deque.prepend([1, 2, 3]);
assert_eq!(deque, [1, 2, 3, 4, 5, 6]);

Move values between collections like [append][VecDeque::append] does but prepend to the front:

#![feature(deque_extend_front)]
use std::collections::VecDeque;

let mut deque1 = VecDeque::from([4, 5, 6]);
let mut deque2 = VecDeque::from([1, 2, 3]);
deque1.prepend(deque2.drain(..));
assert_eq!(deque1, [1, 2, 3, 4, 5, 6]);
assert!(deque2.is_empty());

Prepends all contents of the iterator to the front of the deque, as if [push_front][VecDeque::push_front] was called repeatedly with the values yielded by the iterator.

Examples

#![feature(deque_extend_front)]
use std::collections::VecDeque;

let mut deque = VecDeque::from([4, 5, 6]);
deque.extend_front([3, 2, 1]);
assert_eq!(deque, [1, 2, 3, 4, 5, 6]);

This behaves like [push_front][VecDeque::push_front] was called repeatedly:

use std::collections::VecDeque;

let mut deque = VecDeque::from([4, 5, 6]);
for v in [3, 2, 1] {
    deque.push_front(v);
}
assert_eq!(deque, [1, 2, 3, 4, 5, 6]);

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 strictly greater than the 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']);

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

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

Element at index 0 is the front of the queue.

Panics

Panics if index is strictly greater than the deque's length.

Examples

#![feature(push_mut)]
use std::collections::VecDeque;

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

let x = vec_deque.insert_mut(1, 5);
*x += 7;
assert_eq!(vec_deque, &[1, 12, 2, 3]);

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('a');
buf.push_back('b');
buf.push_back('c');
assert_eq!(buf, ['a', 'b', 'c']);

assert_eq!(buf.remove(1), Some('b'));
assert_eq!(buf, ['a', 'c']);

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<_> = ['a', 'b', 'c'].into();
let buf2 = buf.split_off(1);
assert_eq!(buf, ['a']);
assert_eq!(buf2, ['b', 'c']);

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(&mut 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 n places to the left.

Equivalently,

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

Panics

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

Complexity

Takes *O*(min(n, len() - n)) 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 n places to the right.

Equivalently,

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

Panics

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

Complexity

Takes *O*(min(n, len() - n)) 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. If the VecDeque is not sorted, the returned result is unspecified and meaningless.

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);
// If `num` is unique, `s.partition_point(|&x| x < num)` (with `<`) is equivalent to
// `s.binary_search(&num).unwrap_or_else(|x| x)`, but using `<=` may allow `insert`
// to shift less elements.
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.

The comparator function should return an order code that indicates whether its argument is Less, Equal or Greater the desired target. If the VecDeque is not sorted or if the comparator function does not implement an order consistent with the sort order of the underlying VecDeque, the returned result is unspecified and meaningless.

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.

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 deque is not sorted by the key, the returned result is unspecified and meaningless.

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

Creates an iterator which uses a closure to determine if an element in the range should be removed.

If the closure returns true, the element is removed from the deque and yielded. If the closure returns false, or panics, the element remains in the deque and will not be yielded.

Only elements that fall in the provided range are considered for extraction, but any elements after the range will still have to be moved if any element has been extracted.

If the returned ExtractIf is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use extract_if().for_each(drop) if you do not need the returned iterator, or retain_mut with a negated predicate if you also do not need to restrict the range.

Using this method is equivalent to the following code:

#![feature(vec_deque_extract_if)]
# use std::collections::VecDeque;
# let some_predicate = |x: &mut i32| { *x % 2 == 1 };
# let mut deq: VecDeque<_> = (0..10).collect();
# let mut deq2 = deq.clone();
# let range = 1..5;
let mut i = range.start;
let end_items = deq.len() - range.end;
# let mut extracted = vec![];

while i < deq.len() - end_items {
    if some_predicate(&mut deq[i]) {
        let val = deq.remove(i).unwrap();
        // your code here
#         extracted.push(val);
    } else {
        i += 1;
    }
}

# let extracted2: Vec<_> = deq2.extract_if(range, some_predicate).collect();
# assert_eq!(deq, deq2);
# assert_eq!(extracted, extracted2);

But extract_if is easier to use. extract_if is also more efficient, because it can backshift the elements of the array in bulk.

The iterator also lets you mutate the value of each element in the closure, regardless of whether you choose to keep or remove it.

Panics

If range is out of bounds.

Examples

Splitting a deque into even and odd values, reusing the original deque:

#![feature(vec_deque_extract_if)]
use std::collections::VecDeque;

let mut numbers = VecDeque::from([1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);

let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<VecDeque<_>>();
let odds = numbers;

assert_eq!(evens, VecDeque::from([2, 4, 6, 8, 14]));
assert_eq!(odds, VecDeque::from([1, 3, 5, 9, 11, 13, 15]));

Using the range argument to only process a part of the deque:

#![feature(vec_deque_extract_if)]
use std::collections::VecDeque;

let mut items = VecDeque::from([0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2]);
let ones = items.extract_if(7.., |x| *x == 1).collect::<VecDeque<_>>();
assert_eq!(items, VecDeque::from([0, 0, 0, 0, 0, 0, 0, 2, 2, 2]));
assert_eq!(ones.len(), 3);

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

Clones the elements at the range src and appends them to the end.

Panics

Panics if the starting index is greater than the end index or if either index is greater than the length of the vector.

Examples

#![feature(deque_extend_front)]
use std::collections::VecDeque;

let mut characters = VecDeque::from(['a', 'b', 'c', 'd', 'e']);
characters.extend_from_within(2..);
assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);

let mut numbers = VecDeque::from([0, 1, 2, 3, 4]);
numbers.extend_from_within(..2);
assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);

let mut strings = VecDeque::from([String::from("hello"), String::from("world"), String::from("!")]);
strings.extend_from_within(1..=2);
assert_eq!(strings, ["hello", "world", "!", "world", "!"]);

Clones the elements at the range src and prepends them to the front.

Panics

Panics if the starting index is greater than the end index or if either index is greater than the length of the vector.

Examples

#![feature(deque_extend_front)]
use std::collections::VecDeque;

let mut characters = VecDeque::from(['a', 'b', 'c', 'd', 'e']);
characters.prepend_from_within(2..);
assert_eq!(characters, ['c', 'd', 'e', 'a', 'b', 'c', 'd', 'e']);

let mut numbers = VecDeque::from([0, 1, 2, 3, 4]);
numbers.prepend_from_within(..2);
assert_eq!(numbers, [0, 1, 0, 1, 2, 3, 4]);

let mut strings = VecDeque::from([String::from("hello"), String::from("world"), String::from("!")]);
strings.prepend_from_within(1..=2);
assert_eq!(strings, ["world", "!", "hello", "world", "!"]);