Daily bit(e) of C++ | std::deque
Daily bit(e) of C++ #208, The non-contiguous random-access queue container: std::deque.
The std::deque is a non-contiguous container that models a double-ended queue while still providing random access, albeit at the cost of one extra indirection.
Elements can be added and removed from each end of the queue with O(1) time complexity without invalidating existing iterators (except for the erased elements).
