Выделение памяти под вектор c
Предполагая, что "vec" не осталось места для хранения 5 в "под" функции, где она выделяет новую память?
В кадре стека подфункции? В этом случае 5 будет удалено в конце вспомогательной функции. Но кадр стека основной функции не может расти, так как в этот момент стек стека подфункции лежит поверх стека.
Разделяет ли std::vector память для своих элементов в куче? Но как он освобождает память кучи? Если это локальный вектор в стеке, кадр стека функции, включая вектор, удаляется в конце, не сигнализируя, что вектор будет удален?
Предоставляет ли std::vector память для своих элементов в куче?
Да. Или, точнее, он выделяет на основе распределителя, который вы проходите при строительстве. Вы не указали один, поэтому вы получаете распределитель по умолчанию. По умолчанию это будет куча.
Но как он освобождает память кучи?
Через его destructor, когда он выходит за рамки. (Обратите внимание, что указатель на вектор, выходящий из области действия, не вызовет деструктор). Но если вы передали значение sub , вы построили (и позже уничтожили) новую копию. 5 затем будет отброшен назад на эту копию, копия будет очищена, а вектор в main останется нетронутым.
Все контейнеры в STL параметризуются аргументами шаблона, обычно последний аргумент называется A или Allocator и по умолчанию имеет значение std::allocator<. > , где . представляет тип значения, хранящегося в контейнере.
Allocator - это класс, который используется для обеспечения памяти и сборки/уничтожения элементов в этой области памяти. Он может выделять память из пула или непосредственно из кучи, в зависимости от того, из какого вы построили распределитель. По умолчанию std::allocator<T> представляет собой простую оболочку вокруг ::operator new и, таким образом, выделяет память в куче, как вы предполагали.
Память распределяется по требованию и освобождается по меньшей мере, когда вызывается деструктор vector . С++ 11 вводит shrink_to_fit для освобождения памяти раньше. Наконец, когда вектор перерастает его текущую емкость, выполняется новое (большее) выделение, объекты перемещаются на него, и старое выделение освобождается.
Как и все локальные переменные, деструктор вызывается, когда выполняется, достигает конца области, в которой он был объявлен. Таким образом, перед выходом функции вызывается векторный деструктор, и только после этого стек сжимается, и управление возвращается вызывающему.
В описании контейнера 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>0 , на него можно сократить.
K^2-K-1
Решаем, получаем
K (второй корень, отрицательный, не интересен)
Правильно? Не правильно. Кусок 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 или, зная, что S>0
1+K+K^2+. +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;
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. Действительно, память освобождается.
здесь я определил что размер вектора будет 6. но число будет неумолимо расти, и в какой то момент vector (именно его я сейчас изучаю) будет не хватать памяти.
size - выдает количество элементов в векторе
resize - изменяет количество элементов в векторе
capacity - выдает под сколько элементов выделена память
reserve - резервиурет память
но, я ни как не могу понять как осуществлять проверку на. эм. на то, сколько эллементов осталось свободными? так? и в случае если их осталось меньше чем.. эм. ну пусть будет 1 (на большее кол-во разрядов число ж не может увеличиться, при умножение на 2) то -выделить память . на такое то кол. во. элементов. на какое? не знаю ))) или выделять память на одно число и так делать каждый раз, или же сразу бабахнуть увеличение выделенной памяти в два раза и все. Прошу помощи.
Спасибо.
Помощь в написании контрольных, курсовых и дипломных работ здесь
Выделение памяти размером 0
Если я выделяю память размером 0, например int * yu = new int; и потом пытаюсь её очистить.
Выделение памяти для вектора std::vector<iris> *v = new std::vector<iris>
Можно ли создать вектор, выделить для него память, так что бы он "жил" до конца работы программы.
Он выводит текущий размер, объём зарезервированного пространства и адрес первого элемента.
Как видно, класс vector сам контролирует размер памяти, и самостоятельно "расширяется", т.е. выделяет новый участок памяти и копирует туда данные.
Добавлено через 3 минуты
Соответственно, если тебе нужен сразу массив заданного размера то пишем:
Если знаем максимальные размер, но дополняться будет постепенно, то:
в строках 33-35 каждые 3 операции будет добавлять памяти методом push_back но, сдается мне что этот способ я не просто так назвал костылем, думается мне, что именно таким он и является.
Добавлено через 26 минут
AlexVRud, хм, но в вашем варианте при каждом цикле интеррации цикла происходит выделение доп памяти ч/з push_back у меня же далеко не при каждом цикле происходит увеличение размера, (ну в моем необходимо дополнительная память 1 к 4). опять же а если я буду возводить 3 в степень 100000000 мой код уже не будет работать, поэтому и вопрос, как бы можно было бы добавлять память только тогда, когда она подходит к концу, но при этом не добавлять ее в каждую интеррацию а только тогда когда это становиться необходимо. или я излишне загоняюсь?
Контейнер std::vector представляет собой динамический массив, автоматически увеличивающийся в размере по мере надобности. Он описан в любом приличном руководстве по С++. Там же описываются его методы, достоинства и недостатки по сравнению с другими контейнерами.
В руководствах говорится, что при добавлении нового элемента может потребоваться выделение дополнительной памяти. Но ни одно из них (из тех, что я встречал) не дает ответа на вопрос: что произойдет, если выделить память не удастся? Память ведь не бесконечна.
Дополнительная память выделяется во время работы трёх методов: resize, reserve и push_back. Вначале посмотрим, что по поводу них пишет стандарт (здесь и далее черновик С++11 №3337).
Стандарт
Метод reserve описан в пункте 23.3.6.3. Он ничего не возвращает. При слишком большом новом размере должен запускать исключение std::length_error. Однако здесь же есть сноска, говорящая о том, что данный метод вызывает Allocator::allocate, который может запустить иное исключение.
Метод resize описан в том же пункте. Так же ничего не возвращает. Про исключения не говорится ни слова. Но сказано, что метод присоединяет (appends) новые элементы. Правда не уточняется, использует ли он для этого метод push_back или обходится без него.
push_back описан в пункте 23.3.6.5. Ничего не возвращает. Про исключения запускаемые методом ничего не говорится.
Вот что мы имеем: reserve должен запускать std::length_error, но это на усмотрение распределителя памяти. resize и push_back остаются на совести разработчиков библиотеки.
Тестовая программа
Посмотрим, как ведут себя различные компиляторы. Для этого напишем небольшую программу, посредством которой и будем выводить их на чистую воду. Ее исходный текст приводится ниже.
GCC Linux
Компилятор GCC (реально g++, но это формальность) на системе Linux для методов resize и reserve запустил std::length_error, а последний push_back запустил std::bad_alloc. Таким образом доработанный вариант программы выглядит следующим образом:
Данная программа выводит три строки с наименованиями пойманных исключений:
GCC Windows
Тест проводился дважды. Программа компилировалась и запускалась на исполнение. После вывода строк
C++ Builder 6
Данная IDE потребовала дополнительных исследований. Для нашего примера метод resize запустил исключение EAccessViolation, метод reserve не запустил никакого исключения, наполнение вектора также запустило EAccessViolation.
Согласно документации, исключение EAccessViolation возникает при попытке обращения к неверному адресу памяти. Получается, C++ Builder 6 запускает его и при нехватке памяти? Но почему тогда метод reserve не запустил никакого исключения?
Если наш пример написать так:
То в этом случае метод push_back запустит std::bad_alloc, а не EAccessViolation. Почему такое разное поведение?
Ответ кроется в методе reserve. Обратите внимание: в исходном примере мы передавали туда отрицательное число -1, а в новом примере нормальное число 20. При этом в первом случае он не запустил никакого исключения. Как так? Неужели он смог зарезервировать память под -1 элемент вектора? В поисках ответа на этот вопрос мне пришлось покопаться в исходном коде класса std::vector.
При этом оператор new не только не запускает никакого исключения, но даже возвращает ненулевой указатель. По всей видимости он выделяет какой-то блок памяти, размер которого меньше запрошенного.
Именно это и происходит в наших примерах. Вернемся к первому из них.
Далее происходит заполнение вектора. Так как с точки зрения вектора у него есть достаточное количество памяти, она больше не выделяется. И тут, как и в случае с resize, происходит обращение к недопустимому адресу.
Теперь разберем второй пример (с исключением std::bad_alloc).
Метод reserve резервирует память под 20 элементов. Всё хорошо.
Далее вектор начинает наполняться. Со временем размера массива начинает не хватать, и запрашивается дополнительная память. Здесь по всей видимости используется другой распределитель памяти, лишенный недостатка своего коллеги. Поэтому мы и получаем std::bad_alloc.
Embarcadero RAD Studio 10 и Microsoft Visual Studio 2017
К счастью для нас разработчики C++ Builder 6 не сидели сложа руки и исправили описанную выше странность (правда не могу сказать в какой конкретно версии своего продукта). Так, в Embarcadero RAD Studio 10 Seatle строка
Выводы
Одновременно с этим нужно помнить, что некоторые компиляторы (и не только давно устаревшие) могут приводить к девиантному поведению.
2 комментариев к “std::vector при нехватке памяти”
Читайте также: