Д. Стефенс - C++. Сборник рецептов

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

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

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

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

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

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

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

vector myVec;

// Поместить несколько объектов MyObj в myVec

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

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

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

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

vector vec(1000);

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

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

string defString = "uninitialized";

vector vec(100, defString);

string s = vec[50]; // s = "uninitialized"

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

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

vector vec;

vec reserve(1000);

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

vector vec(100);

string s = vec[50]; // без проблем: s содержит пустую строку

vector vec2;

vec2.reserve(100);

s = vec2[50]; // Не определено