C++

Kontejnerové adaptéry a speciální kontejnery

Přečtěte si o zásobníku, frontě, prioritě_fronty a moderních typech slovní zásoby, jako je span, string_view a optional. Pochopte, kdy adaptéry zjednodušují váš kód.

Co jsou to kontejnerové adaptéry?

Adaptéry kontejnerů jsou obaly kolem stávajících kontejnerů, které poskytují omezené rozhraní. Vynucují konkrétní přístupový vzor skrytím plného rozhraní API kontejneru:

- std::stack — LIFO (poslední vstup, první výstup), standardně podporovanýdeque
- std::queue — FIFO (First In, First Out), ve výchozím nastavení podporovánodeque
- std::priority_queue — maximální halda, ve výchozím nastavení podporovánavector

Adaptéry neposkytují iterátory – máte přístup pouze k hornímu/přednímu prvku. Toto omezení je záměrné: činí záměr kódu jasnějším a zabraňuje náhodnému zneužití.

Zásobník a fronta v akci

Zásobníky a fronty jsou základní datové struktury používané při analýze, BFS/DFS, systémech vrácení zpět a plánování úloh.

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
    }
}

Prioritní fronta (hromada)

std::priority_queueje ve výchozím nastavení maximální halda —top()vrací největší prvek. Pro minimální haldu použijte jako komparátorstd::greater.

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 — Nevlastnící pohled na souvislá data (C++20)

std::spanje lehký, nevlastní pohled na souvislou sekvenci prvků. Nahrazuje vzor náchylný k chybám předávání párů(pointer, size).

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 a volitelné

std::string_view (C++17) je odkaz na řetězec, který nevlastní a je pouze pro čtení. Vyhnete se nákladům na kopírování nebo alokacistd::stringpro funkce, které potřebují pouze číst:

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::volitelné (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
Úskalí

Vzhledem k tomu, žestd::string_viewastd::spannevlastní, mohou snadno viset, pokud budou zničena základní data:

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 — je to pouze ukazatel a vnitřní velikost, bez sémantiky vlastnictví.

Osvědčený postup

Adaptéry kontejnerů použijte, když chcete prosadit disciplínu o tom, jak se přistupuje k prvkům:

- Použijtestd::stackmísto nezpracovanéhodequenebovector, když má smysl pouze LIFO přístup. Tím je záměr zřejmý a zabraňuje náhodnému náhodnému přístupu.
- Použijtestd::queuepro zpracování FIFO (fronty úloh, BFS).
- Použijtestd::priority_queuepro plánování, Dijkstrův algoritmus nebo jakýkoli scénář, kde vždy chcete extrémní prvek.

Pokud potřebujete iteraci, dotazy na velikost v libovolných bodech nebo přístup uprostřed sekvence, použijte přímo podkladový kontejner.

Klíčové poznatky
  • Kontejnerové adaptéry (stack,queue,priority_queue) omezují rozhraní, aby prosazovaly disciplínu používání
  • std::priority_queueje ve výchozím nastavení maximální halda — pro minimální haldu použijtestd::greater
  • std::span(C++20) poskytuje pohled na souvislá data, který nevlastní, a nahrazuje páry(pointer, size)
  • std::string_view(C++17) se vyhýbá kopírování řetězců pro použití pouze pro čtení – ale dávejte pozor na visící odkazy
  • std::optional(C++17) is the type-safe way to represent "maybe no value" without magic sentinel values
  • Nevlastnící výběry dat (span,string_view) nesmí nikdy přežít data, na která odkazují

Kvíz — Otestujte své znalosti

(15 XP)

1. Který adaptér kontejneru poskytuje chování FIFO (First In, First Out)?

2. Jaký typ se standardně vrací`std::priority_queue<int>`z`top()`?

3. Proč je vracení`std::string_view`do místního`std::string`nebezpečné?

Předchozí
Associative Containers: map, set, unordered_map
Další
Iterátory: Lepidlo STL