В работе экспериментально сравнили время выполнения операций для динамического массива (std::vector) и двусвязного списка (std::list) при разных размерах последовательности.
1. Вставка в конец (push_back). У обеих структур время растёт примерно линейно, что соответствует амортизированной сложности O(1) на одну вставку. При этом вектор работает в 7–14 раз быстрее: при n = 200 000 получилось 495 мкс у вектора и 6792 мкс у списка. Вектор хранит данные в одном непрерывном блоке и лишь изредка перевыделяет память, увеличивая ёмкость в разы. Список при каждой вставке выделяет память под новый узел, а это дорогая операция. Отдельные всплески на графике списка (например, 6284 мкс при n = 90 000) объясняются работой менеджера памяти и фоновой нагрузкой системы.
2. Обход элементов. Обе операции имеют сложность O(n), и время растёт линейно. Но обход списка примерно в 4 раза медленнее: при n = 200 000 вышло 269 мкс у вектора и 1066 мкс у списка. Так получается из-за устройства памяти:
• Элементы вектора лежат подряд. Процессор загружает их в кэш целыми строками, а аппаратная предвыборка подгружает следующие данные заранее.
• Узлы списка разбросаны по памяти, и каждый переход по указателю может вызвать промах кэша.
• Узел списка занимает больше места (значение плюс два указателя), поэтому в кэш помещается меньше полезных данных.
Значит, одинаковая асимптотическая сложность не гарантирует одинакового времени работы: O-нотация не учитывает константы и работу кэша.
3. Вставка в начало (push_front). Здесь список значительно эффективнее. При увеличении размера в 15 раз (с 2000 до 30 000) время вектора выросло примерно в 265 раз (со 146 до 38 780 мкс), то есть квадратично, O(n²). Время списка выросло примерно в 17 раз (с 71 до 1197 мкс), то есть линейно. Каждая вставка в начало вектора сдвигает все уже имеющиеся элементы, а у списка она сводится к созданию узла и переназначению указателей, O(1). При n = 30 000 список быстрее примерно в 32 раза.
4. Сортировка. Обе встроенные сортировки имеют сложность O(n log n), и графики растут чуть быстрее линейного. Сортировка вектора (std::sort) оказалась в 1,4–1,9 раза быстрее, чем list.sort(): при n = 50 000 получилось 2765 мкс против 5138 мкс. std::sort использует произвольный доступ к элементам и непрерывное расположение данных. Сортировка слиянием в списке выполняет много переходов по указателям между разбросанными в памяти узлами.
Общий вывод. std::vector выигрывает при вставке в конец, обходе и сортировке благодаря непрерывному хранению данных и эффективному использованию кэша. std::list оправдан там, где нужны частые вставки и удаления в начале или середине последовательности. В остальных случаях предпочтительнее вектор.
