Почему размер вектора() и емкость () отличаются после push back()

Question

Почему размер вектора() и емкость () отличаются после push back()

Я только начинаю изучать векторы и немного путаюсь в size() и capacity()
Я мало знаю о них обоих. Но почему в этой программе оба они разные? даже array(10) освобождает место для 10 элементов и инициализирует с 0.

Перед добавлением array.push_back(5)

Так что array.size(); - это 10, это нормально.

Так что array.capacity(); - это 10, это нормально.

После добавления array.push_back(5)

Так что array.size(); - это 11, что нормально (already 10 time 0 is added and then push_back add one more element 5 ).

Итак, array.capacity(); - это 15 Почему? ( is it reserving 5 blocks for one int? ).

#include <iostream>

#include <vector>

int main(){

    std::vector<int> array(10); // make room for 10 elements and initialize with 0

    array.reserve(10);    // make room for 10 elements

    array.push_back(5);

    std::cout << array.size() << std::endl;

    std::cout << array.capacity() << std::endl;

    return 0;

}

682 6

c++vector allocation

6 ответов:

Comments

Ничего не найдено.

TemplateRex · Accepted Answer · 2016-01-15 15:52:31

Стандарт предписывает, что std::vector<T>::push_back() имеет амортизированную O(1) сложность. Это означает, что расширение должно быть геометрическим, скажем, удвоение объема хранилища каждый раз, когда оно заполняется.

Простой пример: последовательно push_back 32 ints в a std::vector<int>. Вы будете хранить их все один раз, а также делать 31 копию, если вы удваиваете емкость каждый раз, когда она заканчивается. Почему 31? Перед хранением 2-ой элемент, скопировать 1-й; перед хранением 3-й, копировании элементов 1-2, перед хранением 5-й, вы копируете 1-4 и т. д. Так что вы копируете 1 + 2 + 4 + 8 + 16 = 31 раз, с 32 магазинами.

Выполнение формального анализа показывает, что вы получаете O(N) хранилища и копии для N элементов. Это означает амортизированную O(1) сложность в расчете push_back (часто только магазин без копии, иногда магазин и последовательность копий).
Из-за этой стратегии расширения, у вас будет size() < capacity() большую часть времени. Lookup shrink_to_fit и reserve, чтобы узнать, как управлять способностью вектора в более мелкозернистая манера.
Примечание : с геометрической скоростью роста подойдет любой фактор больше 1, и были некоторые исследования, утверждающие, что 1.5 дает лучшую производительность из-за меньшего количества потраченной памяти (потому что в какой-то момент перераспределенная память может перезаписать старую память).

Ed Heal · Accepted Answer · 2016-01-15 14:30:14

Это для эффективности, чтобы не нужно было расширять базовую структуру данных каждый раз, когда вы добавляете элемент. то есть не надо звонить delete/new каждый раз.

Aracthor · Accepted Answer · 2016-01-15 14:40:45

Std::vector::capacity - это не его фактический размер (который возвращается size()), а размер фактического внутреннего выделенного размера.
Другими словами, это размер, которого он может достичь, прежде чем потребуется еще одно перераспределение.
Он не увеличивается на 1 каждый раз, когда вы делаете push_back, Чтобы не вызывать новое перераспределение (что является тяжелым вызовом) для каждого вставленного элемента. Он резервирует больше, потому что не знает, не сделаете ли вы что-нибудь другое push_back сразу после этого, и в этом в этом случае ему не придется изменять размер выделенной памяти для следующих 4 элементов.

Здесь 4 следующих элемента-это компромисс между 1, который оптимизирует выделение памяти по максимуму, но рискует вскоре снова перераспределить ее, и огромным числом, которое позволит вам быстро сделать много push_back, но, возможно, зарезервировать много памяти впустую.

Примечание : Если вы хотите указать емкость самостоятельно (например, если вы знаете максимальный размер вектора), вы можете сделать это с помощью резервная функция-член.

MagoNick · Accepted Answer · 2016-01-15 14:35:48

Используя
std::vector<int> array(10); // make room for 10 elements and initialize with 0
Вы фактически заполнили все десять пробелов нулями. Добавление дополнительного элемента ad приведет к расширению емкости благодаря эффективности. В вашем случае бесполезно вызывать функцию reserve, так как вы создали одинаковое количество элементов.
Проверьте эту и эту связь

MASh · Accepted Answer · 2016-01-15 14:40:29

Size() возвращает, сколько значений у вас есть в векторе.

И capacity() возвращает размер выделенной емкости памяти, то есть сколько значений она может содержать в данный момент.

Jcppython · Accepted Answer · 2017-05-23 15:10:35

Я думаю, что следующий вопрос может дать вам более подробную информацию о способности вектора.

О векторах роста
Я буду ссылаться на ответ в вышеприведенном вопросе.
Стратегия роста capacity необходима для удовлетворения амортизированного постоянного временного требования для операции push_back. Затем стратегия предназначена для экспоненциального роста, как правило, когда пространства не хватает. Короче говоря, size вектора указывают число элементов теперь, в то время как captacity покажите свою способность использовать push_back в будущем.