Структуры данных STL изнутри: vector, list, deque — когда что выбрать

Введение

Основной цикл статей уже использовал std::vector/QVector без подробного разбора внутреннего устройства — в этой статье разберём, как реализованы основные линейные контейнеры STL изнутри, и какая внутренняя структура определяет, для каких сценариев каждый из них подходит лучше остальных.

Концепция

std::vector хранит элементы в едином непрерывном блоке памяти — это даёт O(1) доступ по индексу (прямое вычисление адреса через смещение) и отличную производительность при последовательном переборе (за счёт локальности данных в кеше процессора), но вставка/удаление в середине требует сдвига всех последующих элементов (O(n)), а рост сверх текущей выделенной емкости требует перевыделения всего блока и копирования всех элементов в новый блок. std::list — двусвязный список, где каждый элемент хранится в отдельном, не обязательно соседнем участке памяти, связанном указателями на предыдущий/следующий элемент — это даёт O(1) вставку/удаление в любом месте при наличии итератора на эту позицию, но O(n) доступ по индексу (нужно пройти по цепочке от начала) и худшую производительность переборов из-за отсутствия локальности данных в памяти. std::deque — компромисс: блочная структура, дающая O(1) доступ по индексу (хотя и менее эффективный, чем у vector, из-за дополнительного уровня индирекции) и эффективную вставку/удаление на обоих концах (в отличие от vector, эффективного только для добавления в конец).

Пример кода

// vector — эффективен для последовательного доступа и добавления в конец
std::vector<int> values;
for (int i = 0; i < 1000000; ++i) {
    values.push_back(i); // амортизированное O(1) — изредка происходит дорогое перевыделение,
                          // но в среднем по всем вызовам — константное время
}
int middle = values[500000]; // O(1) — прямое вычисление адреса по индексу

// Вставка в середину vector — дорогая операция, требующая сдвига
values.insert(values.begin() + 500000, 999); // O(n) — сдвиг ~500000 элементов

// list — эффективен для частой вставки/удаления в произвольных местах
std::list<int> linkedValues = {1, 2, 3, 4, 5};
auto it = linkedValues.begin();
std::advance(it, 2); // O(n) — для list нет прямого доступа по индексу, нужен последовательный проход

linkedValues.insert(it, 999); // O(1) — сама вставка по уже имеющемуся итератору быстрая,
                                // в отличие от vector, не требует сдвига остальных элементов

// Доступ по индексу для list НЕ предусмотрен оператором [] вовсе — только через итераторы

// deque — эффективен при частом добавлении/удалении С ОБОИХ концов
std::deque<int> dequeValues;
dequeValues.push_back(1);   // O(1) — добавление в конец
dequeValues.push_front(0);  // O(1) — добавление В НАЧАЛО — операция, недоступная эффективно для vector!

int first = dequeValues[0]; // O(1) — прямой доступ по индексу, как у vector (хотя и менее эффективный)

Пояснения к коду

Цикл push_back для vector — типичный пример «амортизированной» сложности O(1): большинство вызовов действительно занимают константное время, но изредка (когда текущая выделенная емкость исчерпана) происходит дорогое перевыделение всего блока памяти с копированием всех существующих элементов — в среднем по большому числу вызовов это даёт эффективное O(1), хотя отдельные, редкие вызовы значительно дороже остальных. Сравнение вставки в середину vector (O(n), сдвиг) и list (O(1) при наличии итератора) показывает фундаментальное различие — структура list спроектирована именно для эффективной вставки/удаления за счёт принципиального отказа от прямого доступа по индексу, тогда как vector оптимизирован для обратного случая. deque::push_front явно демонстрирует возможность, недоступную эффективно у vector (добавление в начало vector требует сдвига всех существующих элементов, O(n)), за счёт более сложной, блочной внутренней структуры.

Подводные камни

• Использование std::list «по умолчанию», из ожидания, что связный список — более «гибкая» или «правильная» структура данных без реального анализа паттерна использования — на практике, из-за плохой локальности данных в памяти (каждый элемент в потенциально несвязанном участке памяти, что плохо для кеша процессора), std::list часто медленнее std::vector даже для операций, теоретически «выгодных» для list (вставка в середину), если число элементов не очень велико — std::vector в большинстве реальных, практических сценариев на современном оборудовании оказывается предпочтительным выбором по умолчанию, и std::list стоит выбирать осознанно, для случаев с действительно частыми вставками/удалениями в середину больших коллекций.
• Хранение и повторное использование итераторов vector после операций, потенциально вызывающих перевыделение памяти (push_back, insert, превышающие текущую capacity) — в отличие от list, где итераторы остаются валидными при вставке/удалении других элементов, итераторы vector могут быть инвалидированы при перевыделении внутреннего блока памяти, и использование такого «висячего» итератора — неопределённое поведение, классическая, трудно диагностируемая ошибка.
• Игнорирование reserve() для vector, когда заранее известен или может быть оценен итоговый размер коллекции — без предварительного резервирования емкости vector будет выполнять несколько отдельных перевыделений по мере роста (обычно с удвоением емкости при каждом перевыделении), и явный вызов reserve(expectedSize) до начала заполнения избегает этих промежуточных перевыделений, давая заметный выигрыш производительности для известного наперёд, достаточно большого объёма данных.
• Предположение, что deque всегда строго лучше vector, поскольку поддерживает больше операций (включая эффективный push_front) — deque имеет более сложную, блочную внутреннюю структуру по сравнению с простым непрерывным блоком vector, что обычно делает прямой доступ по индексу и последовательный перебор немного менее эффективными у deque по сравнению с vector; выбор между ними должен основываться на реальной потребности именно в эффективной работе с обоими концами коллекции, а не на абстрактном предположении о превосходстве более «богатого» по возможностям интерфейса.