vecdeque.txt (1483B)
1 =============================================================================== 2 VecDeque 3 =============================================================================== 4 5 VecDeque stands for Vector Double-Ended Queue. 6 7 It's a Rust standard library collection (std::collections::VecDeque<T>) that 8 lets you efficiently push and pop elements from both the front and the back — 9 unlike a regular Vec, which is only efficient at the back. 10 11 A ring buffer (aka circular buffer) is the underlying data structure that makes 12 this possible. It's a fixed-size (or growable) contiguous block of memory that's 13 treated as if it wraps around — the end connects back to the beginning, like a 14 clock face. 15 16 Memory layout (capacity 8): [ _ _ C D E _ _ _ ] 17 ↑ ↑ 18 head tail 19 20 push_front(B) → [ _ B C D E _ _ _ ] 21 push_back(F) → [ _ B C D E F _ _ ] 22 23 24 If you keep pushing to the front and the head index would go negative, it just wraps to the last slot in the buffer instead: 25 26 [ _ B C D E F _ _ ] 27 push_front(A) many times, eventually head wraps around: 28 [ F _ _ _ B C D E ] ← wrapped: F is logically "before" B now 29 ↑ tail ↑ head 30 31 32 The buffer only needs to resize (reallocate + reflow into a bigger contiguous 33 chunk) when it's actually full, same amortized-growth idea as Vec. 34 35 You get O(1) operations at both ends, which is exactly what you want for things 36 like sliding windows, work queues, or BFS frontiers.