Выделение памяти под vector

В описании контейнера vector можно встретить такие функции как size и resize, capacity и reserve. С первого взгляда кажется, что половина явно лишняя, ведь размер у вектора может быть только один.
Почему так? Потому что память для вектора выделяется "про запас"(подробнее ниже), и надо уметь управлять и количеством элементов вектора, и количеством памяти, которое он занимает. size и resize - нужны для работы с реальным числом элементов вектора, capacity и reserve - для работы с памятью.
size - выдает количество элементов в векторе
resize - изменяет количество элементов в векторе
capacity - выдает под сколько элементов выделена память
reserve - резервиует память

Вот что сделает код, скомпиленный Visual C++ 6.0:

vector <int> v;
v.push_back(1); //size==1, capacity==1
v.push_back(17); //size==2, capacity==2
v.push_back(23); //size==3, capacity==4


Зачем нужен этот запас?
Допустим, у нас есть вектор из n элементов. Что происходит, когда программист добавляет еще один? Когда есть запасная память, элемент пишется туда. Когда ее нет, выделяется непрерывный кусок памяти достаточный для n*K элементов, где K - коэффицент. В него копируются предыдущие n, добавляется наш новый элемент, старый кусок размером n освобождается. Если бы запаса не было, то память бы выделялась каждый раз при добавлении нового элемента, что страшно неэффективно.
Зачем нужен reserve, если все и без участия программиста так хорошо работает? Это может быть полезно в некоторых ситуациях. Например, знание того, как выделяется память под вектор, можно использовать и в начале, при его задании. Допустим, я точно знаю, что в векторе будет где-то 100-110 элементов. Я сразу же создам вектор размером 110, это поможет избежать перевыделений памяти, положительно скажется на производительности.

vector <int> v;
v.reserve(110);

Это вовсе не означает, что зарезервировано место для 110-ти элементов ровно. Зарезервировано место как минимум для 110 элементов, возможно больше.

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

//если где-то описана такая функция
void myPrint(int* v, int vsize);

//ее можно вызвать так
vector <int> v;
v.push_back(2);
v.push_back(3);
myPrint(&v[0], v.size());

Коэффицент К
(Все приведенные ниже рассуждения верны только для first-fit схем выделения памяти, то есть выделяется первый по порядку подходящий кусок)
Что за коэффицент K, который используется при выделении памяти , чему он равен? Так, как у нас там происходит выделение памяти... Новую выделили, прокопировали туда данные, старую освободили. И так несколько раз. Если память идет подряд, то образуется пробел, который можно было бы использовать. Нужно подобрать такой коэффицент, который позволит эти пробелы использовать. Было вычислено, что коэффицент должен быть меньше, чем (1+sqrt(5))/2. Что примечательно, выражение (1+sqrt(5))/2 - это же "золотое сечение".
Откуда берется это число?

Я видела вот такое доказательство:
Пусть у нас изначально размер вектора был S, S>0.
После первого перевыделения памяти, он стал K*S.
После второго K*K*S.

Нам нужно, чтобы K*K*S влезло в S+K*S, то есть K*K*S<=S+K*S. S>0, на него можно сократить.
K^2-K-1<=0
Решаем, получаем
K<=(1+sqrt(5))/2 (второй корень, отрицательный, не интересен)
Правильно? Не правильно. Кусок K*S все еще занят, его нельзя использовать.

Нам нужно, чтобы в момент выделения K^(n+1)*S память размером S+K*S+K^2*S+...+K^(n-1)*S была достаточной, чтобы вместить этот K^(n+1)*S. K^n*S все еще занят, мы его использовать не можем. В итоге получаем.
S+K*S+K^2*S+...+K^(n-1)*S <= K^(n+1)*S или, зная, что S>0
1+K+K^2+...+K^(n-1) <= K^(n+1)
Решать я это не буду, Andrew Koenig считает, что подходящий в данном случае корень (1+sqrt(5))/2, доверюсь ему.
Если говорить уж совсем точно, то (1+sqrt(5))/2 не совсем правильное число, нужнен коэффицент поменьше. Потому что нужна еще дополнительная память для разных служебных нужд.
В Visual C++ 6.0 взята константа 2. Такой коэффицент использовать пробелы не дает. А вот в Visual C++ 7 уже используется константа 1.5.

Swap Trick
Про выделение памяти ясно. А как с освобождением памяти? Да, при увеличении размера вектора будет выделена память, а когда вектор уменьшается? Нет, она не будет освобождена. Что несколько неудобно, потому что если в векторе было 10000 элементов, а потом их количество уменьшилось до 10 и осталось где-то в таких пределах, то получается что куча памяти пропадает зря. Что можно сделать в такой ситуации? Сделать новый вектор и туда прокопировать старый. Это можно сделать красиво с помощью swap trick.
vector<int>(v).swap(v);
В этой строчке происходит следующее: создается безымянный vector <int>, который инициализируется элементами из v, а потом он меняется с вектором v местами. Это вовсе не гарантирует, что памяти будет выделено ровно столько, сколько нужно, а не больше. Это зависит от реализации. Но, скорее всего, все будет лучше, чем было.
Я читала у Герба Саттера, что swap сохраняет в корректном состоянии все итераторы, ссылки и указатели.

Может я чего-то не понимаю, но у меня получилось вот что.

std::vector <int> v;
std::vector <int>::iterator it;

v.push_back(1);
v.push_back(2);
v.push_back(3);

it=v.begin();
cout<<*it<<endl;

vector<int>(v).swap(v);
cout<<*it<<endl; //компиляла и gcc, и VC++ в обоих случаях получила мусор

Updated 23.11.2005:
Вычитала, что в Visual C++ 7.1 при вызове метода clear() память таки высвобождается. Не могу проверить для 7.1, зато проверила для Microsoft Visual C++ Toolkit 2003. Действительно, память освобождается.

То есть для такого кода:
vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.clear();
cout<<v.capacity()<<endl;

Вывод получается следующим
Microsoft Visual C++ Toolkit 2003:
17
0
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17

Стандарт не указывает должна ли освобождаться память при вызове метода clear(), так что все компиляторы здесь действуют по Стандарту.

Ссылки по теме:
Vector Resizing Algorithm
comp.lamg.c++.moderated, vector growth factor of 1.5


Technorati tag: C++