Пишу для себя реализацию контейнера vector. И не могу понять принцип работы и что вообще делают методи vector::capacity() и vector::reserve(). Читал документацию, но ничего не понимаю.
1 ответ
Дело в том, что внутри вектора используется простой динамический массив (это должно быть очевидно, но я уточню все же), на который можно даже получить указатель через vector:data()
. При этом вектор позволяет почти неограниченно добавлять данные в него (пока память не кончится). Как же он это делает? Также как и вы бы делали с динамическим массивом: запрашивает у ОС блок памяти большего размера, копирует туда все текущие данные, добавляет туда новые данные и освобождает старый блок памяти.
Но есть одна особенность: если память в текущем блоке закончилась и вы хотите еще добавить данные, он запрашивает новый блок памяти куда большего размера, чем необходимо (например в два раза больше, чем есть сейчас, а не N+1, где N это текущее количество элементов в векторе). Зачем? Представьте что вам надо добавлять в конец вектора много-много элементов в цикле. Представьте как медленно оно будет работать, если на каждой итерации придется заново перевыделять память на N+1 элементов, потом это все копировать еще, короче ужас. А если запросить сразу много памяти, то перевыделять память придется куда реже.
Тут конечно важно соблюсти меру, чтобы не было много неиспользуемой памяти. Я не знаю честно, по какой стратегии различные реализации вектора вычисляют размер памяти, который надо выделить, но мне видится так, что выделять каждый раз в 2 раза больше памяти, чем есть, это достаточно оптимально. GCC вроде так и делает.
Теперь непосредственно перейду к вопросу. vector::capacity()
показывает, сколько элементов вектор может вместить без перевыделения памяти, тогда как vector::size()
показывает, сколько элементов хранится в векторе в текущий момент. Понятно, что vector::size()
будет меньше или равен vector::capacity()
. vector::reserve(size_type N)
же говорит вектору выделить достаточно памяти для хранения минимум N элементов, то есть эта функция изменяет vector::capacity()
.
-
ну о том что там динамческний массив я знаю. То есть у меня в класе будет еще переменная
int capacity
. И если я использую в началеvector::reserve()
, тоcapacity
будет в два раза больше? – Oleg_Hudyma 7 апр '17 в 20:43 -
@Oleg_Hudyma учтите, что
vector::reserve(size_type N)
имеет аргумент, указывающий то количество элементов, для которого ему надо выделить память. сколько реально будет выделено памяти я не могу сказать, это надо проверять для каждого компилятора отдельно. Может быть выделено памяти как ровно под N элементов, так и под большее количество. Да и в начале нет смысла использоватьvector::reserve(size_type N)
, вы можете прямо в конструкторе вектора указать, под сколько элементов выделить памяти при создани ивектора. – Flowneee 7 апр '17 в 20:53 -
@Oleg_Hudyma: С чего бы это вдруг
capacity
станет в два раза больше?capacity
обычно растет именно до того значения, которое было указано вreserve()
.reserve()
для того и предназначен, чтобы управлятьcapacity
. Откуда вы взяли "два раза больше"? – AnT 7 апр '17 в 21:13 -
@AnT не обязательно "Note that the resulting vector capacity may be equal or greater than n", то есть я так понимаю в принципе
reserve()
может выделить больше места, чем указано в аргументе, если разработчики предусмотрели именно такую стратегию изменения размера вектора. – Flowneee 7 апр '17 в 22:29 -
@Flowneee: Может, конечно. Но это скорее будут соображения какой-нибудь гранулярности (напр, "
capacity
всегда кратно 16" или "capacity
- всегда степень двойки"), которую такой примитивной взаимосвязью, как "я делаюreserve(20)
, значитcapacity
станет 40" не опишешь. Это скорее сsize
может существовать такая взаимосвязь - как толькоsize
достигаетcapacity
,capacity
увеличивается в 2 раза - одна из возможных стратегий. – AnT 7 апр '17 в 22:47
std::vector::reserve
-- Request a change in capacity (меняет размер выделенной памяти)std::vector::capacity
-- Return size of allocated storage capacity (сообщает этот размер) – avp 7 апр '17 в 20:27