Why Vector size () and capacity () are different after push_back ()

Question

I'm just starting to study vectors and get a little confused about size() and capacity() I know little about both. But why are there different ones in this program? even array(10) creates space for 10 elements and initializes 0.

Before adding array.push_back(5)

So array.size(); equal to 10, which is normal.

So array.capacity(); equal to 10, which is normal.

After adding array.push_back(5)

So array.size(); is 11, which is normal (already 10 time 0 is added and then push_back add one more element 5 ) .

So array.capacity(); there are 15 why? ( 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; } 

Answer 1

The standard provides that std::vector<T>::push_back() has an amortization of O(1) . This means that the extension must be geometric, say, double the storage volume each time it is full.

A simple example: sequentially push_back 32 int in std::vector<int> . You will store them all once, and also make 31 copies if you double the capacity each time you finish. Why 31? Before saving the second item, you copy the 1st; before storing the 3rd, you copy elements 1-2, before storing the 5th, you copy 1-4, etc. So you copy 1 + 2 + 4 + 8 + 16 = 31 times with 32 stores.

Performing a formal analysis shows that you get O(N) stores and copies for elements of N This means amortizing the O(1) complexity over push_back (often only storage without a copy, sometimes storage and a sequence of copies).

Because of this expansion strategy, you will have size() < capacity() most of the time. Search shrink_to_fit and reserve to find out how to manage vector capacity in a finer way.

Note : at a geometric growth rate, any factor in excess of 1 will take place, and there have been some studies that claim that 1.5 gives better performance due to less memory loss (since redistributed memory may overwrite old memory at some point) .

Answer 2

This is for efficiency, so every time you add an item, it should not expand the underlying data structure. i.e. no need to call delete / new every time.

Answer 3

std :: vector :: capacity is not its actual size (which is returned by size() ), but the size of the actual internal allocated size.

In other words, this is the size that it can reach before another redistribution is required.

It does not increase by 1 every time you do push_back , so as not to cause a new redistribution (this is a heavy call) for every element inserted. It reserves more because it does not know if you will not do some other push_back right after that, in which case it will not have to change the size of the allocated memory for the next 4 elements.

Here the 4 following elements are a compromise between 1, which will optimize the memory allocation at maximum, but soon another redistribution and a huge amount will risk, which will allow you to quickly do a lot of push_back , but maybe reserve a lot of memory for nothing.

Note : if you want to specify the capacity yourself (if you know, for example, the maximum size of your vector), you can do this with reserve .

Answer 4

Using

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

You actually filled all ten spaces with zeros. Adding an additional ad element will increase capacity due to efficiency. In your case, it is useless to call a function reserve because you created the same number of elements.

check this and this link

Answer 5

Size() returns the number of values ​​that you specified in the vector.

And capacity() returns the size of the allocated storage capacity, which means how many values ​​it can hold now.

Answer 6

I think the following question may give you more detailed information about the capacity of the vector.

About the development of vectors

I will answer the answer in the above question.

A capacity growth strategy is required to satisfy the arithmetic time constant requirement for the push_back operation. Then the strategy is designed for exponential growth as a whole when there is no space. In short, the size vector indicates the number of elements at present, and captacity shows its ability to be used for push_back in the future.