среда, декабря 27, 2006

vector vs deque

Контейнеры vector и deque очень схожи по описанию. Тем не менее, разница между ними есть и весьма существенная. Кроме того, что к deque можно добавлять элементы в начало, он отличается от vector размещением в памяти. vector всегда будет размещаться в памяти последовательно. Благодаря этому он может очень удачно прикидываться простым массивом. И у него есть специфичные функции для работы с этой самой памятью. Из-за последовательного размещения в памяти произвольный доступ к элементам очень быстрый.
А вот deque может быть запросто в памяти сегментирован. Обычно он реализуется как массив массивов. Поэтому доступ к элементам будет помедленнее. Но зато при добавлении элементов не будет возникать тех проблем, что имеют место у vector с выделением последовательных кусков памяти.

Если сравнивать deque с list, то deque занимает меньше памяти чем list. Ну и с произвольным доступом к элементам у list все похуже. Зато list быстрее справляется с удалением и добавлением элементов в произвольное место списка.

Ссылки по теме:
Оценка производительности контейнеров
comp.lang.c++.moderated deque VS vector
comp.lang.c++.moderated What the deque?!

4 коммент.:

Maniac комментирует...

То есть с точки зрения эффективности изменений это такой перевектор? Или недолист?

А с точки зрения эффективности доступа -- перелист или недовектор?

Alena комментирует...

То есть с точки зрения эффективности изменений это такой перевектор? Или недолист?

Хех, я бы сказала, что это скорее перевектор.

А с точки зрения эффективности доступа -- перелист или недовектор?

Недовектор.

Но это уже что-то вроде гадания на кофейной гуще. Лучше по-нормальному посчитать производительность контейнера в данной реализации STL на данной архитектуре под данную задачу и исходить в выборе контейнера из полученных результатов.

Орнитолог комментирует...

А как же портируемость, если мы будем исходить из характеристик в конкретной реализации stl?

Ещё deque[bool] порой становится альтернативой vector[bool] по ряду причин.
Также deque отличается тем, что ссылки и указатели на его элементы остаются действительными при вставках в конец и начало контейнера. Заметьте, речь о ссылках и указателях, но не об итераторах.

Alena комментирует...

А как же портируемость, если мы будем исходить из характеристик в конкретной реализации stl?

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