9.4. Как увеличивается размер вектора

Для обеспечения быстрого произвольного доступа элементы вектора хранятся последовательно — каждый элемент рядом с предыдущим. Как правило, нас не должно заботить то, как реализован библиотечный тип; достаточно знать, как его использовать. Но в случае векторов и строк реализация частично просачивается в интерфейс.

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

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

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

Функции-члены управления емкостью

Типы vector и string предоставляют описанные в табл. 9.10 функции-члены, позволяющие взаимодействовать с частью реализации, относящейся к резервированию памяти. Функция capacity() сообщает количество элементов, которое контейнер может создать прежде, чем ему понадобится занять больший объем памяти. Функция reserve() позволяет задать количество резервируемых элементов.

Таблица 9.10. Управление размером контейнера

Вызов функции reserve() изменяет емкость вектора, только если требуемое пространство превышает текущую емкость. Если требуемый размер больше текущей емкости, функция reserve() резервирует по крайней мере столько места, сколько затребовано (или несколько больше).

Если требуемый размер меньше или равен существующей емкости, функция reserve() ничего не делает. В частности, вызов функции reserve(), при размере меньшем, чем емкость, не приведет к резервированию контейнером памяти. Таким образом, после вызова функции reserve() емкость будет больше или равна переданному ей аргументу.

В результате вызов функции reserve() никогда не сократит объем контейнера. Точно так же функция-член resize() (см. раздел 9.3.5) изменяет только количество элементов контейнера, а не его емкость. Функцию resize() нельзя использовать для сокращения объема память, которую контейнер держит в резерве.

Функции-члены capacity() и size()

Очень важно понимать различие между емкостью (capacity) и размером (size). Размер — это количество элементов, хранящихся в контейнере в настоящий момент, а емкость — это количество элементов, которое контейнер может содержать, не прибегая к следующей операции резервирования памяти. Следующий код иллюстрирует взаимосвязь размера и емкости:

vector<int> ivec;

// размер нулевой; емкость зависит от реализации

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

// присвоить вектору ivec 24 элемента

for (vector<int>::size_type ix = 0; ix != 24; ++ix)

 ivec.push_back(ix);

// размер 24; емкость равна или больше 24, согласно реализации

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

При запуске на компьютере автора эта программа отобразила следующий результат:

ivec: size: 0 capacity: 0

ivec: size: 24 capacity: 32

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

Визуально текущее состояние вектора ivec можно представить так:

Теперь при помощи функции reserve() можно зарезервировать дополнительное пространство.

ivec.reserve(50); // задать емкость 50 элементов (можно и больше)

// размер будет 24, а емкость - 50 или больше, если так определено

// в реализации

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

Вывод свидетельствует о том, что вызов функции reserve() зарезервировал именно столько места, сколько было запрошено:

ivec: size: 24 capacity: 50

Эту резервную емкость можно впоследствии израсходовать следующим образом:

// добавить элементы, чтобы исчерпать резервную емкость

while (ivec.size() != ivec.capacity())

 ivec.push_back(0);

// емкость не изменилась, размер и емкость теперь равны

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

Результат свидетельствует, что в настоящий момент резервная емкость исчерпана, а размер и емкость равны.

ivec: size: 50 capacity: 50

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

Если теперь добавить в вектор новый элемент, то последует повторное резервирование памяти.

ivec.push_back(42); // добавить еще один элемент

// размер будет 51, а емкость 51 или больше, если так определено

// в реализации

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

Результат выполнения этой части программы имеет следующий вид:

ivec: size: 51 capacity: 100

Он свидетельствует о том, что в данной реализации класса vector использована стратегия удвоения текущей емкости при каждом резервировании новой области памяти.

По мере необходимости можно вызвать функцию shrink_to_fit(), запрашивающую освобождение и возвращение операционной системе памяти, ненужной для текущего размера контейнера:

ivec.shrink_to_fit(); // запрос на возвращение памяти

// размер остался неизменным; емкость определена реализацией

cout << "ivec: size: " << ivec.size()

     << " capacity: " << ivec.capacity() << endl;

Вызов функции shrink_to_fit() является только запросом; нет никакой гарантии того, что память будет действительно возвращена.

Вектор может начать повторное резервирование только после выполнения пользователем операции вставки, когда размер равен емкости, вызова функции resize() или reserve() со значением, превышающим текущую емкость. Количество памяти, резервируемое свыше указанного объема, зависит от реализации.

Каждая реализация обязана следовать стратегии, гарантирующей эффективное использование функции push_back() при добавлении элементов в вектор. С технической точки зрения время создания n элементов вектора составляет время выполнения функции push_back() для первоначально пустого вектора, умноженное на n.

Упражнения раздела 9.4

Упражнение 9.35. Объясните различие между емкостью вектора и его размером.

Упражнение 9.36. Может ли контейнер иметь емкость, меньшую, чем его размер?

Упражнение 9.37. Почему контейнеры list и array не имеют функции-члена capacity()?

Упражнение 9.38. Напишите программу, позволяющую исследовать рост вектора в библиотеке, которую вы используете.

Упражнение 9.39. Объясните, что выполняет следующий фрагмент программы:

vector<string> svec;

svec.reserve(1024);

string word;

while (cin >> word)

 svec.push_back(word);

svec.resize(svec.size() + svec.size()/2);

Упражнение 9.40. Если программа в предыдущем упражнении читает 256 слов, какова ее вероятная емкость после вызова функции resize()? Что, если она читает 512, 1 000 или 1 048 слов?