2.1. Vector and Deque

Vectors are the go-to choice when you need a sequence of elements whose size might change during your program’s execution. Here’s what makes them special:

  • Contiguous Storage: A vector stores its elements in a single, continuous block of memory. This provides lightning-fast random access to elements using their index. Think of it like a neatly organized bookshelf where you can instantly locate any book by its position.

  • Growth and Shrinkage: Vectors automatically expand or shrink as you add (push_back) or remove (pop_back) elements. This dynamic nature eliminates the need to manually pre-allocate or resize arrays.

  • Efficiency at the End: Adding or removing elements from the end of a vector is extremely fast, usually taking constant time \(O(1)\).

Many data structure and algorithms can be implemented with vector. The related algorithms include sorting, binary search, two pointers. There are non-sequential data structures flattened as vectors, like disjoint set (union find), heap tree, segment tree, binary index tree, flat map, flat interval tree etc.


  • Array Replacement: If you need an array-like structure that can grow and shrink, vectors are an ideal replacement for traditional C-style arrays.

  • Fast Back-End Operations: When you frequently add or remove elements from the back of your sequence, vectors excel.

Deques (pronounced “decks”) are double-ended queues. You can efficiently insert and remove elements from both the front and the back, offering more flexibility than traditional stacks or queues. It is normally implemented by vector under the hood [1].

Adaptable Structure: Internally, a deque may be represented as multiple smaller chunks of memory. This gives it flexibility but makes random access by index slightly slower than vectors.

Front and Back Agility: The defining feature of deques is their efficiency in adding (push_front, push_back) and removing (pop_front, pop_back) elements from either end. These operations maintain constant time complexity \(O(1)\).


  • Queues and Stacks: Deques are the natural choice when implementing queues (first-in, first-out) or stacks (last-in, first-out) in your program.

  • Flexibility Needed: If you need to frequently manipulate both the beginning and end of your sequence, deques offer an advantage over vectors.


In the following sections, we will discussion some algorithms related to vector and deque.