Откуда берётся преимущество std::vector над std::list при последовательном обходе, если сложность обхода у обоих O(n)?
std::vector обычно быстрее при последовательном обходе благодаря непрерывному размещению элементов в памяти. Процессор эффективнее использует кэш и аппаратную предвыборку, а обращение к следующему элементу не требует разыменования указателя на отдельный узел. Асимптотическая сложность у обоих контейнеров остаётся O(n), но константные затраты существенно различаются.
std::vector и std::list решают разные задачи. Вектор представляет собой динамический массив с непрерывным диапазоном объектов, а список хранит элементы в отдельных узлах, связанных указателями.
Такое разделение позволяет выбрать компромисс между быстрым последовательным доступом и стабильностью адресов элементов при модификациях. Поэтому асимптотика операции не описывает полностью её практическую производительность.
При обходе std::vector процессор загружает из памяти сразу участок, содержащий несколько соседних элементов. Для std::list следующий узел может находиться далеко от текущего, поэтому каждый переход часто приводит к дополнительному обращению к памяти и плохо предсказывается аппаратной предвыборкой.
Неверно делать вывод, что одинаковая сложность означает одинаковое время работы. На больших объёмах данных список может значительно проигрывать из-за промахов кэша, разыменования указателей и затрат на размещение узлов.
Элемент std::vector расположен рядом со своими соседями. Последовательный итератор фактически перемещается по непрерывному массиву, поэтому чтение хорошо использует кэш-линии процессора. Кроме того, вектор не требует отдельного указателя для перехода к следующему элементу.
Узел std::list обычно содержит сам элемент и ссылки на соседние узлы. Итератор приращивается переходом по указателю, а адрес следующего узла заранее неизвестен. Это создаёт pointer chasing: процессор не может так же эффективно загружать будущие данные наперёд.
У списка есть дополнительные расходы: отдельное выделение памяти для узлов, служебные указатели и возможная фрагментация кучи. Они не меняют оценку O(n), но увеличивают константу времени и потребление памяти.
Преимущество вектора не абсолютно. Если элементы очень крупные, обход может быть ограничен пропускной способностью памяти. Если во время работы критичны вставки и удаления при уже известной позиции, стабильность итераторов и отсутствие перемещения объектов могут сделать std::list подходящим выбором, несмотря на более медленный обход.
Сервис обрабатывает несколько миллионов записей: контейнер заполняется пакетами, затем записи последовательно фильтруются и агрегируются. Рассматривались std::vector и std::list.
std::list упрощает вставки в известные позиции и сохраняет адреса элементов при большинстве операций, но платит за это разрозненным размещением памяти, служебными указателями и плохой локальностью. std::vector требует учитывать перевыделение при росте, зато поддерживает компактное хранение и быстрый последовательный обход.
Был выбран std::vector с предварительным резервированием достаточной ёмкости. Это сохранило непрерывное размещение, уменьшило число перевыделений и ускорило основной этап обработки. Список имел бы смысл только при действительно частых вставках или удалениях в середине, когда позиция уже известна и стоимость перемещения элементов вектора доминирует.
Нет. reserve предотвращает перевыделения до достижения указанной ёмкости, но не создаёт дополнительного преимущества вместо непрерывного хранения: сама структура std::vector и так остаётся непрерывной. Предварительное резервирование лишь снижает стоимость роста и риск инвалидировать итераторы из-за перевыделения.
Нет. Вставка в список имеет константную сложность только после получения итератора на нужную позицию. Поиск этой позиции последовательным обходом занимает O(n) и обычно страдает от плохой локальности. В векторе поиск позиции может быть быстрым, но сдвиг элементов после неё занимает O(n); фактический выбор зависит от частоты операций, размера объектов и доминирующей части нагрузки.
Да, но причина будет не в худшей асимптотике. Вектор хранит сами крупные объекты подряд, поэтому при чтении только небольшого поля каждого объекта он может загружать много ненужных данных. В такой ситуации иногда применяют хранение объектов отдельно, массивы структурированных полей или контейнер указателей; однако указатели возвращают часть затрат на разыменование и ухудшают локальность, поэтому решение нужно проверять измерениями.