Struct std::collections::vec_deque::VecDeque1.0.0[][src]

pub struct VecDeque<T> { /* fields omitted */ }
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.

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

impl<T> VecDeque<T>[src]

pub fn new() -> VecDeque<T>[src]

Creates an empty VecDeque.

Examples

use std::collections::VecDeque;

let vector: VecDeque<u32> = VecDeque::new();
Run

pub fn with_capacity(capacity: usize) -> VecDeque<T>[src]

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

Examples

use std::collections::VecDeque;

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

pub fn get(&self, index: usize) -> Option<&T>[src]

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

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>[src]

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

pub fn swap(&mut self, i: usize, j: usize)[src]

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

pub fn capacity(&self) -> usize[src]

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

Examples

use std::collections::VecDeque;

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

pub fn reserve_exact(&mut self, additional: usize)[src]

Reserves the minimum capacity for exactly additional more elements to be inserted in the given VecDeque. 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> = vec![1].into_iter().collect();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);
Run

pub fn reserve(&mut self, additional: usize)[src]

Reserves capacity for at least additional more elements to be inserted in the given VecDeque. 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> = vec![1].into_iter().collect();
buf.reserve(10);
assert!(buf.capacity() >= 11);
Run

pub fn try_reserve_exact(
    &mut self,
    additional: usize
) -> Result<(), TryReserveError>
[src]

🔬 This is a nightly-only experimental API. (try_reserve #48043)

new API

Tries to reserve the minimum capacity for exactly additional more elements to be inserted in the given VecDeque<T>. 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 reserve if future insertions are expected.

Errors

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

Examples

#![feature(try_reserve)]
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)
}
Run

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>[src]

🔬 This is a nightly-only experimental API. (try_reserve #48043)

new API

Tries to reserve capacity for at least additional more elements to be inserted in the given VecDeque<T>. 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

#![feature(try_reserve)]
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)
}
Run

pub fn shrink_to_fit(&mut self)1.5.0[src]

Shrinks the capacity of the VecDeque as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the VecDeque 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);
Run

pub fn shrink_to(&mut self, min_capacity: usize)[src]

🔬 This is a nightly-only experimental API. (shrink_to #56431)

new API

Shrinks the capacity of the VecDeque 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

#![feature(shrink_to)]
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);
Run

pub fn truncate(&mut self, len: usize)1.16.0[src]

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

If len is greater than the VecDeque’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]);
Run

pub fn iter(&self) -> Iter<'_, T>

Notable traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;
[src]

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

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Notable traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;
[src]

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

pub fn as_slices(&self) -> (&[T], &[T])1.5.0[src]

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

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

Examples

use std::collections::VecDeque;

let mut vector = VecDeque::new();

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

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

vector.push_front(10);
vector.push_front(9);

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

pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])1.5.0[src]

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

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

Examples

use std::collections::VecDeque;

let mut vector = VecDeque::new();

vector.push_back(0);
vector.push_back(1);

vector.push_front(10);
vector.push_front(9);

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

pub fn len(&self) -> usize[src]

Returns the number of elements in the VecDeque.

Examples

use std::collections::VecDeque;

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

pub fn is_empty(&self) -> bool[src]

Returns true if the VecDeque is empty.

Examples

use std::collections::VecDeque;

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

pub fn range<R>(&self, range: R) -> Iter<'_, T>

Notable traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;
where
    R: RangeBounds<usize>, 
1.51.0[src]

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

Panics

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

Examples

use std::collections::VecDeque;

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

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

pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>

Notable traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;
where
    R: RangeBounds<usize>, 
1.51.0[src]

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

Panics

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

Examples

use std::collections::VecDeque;

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

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

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>

Notable traits for Drain<'_, T>

impl<'_, T> Iterator for Drain<'_, T> type Item = T;
where
    R: RangeBounds<usize>, 
1.6.0[src]

Creates a draining iterator that removes the specified range in the VecDeque and yields the removed items.

Note 1: The element range is removed even if the iterator is not consumed until the end.

Note 2: It is unspecified how many elements are removed from the deque, if the Drain value is not dropped, but the borrow it holds expires (e.g., due to mem::forget).

Panics

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

Examples

use std::collections::VecDeque;

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

// A full range clears all contents
v.drain(..);
assert!(v.is_empty());
Run

pub fn clear(&mut self)[src]

Clears the VecDeque, removing all values.

Examples

use std::collections::VecDeque;

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

pub fn contains(&self, x: &T) -> bool where
    T: PartialEq<T>, 
1.12.0[src]

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

Examples

use std::collections::VecDeque;

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

vector.push_back(0);
vector.push_back(1);

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

pub fn front(&self) -> Option<&T>[src]

Provides a reference to the front element, or None if the VecDeque 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));
Run

pub fn front_mut(&mut self) -> Option<&mut T>[src]

Provides a mutable reference to the front element, or None if the VecDeque 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));
Run

pub fn back(&self) -> Option<&T>[src]

Provides a reference to the back element, or None if the VecDeque 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));
Run

pub fn back_mut(&mut self) -> Option<&mut T>[src]

Provides a mutable reference to the back element, or None if the VecDeque 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));
Run

pub fn pop_front(&mut self) -> Option<T>[src]

Removes the first element and returns it, or None if the VecDeque 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);
Run

pub fn pop_back(&mut self) -> Option<T>[src]

Removes the last element from the VecDeque 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));
Run

pub fn push_front(&mut self, value: T)[src]

Prepends an element to the VecDeque.

Examples

use std::collections::VecDeque;

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

pub fn push_back(&mut self, value: T)[src]

Appends an element to the back of the VecDeque.

Examples

use std::collections::VecDeque;

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

pub fn swap_remove_front(&mut self, index: usize) -> Option<T>1.5.0[src]

Removes an element from anywhere in the VecDeque 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]);
Run

pub fn swap_remove_back(&mut self, index: usize) -> Option<T>1.5.0[src]

Removes an element from anywhere in the VecDeque 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]);
Run

pub fn insert(&mut self, index: usize, value: T)1.5.0[src]

Inserts an element at index within the VecDeque, 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 VecDeque’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']);
Run

pub fn remove(&mut self, index: usize) -> Option<T>[src]

Removes and returns the element at index from the VecDeque. 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]);
Run

#[must_use = "use `.truncate()` if you don't need the other half"]
pub fn split_off(&mut self, at: usize) -> VecDeque<T>
1.4.0[src]

Splits the VecDeque into two at the given index.

Returns a newly allocated VecDeque. self contains elements [0, at), and the returned VecDeque 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<_> = vec![1, 2, 3].into_iter().collect();
let buf2 = buf.split_off(1);
assert_eq!(buf, [1]);
assert_eq!(buf2, [2, 3]);
Run

pub fn append(&mut self, other: &mut VecDeque<T>)1.4.0[src]

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<_> = vec![1, 2].into_iter().collect();
let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect();
buf.append(&mut buf2);
assert_eq!(buf, [1, 2, 3, 4]);
assert_eq!(buf2, []);
Run

pub fn retain<F>(&mut self, f: F) where
    F: FnMut(&T) -> bool
1.4.0[src]

Retains only the elements specified by the predicate.

In other words, remove all elements e such that 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]);
Run

The exact order may be useful for tracking external state, like an index.

use std::collections::VecDeque;

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

let keep = [false, true, true, false, true];
let mut i = 0;
buf.retain(|_| (keep[i], i += 1).0);
assert_eq!(buf, [2, 3, 5]);
Run

pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T)1.33.0[src]

Modifies the VecDeque 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]);
Run

pub fn make_contiguous(&mut self) -> &mut [T]

Notable traits for &[u8]

impl Read for &[u8]impl Write for &mut [u8]
1.48.0[src]

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 VecDeque 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 &[_]));
Run

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 &[_]);
}
Run

pub fn rotate_left(&mut self, mid: usize)1.36.0[src]

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

pub fn rotate_right(&mut self, k: usize)1.36.0[src]

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]);
Run
🔬 This is a nightly-only experimental API. (vecdeque_binary_search #78021)

Binary searches this sorted VecDeque for a given element.

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].

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

let deque: VecDeque<_> = vec![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)));
Run

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

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

let mut deque: VecDeque<_> = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
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]);
Run

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize> where
    F: FnMut(&'a T) -> Ordering
[src]

🔬 This is a nightly-only experimental API. (vecdeque_binary_search #78021)

Binary searches this sorted VecDeque with a comparator function.

The comparator function should implement an order consistent with the sort order of the underlying VecDeque, 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].

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

let deque: VecDeque<_> = vec![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)));
Run

pub fn binary_search_by_key<'a, B, F>(
    &'a self,
    b: &B,
    f: F
) -> Result<usize, usize> where
    F: FnMut(&'a T) -> B,
    B: Ord
[src]

🔬 This is a nightly-only experimental API. (vecdeque_binary_search #78021)

Binary searches this sorted VecDeque with a key extraction function.

Assumes that the VecDeque 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].

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

let deque: VecDeque<_> = vec![(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)));
Run

pub fn partition_point<P>(&self, pred: P) -> usize where
    P: FnMut(&T) -> bool
[src]

🔬 This is a nightly-only experimental API. (vecdeque_binary_search #78021)

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 this 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

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

let deque: VecDeque<_> = vec![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)));
Run

impl<T> VecDeque<T> where
    T: Clone
[src]

pub fn resize(&mut self, new_len: usize, value: T)1.16.0[src]

Modifies the VecDeque 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]);
Run

Trait Implementations

impl<T> Clone for VecDeque<T> where
    T: Clone
[src]

pub fn clone(&self) -> VecDeque<T>[src]

Returns a copy of the value. Read more

pub fn clone_from(&mut self, other: &VecDeque<T>)[src]

Performs copy-assignment from source. Read more

impl<T> Debug for VecDeque<T> where
    T: Debug
[src]

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>[src]

Formats the value using the given formatter. Read more

impl<T> Default for VecDeque<T>[src]

pub fn default() -> VecDeque<T>[src]

Creates an empty VecDeque<T>.

impl<T> Drop for VecDeque<T>[src]

pub fn drop(&mut self)[src]

Executes the destructor for this type. Read more

impl<'a, T> Extend<&'a T> for VecDeque<T> where
    T: 'a + Copy
1.2.0[src]

pub fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = &'a T>, 
[src]

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

pub fn extend_one(&mut self, &T)[src]

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

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)[src]

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

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

impl<A> Extend<A> for VecDeque<A>[src]

pub fn extend<T>(&mut self, iter: T) where
    T: IntoIterator<Item = A>, 
[src]

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

pub fn extend_one(&mut self, elem: A)[src]

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

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)[src]

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

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

impl<T> From<Vec<T, Global>> for VecDeque<T>1.10.0[src]

pub fn from(other: Vec<T, Global>) -> VecDeque<T>[src]

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.

impl<T> From<VecDeque<T>> for Vec<T, Global>1.10.0[src]

pub fn from(other: VecDeque<T>) -> Vec<T, Global>

Notable traits for Vec<u8, A>

impl<A: Allocator> Write for Vec<u8, A>
[src]

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

impl<A> FromIterator<A> for VecDeque<A>[src]

pub fn from_iter<T>(iter: T) -> VecDeque<A> where
    T: IntoIterator<Item = A>, 
[src]

Creates a value from an iterator. Read more

impl<A> Hash for VecDeque<A> where
    A: Hash
[src]

pub fn hash<H>(&self, state: &mut H) where
    H: Hasher
[src]

Feeds this value into the given Hasher. Read more

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher
1.3.0[src]

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

impl<A> Index<usize> for VecDeque<A>[src]

type Output = A

The returned type after indexing.

pub fn index(&self, index: usize) -> &A[src]

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

impl<A> IndexMut<usize> for VecDeque<A>[src]

pub fn index_mut(&mut self, index: usize) -> &mut A[src]

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

impl<T> IntoIterator for VecDeque<T>[src]

pub fn into_iter(self) -> IntoIter<T>

Notable traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = T;
[src]

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

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<'a, T> IntoIterator for &'a mut VecDeque<T>[src]

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> IterMut<'a, T>

Notable traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;
[src]

Creates an iterator from a value. Read more

impl<'a, T> IntoIterator for &'a VecDeque<T>[src]

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> Iter<'a, T>

Notable traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;
[src]

Creates an iterator from a value. Read more

impl<A> Ord for VecDeque<A> where
    A: Ord
[src]

pub fn cmp(&self, other: &VecDeque<A>) -> Ordering[src]

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

#[must_use]
fn max(self, other: Self) -> Self
1.21.0[src]

Compares and returns the maximum of two values. Read more

#[must_use]
fn min(self, other: Self) -> Self
1.21.0[src]

Compares and returns the minimum of two values. Read more

#[must_use]
fn clamp(self, min: Self, max: Self) -> Self
1.50.0[src]

Restrict a value to a certain interval. Read more

impl<'_, A, B, const N: usize> PartialEq<&'_ [B; N]> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &&[B; N]) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<'_, A, B> PartialEq<&'_ [B]> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &&[B]) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<'_, A, B, const N: usize> PartialEq<&'_ mut [B; N]> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &&mut [B; N]) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<'_, A, B> PartialEq<&'_ mut [B]> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &&mut [B]) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<A, B, const N: usize> PartialEq<[B; N]> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &[B; N]) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<A, B> PartialEq<Vec<B, Global>> for VecDeque<A> where
    A: PartialEq<B>, 
1.17.0[src]

pub fn eq(&self, other: &Vec<B, Global>) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<A> PartialEq<VecDeque<A>> for VecDeque<A> where
    A: PartialEq<A>, 
[src]

pub fn eq(&self, other: &VecDeque<A>) -> bool[src]

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

#[must_use]
fn ne(&self, other: &Rhs) -> bool
[src]

This method tests for !=.

impl<A> PartialOrd<VecDeque<A>> for VecDeque<A> where
    A: PartialOrd<A>, 
[src]

pub fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering>[src]

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

#[must_use]
fn lt(&self, other: &Rhs) -> bool
[src]

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

#[must_use]
fn le(&self, other: &Rhs) -> bool
[src]

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

#[must_use]
fn gt(&self, other: &Rhs) -> bool
[src]

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

#[must_use]
fn ge(&self, other: &Rhs) -> bool
[src]

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

impl<A> Eq for VecDeque<A> where
    A: Eq
[src]

Auto Trait Implementations

impl<T> RefUnwindSafe for VecDeque<T> where
    T: RefUnwindSafe

impl<T> Send for VecDeque<T> where
    T: Send

impl<T> Sync for VecDeque<T> where
    T: Sync

impl<T> Unpin for VecDeque<T> where
    T: Unpin

impl<T> UnwindSafe for VecDeque<T> where
    T: UnwindSafe

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

pub fn type_id(&self) -> TypeId[src]

Gets the TypeId of self. Read more

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

pub fn borrow(&self) -> &T[src]

Immutably borrows from an owned value. Read more

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

pub fn borrow_mut(&mut self) -> &mut T[src]

Mutably borrows from an owned value. Read more

impl<T> From<T> for T[src]

pub fn from(t: T) -> T[src]

Performs the conversion.

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

pub fn into(self) -> U[src]

Performs the conversion.

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

pub fn to_owned(&self) -> T[src]

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

pub fn clone_into(&self, target: &mut T)[src]

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

recently added

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

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>[src]

Performs the conversion.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>[src]

Performs the conversion.