C++. Сборник рецептов

оператора присвоения. Это очень важно из-за семантики копирования vector — если конструктор копирования или присвоение объектов не работает, то результаты, получаемые из vector, могут отличаться от того, что в него помещалось. А это плохо.

После добавления некоторого набора объектов в vector его буфер заполняется, и для добавления новых объектов его требуется увеличить. Алгоритм увеличения размера зависит от реализации, но обычно буфер размера n увеличивается до 2n+1. Важным здесь является то, как vector увеличивает свой буфер. Вы не можете просто сказать операционной системе неопределенно увеличить свой фрагмент памяти кучи. Требуется запросить новый фрагмент, который больше уже имеющегося. В результате процесс увеличения размера буфера выглядит следующим образом.

1. Выделить память для нового буфера.

2. Скопировать старые данные в новый буфер.

3. Удалить старый буфер.

Это позволяет vector хранить все его объекты в одном непрерывном фрагменте памяти.

Оптимизация производительности vector

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

Для начала, vector (или любой другой контейнер из стандартной библиотеки) не хранит объекты. Он хранит копии объектов. Это значит, что каждый раз, когда в vector заносится новый объект, он туда не «кладется». С помощью конструктора копирования или оператора присвоения он копируется в другое место. Аналогично при получении значения из vector происходит копирование того, что находится в векторе по указанному индексу, в локальную переменную. Рассмотрим простое присвоение элемента vector локальной переменной.

vector<MyObj> myVec;
// Поместить несколько объектов MyObj в myVec
MyObj obj = myVec[10]; // Скопировать объект с индексом 10

Это присвоение вызывает оператор присвоения obj, в качестве правого операнда которого используется объект, возвращенный myVec[10]. Накладные расходы на производительность при работе с большим количеством объектов резко возрастают, так что их лучше всего избегать.

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

Изменение размера буфера тоже не дешево. Копирование каждого элемента буфера требует много работы, и этого лучше всего избегать. Чтобы защититься от этого, явно укажите размер буфера. Имеется пара способов сделать это. Простейшим способом сделать это является указание размера при создании вектора.

vector<string> vec(1000);

Здесь резервируется место для 1000 строк, и при этом производится инициализация каждого слота буфера с помощью конструктора string по умолчанию. При этом подходе приходится платить за создание каждой из этих строк, но добавляются определенные меры безопасности в виде инициализации каждого элемента буфера пустой строкой. Это означает, что при ссылке на элемент, значение которого еще не было присвоено, будет просто получена пустая строка.

Если требуется проинициализировать буфер каким-то определенным значением, можно передать объект, который требуется скопировать в каждый слот буфера.

string defString = 'uninitialized';
vector<string> vec(100, defString);
string s = vec[50]; // s = 'uninitialized'

В этом варианте vec с помощью конструктора копирования создаст 100 элементов, содержащих значение из defString.

Другим способом резервирования пространства буфера является вызов метода reserve, расположенный после создания vector.

vector<string> vec;
vec reserve(1000);

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

vector<string> vec(100);
string s = vec[50]; // без проблем: s содержит пустую строку
vector<string> vec2;
vec2.reserve(100);
s = vec2[50];      // Не определено

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

Наконец, плохой идеей является вставка элементов в любое место, кроме конца вектора. Посмотрите на рис. 6.1. Так как vector — это просто массив с дополнительными прибамбасами, становится очевидно, почему следует добавлять элементы только в конец вектора. Объекты в vector хранятся последовательно, так что при вставке элемента в любое место, кроме конца, скажем, по индексу n, объекты с n+1 до конца должны быть сдвинуты на один (в сторону конца) и освободить место для нового элемента. Сложность этой операции линейна, что означает, что она оказывается дорогостоящей даже для векторов скромного размера. Удаление элемента вектора имеет такой же эффект: оно означает, что все индексы больше n должны быть сдвинуты на один слот вверх. Если требуется возможность вставки и удаления в произвольном месте контейнера, вместо вектора следует использовать list.

6.3. Копирование вектора

Проблема

Требуется скопировать содержимое одного vector в другой.

Решение

Имеется пара способов сделать это. Можно при создании vector использовать конструктор копирования, а можно использовать метод assign. Пример 6.3 показывает оба этих способа.

Пример 6.3. Копирование содержимого vector

#include <iostream>
#include <vector>
#include <string>