selfjungle Just another WordPress weblog

std::vector appending elements in amortized constant time

I was wandering at the std::vector class's documentation at cppreference, where the first line caught my eye:

Accessing members of a vector can be done in constant time, appending elements to a vector can be done in amortized constant time, whereas locating a specific value or inserting elements into the vector takes linear time.

Adding a new element takes amortized constant time? Why not linear?

Let wikipedia explain:

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, so the amortized time per operation is O(n) / n = O(1).

How does it apply to std::vector? Does it double its size when it's full?

#include <iostream>
#include <vector>

std::vector<int> v(5); // create az int vector with 5 elements
std::cout << v.capacity() << std::endl;  // capacity = 5

v.push_back(13); // add a new element at the end of the vector
std::cout << v.capacity() << std::endl; // capacity = 10!

So std::vector doubles its size when full indeed.