Container Adaptors & Special Containers

Learn about stack, queue, priority_queue, and modern vocabulary types like span, string_view, and optional. Understand when adaptors simplify your code.

What Are Container Adaptors?

Container adaptors are wrappers around existing containers that provide a restricted interface. They enforce a specific access pattern by hiding the full container API:

- std::stack — LIFO (Last In, First Out), backed by deque by default
- std::queue — FIFO (First In, First Out), backed by deque by default
- std::priority_queue — max-heap, backed by vector by default

Adaptors do not provide iterators — you can only access the top/front element. This restriction is intentional: it makes the code's intent clearer and prevents accidental misuse.

Stack and Queue in Action

Stacks and queues are fundamental data structures used in parsing, BFS/DFS, undo systems, and task scheduling.

stack_queue.cpp

#include <stack>
#include <queue>
#include <string>
#include <iostream>

// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
    std::stack<char> stk;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stk.empty()) return false;
            char top = stk.top();
            stk.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stk.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_balanced("({[]})") << '\n';   // true
    std::cout << is_balanced("({[}])") << '\n';   // false

    // Queue — BFS-style task processing
    std::queue<std::string> tasks;
    tasks.push("compile");
    tasks.push("link");
    tasks.push("run tests");

    while (!tasks.empty()) {
        std::cout << "Processing: " << tasks.front() << '\n';
        tasks.pop();   // removes from front
    }
}

Priority Queue (Heap)

std::priority_queue is a max-heap by default — top() returns the largest element. For a min-heap, use std::greater as the comparator.

priority_queue.cpp

#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>

struct Task {
    int priority;
    std::string name;
};

int main() {
    // Max-heap (default) — largest first
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    while (!max_heap.empty()) {
        std::cout << max_heap.top() << ' ';  // 50 30 20 10
        max_heap.pop();
    }
    std::cout << '\n';

    // Min-heap — smallest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    std::cout << "Min: " << min_heap.top() << '\n';  // 10

    // Custom comparator with lambda
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // higher priority first
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
    task_queue.push({3, "low priority"});
    task_queue.push({10, "critical"});
    task_queue.push({7, "medium"});

    while (!task_queue.empty()) {
        auto& t = task_queue.top();
        std::cout << "[" << t.priority << "] " << t.name << '\n';
        task_queue.pop();
    }
}

std::span — Non-Owning View of Contiguous Data (C++20)

std::span is a lightweight, non-owning view over a contiguous sequence of elements. It replaces the error-prone pattern of passing (pointer, size) pairs.

span_example.cpp

#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>

// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
    if (data.empty()) return;
    std::cout << "Size: " << data.size() << '\n';
    std::cout << "First: " << data.front() << '\n';
    std::cout << "Last:  " << data.back() << '\n';

    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum:   " << sum << '\n';

    // Subviews
    auto first3 = data.first(3);   // first 3 elements
    auto last2  = data.last(2);    // last 2 elements
    auto mid    = data.subspan(1, 3);  // 3 elements starting at index 1
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {10, 20, 30, 40, 50};
    int c_arr[] = {100, 200, 300, 400, 500};

    print_stats(vec);     // works with vector
    print_stats(arr);     // works with array
    print_stats(c_arr);   // works with C-array
}

string_view and optional

std::string_view (C++17) is a non-owning, read-only reference to a string. It avoids the cost of copying or allocating std::string for functions that only need to read:

``cpp void greet(std::string_view name) { // no copy, no allocation std::cout << "Hello, " << name << '\n'; } greet("world"); // works with string literals greet(std::string{"world"}); // works with std::string``

std::optional (C++17) represents a value that might or might not be present — a type-safe replacement for "magic values" or raw pointers to indicate absence:

``cpp std::optional find_index(std::span data, int target) { for (int i = 0; i < data.size(); ++i) if (data[i] == target) return i; return std::nullopt; // not found } auto idx = find_index(vec, 42); if (idx) std::cout << "Found at " << *idx << '\n'; std::cout << idx.value_or(-1) << '\n'; // -1 if empty``

Pitfall

Since std::string_view and std::span are non-owning, they can easily dangle if the underlying data is destroyed:

``cpp std::string_view bad() { std::string temp = "hello"; return temp; // DANGLING — temp destroyed at end of scope }``

Never return a string_view or span to a local variable. They are safe for function parameters (the caller's data outlives the call), but dangerous as return values unless you can guarantee the source outlives the view.

The same applies to std::span — it is just a pointer and a size internally, with no ownership semantics.

Best Practice

Use container adaptors when you want to enforce a discipline on how elements are accessed:

- Use std::stack instead of a raw deque or vector when only LIFO access is meaningful. This makes the intent obvious and prevents accidental random access.
- Use std::queue for FIFO processing (task queues, BFS).
- Use std::priority_queue for scheduling, Dijkstra's algorithm, or any scenario where you always want the extreme element.

If you need iteration, size queries at arbitrary points, or mid-sequence access, use the underlying container directly.

Key Takeaways

Container adaptors (stack, queue, priority_queue) restrict the interface to enforce usage discipline
std::priority_queue is a max-heap by default — use std::greater for a min-heap
std::span (C++20) provides a non-owning view over contiguous data, replacing (pointer, size) pairs
std::string_view (C++17) avoids copying strings for read-only use — but watch for dangling references
std::optional (C++17) is the type-safe way to represent "maybe no value" without magic sentinel values
Non-owning views (span, string_view) must never outlive the data they reference

Quiz — Test Your Knowledge

(15 XP)

1. Which container adaptor provides FIFO (First In, First Out) behavior?

2. What type does `std::priority_queue<int>` return from `top()` by default?

3. Why is returning a `std::string_view` to a local `std::string` dangerous?

Associative Containers: map, set, unordered_map

Iterators: The STL Glue