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 bydequeby default
- std::queue — FIFO (First In, First Out), backed bydequeby default
- std::priority_queue — max-heap, backed byvectorby 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_queueis a max-heap by default —top()returns the largest element. For a min-heap, usestd::greateras 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::spanis 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 allocatingstd::stringfor functions that only need to read:

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:

std::optional<int> find_index(std::span<const int> 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

Capcană

Sincestd::string_viewandstd::spanare non-owning, they can easily dangle if the underlying data is destroyed:

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.

Bună practică

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

- Usestd::stackinstead of a rawdequeorvectorwhen only LIFO access is meaningful. This makes the intent obvious and prevents accidental random access.
- Usestd::queuefor FIFO processing (task queues, BFS).
- Usestd::priority_queuefor 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.

Idei cheie

Container adaptors (stack,queue,priority_queue) restrict the interface to enforce usage discipline
std::priority_queueis a max-heap by default — usestd::greaterfor 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

Test — Verifică-ți cunoștințele

(15 XP)

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

2. Ce tip returnează`std::priority_queue<int>`de la`top()`în mod implicit?

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

Containere asociative: hartă, set, hartă_neordonată

Următor

Iterators: The STL Glue