Why vector has different capacity and other than the size?

Question

Below are program of vector and gives different result for capacity in c++11 mode.

#include<iostream>
#include<vector>
using namespace std;

int main(){
vector<int>a ={1,2,3};
cout<<"vector a size :"<<a.size()<<endl;
cout<<"vector a capacity :"<<a.capacity()<<endl<<endl;;

vector<int>b ;
b.push_back(1);
b.push_back(2);
b.push_back(3);
cout<<"vector b size :"<<b.size()<<endl;
cout<<"vector b capacity :"<<b.capacity()<<endl;
return 0;
}

OUTPUT
vector a size :3
vector a capacity:3

vector b size :3
vector b capacity :4

Why this program gives different values for capacity of a and b while both have same number of values and how size is different from capacity?

But i think this is partial answer of my question .because why capacity of vector a and b become different on same PC and same compiler. — GIRISH kuniyal, Nov 23 '16 at 18:21
@GIRISHkuniyal Why the became different? Initialization is different. — Algirdas Preidžius, Nov 23 '16 at 18:25
@GIRISHkuniyal In the first case, the vector knows how many elements you want inserted total. It could be that you never insert elements again (ex: if you had declared `a` as `const`), so no need to allocate extra elements. In the second case, each `push_back` calls assumes more calls are to come, so the vector is conservative and allocates more just in case. — KABoissonneault, Nov 23 '16 at 18:29

score 3 · Accepted Answer · answered Nov 23 '16 at 18:24

The reason is related to the very essence of the extension algorithm of the vector. When initializing a vector, the number of extra capacity applied is 0. In the i-th time an extension is needed, the vector copies its contain to a new vector, with capacity doubled then its current size. This method makes the whole idea of size-changing array very efficient, since in amortized time (meaning the average time over N operations), we get O(1) insertion complexity. You can see that after we add one more integer to the first vector, we get a capacity of 6. http://coliru.stacked-crooked.com/a/f084820652f025b8

score 0 · Answer 2 · answered Nov 23 '16 at 18:30

By allocating more elements than needed, the vector does not need to reallocate memory when new elements are added to the vector. Also, when reducing the size, reallocation is not needed at all.

Reallocation of memory is a relatively expensive operation (creating new block, copying elements across, removing old block).

The trade-off is that the vector may have allocated more memory than it will need (e.g. if it allocates memory for elements that never get added/used). Practically, unless available memory is scarce, the cost of allocating a larger block (and reallocating less often) is less than the cost or reallocating every time.

Why vector has different capacity and other than the size?

2 Answers2