Контейнеры 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?!
Left DataDog
3 дня назад
Atom feed
4 коммент.:
То есть с точки зрения эффективности изменений это такой перевектор? Или недолист?
А с точки зрения эффективности доступа -- перелист или недовектор?
То есть с точки зрения эффективности изменений это такой перевектор? Или недолист?
Хех, я бы сказала, что это скорее перевектор.
А с точки зрения эффективности доступа -- перелист или недовектор?
Недовектор.
Но это уже что-то вроде гадания на кофейной гуще. Лучше по-нормальному посчитать производительность контейнера в данной реализации STL на данной архитектуре под данную задачу и исходить в выборе контейнера из полученных результатов.
А как же портируемость, если мы будем исходить из характеристик в конкретной реализации stl?
Ещё deque[bool] порой становится альтернативой vector[bool] по ряду причин.
Также deque отличается тем, что ссылки и указатели на его элементы остаются действительными при вставках в конец и начало контейнера. Заметьте, речь о ссылках и указателях, но не об итераторах.
А как же портируемость, если мы будем исходить из характеристик в конкретной реализации stl?
Угу, в случае, если код планируется куда-либо портировать то я бы прогнала тесты на нескольких реализациях. В любом случае, надо исходить из поставленной задачи.
Отправить комментарий