1. Зачем нужны контейнерные адаптеры
Если честно, первый вопрос новичка здесь абсолютно нормальный: «Почему нельзя просто взять std::vector и делать всё руками? Зачем мне какой-то std::stack?» И это хороший вопрос — в нём чувствуется инженерная подозрительность (а она в программировании спасает чаще, чем кофе).
Ответ примерно такой: иногда нам нужна не «коробка для хранения», а контракт на способ доступа. То есть нам важно не только где лежат элементы, но и какими операациями мы обязаны пользоваться, чтобы алгоритм оставался понятным.
Например, если по смыслу задачи у вас «последнее добавленное действие нужно отменять первым» — это стек. Можно симулировать стек на vector, но адаптер stack делает две полезные вещи: во‑первых, показывает намерение (читатель кода сразу понимает LIFO), во‑вторых, не даёт вам «вдруг» полезть в середину и сломать смысл структуры.
Важно также понимать, что контейнерные адаптеры — это часть стандартной библиотеки, и вокруг них есть отдельные требования и обсуждения на уровне комитета (WG21): например, изменения и уточнения, связанные со stack/queue, периодически попадают в редакторские отчёты и LWG‑обсуждения.
Что такое «контейнерный адаптер» простыми словами
Представьте, что у вас есть склад (контейнер), а вам нужно организовать пункт выдачи с жёсткими правилами. Склад может быть большим, с множеством дверей, но пункт выдачи говорит: «Мы выдаём только через одно окошко». Вот адаптер — это «окошко» с правилами.
Технически идея такая: адаптер хранит внутри некоторый контейнер (обычно deque или vector), но наружу выдаёт ограниченный набор операций. И это ограничение — не недостаток, а фича: оно защищает структуру данных от неправильного использования.
У трёх адаптеров, которые мы сегодня разбираем, есть три «модели поведения»:
- stack — LIFO (last in, first out): последним положили → первым достали.
- queue — FIFO (first in, first out): первым пришёл → первым обслужили.
- priority_queue — «всегда отдавай лучший»: лучший по заданному правилу оказывается сверху.
А теперь важный нюанс, который потом спасает от боли: адаптеры почти всегда не дают итераторов, то есть «пройтись range-for и посмотреть все элементы» нельзя. И снова: это не потому, что разработчики STL забыли, а потому что они сознательно не хотят, чтобы вы делали обход там, где концептуально правильнее «доставать по одному».
2. std::stack: модель LIFO
Когда вы впервые видите стек, он кажется слишком простым: «Ну… это как стопка тарелок». Да, именно так. И в программировании эта «стопка тарелок» встречается постоянно: отмена действий (undo), обработка вложенности (скобки), возврат из функций (стек вызовов — мы про него уже говорили), откат шагов алгоритма.
В интерфейсе std::stack есть главное трио: push(), top(), pop(). Плюс служебные empty() и size(). И вот здесь прячется классическая ловушка новичка: pop() ничего не возвращает. Это сделано намеренно: чтобы вы не провоцировались писать код, который случайно использует удалённый элемент. Поэтому правило такое: сначала top(), потом pop().
Мини‑пример: стек чисел
#include <stack>
#include <iostream>
int main() {
std::stack<int> st;
st.push(10);
st.push(20);
std::cout << st.top() << '\n'; // 20
st.pop();
std::cout << st.top() << '\n'; // 10
}
Обратите внимание: если вы попытаетесь сделать int x = st.pop();, компилятор будет праведно возмущаться, потому что pop() — это void.
Безопасность: сначала empty()
Если стек пустой, top() — это уже «выход за контракт». В STL это обычно приводит к неопределённому поведению (или к падению, или к странностям — то есть к классике жанра «работало же вчера»).
#include <stack>
#include <iostream>
int main() {
std::stack<int> st;
if (!st.empty()) {
std::cout << st.top() << '\n';
st.pop();
} else {
std::cout << "Stack is empty\n"; // Stack is empty
}
}
3. std::queue: модель FIFO
Очередь в жизни — вещь неприятная, но в коде она часто делает поведение системы понятным. FIFO особенно полезна, когда у вас есть «входящие события» и «обработка в порядке поступления»: запросы пользователя, задания на печать, сообщения от сети (это мы будем обсуждать сильно позже, но очередь как структура данных — уже сейчас).
Интерфейс std::queue устроен так, чтобы вы думали о двух концах: в «хвост» добавляем (push()), из «головы» забираем (front() + pop()). Для отладки или редких сценариев можно смотреть back() — кто последний в очереди.
И снова важное: pop() ничего не возвращает — по тем же причинам безопасности, что и у стека.
Мини‑пример: очередь строк
#include <queue>
#include <string>
#include <iostream>
int main() {
std::queue<std::string> q;
q.push("first");
q.push("second");
std::cout << q.front() << '\n'; // first
q.pop();
std::cout << q.front() << '\n'; // second
}
«Снять элемент» правильно: два шага
Вот шаблон, который стоит запомнить как жест:
#include <queue>
int main() {
std::queue<int> q;
q.push(7);
if (!q.empty()) {
int x = q.front();
q.pop();
(void)x;
}
}
Если вы делаете обработчик «пока очередь не пуста» — этот паттерн становится вашим лучшим другом.
4. std::priority_queue: очередь с приоритетом
После FIFO очередь с приоритетом сначала кажется читерством: «Почему этот пролез без очереди?» Потому что у него приоритет. В коде это встречается в планировщиках задач, обработке событий «срочно», выборе следующей работы для выполнения, иногда в алгоритмах (например, где нужно постоянно брать минимальный/максимальный элемент).
std::priority_queue — тоже адаптер: он скрывает внутренности и даёт вам «добавь элемент» и «дай лучший элемент». Под «лучшим» обычно понимается максимальный (по умолчанию сверху максимум). Важно: это не означает, что вся структура «полностью отсортирована». Гарантия — только про top().
Тема priority_queue регулярно всплывает в обсуждениях стандартной библиотеки (например, через вопросы к конструкторам и спецификациям), что подчёркивает: структура популярная, важная и не совсем тривиальная внутри.
Мини‑пример: по умолчанию сверху максимум
#include <queue>
#include <iostream>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(42);
std::cout << pq.top() << '\n'; // 42
pq.pop();
std::cout << pq.top() << '\n'; // 10
}
«Сверху минимум»: меняем правило
В стандартной библиотеке есть готовый компаратор std::greater<T>. С ним «лучшим» становится минимальный (потому что правило сравнения меняется).
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(10);
pq.push(5);
pq.push(42);
std::cout << pq.top() << '\n'; // 5
}
Синтаксис выглядит «страшнее», чем смысл. Тут просто написано: храним int, внутри используем vector<int>, а «кто лучше» определяем через greater<int>.
5. Полезные нюансы и визуальные модели
Шпаргалка: stack vs queue vs priority_queue
Когда конструкций становится много, мозг начинает требовать шпаргалку. Это нормально: мозг не обязан помнить всё, он обязан уметь быстро восстановить.
| Адаптер | Модель | Как добавляем | Как смотрим следующий | Как удаляем следующий | Можно ли пройтись по всем? |
|---|---|---|---|---|---|
|
LIFO | |
|
|
Нет (итераторов нет) |
|
FIFO | |
|
|
Нет (итераторов нет) |
|
«лучший сверху» | |
|
|
Нет (итераторов нет) |
Заметьте, что у всех трёх есть общее правило безопасности: перед top()/front() стоит подумать, не пусто ли (empty()), потому что эти функции предполагают «элемент существует».
Почему у адаптеров нет итераторов
На первых порах отсутствие итераторов раздражает. Очень хочется написать for (auto x : st) и посмотреть содержимое. Но в этом и педагогический смысл контейнерных адаптеров: они заставляют вас мыслить операциями, а не «просто коллекцией».
Стек и очередь хороши именно тогда, когда вам не нужно заглядывать внутрь произвольно. Если вам всё время хочется «посмотреть середину» или «удалить третий элемент» — это сигнал, что модель данных выбрана неверно: возможно, вам нужен обычный контейнер (deque, vector, list) или другая структура.
Иногда люди «обходят» адаптеры: делают копию и вынимают по одному, печатая элементы. Это допустимо для отладки, но в рабочем коде часто означает, что структура используется не по назначению. К тому же копирование может быть дорогим, а главное — вы теряете чёткость: читателю приходится понимать, что за «фокус» вы сейчас делаете и зачем.
Маленькие схемы: LIFO и FIFO
Чтобы закрепить модель, полезно один раз увидеть это как поток действий, а не как «методы из учебника».
flowchart LR
A[push 1] --> B[push 2] --> C[push 3]
C --> D[pop -> 3]
D --> E[pop -> 2]
E --> F[pop -> 1]
Это стек: пришли 1,2,3 — ушли 3,2,1.
flowchart LR
A[push 1] --> B[push 2] --> C[push 3]
C --> D[pop -> 1]
D --> E[pop -> 2]
E --> F[pop -> 3]
Это очередь: пришли 1,2,3 — ушли 1,2,3.
А вот priority_queue отличается тем, что порядок «ухода» зависит от правила «кто лучше». Если правило — «больше число лучше», то уйдут 42, потом 10, потом 5 (как в примере выше). При другом компараторе уйдут иначе.
6. Мини‑диспетчер задач: пример применения адаптеров
Чтобы адаптеры не остались «в вакууме», давайте продолжим линию учебного приложения. Допустим, у нас есть простой консольный диспетчер задач. Раньше мы могли хранить задачи в std::vector, искать, сортировать и так далее. А сегодня добавим три жизненные фичи: undo, очередь входящих задач, очередь срочных задач. Это реалистично и хорошо показывает, почему адаптер — это «контейнер + намерение».
Предположим, задача выглядит так (мы уже знакомы со struct из прошлых дней):
#include <string>
struct Task {
std::string title;
int priority = 0; // больше = важнее
};
Undo как stack: отменяем последнее действие
Undo логично делать стеком: последнее изменение — первое отменяемое.
#include <stack>
#include <string>
struct Action {
std::string description;
};
int main() {
std::stack<Action> undo;
undo.push({"Added task 'Buy milk'"});
undo.push({"Deleted task 'Read book'"});
Action last = undo.top();
undo.pop();
(void)last;
}
Да, здесь действие пока «игрушечное» (просто текст). Но смысл виден: вы не «просматриваете историю», вы снимаете её слой за слоем.
Входящие задачи как queue: обрабатываем по порядку поступления
Если задачи приходят как события (например, пользователь быстро добавил несколько пунктов), мы можем поставить их в FIFO‑очередь на обработку.
#include <queue>
#include <string>
struct Task {
std::string title;
int priority = 0;
};
int main() {
std::queue<Task> inbox;
inbox.push({"Wash dishes", 1});
inbox.push({"Pay bills", 2});
Task t = inbox.front();
inbox.pop();
(void)t;
}
Срочные задачи как priority_queue: всегда берём самую важную
Если у нас есть «обычные» и «срочные» — удобно держать срочные отдельно. Для начала пусть «сверху максимум priority». Тогда нужен компаратор.
#include <queue>
#include <vector>
#include <string>
struct Task {
std::string title;
int priority = 0;
};
struct ByPriority {
bool operator()(const Task& a, const Task& b) const {
return a.priority < b.priority; // у кого priority больше, тот "лучше"
}
};
int main() {
std::priority_queue<Task, std::vector<Task>, ByPriority> urgent;
urgent.push({"Fix prod bug", 100});
urgent.push({"Refactor code", 10});
Task best = urgent.top();
urgent.pop();
(void)best;
}
Здесь важно не столько запомнить priority_queue<...> целиком, сколько уловить идею: «внутри лежит контейнер, сверху торчит интерфейс, а правило “кто лучше” — это часть типа».
7. Типичные ошибки при работе с stack/queue/priority_queue
Ошибка №1: ожидать, что pop() возвращает значение.
После vector::pop_back() новички иногда по инерции пытаются написать x = pop(). У адаптеров stack/queue/priority_queue метод pop() возвращает void. Правильный паттерн всегда двухшаговый: сначала top() или front(), потом pop(). Если вы перепутаете, компилятор вас остановит, но лучше сразу держать эту привычку, чтобы код читался предсказуемо.
Ошибка №2: вызывать top()/front() на пустом адаптере.
Адаптеры не обязаны вас «спасать» в рантайме. Если структура пуста, обращение к top() или front() — это нарушение контракта. Поэтому либо вы проверяете empty(), либо проектируете код так, чтобы пустота была невозможна по логике (и это прямо видно из контекста).
Ошибка №3: пытаться обойти адаптер range-for’ом и “посмотреть всё”.
У stack, queue, priority_queue нет итераторов — и это часть идеи. Если вам постоянно нужен обход, значит вам нужен другой контейнер, или вам нужна дополнительная структура для просмотра/логирования. Попытки «достать внутренний контейнер» ради обхода обычно превращают код в хрупкий трюк, который сложно поддерживать.
Ошибка №4: использовать адаптер там, где нужен произвольный доступ или удаление “из середины”.
Стек и очередь — это структуры с очень конкретной философией. Если ваша бизнес‑логика требует «удали элемент по индексу» или «вставь между вторым и третьим», то адаптер будет только мешать. В такой ситуации лучше честно выбрать vector/deque/list и работать с ними напрямую, вместо того чтобы воевать с интерфейсом, который специально сделан “узким”.
Ошибка №5: неверно понимать компаратор у priority_queue и удивляться “почему сверху не то”.
У priority_queue компаратор задаёт правило, по которому определяется “лучший” элемент. Если вы перепутаете знак сравнения, то у вас сверху окажется не самый важный, а самый неважный — и это особенно неприятно, потому что код будет компилироваться и работать, просто «странно». Поэтому компаратор стоит писать максимально прямолинейно и проверять на маленьком примере с 2–3 элементами, как в наших мини‑фрагментах.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ