Once std::vector is filled (size() equals to capacity()), a subsequent push_back(…) results in an exponential expansion of the vector capacity. The following table shows that the expansion happens when the index reaches a power of two:
index: 0, capacity: 1, address: 0x1fa6c20 index: 1, capacity: 2, address: 0x1fa6c40 index: 2, capacity: 4, address: 0x1fa6c20 index: 4, capacity: 8, address: 0x1fa6c60 index: 8, capacity: 16, address: 0x1fa6c90 index: 16, capacity: 32, address: 0x1fa6ce0 index: 32, capacity: 64, address: 0x1fa6d70 index: 64, capacity: 128, address: 0x1fa6e80 index: 128, capacity: 256, address: 0x1fa7090 index: 256, capacity: 512, address: 0x1fa74a0 index: 512, capacity: 1024, address: 0x1fa7cb0 index: 1024, capacity: 2048, address: 0x1fa8cc0 index: 2048, capacity: 4096, address: 0x1faacd0 index: 4096, capacity: 8192, address: 0x1faece0 index: 8192, capacity: 16384, address: 0x1fb6cf0 index: 16384, capacity: 32768, address: 0x1fc6d00 index: 32768, capacity: 65536, address: 0x1fe6d10 index: 65536, capacity: 131072, address: 0x2026d20 index: 131072, capacity: 262144, address: 0x20a6d30 index: 262144, capacity: 524288, address: 0x21a6d40 index: 524288, capacity: 1048576, address: 0x23a6d50 index: 1048576, capacity: 2097152, address: 0x27a6d60 index: 2097152, capacity: 4194304, address: 0x2fa6d70 index: 4194304, capacity: 8388608, address: 0x7f8e9225f010 index: 8388608, capacity: 16777216, address: 0x7f8e8e25e010 index: 16777216, capacity: 33554432, address: 0x7f8e8625d010 index: 33554432, capacity: 67108864, address: 0x7f8e7625c010 index: 67108864, capacity: 134217728, address: 0x7f8e5625b010 index: 134217728, capacity: 268435456, address: 0x7f8e1625a010 index: 268435456, capacity: 536870912, address: 0x7f8d96259010 index: 536870912, capacity: 1073741824, address: 0x7f8c96258010
This is why std::vector::push_back complexity is amortized constant. Below I provided the source code that generates this table:
#include <iostream>
#include <vector>
#include <chrono>
typedef std::chrono::steady_clock Clock;
void test(bool reserve)
{
std::vector<int> v;
std::cerr << "Reserve: " << (reserve?"true":"false") << "\n";
size_t size = 1000 * 1000 * 1000;
if(reserve)
{
v.reserve(size);
//v.resize(size);
//v.clear();
}
size_t last_cap = v.capacity();
const auto start_time = Clock::now();
for (size_t i = 0; i < size; ++i)
{
v.push_back(i);
size_t cur_cap = v.capacity();
if (cur_cap != last_cap)
{
last_cap = cur_cap;
std::cout << "index: " << i << ", capacity: " << last_cap << ", address: " << static_cast<void *>(v.data()) << std::endl;
}
}
const auto end_time = Clock::now();
std::cout << "time elapsed: " << 1e-6*std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() << " s\n";
}
int main()
{
test(false);
test(true);
test(false);
}
In opposite to std::vector, the insertion or removal of elements of std::deque at the end or beginning is constant O(1), but not amortized constant.
