C++ STL Container Adaptors

Container Adaptors Base Architecture

Container adaptors are not distinct data structures. They act as restrictive wrappers around existing sequence containers (std::vector, std::deque, std::list). They disable iterators and hide the underlying container's public interface, exposing only specific methods to enforce strict data access patterns (LIFO, FIFO, or Priority-based).

By default, they use composition. The underlying container is stored as a protected member variable named c.

`std::stack`

Under the Hood Implementation Enforces LIFO (Last-In, First-Out). The default underlying container is std::deque<T>. It maps:

push() to c.push_back()
pop() to c.pop_back()
top() to c.back() std::deque is preferred over std::vector because deque allocates memory in discrete chunks. This prevents the large O(N) data copying that occurs when a vector exhausts its capacity and reallocates. std::vector or std::list can be explicitly specified as the backing container if memory contiguity or specific allocation patterns are required.

Data Types std::stack<T, Container = std::deque<T>>

ASCII Illustration

      Push  Pop
        |    ^
        v    |
      +--------+
Top ->|   40   |  <-- c.back()
      +--------+
      |   30   |
      +--------+
      |   20   |
      +--------+
      |   10   |  <-- c.front()
      +--------+

Big O Complexity

Push / Emplace: O(1)
Pop: O(1)
Top: O(1)
Size / Empty: O(1)

Typical Usage Scenarios Depth-First Search (DFS) algorithms. Call stack simulation. Expression parsing (e.g., Shunting Yard algorithm, Abstract Syntax Tree evaluation). Undo mechanisms in state machines.

`std::queue`

Under the Hood Implementation Enforces FIFO (First-In, First-Out). The default underlying container is std::deque<T>. It maps:

push() to c.push_back()
pop() to c.pop_front()
front() to c.front()
back() to c.back() std::vector cannot be used as the backing container for std::queue because std::vector lacks a pop_front() method (which would require an O(N) shift of all elements). std::list is a valid alternative if extreme pointer stability is needed.

Data Types std::queue<T, Container = std::deque<T>>

ASCII Illustration

          +----+----+----+----+
Pop <---  | 10 | 20 | 30 | 40 | <--- Push
          +----+----+----+----+
            ^              ^
          Front           Back

Big O Complexity

Push / Emplace: O(1)
Pop: O(1)
Front / Back: O(1)

Typical Usage Scenarios Breadth-First Search (BFS) algorithms. Task scheduling. Inter-thread message buffering. I/O request queues where strict ordering must be preserved.

`std::priority_queue`

Under the Hood Implementation Enforces access to the "largest" element as defined by a comparator. The default underlying container is std::vector<T>. It is implemented as a Binary Max-Heap represented as a contiguous array. It does not use standard container push/pop directly. Instead, it relies on <algorithm> heap operations applied to the underlying vector:

push() calls c.push_back() followed by std::push_heap() (sifts the element up the tree).
pop() calls std::pop_heap() (swaps root with the last element, sifts the new root down), followed by c.pop_back().
top() calls c.front(). The default comparator is std::less<T>, which counter-intuitively creates a Max-Heap because std::pop_heap moves the largest element to the end of the sequence.

Data Types std::priority_queue<T, Container = std::vector<T>, Compare = std::less<typename Container::value_type>>

ASCII Illustration

Conceptual Tree:
           [100]           <-- Top (Index 0)
          /     \
      [80]       [90]      <-- Indices 1, 2
      /  \       /  \
   [30]  [40] [70]  [10]   <-- Indices 3, 4, 5, 6

Underlying std::vector Memory:
+-----+----+----+----+----+----+----+
| 100 | 80 | 90 | 30 | 40 | 70 | 10 |
+-----+----+----+----+----+----+----+
   0    1    2    3    4    5    6
Parent(i) = (i - 1) / 2
LeftChild(i) = 2i + 1
RightChild(i) = 2i + 2

Big O Complexity

Push / Emplace: O(\log N) (Heap sift-up)
Pop: O(\log N) (Heap sift-down)
Top: O(1)
Construction from range: O(N) using std::make_heap (bottom-up heap construction, strictly faster than N individual pushes).

Typical Usage Scenarios Dijkstra's Shortest Path algorithm. A* Pathfinding. Processing events strictly by timestamp or priority level. Computing Top-K elements in a continuous data stream.

Examples

Standard Stack and Queue

#include <stack>
#include <queue>
#include <vector>

void adapter_standard_operations() {
    // std::stack mapping to deque
    std::stack<int> memory_addresses;
    memory_addresses.push(0x1000);
    memory_addresses.emplace(0x1004); // Constructs directly in underlying deque
    
    int top_addr = memory_addresses.top(); // 0x1004
    memory_addresses.pop(); // Returns void. Requires separate top() and pop() for exception safety.

    // std::queue mapping to deque
    std::queue<int> task_ids;
    task_ids.push(1);
    task_ids.push(2);
    
    int next_task = task_ids.front(); // 1
    task_ids.pop();
}

Priority Queue: Min-Heap and Custom Comparators

#include <queue>
#include <vector>

struct NodeCost {
    int node_id;
    int cost;
    
    NodeCost(int id, int c) : node_id(id), cost(c) {}
};

// Custom comparator for Min-Heap.
// Must return true if lhs has LOWER priority than rhs.
// For a Min-Heap, larger costs should have lower priority (sink to bottom).
struct GreaterCost {
    bool operator()(const NodeCost& lhs, const NodeCost& rhs) const {
        return lhs.cost > rhs.cost; 
    }
};

void priority_queue_operations() {
    // Default Max-Heap. Largest int is at top().
    std::priority_queue<int> max_heap;
    max_heap.push(50);
    max_heap.push(100); // 100 becomes top()

    // Min-Heap using standard library comparator
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(50);
    min_heap.push(10);  // 10 becomes top()

    // Custom Min-Heap for complex structs
    // Requires specifying the generic type, the container, and the comparator type.
    std::priority_queue<NodeCost, std::vector<NodeCost>, GreaterCost> frontier;
    frontier.emplace(1, 500);
    frontier.emplace(2, 150); // Becomes top() because 150 < 500
    
    // To process:
    while(!frontier.empty()) {
        NodeCost current = frontier.top();
        frontier.pop(); // O(log N) heap reorganization
        // Process current...
    }
}

Dijkstra's Algorithm

Dijkstra's algorithm computes the shortest path tree from a single source node to all other nodes in a graph with non-negative edge weights. It is a greedy algorithm utilizing a Priority Queue to continuously expand the frontier of explored nodes by selecting the node with the lowest accumulated distance.

Conceptual Execution

Dijkstra's Algorithm determines the shortest path from a single source node to all other reachable nodes in a graph. It strictly requires non-negative edge weights.

Phase 1: Initialization

Assign a distance value to every node. Set the source node's distance to zero. Set all other nodes' distances to infinity.
Mark all nodes as unvisited.
Designate the source node as the current operating node.

Phase 2: Evaluation and Relaxation

Identify the unvisited node with the lowest recorded distance. This becomes the new current node.
Examine all unvisited adjacent neighbors of this current node.
Calculate the tentative distance to each neighbor: Current Node Distance + Edge Weight to Neighbor.
Compare the tentative distance to the neighbor's currently recorded distance. If the tentative distance is strictly less than the recorded distance, overwrite the recorded distance with the tentative value.

Phase 3: State Finalization

After evaluating all unvisited neighbors of the current node, mark the current node as visited.
A visited node is permanently locked. Its recorded distance is the guaranteed minimum path from the source. It is never re-evaluated.

Phase 4: Termination

Loop Phase 2 and Phase 3.
Halt execution when the unvisited set is empty.
Halt execution prematurely if the lowest recorded distance among all remaining unvisited nodes is infinity. This indicates the remaining unvisited nodes are topologically isolated from the source.

Min-Heap Inversion

The standard std::priority_queue implements a Max-Heap via std::less. Dijkstra strictly requires a Min-Heap. The architectural standard is to supply std::greater as the comparator type.

Data Structures

Graph Representation: Adjacency List std::vector<std::vector<Edge>>. Preferred over adjacency matrices for memory efficiency ( vs ) and faster iteration over neighbors.
Distance Tracking: Contiguous array std::vector<uint32_t> initialized to maximum integer bounds representing infinity.
Frontier Tracking: std::priority_queue storing state objects.

ASCII Graph and Execution State

Target Graph:

      (4)       (1)
  [0] ----> [1] ----> [2]
   |         |         ^
   |         | (2)     |
(1)|         v         | (5)
   +------> [3] -------+

Memory State Progression (Source = 0):

Init:
Distances: [0, INF, INF, INF]
PQ: {(dist: 0, node: 0)}

Step 1 (Pop 0):
Relax 0->1 (dist 4): Distances[1] = 4. PQ push {(4, 1)}
Relax 0->3 (dist 1): Distances[3] = 1. PQ push {(1, 3)}
PQ State: {(1, 3), (4, 1)}

Step 2 (Pop 3):
Relax 3->2 (dist 1+5=6): Distances[2] = 6. PQ push {(6, 2)}
PQ State: {(4, 1), (6, 2)}

Step 3 (Pop 1):
Relax 1->2 (dist 4+1=5): Distances[2] = 5. PQ push {(5, 2)}
Relax 1->3 (dist 4+2=6): Ignored (6 > Distances[3]=1)
PQ State: {(5, 2), (6, 2)}

Step 4 (Pop 2 at dist 5):
No outgoing edges.
PQ State: {(6, 2)}

Step 5 (Pop 2 at dist 6):
Stale state detected (6 > Distances[2]=5). Discard immediately.
PQ State: Empty. Halt.

Implementation

#include <vector>
#include <queue>
#include <limits>
#include <cstdint>

// Defines an immutable directed connection.
struct Edge {
    uint32_t target;
    uint32_t weight;
};

// Represents a node in the priority queue frontier.
struct State {
    uint32_t distance;
    uint32_t node;

    // Invert the operator to allow std::greater to form a Min-Heap.
    // The heap will order elements such that the smallest distance is at the top.
    bool operator>(const State& other) const {
        return distance > other.distance;
    }
};

// Computes the shortest path from the source to all reachable nodes.
// Unreachable nodes remain at std::numeric_limits<uint32_t>::max().
std::vector<uint32_t> compute_shortest_paths(
    const std::vector<std::vector<Edge>>& graph, 
    uint32_t source_node) 
{
    const size_t vertex_count = graph.size();
    
    // Contiguous memory allocation for distance tracking.
    std::vector<uint32_t> distances(vertex_count, std::numeric_limits<uint32_t>::max());
    distances[source_node] = 0;

    // Define the Min-Heap. 
    // Container: std::vector<State>
    // Comparator: std::greater<State>
    std::priority_queue<State, std::vector<State>, std::greater<State>> frontier;
    frontier.push({0, source_node});

    while (!frontier.empty()) {
        // Extract the minimum distance node. O(log V)
        State current = frontier.top();
        frontier.pop();

        // Stale State Discarding
        // std::priority_queue lacks a decrease_key operation. Duplicate nodes with
        // shorter distances are pushed. When a stale, longer-distance duplicate 
        // reaches the top, it is bypassed to prevent redundant edge relaxation.
        if (current.distance > distances[current.node]) {
            continue;
        }

        // Edge Relaxation
        for (const Edge& edge : graph[current.node]) {
            uint32_t new_distance = current.distance + edge.weight;

            if (new_distance < distances[edge.target]) {
                distances[edge.target] = new_distance;
                // Push the improved state to the heap. O(log V)
                frontier.push({new_distance, edge.target});
            }
        }
    }

    return distances;
}

Under the Hood Mechanics

Stale State Discarding vs. `decrease_key`

A theoretical strict Fibonacci Heap implementation of Dijkstra uses a decrease_key operation to mutate an existing node's distance in time. Standard library adaptors do not support mutating internal container elements. Pushing duplicate, updated states into std::priority_queue and discarding stale states upon extraction is the standard industry implementation. It leverages contiguous vector memory and hardware cache line prefetching, consistently outperforming pointer-based heaps in practical benchmarks.

Big-O Complexity

Time: O(E log V) where E is the number of edges and V is the number of vertices. Each edge triggers at most one heap insertion.
Space: O(V) for the distances array and the std::priority_queue capacity. The graph itself requires O(V + E).

C++ STL Container Adaptors

Container Adaptors Base Architecture

std::stack

std::queue

std::priority_queue

Examples

Dijkstra's Algorithm

Conceptual Execution

Phase 1: Initialization

Phase 2: Evaluation and Relaxation

Phase 3: State Finalization

Phase 4: Termination

Min-Heap Inversion

Data Structures

ASCII Graph and Execution State

Implementation

Under the Hood Mechanics

Stale State Discarding vs. decrease_key

Big-O Complexity

`std::stack`

`std::queue`

`std::priority_queue`

Stale State Discarding vs. `decrease_key`