четверг, июня 30, 2005

Выделение памяти под 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:

13 коммент.:

Анонимный комментирует...

Я читала у Герба Саттера, что swap сохраняет в корректном состоянии все итераторы, ссылки и указатели.

...

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


А я тут вычитал у Мейерса, что swap таки сохраняет корректность итераторов, но корректны они становятся для того контейнера, куда был сделан swap (что, в-общем, логично). Так что it в коде указывает на только что удалённый локальный безымянный vector<int>. Отсюда и мусор.

Alena комментирует...

Так что it в коде указывает на только что удалённый локальный безымянный vector<int>. Отсюда и мусор.

Угу, тогда все сходится.

Анонимный комментирует...

Круто,
swap
у меня отлично работает.

Странно, что в стандарте не предусмотрено освобождение памяти.

Dragon комментирует...

Странно, что в стандарте не предусмотрено освобождение памяти.
Самое интересное, что спустя 4,5 года ситуация не изменилась.

CodeBlocks 8.02:
17
17

Анонимный комментирует...

Память под вектор очищается так:
vector v(8,9);
cout<<v.capacity();
v.~vector();
cout<<'\n'<<v.capacity();

Alena комментирует...

2Анонимный
Память под вектор очищается так:

Явный вызов деструктора - как правило плохая идея. Почему так можно почитать тут
http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.5

3fh комментирует...

Как насчет

template<class T> void reset(T & object)
{
object.~T();
new (&object) T;
}
...
vector<int> v;
...
reset(v);

?

Alena комментирует...

3fh
Как насчет
Это было бы удобно, если бы было в самом STL.
А так - вариант, только если ресетить вектор надо часто. Старый добрый swap trick довольно известен и хорошо читается.

Анонимный комментирует...

в Visual Studio 2008 clear() память не читстит.

Mikle комментирует...

Извините, Лена, не по теме: вот за "не пью и не курю" - молодчина! Успехов!

Анонимный комментирует...

Спасибо!

Анонимный комментирует...

Последние два неравенства не в ту сторону.

Анонимный комментирует...

Таки надо заметить, что с выходом С++11 ситуация таки улучшилась и у вектора появился метод shrink_to_size(), который, впрочем, тоже может не уменьшить вместимость вектора «впритык» до размера, но вряд ли будет хуже :)