6.3. Как растет вектор?

6.3. Как растет вектор?

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

Вектор может запрашивать память не под каждый новый элемент. Вместо этого она запрашивается с некоторым запасом, так что после очередного выделения вектор может поместить в себя некоторое количество элементов, не обращаясь за ней снова. (Каков размер этого запаса, зависит от реализации.) На практике такое свойство вектора обеспечивает значительное увеличение его эффективности, особенно для небольших объектов. Давайте рассмотрим некоторые примеры из реализации стандартной библиотеки С++ от компании Rogue Wave. Однако сначала определим разницу между размером и емкостью контейнера.

Емкость – это максимальное количество элементов, которое может вместить контейнер без дополнительного выделения памяти. (Емкостью обладают только те контейнеры, в которых элементы хранятся в непрерывной области памяти, – vector, deque и string. Для контейнера list это понятие не определено.) Емкость может быть получена с помощью функции capacity(). Размер – это реальное количество элементов, хранящихся в данный момент в контейнере. Размер можно получить с помощью функции size(). Например:

#include vector

#include iostream

int main()

{

vector int ivec;

cout "ivec: размер: " ivec.size()

" емкость: " ivec.capacity() endl;

for ( int ix = 0; -ix 24; ++ix ) {

ivec.push_back( ix );

cout "ivec: размер: " ivec.size()

" емкость: " ivec.capacity() endl;

}

}

В реализации Rogue Wave и размер, и емкость ivec сразу после определения равны 0. После вставки первого элемента размер становится равным 1, а емкость – 256. Это значит, что до первого дополнительного выделения памяти в ivec можно вставить 256 элементов. При добавлении 256-го элемента вектор должен увеличиться: выделить память объемом в два раза больше текущей емкости, скопировать в нее старые элементы и освободить прежнюю память. Обратите внимание: чем больше и сложнее тип данных элементов, тем менее эффективен вектор в сравнении со списком. В таблице 6.1 показана зависимость начальной емкости вектора от используемого типа данных.

Таблица 6.1. Размер и емкость для различных типов данных

Тип данных

Размер в байтах

Емкость после первой вставки

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

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

Упражнение 6.4

Объясните, какой из типов контейнера – вектор или список – больше подходит для приведенных примеров (во всех случаях происходит вставка неизвестного заранее числа элементов):.

(a) Целые числа

(b) Указатели на большие сложные объекты

(c) Большие сложные объекты