Contiguous Container Allocation

The contiguous containers in the standard library, i.e., std::vector, std::basic_string family including std::string, have methods to view and control the allocation:

size() Number of constructed elements
resize() Changes the size. For grow, adds new elements, for shrink, deletes element beyond the new size
capacity() Number of elements that fit without reallocation
reserve() Grows capacity (not the size)

To allow you to efficiently use std::vector without worrying about manual reallocation, the language standard states for push_back() and emplace_back() that they must have "amortized O(1)" complexity.

For libstdc++(GCC) and libc++ (Clang), the growth factor is 2×:

`std::vector<int> v`	Size Before	Capacity Before	Realloc?	Capacity After	Copied Elements
`v.push_back(1)`	0	0	yes	1	0
`v.push_back(2)`	1	1	yes	2	1
`v.push_back(3)`	2	2	yes	4	2
`v.push_back(4)`	3	4	no	4	0
`v.push_back(5)`	4	4	yes	8	4
`v.push_back(6)`	5	8	no	8	0
`v.push_back(7)`	6	8	no	8	0
`v.push_back(8)`	7	8	no	8	0
`v.push_back(9)`	8	8	yes	16	8
`v.push_back(10)` – `v.push_back(16)`	9–15	16	no	16	0
`v.push_back(17)`	16	16	yes	32	16
`v.push_back(18)` – `v.push_back(32)`	17–31	32	no	32	0
`v.push_back(33)`	32	32	yes	64	32

The GCC code is in _M_check_len(), and the Clang code is in __recommend()
The new capacity at each reallocation is size + max(size, 1), which for all cases after the first is just 2 * size
The total number of move operations across all reallocations to reach size N grows as O(N). This is the geometric series 1 + 2 + 4 + 8 + …, which converges to roughly 2N, which is what gives push_back its amortized O(1) guarantee
The wastage (capacity() - size()) is from the range of [0%, 50%). shrink_to_fit() can be used to reduce this, or by swapping std::vector<int>(v).swap(v);

We can verify the table using code:

For MSVC, the growth factor is 1.5×:

`std::vector<int> v`	Size Before	Capacity Before	Realloc?	Capacity After	Copied Elements
`v.push_back(1)`	0	0	yes	1	0
`v.push_back(2)`	1	1	yes	2	1
`v.push_back(3)`	2	2	yes	3	2
`v.push_back(4)`	3	3	yes	4	3
`v.push_back(5)`	4	4	yes	6	4
`v.push_back(6)`	5	6	no	6	0
`v.push_back(7)`	6	6	yes	9	6
`v.push_back(8)` – `v.push_back(9)`	7–8	9	no	9	0
`v.push_back(10)`	9	9	yes	13	9
`v.push_back(11)` – `v.push_back(13)`	10–12	13	no	13	0
`v.push_back(14)`	13	13	yes	19	13
`v.push_back(15)` – `v.push_back(19)`	14–18	19	no	19	0
`v.push_back(20)`	19	19	yes	28	19
`v.push_back(21)` – `v.push_back(28)`	20–27	28	no	28	0
`v.push_back(29)`	28	28	yes	42	28
`v.push_back(30)` – `v.push_back(33)`	29–32	42	no	42	0

In _Calculate_growth()
Note the multiple reallocations at the start
The new capacity at each reallocation is size + size / 2 (integer division), which for large capacities approaches 1.5 * size
The total number of move operations across all reallocations to reach size N grows as O(N). For 1.5× growth the geometric series going back from N is N + N·(2/3) + N·(2/3)² + …, which converges to roughly 3N — more total copies than 2× growth, since reallocations are more frequent
The wastage (capacity() - size()) is in the range [0%, 33%). Just after a reallocation, the new capacity is ~1.5× the old, and only one new element has been added, leaving ~1/3 of the allocation unused. shrink_to_fit() can be used to reduce this, or by swapping std::vector<int>(v).swap(v);