Developer Tales or everything about everything

14Дек/126

Анализ производительности std::vector, std::list & std::deque

В этой статье рассматривается тестирование производительности стандартных STL-контейнеров C++: std::vector, std::list и std::deque. Тестирование скорости работы контейнеров проводится для операций вставки, поиска и удаления.

Эта статья является переводом, оригинальная статья находится здесь.

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

Однако, теория обычно расходится с практикой: на практике часто используют кэш памяти. Данные в векторе располагаются последовательно, в то время, как данные списка могут быть размещены в разных участках памяти. Что это дает? Двусвязная очередь - это структура, которая нацелена на получение всех преимуществ std::list и std::vector и избежание их недостатков.

Все тесты проводились на Intel Core i7 Q 820 @ 1.73GHz на GCC 4.7.2 с параметрами -02 и -march=native. Код скомпилирован с поддержкой C++11 (-std=c++11).

Во всех графиках вертикальная ось представляет количество времени, требуемое для проведения операций - чем меньше это значение, тем лучше. Горизонтальная ось - это количество элементов в коллекции.

Просмотров: 12097