Книга: Эффективное использование STL

Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти

Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти

Одной из самых замечательных особенностей контейнеров STL является автоматическое наращивание памяти в соответствии с объемом внесенных данных (при условии, что при этом не превышается максимальный размер контейнера — его можно узнать при помощи функции max_size). Для контейнеров vector и string дополнительная память выделяется аналогом функции realloc. Процедура состоит из четырех этапов:

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

2. Копирование всех элементов из старой памяти контейнера в новую память.

3. Уничтожение объектов в старой памяти.

4. Освобождение старой памяти.

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

Функция reserve позволяет свести к минимуму количество дополнительных перераспределений памяти и избежать затрат на обновление недействительных итераторов/указателей/ссылок. Но прежде чем объяснять, как это происходит, позвольте напомнить о существовании четырех взаимосвязанных функций, которые иногда путают друг с другом. Из всех стандартных контейнеров перечисленные функции поддерживаются только контейнерами vector и string.

• Функция size() возвращает текущее количество элементов в контейнере. Она не сообщает, сколько памяти контейнер выделил для хранящихся в нем элементов.

• Функция capacity() сообщает, сколько элементов поместится в выделенной памяти. Речь идет об общемколичестве элементов, а не о том, сколько ещеэлементов можно разместить без расширения контейнера. Если вас интересует объем свободной памяти vector или string, вычтите size() из capacity(). Если size() и capacity() возвращают одинаковые значения, значит, в контейнере не осталось свободного места, и следующая вставка (insert, push_back и т. д.) вызовет процедуру перераспределения памяти, описанную выше.

• Функция resize(size_t n) изменяет количество элементов, хранящихся в контейнере. После вызова resize функция size вернет значение n. Если n меньше текущего размера, лишние элементы в конце контейнера уничтожаются. Если n больше текущего размера, в конец контейнера добавляются новые элементы, созданные конструктором по умолчанию. Если n больше текущей емкости контейнера, перед созданием новых элементов происходит перераспределение памяти.

•Функция reserve(size_t n) устанавливает минимальную емкость контейнера равной n — при условии, что n не меньше текущего размера. Обычно это приводит к перераспределению памяти вследствие увеличения емкости (если n меньше текущей емкости, vector игнорирует вызов функции и не делает ничего, а string можетуменьшить емкость до большей из величин (size(), n)), но размер string при этом заведомо не изменяется. По собственному опыту знаю, что усечение емкости string вызовом reserve обычно менее надежно, чем «фокус с перестановкой», описанный в совете 17.

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

Предположим, вы хотите создать vector<int> с числами из интервала 1–1000. Без использования reserve это делалось бы примерно так:

vector<int> v;
for (int i=1; i<=1000; ++i) v.push_back(i):

В большинстве реализаций STL при выполнении этого фрагмента произойдет от 2 до 10 расширений контейнера. Кстати, число 10 объясняется очень просто. Вспомните, что при каждом перераспределении емкость vector обычно увеличивается вдвое, а 1000 примерно равно 2¹⁰.

vector<int> v;
v.reserve(1000);
for (int i=1; i<=1000; ++i) v.push_back(i);

В этом случае количество расширений будет равно нулю.

Взаимосвязь между size и capacity позволяет узнать, когда вставка в vector или string приведет к расширению контейнера. В свою очередь, это позволяет предсказать, когда вставка приведет к недействительности итераторов, указателей и ссылок в контейнере. Пример:

string s;
if (s.size() < s.capacity()) {
 s.push_back('x');
}

В этом фрагменте вызов push_back не может привести к появлению недействительных итераторов, указателей и ссылок, поскольку емкость string заведомо больше текущего размера. Если бы вместо push_back выполнялась вставка в произвольной позиции строки функцией insert, это также гарантировало бы отсутствие перераспределений памяти, но в соответствии с обычными правилами действительности итераторов для вставки в string все итераторы/указатели/ссылки от точки вставки до конца строки стали бы недействительными.

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

Оглавление книги