C++ для начинающих

Тип данных	Размер в байтах	Емкость после первой вставки
int	5	256
double	8	128
простой класс #1	12	85
string	12	85
большой простой класс	8000	1
большой сложный класс	8000	1

Итак, в реализации Rogue Wave при первой вставке выделяется точно или примерно 1024 байта. После каждого дополнительного выделения памяти емкость удваивается. Для типа данных, имеющего большой размер, емкость мала, и увеличение памяти с копированием старых элементов происходит часто, вызывая потерю эффективности. (Говоря о сложных классах, мы имеем в виду класс, обладающий копирующим конструктором и операцией присваивания.) В таблице 6.2 показано время в секундах, необходимое для вставки десяти миллионов элементов разного типа в список и в вектор. Таблица 6.3 показывает время, требуемое для вставки 10 000 элементов (вставка элементов большего размера оказалась слишком медленной).

Таблица 6.2. Время в секундах для вставки 10 000 000 элементов

Тип данных	List	Vector
int	10.38	3.76
double	10.72	3.95
простой класс	12.31	5.89
string	14.42	11.8

Таблица 6.3. Время в секундах для вставки 10 000 элементов

Тип данных	List	Vector
большой простой класс	0.36	2.23
большой сложный класс	2.37	6.70

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

Вставка элемента как в список, так и в вектор, требует вызова копирующего конструктора, если он определен. (Копирующий конструктор инициализирует один объект значением другого. В разделе 2.2 приводится начальная информация, а в разделе 14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие в поведении простых и сложных объектов при вставке в контейнер. Объекты простого класса вставляются побитовым копированием (биты одного объекта пересылаются в биты другого), а для строк и сложных классов это производится вызовом копирующего конструктора.

Вектор должен вызывать их для каждого элемента при перераспределении памяти. Более того, освобождение памяти требует работы деструкторов для всех элементов (понятие деструктора вводится в разделе 2.2). Чем чаще происходит перераспределение памяти, тем больше времени тратится на эти дополнительные вызовы конструкторов и деструкторов.

Конечно, одним из решений может быть переход от вектора к списку, когда эффективность вектора становится слишком низкой. Другое, более предпочтительное решение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указатели на них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70 секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизило частоту перераспределения памяти. Кроме того, копирующий конструктор и деструктор не вызываются больше для каждого элемента при копировании прежнего содержимого вектора.

Функция reserve() позволяет программисту явно задать емкость контейнера . Например:

int main() {

vector string svec;

svec.reserve( 32 ); // задает емкость равной 32

// ...

}

svec получает емкость 32 при размере 0. Однако эксперименты показали, что любое изменение начальной емкости для вектора, у которого она по умолчанию отлична от 1, ведет к снижению производительности. Так, для векторов типа string и double увеличение емкости с помощью reserve() дало худшие показатели. С другой стороны, увеличение емкости для больших сложных типов дает значительный рост производительности, как показано в таблице 6.4.

Таблица 6.4. Время в секундах для вставки 10 000 элементов при различной емкости*

Емкость	Время в секундах
1 по умолчанию	670
4,096	555
8,192	444
10,000	222
*Сложный класс размером 8000 байт с конструктором копирования и деструктором

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

Упражнение 6.2

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

Упражнение 6.3