Rust Reference ยท Collections
Rust VecDeque<T> type
Reference for Rust VecDeque<T>: ring buffer layout, push_front, push_back, pop_front, pop_back, indexing, make_contiguous, rotation and use as a queue.
VecDeque<T> (pronounced "vec-deck") is a growable double-ended queue built on a ring buffer. It supports O(1) insertion and removal at both ends, and O(1) indexing, which makes it the right tool for queues, sliding windows and breadth-first search. A Vec<T> is fast at the back only; removing from its front costs O(n).
Because the elements wrap around the end of the buffer, a VecDeque is not guaranteed to be one contiguous block, so it cannot dereference to a slice. Use as_slices(), make_contiguous() or iterators when you need to look at all elements.
use std::collections::VecDeque; let mut q = VecDeque::new(); q.push_back(1); q.push_front(0);
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Syntax
pub struct VecDeque<T, A: Allocator = Global> { /* private */ } VecDeque::new() -> VecDeque<T> VecDeque::with_capacity(capacity: usize) -> VecDeque<T> VecDeque::from(array_or_vec) q.push_back(value) q.push_front(value) q.pop_back() -> Option<T> q.pop_front() -> Option<T> q.front() -> Option<&T> q.back() -> Option<&T> q[i] q.get(i) -> Option<&T>
| Name | Description |
|---|---|
capacity |
Number of elements to reserve space for. |
value |
The element to add; moved into the deque. |
i |
Logical index counted from the front (0 is the front element). |
Returns: the pop_*, front, back and get methods return Option, so an empty deque gives None.
Panics: q[i] panics when i >= len. insert(i, v) panics when i > len; remove(i) returns Option<T> instead of panicking.
Usage notes
- Choose it for queues.
push_backpluspop_frontis a FIFO queue;push_backpluspop_backis a stack. Both ends are O(1) amortized. - Indexing is O(1) but slightly slower than
Vecindexing because of the wrap-around arithmetic. - It is not a slice. Methods like
sort,binary_searchorwindowsneedmake_contiguous()(O(n), mutable) or the two halves fromas_slices().iter()always yields elements in logical order. - Conversions:
Vec<T>intoVecDeque<T>is O(1) (it reuses the buffer), andVecDeque<T>intoVec<T>is O(1) if the data is already contiguous, otherwise O(n).collect()andFrom<[T; N]>also work. - Middle insertion and removal are O(min(i, n - i)), because the deque shifts whichever side is shorter.
- Capacity is managed like a vector's; see
capacity and reserve. Do not rely on the exact numbers. - Other methods:
extend,append,drain,retain,truncate,swap,contains,iter_mut,range,split_off,resizeandrotate_left/rotate_right. - Thread safety: like other std collections it is not synchronized; wrap in a
Mutexor use channels to share it.
Related
Vec<T>,LinkedList<T>,BinaryHeap<T>,std::collections- Lessons: Other collections, Vectors