int main()

{ vector<int> v;

vector<int>::size type nO = 12345, nl;

cout << v.size0 v.capacity()\n ;

for (long i=OL; i<100000L; i++) { nl = v.capacity(); if (nl != nO)

{ cout << setw(8) << v.sizeO <<

<< setw{8) << nl << endl; nO = nl;

v.push back(123); v.sizeO увеличивается на 1

return 0;

В этой программе размер вектора v вырастает от О до 99 999. Число элементов вектора, для которых выделена память, v.capacity{) показывается каждый раз, когда это значение изменяется по сравнению с прошлым шагом. Значения, которые хранятся в векторе, не имеют отношения к нашей текущей задаче, все элементы вектора равны 123. В начале работы программы вектор пуст и значение &.sfze(), как и v.capacityQ, равно нулю. После добавления первого элемента значение v.size() становится равным 1, но v.capacityQ, количество элементов, для которых зарезервирована память, равно некоторому большему значению. Для ВС5 это значение 256, для некоторых других версий STL оно равно 1024. При, казалось бы, неэффективном расходовании памяти такая схема имеет преимущество в том, что потребуется много времени, прежде чем возникнет необходимость в перераспределении памяти, поскольку емкость, равная, допустим, 256, используется для всех размеров вектора 1, 2, 3, 256. Только когда значение v.sizeQ станет равным 257, нам потребуется перераспределить память. Для используемой здесь реализации STL емкость после этого удвоится, чтобы хватило памяти для размеров 257, 258,512. Принцип удвоения емкости соблюдается при всех перераспределениях памяти, как показывает следующий вывод программы, откомпилированной с помощью ВС5:

V.sizeO v.capacityO

1 256 257 512 513 1024

1025 2048

2049 4096

4097 8192

8193 16384

16385 32768

32769 65536

65537 131072

Функция capacity возвращает информацию о распределении памяти; существует связанная с ней функция reserve, которая позволяет контролировать это распределение. После выполнения вызова

V.reserve(п);

значение v.capacityO будет равно по меньшей мере п. Функция reserve может ускорить выполнение программы, если мы знаем заранее, сколько элементов будет содержать вектор v. Например, если в программе capacity.cpp добавить строчку

v.reserve(lOOOOO);

непосредственно перед циклом for, вывод этой программы будет содержать только две следующие строчки:

V.sizeO V.capacityO О 100000

Выделение памяти произойдет всего один раз. После этого вызова reserve в векторе хватит места для всех 100 ООО элементов, которые будут добавлены в операторе for.

Перераспределение памяти, значения итераторов и функция reserve

Когда в результате роста происходит перераспределение выделенной памяти для вектора v, что приводит к увеличению значения v.capacityO, то, как правило, любые итераторы, ссылающиеся на элементы вектора v, становятся недействительными. Это станет ясно, если считать итераторы указателями, которые хранят адреса элементов. Перераспределение памяти может потребовать, что весь вектор будет перемещен в другие участки памяти, и мы не можем ожидать, что использовавшиеся с этим вектором итераторы автоматически обновятся. Например:

vector<int> V, w;

vector<int>::iterator i; v.push back(0); i = V.beginO ;

for (long k=lL; k<100000L; k++)

v.push back(k); cout (*i); ???

В последней строке этого фрагмента i ссылается на участок памяти, который может уже не принадлежать вектору v. Как если бы мы захотели навестить старого знакомого по адресу, где он когда-то проживал, но сейчас там живут другие люди. Однако есть исключения; если вторая строчка этого фрагмента (обозначенная тремя точками) содержит оператор

V.reserve(N);

где ЛГ > 100 ООО, тогда в цикле for не произойдет перераспределения памяти и значение i останется равным v.beginQ.

Как видно из раздела 1.9, мы можем использовать выражения i + nni-n, где i является итератором, an- целым, для векторов (а также для двусторонних очередей, но не для списков). Это дает возможность правильно запомнить позиции в векторе:

vector<int> v; vector<int>::iterator i; int k;

for (...) v.push back(...); i = . . . ;

к = i - V.beginO; *i == v[k]

for (...) v.push back(...);

Расширение v может привести к перераспределению памяти,

что сделает *i неопределенным.

i = V.beginO + к; *i == v[k] снова

Итератор i ссылается на тот же элемент, что и до этого,

хотя этот элемент, возможно, находится в другом месте

памяти

Как отмечается в комментарии, нам нет необходимости использовать итераторы для доступа к элементам вектора: оператор доступа по индексу [], который применяется к массивам, определен также и для векторов, поэтому в конце этого фрагмента мы можем написать v[k] вместо *i. В общем случае можно писать

v[k] вместо * (v.beginО + к)

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

3.3. обзор функций-членов класса vector

Ниже перечислены все функции-члены класса vector с кратким описанием или ссылкой на соответствующий раздел. Эти объявления могут содержаться