STL vector's capacity with 1000 init size doubles after inserting first object

STL vector's capacity doubles for no (apparent) reason.

I create a vector with an initial size of 1000, insert one item. I would expect the capacity to remain 1000.

vector <int> v开发者_运维问答ec(1000);

cout << "vector capacity " << (unsigned int)vec.capacity() << endl;
vec.push_back(11);

cout << "vector capacity " << (unsigned int)vec.capacity() << endl;

The output is: vector capacity 1000

vector capacity 2000 --> after inserting one item

The constructor for std::vector creates a vector with 1000 elements initialized with the default value, in this case 0. It does NOT create an empty vector with space for 1000 elements to be appended later.

Then you add an additional element, and thus the size() of the vector is now 1001. Since it needs to reallocate, it doubles the allocated capacity, in order to amortize latter push_back()'s.

I would expect the capacity to remain 1000.

The size starts out at 1000, so the capacity would have to be at least 1001.

As for the doubling, that's because a vector is a dynamic array, and doubling the capacity every time that the threat of size() > capacity() pops up makes sure you get amortized O(1) push_back. To cite the Wikipedia:

As n elements are inserted, the capacities form a geometric progression. Expanding the array by any constant proportion ensures that inserting n elements takes O(n) time overall, meaning that each insertion takes amortized constant time. The value of this proportion a leads to a time-space tradeoff: the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n.

First of all, don't confuse size() and capacity().

• size() gives you the number of elements the vector contains.
• capacity() gives the current number of reserved memory slots (how many elements fit in the memory the vector has reserved). The capacity is always equal or bigger than the size.

Now, vector<int> vec(1000); creates a vector of size 1000, so adding one element will give you a vector of size 1001.

The capacity, on the other hand, is automatically handled by the vector, and how, depends on the implementation. The typical way of doing it is to double the capacity whenever the vector has to grow, so in effect, the mean time to add new elements remains constant, no matter how many items there are in the vector.