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

Преобразования контейнеров

Иногда в разных точках программы нужно обеспечить поведение или показатели эффективности, соответствующие разным типам контейнеров. Например, при включении объектов в контейнер требуется эффективность дека, а при их индексировании - эффективность вектора. У всех основных последовательных контейнеров (вектора, дека и списка) имеется конструктор, которому при вызове передаются два итератора (указывающие на начало и конец интервала, элементы которого образуют новый объект), и функция assign() для загрузки данных в существующий контейнер. Это позволяет легко перемещать объекты из одного последовательного контейнера в другой.

В следующем примере объекты загружаются в дек, который затем преобразуется в вектор:

: C07:DequeConversion.cpp {-Ьог}

Загрузка данных в дек с последующим преобразованием в вектор

{L} Noisy

linclude <algorithm>

linclude <cstdlib>

linclude <deque>

linclude <iostream>

linclude <iterator>

linclude <vector>

linclude Noisy.h

using namespace std:

int main(int argc. char* argv[]) { int size = 25:

1f(argc >- 2) size = atoi(argv[l]); deque<Noisy> d:

generate n(back inserter(d). size. NoisyGenO): cout \n Converting to a vector(l) endl: vector<Noisy> vKd.beginO, d.endO): cout \n Converting to a vector(2) endl: vector<Noisy> v2: v2.reserve(d.size()): v2.assigned.beginO. d.endO): cout \n Cleanup endl: } III:-

Размеры контейнера могут быть разными, это ничего не изменит - объекты просто создаются в новых векторах копирующим конструктором. Интересно другое: независимо от количества элементов память для vl выделяется только один раз. Может показаться, что для vl, как и для v2, следовало бы заранее выделить память, чтобы предотвратить нежелательные многократные ее перераспределения. Но в действительности это не нужно, поскольку использованный при создании vl конструктор заранее определяет необходимый объем памяти.

Издержки на перераспределение памяти

Интересно посмотреть, что происходит с деком при переполнении выделенной памяти, и сравнить с программой VectorOverflow.cpp:

: C07:DequeOverflow.cpp {-bor}

При включении большого количества элементов

с конца контейнера дек работает гораздо

эффективнее вектора, поскольку он не требует

копирования и уничтожения элементов.

#include <cstd11b>

#include <deque>

finclude Noisy.h

using namespace std:

int mainCint argc. char* argv[]) ( int size = 1000:

ifCargc >= 2) size = atoi(argv[l]): deque<Noisy> dn: Noisy n:

forCint i = 0: i < size: i++)

dn.push back(n): cout \n cleaning up endl: } III:-

Ha этот раз перед появлением завершающей надписи cleaning up сообщения о вызове деструкторов практически не выводятся. Поскольку память для дека выделяется несколькими блоками (вместо одного непрерывного блока, как для вектора), деку не приходится перемещать данные между блоками, а следовательно, отпадает необходимость в лишнем конструировании копий и уничтожении элементов. По той же причине дек обеспечивает эффективную вставку элементов в начало контейнера, поскольку при нехватке памяти он просто выделяет новый блок для начальных элементов (разве что может потребоваться заново выделить память для индексного блока, связывающего блоки данных). С другой стороны, вставка в середину дека выполняется не так тривиально, как для векторов (хотя и с меньшими затратами).

Благодаря разумной схеме управления памятью в деках включение новых элементов в начало или конец контейнера не аннулирует существующие итераторы, как в случае векторов (см. пример VectorCoreDump.cpp). Если вы будете ограничиваться теми операциями, которые выполняются деком с наибольшей эффективностью (вставка и удаление элементов с обоих концов, достаточно быстрый перебор и индексирование), дек вас не подведет.

Проверка границ при произвольном доступе

в векторах и деках определены две функции произвольного доступа: оператор индексирования [ ] и функция at(), которая проверяет границы индексируемого контейнера и запускает исключение при их нарушении. Вызов at() обходится дороже простого индексирования:

: C07:Indexing\/sAt.cpp

Сравнение функции atO с оператором []

#include <ctime>

#include <deque>

#include <iostream>

#1 ncl ude <vector> linclude ../require.h using namespace std;

int mainCint argc. char* argv[]) { long count = 1000: int sz = 1000:

if(argc >= 2) count = atoi(argv[l]); if(argc >= 3) sz = atoi(argv[2]): vector<int> vi(sz): clock t ticks = clockO: for(int il =0: il < count; il++) for(int j = 0; j < sz: j++) vi[j];

cout vector[] clockO - ticks endl: ticks = ClockO:

for(int i2 =0: i2 < count: i2++) for(int J = 0: j < sz: j++) vi.at(j):

cout vector: :at() clockO-ticks endl: deque<int> di(sz): ticks = ClockO;

for(int i3 =0; i3 < count: i3++) for(int j = 0: j < SZ; j++) di[j];

cout deque[] clockO - ticks endl: ticks = ClockO:

for(int i4 =0: i4 < count; i4++) for(int j = 0: j < sz: j++) di.at(j):

cout deque: :atO clockO-ticks endl; Поведение atO при нарушении границ контейнера: try {

di .at(vi .SizeO + 1): } catch(...) { cerr Exception thrown endl:

} /:-

Как было показано в главе 1, в разных системах неперехваченные исключения обрабатываются по-разному. И все же при использовании функции at() вы хотя бы узнаете о возникших проблемах, тогда при использовании оператора [ ] можно остаться в неведении.

Список

Контейнер list реализуется в виде двусвязного списка. Такая реализация обеспечивает быструю вставку и удаление элементов в любой позиции, тогда как у векторов и деков эта операция обходится гораздо дороже. С другой стороны, произвольный доступ к элементам в списке выполняется настолько медленно, что у него даже нет оператора [ ]. Списки лучше всего использовать при последовательном переборе элементов от начала к концу контейнера (или наоборот) вместо случайного выбора элементов из середины. Впрочем, даже последовательный перебор в списках может работать медленнее, чем в векторах, но при относительно небольшом объеме перебора это не станет узким местом программы.