четверг, июня 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:

26 коммент.:

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

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

...

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


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

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

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

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

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

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

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

Artem Artemenko комментирует...

Странно, что в стандарте не предусмотрено освобождение памяти.
Самое интересное, что спустя 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(), который, впрочем, тоже может не уменьшить вместимость вектора «впритык» до размера, но вряд ли будет хуже :)

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

скоко лет прошло с 2006 года? программисты посчитайте

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

#include
#include

using namespace std;

class A {
public:
static int cnt;
A(int a) {cout << "object created" << endl;}
~A() {++cnt; cout << "object deleted" << endl;}
};

int A::cnt = 0;

int main()
{
cout << "begin" << endl;
cout << A::cnt << endl;
vector v(4, 1); //
cout << v.capacity() << endl;
cout << "push_begin" << endl;
v.push_back(1);
cout << "vector created" << endl;
cout << A::cnt << endl;
}

Ребята, я понимаю, что с момента создания поста прошло много лет, но мне нужна ваша помощь. Не вдупляю, ну вот создали мы новый вектор при добавлении элемента, скопировали туда все старые значения, почему деструкторы вызываются? У нас теперь вектор на новом месте, зачем что-то удалять из мусора, то есть того кусочка памяти откуда мы ушли. Какая разница че там хранится, почему просто у старых объектов не поменять адреса и дело с концом?

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

Евгений Кондратенко
Похоже, часть угловых скобок Блоггер съел, поэтому пример не очень понятен.

зачем что-то удалять из мусора, то есть того кусочка памяти откуда мы ушли.

Если не удалять, получится утечка памяти.

Какая разница че там хранится, почему просто у старых объектов не поменять адреса и дело с концом?

Для того, чтобы "у старых объектов поменять адреса" нужно сначала их со старого места удалить и на новое положить.

Если вы хотите уменьшить число копирований памяти, смотрите в сторону std::move и emplace_back.

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

Доброго времени суток, Елена. Я с Вами согласен забавная история - эти вектора да еще в разных версиях компиляторов с ++. Качнул себе VS-2013 и попробовал ваш пример освобождения памяти вектора
vector v;
v.reserve(17);
cout< v;
std::vector ::iterator it;

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

it = v.begin();
cout << *it << endl;
cout << v.capacity() << endl;
vector(v).swap(v);
cout << v.capacity() << endl;
it = v.begin(); cout << *it << endl;
Вывод: нифига не чистит, не освобождает не не не
Начинаю исследования и заменяю swap на v.swap(vector()); - и вот тебе счастье !!!!.
Надо же и чистит и освобождает. Кстати работает и при выделении памяти через v.reserve(17); и через v.resize(17);
А вот распечатать(узреть мусор) этот факт не удается. Указатель(итератор) на вектор нулевой длинны ничего не указывает?
Вот такая жизнь на планете VS-2017. Сегодня. Еленочке Спасибо !

С уважением Олег.

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

Елена, приношу свои извинения, но что то где то глючит и мой комментарий от 11/3/18 23.46 -
Аноним - Олег отправлен к вам с вырванным куском текста из середины поста. Могу предположить что это произошло по причине ограничения длинны поста системой. Поэтому отсылаю Вам мой пост еще раз но предварительно разобью его на две части. Большая просьба. Елена замените пож. мой коммент. если не трудно, а то смысл послания в нем существенно искажен.
С уважением Олег.

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

Доброго времени суток, Елена. Я с Вами согласен забавная история - эти вектора да еще в разных версиях компиляторов с ++. Качнул себе VS-2013 и попробовал ваш пример освобождения памяти вектора
vector v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.clear();
cout<<v.capacity()<<endl;
Вывод: не чистит - досадно но ладно качнул VS-2017 и снова результат тот же.
С уважением Олег продолжение следует.

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

Попробовал другой ваш пример на VS-2017
std::vector v;
std::vector ::iterator it;

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

it = v.begin();
cout << *it << endl;
cout << v.capacity() << endl;
vector(v).swap(v);
cout << v.capacity() << endl;
it = v.begin(); cout << *it << endl;
Вывод: нифига не чистит, не освобождает не не не
Начинаю исследования и заменяю swap на v.swap(vector()); - и вот тебе счастье !!!!.
Надо же и чистит и освобождает. Кстати работает и при выделении памяти через v.reserve(17); и через v.resize(17);
А вот распечатать(узреть мусор) этот факт не удается. Указатель(итератор) на вектор нулевой длинны ничего не указывает?
Вот такая жизнь на планете VS-2017. Сегодня. Еленочке Спасибо !

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

Кстати в том же примере(для VS-2017) с вопросом очистки памяти хорошо справился и библиотечный деструктор (v.~vector();). Ваше замечание "Явный вызов деструктора - как правило плохая идея." - оценить не смог по причине неактуальности приведенной ссылки. Елена, не могли бы Вы слегка обосновать ваше замечание или привести другую ссылку.
C уважением Олег.

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

Олег,

отправлен к вам с вырванным куском текста из середины поста. Могу предположить что это произошло по причине ограничения длинны поста системой.

Может, проблема в угловых скобках? Похоже, Блоггер их так и не научился экранировать.

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

Уважаемый Олег,
Пост был в 2005, а сейчас на дворе 2018-й.
Этот трик больше не нужен http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

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

Здравствуйте, Елена! Вопрос может не совсем в тот пост, было бы здорово почитать про ваш опыт и мнение, и возможно разбор каких нибудь наиболее проблемных и узких мест по теме Most vexing parse in C++, классика, но обжигался сам не раз, и не всегда удаётся это победить сходу.

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

Нужен, потому что shrink_to_fit запрос без привязки, и нет гарантий что он выполнится и приведет емкость вашего вектора к его реальному размеру по количеству элементов. Если делать чтоб наверняка, то надо делать через swap. Чтобы было понятно о чём я: The request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size. - это из cpp reference, который вы указали выше.

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

Очень классный сайт, спасибо Вам, подробно разбираете процессы, происходящие внутри, а не пробегаетесь по векторам поверхностно, именно то, что искал!