{L} Noisy #include <algorithm> linclude <iostream> linclude <iterator> linclude <vector> linclude Noisy.h using namespace std;

int mainO { vector<Noisy> v: v.reserve(ll):

cout 11 spaces have been reserved endl: generate n(back inserter(v), 10, NoisyGenO): ostream iterator<Noisy> out(cout. ); cout endl:

copy(v.begin(). v.endO, out):

cout Inserting an element: endl:

vector<Noisy>::iterator it =

V.beginO + v.sizeO / 2: Middle v.insert(it. NoisyO): cout endl:

copy(v.beginO, v.endO. out):

cout \nErasing an element: endl:

Старое значение it использовать нельзя:

it = V.beginO + v.sizeO / 2:

v.erase(it):

cout endl:

copy(v.beginO. v.endO, out): cout endl: ) III:-

При запуске программы становится видно, что вызов reserve() всего лишь резервирует память - конструкторы элементов при этом не вызываются. Вызов generate n() требует основательной работы: при каждом вызове NoisyGen::operator() происходит конструирование объекта, конструирование копии (в векторе) и уничтожение временного объекта. Но если объект вставляется в середину вектора, для сохранения линейности массива вектор должен сдвинуть все следующие элементы на одну позицию. Свободного места в векторе достаточно, поэтому смещение выполняется оператором присваивания (хотя если бы аргумент reserve() был равен 10 вместо И, пришлось бы выделять дополнительную память). При уничтожении элемента функцией erase() оператор присваивания снова используется для смещения всех последующих элементов на одну позицию назад, чтобы занять освободившееся место (обратите внимание: для этого необходимо, чтобы оператор присваивания правильно уничтожал левосторонний объект). После сдвига элементов остается удалить последний элемент массива.

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

довательность элементов (все блоки и порядок их следования отслеживаются контейнером в непрерывной структуре данных). При такой базовой структуре затраты на добавление или удаление элементов с любого конца дека относительно невелики. Вдобавок деку, в отличие от вектора, не приходится копировать и уничтожать объекты при выделении нового блока, поэтому при добавлении заранее неизвестного количества элементов с любого конца контейнера дек работает гораздо эффективнее вектора. Таким образом, вектор оптимален лишь в том случае, если вы хорошо знаете, сколько объектов будет храниться в контейнере. Многие из приведенных ранее программ, использовавших вектор и функцию push back(), более эффективно работали бы с деком. Интерфейс дека незначительно отличается от интерфейса вектора (например, у дека есть функции push front() и pop front(), которых нет у вектора), поэтому переход с вектора на дек в программе осушествляется тривиально. Рассмотрим пример StringVector.cpp; чтобы перевести его на использование дека, достаточно повсюду заменить слово vector словом deque . Следующая программа является модификацией программы StringVector.cpp. Добавлены операции с деком, параллельные операциям с вектором, и сравнительный хронометраж:

: C07:Str1ngDeque.cpp

Модификация StringVector.cpp

linclude <cstddef>

linclude <ctime>

linclude <deque>

linclude <fstream>

linclude <iostream>

linclude <iterator>

linclude <sstream>

linclude <string>

linclude <vector>

linclude ../require.h

using namespace std;

int main(int argc. char* argv[]) ( char* fname = StringDeque.cpp ; if(argc > 1) fname = argv[l]: ifstream in(fname); assure(in. fname): vector<string> vstrings: deque<string> dstrings; string line:

Загрузка данных в вектор: clock t ticks = clockO: while(getline(in. line))

vstri ngs.push back(1i ne): ticks = clockO - ticks: cout Read into vector: ticks endl; To же для дека: ifstream in2(fname): assure(in2. fname); ticks = ClockO: while(getline(in2. line))

dstri ngs.push back(1i ne): ticks = clockO - ticks: cout Read into deque: ticks endl: Теперь сравниваем индексирование:

ticks = clockO:

for(size t i = 0: i < vstrings.sizeO: i++) { ostringstream ss: ss i:

vstrings[i] = ss.strO + : + vstrings[i]:

ticks = clockO - ticks:

cout Indexing vector: ticks endl:

ticks = clockO:

for(size t j = 0: j < dstrings.size(): { ostringstream ss: ss j:

dstringsEj] = ss.strO + : + dstrings[j]:

ticks = clockO - ticks:

cout Indexing deque: ticks endl:

Сравнение перебора

ofstream tmpl( tmpl.tmp ). tmp2( tmp2.tmp ): ticks = clockO:

copy(vstrings.begin(). vstrings.end().

ostreamjterator<string>(tmpl. \n )): ticks = clockO - ticks: cout Iterating vector: ticks endl: ticks = clockO:

copy(dstrings.begin(). dstrings.end(),

ostream iterator<string>(tmp2. \n )): ticks = clockO - ticks: cout Iterating deque: ticks endl: } III:-

После всего, что говорилось о неэффективности включения элементов в вектор из-за перераспределения памяти, можно было бы ожидать радикальных различий между результатами двух тестов. Тем не менее, для текстового файла размером 1,7 Мбайт программа, созданная одним из компиляторов, выдала следующие результаты (не в секундах, а в тактах, зависящих от платформы и компилятора):

Read into vector: 8350 Read into deque: 7690 Indexing vector: 2360 Indexing deque: 2480 Iterating vector: 2470 Iterating deque: 2410

Результаты для другого компилятора и платформы выглядели примерно также. Выходит, все не так уж плохо? Отсюда можно сделать несколько важных выводов.

Мы (программисты и авторы) не всегда точно представляем, какие именно компоненты нащих программ работают недостаточно эффективно.

Эффективность определяется несколькими факторами. В нащем примере затраты на чтение строк и их преобразование к типу string могут существенно превосходить дополнительные затраты, связанные с неоптимальным выбором контейнера.

Вероятно, класс string достаточно хорошо спроектирован в плане эффективности.