C++ STL Sequence Containers

`std::vector`

Under the Hood Implementation A dynamic, contiguous array. The standard implementation uses three pointers managed via std::allocator:

T* _M_start: Points to the beginning of the allocated memory.
T* _M_finish: Points to one past the last constructed element (dictates size()).
T* _M_end_of_storage: Points to one past the end of the allocated memory (dictates capacity()). When size() == capacity() during a push operation, the vector allocates a new buffer (typically 1.5\times or 2\times the current capacity), move-constructs (if noexcept) or copy-constructs the elements to the new buffer, destroys the old elements, and frees the old buffer.

Data Types Memory allocated on the heap. Elements are of type T.

ASCII Illustration

[ _M_start ]  [ _M_finish ][ _M_end_of_storage ]
      |             |                            |
      v             v                            v
    +---+---+---+---+---+---+---+---+---+---+----+
    | 0 | 1 | 2 | 3 | x | x | x | x | x | x | x  |
    +---+---+---+---+---+---+---+---+---+---+----+
    \_______________/ \_________________________/
      Constructed            Uninitialized
      Elements               Capacity Space

Big O Complexity

Access: O(1)
Push/Pop Back: Amortized O(1). Worst-case O(N) if reallocation occurs.
Insert/Erase: O(N). Requires shifting all subsequent elements.
Search: O(N) for unsorted, O(\log N) via binary search if sorted.

Typical Usage Scenarios The default container. High performance due to spatial locality, which maximizes CPU L1/L2 cache hits and hardware prefetching. Used when element access is random and insertions/deletions primarily happen at the end.

`std::deque`

Under the Hood Implementation A double-ended queue implemented as a piecewise-contiguous array. It consists of a central directory (a "map") of pointers. Each pointer in the map points to a fixed-size memory block (a "chunk" or "node") allocated on the heap.

T** _M_map: Array of pointers to chunks.
size_t _M_map_size: Capacity of the directory.
iterator _M_start: Points to the first element in the first active chunk.
iterator _M_finish: Points to the last element in the last active chunk. Chunk size is typically determined by the compiler to fit within a standard page or cache line (e.g., 512 bytes / sizeof(T)). When a chunk fills up, a new chunk is allocated and its pointer is added to the central map. If the map fills up, the array of pointers (not the data itself) is reallocated.

Data Types Heap-allocated map (T**) pointing to heap-allocated arrays (T*).

ASCII Illustration

          _M_map (Array of Pointers)
          +-------+-------+-------+-------+
          | ptr_0 | ptr_1 | ptr_2 | ptr_3 |
          +-------+-------+-------+-------+
              |       |       |       |
      +-------+       |       |       +---------------+
      |               |       +-------+               |
      v               v               v               v
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
| x | x | 0 |   | 1 | 2 | 3 |   | 4 | 5 | 6 |   | 7 | x | x |
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
      ^                                           ^
   _M_start                                    _M_finish

Big O Complexity

Access: O(1). Requires constant time arithmetic: computing the chunk index and the offset within the chunk (two pointer dereferences).
Push/Pop Front & Back: O(1).
Insert/Erase: O(N). Elements must be shifted, crossing chunk boundaries if necessary.

Typical Usage Scenarios Sliding window algorithms, job queues, or when rapid insertions/deletions are required at both ends but random access is still necessary.

`std::list`

Under the Hood Implementation A doubly-linked list. Each element is stored in an independent heap allocation containing pointers to the adjacent nodes. The container itself tracks:

Node* _M_head (often a dummy/sentinel node to simplify operations).
size_t _M_size (required in C++11 to ensure O(1) size()). Each node is defined as:

struct Node {
    Node* prev;
    Node* next;
    T data;
};

Data Types Structs allocated piecemeal on the heap.

ASCII Illustration

      +-------------+    +-------------+    +-------------+
      |  Node 1     |    |  Node 2     |    |  Node 3     |
0 <---| prev        |<---| prev        |<---| prev        |
      | data: 'A'   |    | data: 'B'   |    | data: 'C'   |
      | next        |--->| next        |--->| next        |---> 0
      +-------------+    +-------------+    +-------------+
             ^                                     ^
          _M_head                               _M_tail

Big O Complexity

Access: O(N). Must traverse nodes sequentially.
Push/Pop Front & Back: O(1).
Insert/Erase: O(1), provided an iterator to the exact position is already possessed.
Splice: O(1) (transferring elements from one list to another).

Typical Usage Scenarios Extensive insertion, deletion, or movement of elements in the middle of a sequence where iterators and references to existing elements must not be invalidated. Poor cache locality; iteration triggers cache misses.

`std::forward_list` (C++11)

Under the Hood Implementation A singly-linked list designed for zero-overhead compared to a hand-rolled C-style linked list. It deliberately omits tracking the size (size() function does not exist) and tail pointer.

Node* _M_head. Each node is defined as:

struct Node {
    Node* next;
    T data;
};

Data Types Structs allocated piecemeal on the heap.

ASCII Illustration

 _M_head
    |
    v
+---------+      +---------+      +---------+
| data: 1 |      | data: 2 |      | data: 3 |
| next    | ---> | next    | ---> | next    | ---> nullptr
+---------+      +---------+      +---------+

Big O Complexity

Access: O(N). Unidirectional traversal only.
Push/Pop Front: O(1).
Insert/Erase After: O(1) (insert_after, erase_after).
Push/Pop Back: Not supported directly.

Typical Usage Scenarios Severely memory-constrained embedded environments where spatial overhead per node must be strictly minimized, bidirectional traversal is unneeded, and standard std::list carries too much state overhead.

`std::array` (C++11)

Under the Hood Implementation A zero-overhead, thin struct wrapper around a raw C-style array. The memory is strictly contiguous and allocated dynamically on the stack, within a struct, or in the data segment—wherever the std::array itself is instantiated. It performs no heap allocations.

template<typename T, std::size_t N>
struct array {
    T _M_elems[N];
};

Data Types Contiguous bytes of T. Size N is encoded directly into the container's type. std::array<int, 5> and std::array<int, 6> are distinct, incompatible types.

ASCII Illustration

Stack / In-Place Memory
+-------+-------+-------+-------+-------+
|   0   |   1   |   2   |   3   |   4   |
+-------+-------+-------+-------+-------+
 \_____________________________________/
       Exactly N elements of type T

Big O Complexity

Access: O(1).
Push/Pop/Insert/Erase: N/A. The size is fixed at compile-time and cannot be altered. Elements can be overwritten, but the container cannot grow or shrink.

Typical Usage Scenarios Known bounds fixed at compile time. Used heavily in safety-critical, hard-real-time, and embedded systems to statically guarantee no dynamic memory allocation (malloc/new) occurs, preventing heap fragmentation and ensuring deterministic execution times. Replaces T arr[N] to provide STL-compatible iterators and bounds checking via .at().

Contiguous Memory: std::vector and std::array

#include <vector>
#include <array>
#include <cstdint>

struct Telemetry {
    uint32_t timestamp;
    double velocity;
    
    // Constructor required for emplace operations
    Telemetry(uint32_t ts, double v) : timestamp(ts), velocity(v) {}
};

void sequence_contiguous_operations() {
    // std::array: Memory allocated exactly where the stack frame resides. 
    // Zero dynamic allocation. Strict bounds.
    std::array<int, 4> calibration_matrix = {10, 20, 30, 40};
    
    // std::vector: Heap allocation. 
    std::vector<Telemetry> buffer;
    
    // CRITICAL: Pre-allocate to prevent O(N) reallocation and copying.
    // Alters _M_end_of_storage pointer, leaves _M_finish unchanged.
    buffer.reserve(1024); 
    
    // emplace_back: Constructs the object directly in the uninitialized memory space 
    // pointed to by _M_finish. Bypasses temporary object creation and move/copy semantics.
    buffer.emplace_back(16234212, 14.5);
}

Node-Based Memory: std::list and std::forward_list

#include <list>
#include <forward_list>
#include <iterator>

void sequence_node_operations() {
    std::list<int> active_tasks = {10, 20, 30};
    std::list<int> pending_tasks = {40, 50, 60};

    auto it = active_tasks.begin();
    std::advance(it, 1); // Iterates _M_next pointer to reach node '20'. O(N) time.

    // Splice: Transfers elements without data copying or memory allocation.
    // Rewires _M_prev and _M_next pointers. O(1) time complexity.
    active_tasks.splice(it, pending_tasks); 
    // pending_tasks is now empty. active_tasks is: 10, 40, 50, 60, 20, 30.

    std::forward_list<int> f_list = {1, 2, 3};
    // insert_after enforces O(1) operations for singly-linked lists. 
    // Lacks _M_prev, so inserting directly AT an iterator requires O(N) traversal.
    f_list.insert_after(f_list.begin(), 99); 
    // f_list is: 1, 99, 2, 3.
}

Contiguous Memory: std::vector and std::array

#include <vector>
#include <array>
#include <cstdint>

struct Telemetry {
    uint32_t timestamp;
    double velocity;
    
    // Constructor required for emplace operations
    Telemetry(uint32_t ts, double v) : timestamp(ts), velocity(v) {}
};

void sequence_contiguous_operations() {
    // std::array: Memory allocated exactly where the stack frame resides. 
    // Zero dynamic allocation. Strict bounds.
    std::array<int, 4> calibration_matrix = {10, 20, 30, 40};
    
    // std::vector: Heap allocation. 
    std::vector<Telemetry> buffer;
    
    // CRITICAL: Pre-allocate to prevent O(N) reallocation and copying.
    // Alters _M_end_of_storage pointer, leaves _M_finish unchanged.
    buffer.reserve(1024); 
    
    // emplace_back: Constructs the object directly in the uninitialized memory space 
    // pointed to by _M_finish. Bypasses temporary object creation and move/copy semantics.
    buffer.emplace_back(16234212, 14.5);
}

Ragged Array / Adjacency List: std::vector<std::vector<T>>

Under the Hood Memory Layout: A std::vector<std::vector<int>> does not allocate a contiguous 2D block of memory. The outer vector allocates a contiguous array of std::vector objects on the heap. Each inner std::vector object (typically 24 bytes comprising _M_start, _M_finish, _M_end_of_storage) independently manages its own separate heap allocation for its integer payload.

Accessing graph[i][j] requires two dependent memory fetches:

Read the outer vector's heap allocation to retrieve the control block for the i-th inner vector.
Read the i-th inner vector's _M_start pointer to traverse to a distinct heap location and retrieve the j-th element. This breaks CPU cache locality between rows. For dense matrices, a flat 1D std::vector<T> accessed via [row * cols + col] is strictly superior. std::vector<std::vector<T>> is optimal only when inner array sizes vary drastically (ragged arrays), preventing massive overallocation.

#include <vector>
#include <cstdint>

void ragged_array_operations() {
    // Outer vector pre-allocates space for 5 inner vector control blocks.
    // Inner vectors remain empty (size 0, capacity 0).
    std::vector<std::vector<uint32_t>> adjacency_list(5);

    // Inner vectors are allocated distinct, varying capacities on the heap.
    adjacency_list[0] = {1, 2, 3};       // Size 3
    adjacency_list[1] = {0};             // Size 1
    adjacency_list[2] = {0, 3, 4, 1};    // Size 4
    adjacency_list[3] = {0, 2};          // Size 2
    adjacency_list[4] = {2};             // Size 1

    // To add an element to a specific row:
    // Requires vector control block lookup, then inner vector bounds check/reallocation.
    adjacency_list[1].push_back(4); 
}

C++ STL Sequence Containers

std::vector

std::deque

std::list

std::forward_list (C++11)

std::array (C++11)

`std::vector`

`std::deque`

`std::list`

`std::forward_list` (C++11)

`std::array` (C++11)