1. Введение
Когда начинаешь программировать, очень хочется верить в сказку: «есть один контейнер, который быстрый, удобный и всегда правильный». В реальности стандартная библиотека C++ — как набор кухонных ножей: один идеально режет хлеб, другой — мясо, а третий вообще штопор (и да, им тоже можно резать, но потом придётся объяснять следователю). Сегодня мы сравним три последовательных контейнера и научимся задавать правильный вопрос: какие операции в моём сценарии самые частые.
Мы будем говорить про последовательные контейнеры — такие, где элементы идут в определённом порядке (первый, второй, третий…), но внутри памяти они устроены по‑разному. В C++ к ним относятся, например, std::vector, std::deque, std::list (и ещё другие, но сегодня — ровно эти три). В стандарте эти контейнеры фигурируют как отдельные «семейства» с собственной спецификацией.
Чтобы не потеряться, зафиксируем главную «идею дня»: выбор контейнера — это выбор компромисса. Где-то вы выигрываете на вставках, где-то — на обходе, где-то — на доступе по индексу. А бесплатно бывает только сыр в мышеловке, и то — не для мыши.
2. std::vector: быстрый, пока не вставляешь в начало
std::vector обычно становится «контейнером по умолчанию» (и это нормально). Он очень дружелюбен к процессору: элементы лежат подряд в памяти, поэтому обход по всем элементам часто получается быстрым на практике. Но у vector есть и характерная слабость: когда вы вставляете/удаляете элементы в начале или в середине, ему приходится «сдвигать хвост», как если бы вы в Excel вставили строку наверх и вся таблица поехала вниз.
Интуиция про vector
У std::vector<T> внутри есть один большой «кусок памяти» под элементы T. Из этого рождаются два ключевых свойства.
Первое — быстрый доступ по индексу: v[i] обычно работает очень быстро, потому что «i‑й элемент» можно вычислить как «начальный адрес + i * sizeof(T)».
Второе — рост. Когда vector переполняется, ему иногда приходится выделить новый (обычно больший) кусок памяти и перенести туда все элементы. В предыдущих темах вы уже видели reserve() как способ уменьшить число таких дорогих шагов.
Небольшая визуализация (очень упрощённо):
flowchart LR A["vector: один непрерывный блок"] --> B["[0][1][2][3][4]..."]
Мини‑пример: индекс и быстрый обход
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{10, 20, 30};
std::cout << v[1] << '\n'; // 20
}
Этот пример кажется слишком простым, но в нём главное: vector действительно задуман как «динамический массив» — индексирование естественно и удобно.
Мини‑пример: вставка в начало
#include <vector>
int main() {
std::vector<int> v{2, 3, 4};
v.insert(v.begin(), 1); // элементы "сдвигаются" вправо
}
Мы пока не углубляемся в детали стоимости и «что будет с итераторами/ссылками» — это следующая лекция дня. Сейчас достаточно запомнить ощущение: insert ближе к началу у vector — потенциально дорогая операция, потому что нужно «подвинуть» элементы.
3. std::deque: операции на двух концах
Если vector — это коридор с одной дверью (удобно добавлять в конец), то deque — это коридор с дверью и спереди, и сзади. Название буквально так и читается: double‑ended queue. Он отлично подходит, когда вы хотите часто добавлять и удалять элементы на обоих концах: push_front, push_back, pop_front, pop_back.
При этом deque, в отличие от list, всё ещё умеет доступ по индексу d[i]. Но внутренне это обычно устроено не как один сплошной блок, а как набор блоков (мы упрощаем, но полезную картинку вы должны унести).
Упрощённая схема:
flowchart LR A["deque: блоки"] --> B["[ ][ ][ ]"] A --> C["[ ][ ][ ]"] A --> D["[ ][ ][ ]"]
Зачем deque, если есть vector
Потому что в vector «быстро добавлять в начало» — это боль, а deque для этого и создан. В реальных задачах часто встречается сценарий «очередь задач», «буфер сообщений», «история последних событий», где естественно работать с двумя концами.
Мини‑пример: операции на обоих концах
#include <deque>
#include <iostream>
int main() {
std::deque<int> d{2, 3};
d.push_front(1);
d.push_back(4);
std::cout << d.front() << ' ' << d.back() << '\n'; // 1 4
}
Здесь нет никакой магии — просто ключевая роль deque: два конца работают как «родные».
Важное уточнение
deque не обязан быть «улучшенным vector». Это отдельный компромисс. Как правило, он жертвует частью «идеальной непрерывности памяти» ради удобства операций на обоих концах. Детально влияние памяти на скорость мы обсудим в финальной лекции дня, но уже сейчас можно помнить фразу: deque часто “про удобство концов”, а vector — “про плотность данных”.
4. std::list: узлы и работа по позициям
std::list — это двусвязный список. Представьте бусы: каждый элемент — отдельная бусина (узел), и у каждой бусины есть ссылка на предыдущую и следующую. В отличие от vector и deque, элементы списка не обязаны лежать подряд в памяти. Это называется узловой (node‑based) контейнер: каждый узел обычно выделяется отдельно.
Схема на пальцах:
flowchart LR A["[10]"] <--> B["[20]"] <--> C["[30]"]
Чем list отличается от vector и deque
Главная «психологическая» разница такая: list — это не про индексы, а про позиции.
У std::list нет operator[]. И это не потому, что авторы STL «забыли добавить», а потому, что сама идея «быстро взять i‑й элемент» плохо сочетается со списком: чтобы добраться до i‑го, нужно пройти по ссылкам i шагов.
Зато у list есть сильная сторона: вставка/удаление в известной позиции (когда у вас уже есть итератор) обычно не требует сдвига всех остальных элементов. Опять же, сегодня мы держим это на уровне интуиции: «не двигаем хвост» — это смысл.
Мини‑пример: вставка по итератору
#include <list>
#include <iostream>
int main() {
std::list<int> lst{10, 30};
auto it = lst.begin();
++it; // позиция на 30
lst.insert(it, 20); // вставили 20 перед 30
for (int x : lst) {
std::cout << x << ' ';
}
std::cout << '\n'; // 10 20 30
}
Итератор здесь — это «маркер позиции». Список особенно хорош, когда вы часто работаете «внутри» последовательности, и для вас важнее быстро вставлять/удалять по месту, чем быстро индексировать.
Ловушка мышления про O(1) вставку
Новичок часто слышит: «в list вставка O(1)» и делает вывод: «значит, list всегда лучше для вставок». Но это половина правды. Вставка может быть быстрой, если вы уже знаете место (у вас есть итератор). А вот «найти место» — отдельная часть стоимости, которая часто требует линейного прохода.
Сегодня мы просто запомним формулу:
“найти позицию” + “вставить в позицию” = две разные задачи.
list ускоряет вторую часть, но не обязан ускорять первую.
5. Как выбирать контейнер: сравнение и мини‑сценарии
Сравнительная таблица
Когда вы в следующий раз будете выбирать контейнер, полезно иметь перед глазами небольшую «карту местности». Сейчас мы сделаем её максимально практичной: не как табличку из стандарта, а как шпаргалку разработчика, который уже один раз пытался сделать очередь на vector и потом долго смотрел в потолок.
| Операция / свойство | |
|
|
|---|---|---|---|
| Доступ по индексу c[i] | Да, сильная сторона | Да, обычно нормально | Нет, концептуально “не его” |
|
Обычно очень хорошо | Хорошо | Хорошо, но не главная причина выбора |
|
Обычно плохо (сдвиги) | Сильная сторона | Хорошо |
| Вставка/удаление в середине | Обычно дорого (сдвиги) | Обычно тоже не подарок | Обычно хорошо, если позиция уже найдена |
| Линейный обход “все элементы подряд” | Обычно очень быстрый | Обычно неплохо, но менее “плотно” | Часто медленнее из-за разрозненных узлов |
| Тип мышления | “массив + рост” | “очередь с двумя концами” | “позиции‑итераторы, узлы” |
Эта таблица — не “математика на века”, а рабочее приближение. Но оно очень помогает не выбирать контейнер «по настроению». И да, стандартная библиотека явно выделяет deque, list, vector как отдельные контейнеры со своей спецификацией и «семействами» операций.
Мини‑сценарии из TaskKeeper
До этого момента курса мы условно развивали консольное приложение TaskKeeper: храним задачи, печатаем список, фильтруем, сортируем, ищем по условиям. В реальности для большинства таких задач std::vector<Task> — отличный выбор, и вы не обязаны усложнять себе жизнь только потому, что “в C++ есть ещё контейнеры”.
Но есть ситуации, когда другой контейнер звучит естественнее. Давайте посмотрим на три мини‑сценария. Здесь наша цель — не переписать приложение, а научиться узнавать ситуации.
Для примеров введём простейшую модель задачи:
#include <string>
struct Task {
int id{};
std::string title;
};
Сценарий A: “список задач” — чаще всего vector
Если вы чаще всего делаете “показать все задачи”, “отсортировать”, “пройтись циклом и распечатать”, “найти по условию”, то vector обычно остаётся самым простым и быстрым вариантом. В такой задаче вам важны компактность и удобство алгоритмов.
#include <iostream>
#include <vector>
int main() {
std::vector<int> ids{101, 102, 103};
for (int id : ids) {
std::cout << id << ' ';
}
std::cout << '\n'; // 101 102 103
}
Ключевой момент: линейный обход в vector — это “родной сценарий”. Вы чаще всего будете делать именно его.
Сценарий B: “очередь событий” — просится deque
Представьте, что мы добавили в TaskKeeper обработку событий интерфейса: пользователь вводит команды, а мы хотим хранить “очередь команд на выполнение” так, чтобы иногда добавлять срочную команду “вперёд очереди”. Это уже похоже на работу с двумя концами.
#include <deque>
#include <iostream>
#include <string>
int main() {
std::deque<std::string> q;
q.push_back("load");
q.push_front("help"); // срочно показать help
std::cout << q.front() << '\n'; // help
}
Идея простая: deque удобен, когда “спереди тоже жизнь”, а не только хвост.
Сценарий C: “активные задачи и перестановки” — возможен list
Допустим, у нас есть очередь “активных задач”, и мы часто перемещаем задачу из середины куда‑то ещё (например, переносим в конец, потому что задача “заблокировалась”). Если у нас уже есть итератор на нужную задачу, список может оказаться удобным из‑за работы “по позициям”.
#include <list>
#include <iostream>
int main() {
std::list<int> active{1, 2, 3};
auto it = active.begin();
++it; // указывает на 2
active.erase(it); // убрали 2
std::cout << active.front() << '\n'; // 1
}
Обратите внимание: мы пока не обсуждаем “что будет с итераторами” и “какие гарантии у кого”. Это следующая лекция дня. Здесь важна сама модель: список — это контейнер, где естественно мыслить итераторами‑позициями, а не индексами.
6. Типичные ошибки
Ошибка №1: выбирать std::list, потому что “там вставка O(1)”, и ожидать ускорения всего приложения.
Это частая ловушка: звучит научно, выглядит убедительно, а потом оказывается, что вы всё равно делаете линейный поиск нужного места, просто теперь ещё и обход стал менее дружелюбным к памяти. Правильнее разделять задачу на две части: сначала понять, как вы находите позицию, и только потом думать, как вы вставляете.
Ошибка №2: пытаться обращаться к std::list по индексу, как к массиву.
Иногда рука сама пишет lst[i], потому что “ну я же хочу третий элемент”. У list нет operator[], и это честное предупреждение от STL: контейнер не создан для “третий элемент за O(1)”. Если вам нужен индекс — почти наверняка vector или deque будет ближе по смыслу.
Ошибка №3: считать std::deque “тем же vector, только круче”.
deque действительно умеет индексацию и добавление в конец, но его ключевая роль — эффективные операции на обоих концах. Если ваш сценарий — “много читаем подряд, редко меняем”, то vector часто проще и предсказуемее. deque стоит доставать, когда вам реально нужен push_front/pop_front.
Ошибка №4: пытаться оптимизировать контейнер “на всякий случай”, не имея профиля операций.
Очень хочется выбрать “самый правильный” контейнер заранее, но правильный контейнер зависит от того, что вы делаете чаще всего: обход, вставки, доступ по индексу, работа с концами. Поэтому здоровый порядок мыслей такой: сначала выписываем типовые операции, потом выбираем контейнер под эти операции, и только потом думаем про тонкости.
Ошибка №5: смешивать модели мышления: хранить данные как в vector, а работать как со списком.
Например, делать много вставок в начало vector в цикле и удивляться, почему стало медленно. Контейнеры очень “воспитывают”: если работать против их природы, они начинают мстить (тихо, без предупреждений, просто медленнее).
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ