Struct collections::vec_deque::VecDeque
[−]
[src]
pub struct VecDeque<T> {
tail: usize,
head: usize,
buf: RawVec<T>,
}VecDeque is a growable ring buffer, which can be used as a double-ended
queue efficiently.
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.
Fields
tail | |
head | |
buf |
Methods
impl<T> VecDeque<T>
fn ptr(&self) -> *mut T
Marginally more convenient
fn cap(&self) -> usize
Marginally more convenient
unsafe fn buffer_as_slice(&self) -> &[T]
Turn ptr into a slice
unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T]
Turn ptr into a mut slice
unsafe fn buffer_read(&mut self, off: usize) -> T
Moves an element out of the buffer
unsafe fn buffer_write(&mut self, off: usize, value: T)
Writes an element into the buffer, moving it.
fn is_full(&self) -> bool
Returns true if and only if the buffer is at capacity
fn wrap_index(&self, idx: usize) -> usize
Returns the index in the underlying buffer for a given logical element index.
fn wrap_add(&self, idx: usize, addend: usize) -> usize
Returns the index in the underlying buffer for a given logical element index + addend.
fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize
Returns the index in the underlying buffer for a given logical element index - subtrahend.
unsafe fn copy(&self, dst: usize, src: usize, len: usize)
Copies a contiguous block of memory len long from src to dst
unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize)
Copies a contiguous block of memory len long from src to dst
unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize)
Copies a potentially wrapping block of memory len long from src to dest. (abs(dst - src) + len) must be no larger than cap() (There must be at most one continuous overlapping region between src and dest).
unsafe fn handle_cap_increase(&mut self, old_cap: usize)
Frobs the head and tail sections around to handle the fact that we just reallocated. Unsafe because it trusts old_cap.
impl<T> VecDeque<T>
fn new() -> VecDeque<T>
Creates an empty VecDeque.
fn with_capacity(n: usize) -> VecDeque<T>
Creates an empty VecDeque with space for at least n elements.
fn get(&self, index: usize) -> Option<&T>
Retrieves an element in the VecDeque by index.
Examples
extern crate collections; fn main() { 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)); }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));
fn get_mut(&mut self, index: usize) -> Option<&mut T>
Retrieves an element in the VecDeque mutably by index.
Examples
extern crate collections; fn main() { 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); }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);
fn swap(&mut self, i: usize, j: usize)
Swaps elements at indices i and j.
i and j may be equal.
Fails if there is no element with either index.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(3); buf.push_back(4); buf.push_back(5); buf.swap(0, 2); assert_eq!(buf[0], 5); assert_eq!(buf[2], 3); }use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(3); buf.push_back(4); buf.push_back(5); buf.swap(0, 2); assert_eq!(buf[0], 5); assert_eq!(buf[2], 3);
fn capacity(&self) -> usize
Returns the number of elements the VecDeque can hold without
reallocating.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let buf: VecDeque<i32> = VecDeque::with_capacity(10); assert!(buf.capacity() >= 10); }use std::collections::VecDeque; let buf: VecDeque<i32> = VecDeque::with_capacity(10); assert!(buf.capacity() >= 10);
fn reserve_exact(&mut self, additional: usize)
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
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); buf.reserve_exact(10); assert!(buf.capacity() >= 11); }use std::collections::VecDeque; let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); buf.reserve_exact(10); assert!(buf.capacity() >= 11);
fn reserve(&mut self, additional: usize)
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
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); buf.reserve(10); assert!(buf.capacity() >= 11); }use std::collections::VecDeque; let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); buf.reserve(10); assert!(buf.capacity() >= 11);
fn shrink_to_fit(&mut self)
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
extern crate collections; fn main() { 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); }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);
fn truncate(&mut self, len: usize)
Shortens a VecDeque, dropping excess elements from the back.
If len is greater than the VecDeque's current length, this has no
effect.
Examples
#![feature(deque_extras)] extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(5); buf.push_back(10); buf.push_back(15); buf.truncate(1); assert_eq!(buf.len(), 1); assert_eq!(Some(&5), buf.get(0)); }#![feature(deque_extras)] use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(5); buf.push_back(10); buf.push_back(15); buf.truncate(1); assert_eq!(buf.len(), 1); assert_eq!(Some(&5), buf.get(0));
fn iter(&self) -> Iter<T>
Returns a front-to-back iterator.
Examples
extern crate collections; fn main() { 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); }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);
fn iter_mut(&mut self) -> IterMut<T>
Returns a front-to-back iterator that returns mutable references.
Examples
extern crate collections; fn main() { 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); }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);
fn as_slices(&self) -> (&[T], &[T])
Returns a pair of slices which contain, in order, the contents of the
VecDeque.
fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])
Returns a pair of slices which contain, in order, the contents of the
VecDeque.
fn len(&self) -> usize
Returns the number of elements in the VecDeque.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut v = VecDeque::new(); assert_eq!(v.len(), 0); v.push_back(1); assert_eq!(v.len(), 1); }use std::collections::VecDeque; let mut v = VecDeque::new(); assert_eq!(v.len(), 0); v.push_back(1); assert_eq!(v.len(), 1);
fn is_empty(&self) -> bool
Returns true if the buffer contains no elements
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut v = VecDeque::new(); assert!(v.is_empty()); v.push_front(1); assert!(!v.is_empty()); }use std::collections::VecDeque; let mut v = VecDeque::new(); assert!(v.is_empty()); v.push_front(1); assert!(!v.is_empty());
fn drain<R>(&mut self, range: R) -> Drain<T> where R: RangeArgument<usize>
Create 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
(eg. 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
extern crate collections; fn main() { use std::collections::VecDeque; let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); assert_eq!(vec![3].into_iter().collect::<VecDeque<_>>(), v.drain(2..).collect()); assert_eq!(vec![1, 2].into_iter().collect::<VecDeque<_>>(), v); // A full range clears all contents v.drain(..); assert!(v.is_empty()); }use std::collections::VecDeque; let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); assert_eq!(vec![3].into_iter().collect::<VecDeque<_>>(), v.drain(2..).collect()); assert_eq!(vec![1, 2].into_iter().collect::<VecDeque<_>>(), v); // A full range clears all contents v.drain(..); assert!(v.is_empty());
fn clear(&mut self)
Clears the buffer, removing all values.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut v = VecDeque::new(); v.push_back(1); v.clear(); assert!(v.is_empty()); }use std::collections::VecDeque; let mut v = VecDeque::new(); v.push_back(1); v.clear(); assert!(v.is_empty());
fn front(&self) -> Option<&T>
Provides a reference to the front element, or None if the sequence is
empty.
Examples
extern crate collections; fn main() { 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)); }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));
fn front_mut(&mut self) -> Option<&mut T>
Provides a mutable reference to the front element, or None if the
sequence is empty.
Examples
extern crate collections; fn main() { 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)); }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));
fn back(&self) -> Option<&T>
Provides a reference to the back element, or None if the sequence is
empty.
Examples
extern crate collections; fn main() { 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)); }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));
fn back_mut(&mut self) -> Option<&mut T>
Provides a mutable reference to the back element, or None if the
sequence is empty.
Examples
extern crate collections; fn main() { 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)); }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));
fn pop_front(&mut self) -> Option<T>
Removes the first element and returns it, or None if the sequence is
empty.
Examples
extern crate collections; fn main() { 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); }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);
fn push_front(&mut self, value: T)
Inserts an element first in the sequence.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut d = VecDeque::new(); d.push_front(1); d.push_front(2); assert_eq!(d.front(), Some(&2)); }use std::collections::VecDeque; let mut d = VecDeque::new(); d.push_front(1); d.push_front(2); assert_eq!(d.front(), Some(&2));
fn push_back(&mut self, value: T)
Appends an element to the back of a buffer
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(1); buf.push_back(3); assert_eq!(3, *buf.back().unwrap()); }use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(1); buf.push_back(3); assert_eq!(3, *buf.back().unwrap());
fn pop_back(&mut self) -> Option<T>
Removes the last element from a buffer and returns it, or None if
it is empty.
Examples
extern crate collections; fn main() { 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)); }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));
fn is_contiguous(&self) -> bool
fn swap_remove_back(&mut self, index: usize) -> Option<T>
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.
Examples
extern crate collections; fn main() { 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.swap_remove_back(0), Some(1)); assert_eq!(buf.len(), 2); assert_eq!(buf[0], 3); assert_eq!(buf[1], 2); }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.swap_remove_back(0), Some(1)); assert_eq!(buf.len(), 2); assert_eq!(buf[0], 3); assert_eq!(buf[1], 2);
fn swap_remove_front(&mut self, index: usize) -> Option<T>
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.
Examples
extern crate collections; fn main() { 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.swap_remove_front(2), Some(3)); assert_eq!(buf.len(), 2); assert_eq!(buf[0], 2); assert_eq!(buf[1], 1); }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.swap_remove_front(2), Some(3)); assert_eq!(buf.len(), 2); assert_eq!(buf[0], 2); assert_eq!(buf[1], 1);
fn insert(&mut self, index: usize, value: T)
Inserts an element at index within the VecDeque. Whichever
end is closer to the insertion point will be moved to make room,
and all the affected elements will be moved to new positions.
Panics
Panics if index is greater than VecDeque's length
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(10); buf.push_back(12); buf.insert(1, 11); assert_eq!(Some(&11), buf.get(1)); }use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(10); buf.push_back(12); buf.insert(1, 11); assert_eq!(Some(&11), buf.get(1));
fn remove(&mut self, index: usize) -> Option<T>
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.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(1); buf.push_back(2); buf.push_back(3); assert_eq!(buf.remove(1), Some(2)); assert_eq!(buf.get(1), Some(&3)); }use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(1); buf.push_back(2); buf.push_back(3); assert_eq!(buf.remove(1), Some(2)); assert_eq!(buf.get(1), Some(&3));
fn split_off(&mut self, at: usize) -> Self
Splits the collection into two at the given index.
Returns a newly allocated Self. self contains elements [0, at),
and the returned Self contains elements [at, len).
Note that the capacity of self does not change.
Panics
Panics if at > len
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect(); let buf2 = buf.split_off(1); // buf = [1], buf2 = [2, 3] assert_eq!(buf.len(), 1); assert_eq!(buf2.len(), 2); }use std::collections::VecDeque; let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect(); let buf2 = buf.split_off(1); // buf = [1], buf2 = [2, 3] assert_eq!(buf.len(), 1); assert_eq!(buf2.len(), 2);
fn append(&mut self, other: &mut Self)
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
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); buf.append(&mut buf2); assert_eq!(buf.len(), 6); assert_eq!(buf2.len(), 0); }use std::collections::VecDeque; let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); buf.append(&mut buf2); assert_eq!(buf.len(), 6); assert_eq!(buf2.len(), 0);
fn retain<F>(&mut self, f: F) where F: FnMut(&T) -> bool
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 and preserves the order of the retained
elements.
Examples
extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.extend(1..5); buf.retain(|&x| x%2 == 0); let v: Vec<_> = buf.into_iter().collect(); assert_eq!(&v[..], &[2, 4]); }use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.extend(1..5); buf.retain(|&x| x%2 == 0); let v: Vec<_> = buf.into_iter().collect(); assert_eq!(&v[..], &[2, 4]);
impl<T: Clone> VecDeque<T>
fn resize(&mut self, new_len: usize, value: T)
Modifies the VecDeque in-place so that len() is equal to new_len,
either by removing excess elements or by appending copies of a value to the back.
Examples
#![feature(deque_extras)] extern crate collections; fn main() { use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(5); buf.push_back(10); buf.push_back(15); buf.resize(2, 0); buf.resize(6, 20); for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) { assert_eq!(a, b); } }#![feature(deque_extras)] use std::collections::VecDeque; let mut buf = VecDeque::new(); buf.push_back(5); buf.push_back(10); buf.push_back(15); buf.resize(2, 0); buf.resize(6, 20); for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) { assert_eq!(a, b); }