хранить все его объекты в одном непрерывном фрагменте памяти.
Оптимизация производительности 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>
#include <algorithm>
using namespace std;
// Вспомогательная функция для печати содержимого вектора
template<typename T>
void vecPrint (const vector<T>& vec) {
cout << "{";
for (typename vector<T>::const_iterator p = vec.begin;