Адаптеры контейнеров и специальные контейнеры

Узнайте о stack, queue, priority_queue и современных словарных типах, таких как span, string_view и optional. Поймите, когда адаптеры упрощают ваш код.

Что такое адаптеры контейнеров?

Адаптеры контейнеров — это обёртки вокруг существующих контейнеров, предоставляющие ограниченный интерфейс. Они навязывают определённый паттерн доступа, скрывая полный API контейнера:

- std::stack — LIFO (последним пришёл, первым ушёл), по умолчанию использует deque
- std::queue — FIFO (первым пришёл, первым ушёл), по умолчанию использует deque
- std::priority_queue — максимальная куча, по умолчанию использует vector

Адаптеры не предоставляют итераторов — вы можете обращаться только к верхнему/переднему элементу. Это ограничение намеренное: оно делает намерение кода яснее и предотвращает случайное некорректное использование.

Stack и Queue в действии

Стеки и очереди — фундаментальные структуры данных, используемые в синтаксическом разборе, BFS/DFS, системах отмены и планировании задач.

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

Очередь с приоритетом (куча)

std::priority_queue по умолчанию является максимальной кучей — top() возвращает наибольший элемент. Для минимальной кучи используйте std::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 — невладеющее представление непрерывных данных (C++20)

std::span — это легковесное невладеющее представление непрерывной последовательности элементов. Оно заменяет подверженный ошибкам паттерн передачи пар (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 и optional

std::string_view (C++17) — это невладеющая ссылка на строку только для чтения. Она позволяет избежать затрат на копирование или выделение std::string для функций, которым нужно только читать:

void greet(std::string_view name) {  // без копирования, без выделения
    std::cout << "Hello, " << name << '\n';
}
greet("world");               // работает со строковыми литералами
greet(std::string{"world"});  // работает с std::string

std::optional (C++17) представляет значение, которое может присутствовать или отсутствовать — типобезопасная замена «магическим значениям» или сырым указателям для обозначения отсутствия:

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;  // не найдено
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n';  // -1 если пусто

Подводный камень

Поскольку std::string_view и std::span являются невладеющими, они легко могут стать висячими, если базовые данные уничтожены:

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // ВИСЯЧИЙ — temp уничтожен в конце области видимости
}

Никогда не возвращайте string_view или span, ссылающийся на локальную переменную. Они безопасны для параметров функции (данные вызывающего живут дольше вызова), но опасны как возвращаемые значения, если вы не можете гарантировать, что источник живёт дольше представления.

То же касается std::span — внутренне это просто указатель и размер, без семантики владения.

Лучшая практика

Используйте адаптеры контейнеров, когда хотите навязать дисциплину доступа к элементам:

- Используйте std::stack вместо «сырого» deque или vector, когда осмыслен только LIFO-доступ. Это делает намерение очевидным и предотвращает случайный произвольный доступ.
- Используйте std::queue для FIFO-обработки (очереди задач, BFS).
- Используйте std::priority_queue для планирования, алгоритма Дейкстры или любого сценария, где всегда нужен экстремальный элемент.

Если вам нужна итерация, запросы размера в произвольных точках или доступ к середине последовательности, используйте базовый контейнер напрямую.

Ключевые выводы

Адаптеры контейнеров (stack, queue, priority_queue) ограничивают интерфейс для навязывания дисциплины использования
std::priority_queue по умолчанию является максимальной кучей — используйте std::greater для минимальной кучи
std::span (C++20) предоставляет невладеющее представление непрерывных данных, заменяя пары (pointer, size)
std::string_view (C++17) позволяет избежать копирования строк для чтения — но остерегайтесь висячих ссылок
std::optional (C++17) — типобезопасный способ представить «возможно, нет значения» без магических значений-маркеров
Невладеющие представления (span, string_view) никогда не должны переживать данные, на которые они ссылаются

Тест — проверьте свои знания

(15 XP)

1. Какой адаптер контейнера обеспечивает поведение FIFO (первым пришёл, первым ушёл)?

2. Какой элемент по умолчанию возвращает `top()` у `std::priority_queue<int>`?

3. Почему возвращение `std::string_view` на локальную `std::string` опасно?

Ассоциативные контейнеры: map, set, unordered_map

Итераторы: связующее звено STL