Скотт Мейерс - Эффективное использование STL

• Функция 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с числами из интервала 1–1000. Без использования reserveэто делалось бы примерно так:

vector v;

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

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

vector 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.