Exponential growth policy of std::vector

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.

Leave a Reply

Your email address will not be published. Required fields are marked *