A [[std::vector]] grows by allocating a bigger block, copying or moving the elements into it and releasing the old one. That strategy gives you constant-time [[push_back]] on average, but it costs memory and it invalidates iterators and references. Knowing when the vector reallocates is the difference between code that works and code that mysteriously breaks.
Capacity and size
A vector has a size, which is the number of elements it holds, and a capacity, which is the number of elements it can hold without reallocating.
#include
#include
#include
int main() {
std::vector parcels;
std::cout << "empty vector: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
parcels.push_back("p-001");
parcels.push_back("p-002");
parcels.push_back("p-003");
std::cout << "after three: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
parcels.pop_back();
std::cout << "after pop: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
return 0;
}The output shows that removing an element does not reduce the capacity:
empty vector: size=0 capacity=0
after three: size=3 capacity=4
after pop: size=2 capacity=4The exact capacities are implementation defined, but the pattern is always the same: capacity is at least the size, and it never shrinks on its own.
How the growth works
When a vector runs out of capacity it allocates a new block, moves or copies the elements across and frees the old block. Most implementations grow geometrically, so the number of reallocations for n insertions is logarithmic rather than linear.
#include
#include
int main() {
std::vector parcels;
int reallocations = 0;
std::size_t last_capacity = parcels.capacity();
for (int i = 0; i < 16; ++i) {
parcels.push_back(i);
if (parcels.capacity() != last_capacity) {
++reallocations;
std::cout << "grew to capacity " << parcels.capacity()
<< " at size " << parcels.size() << '\n';
last_capacity = parcels.capacity();
}
}
std::cout << "reallocations: " << reallocations << '\n';
return 0;
}The output shows the geometric growth in action:
grew to capacity 1 at size 1
grew to capacity 2 at size 2
grew to capacity 4 at size 3
grew to capacity 8 at size 5
grew to capacity 16 at size 9
reallocations: 5Sixteen insertions caused five reallocations. The alternative, growing by one each time, would have caused fifteen.
reserve and resize
reserve changes the capacity without changing the size. resize changes the size, adding default-constructed elements if it grows.
#include
#include
#include
int main() {
std::vector parcels;
parcels.reserve(100);
std::cout << "after reserve: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
parcels.resize(3);
std::cout << "after resize: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
for (const std::string& parcel : parcels) {
std::cout << "[" << parcel << "] ";
}
std::cout << '\n';
return 0;
}The output shows the reserve giving capacity without elements, and the resize adding three empty strings:
after reserve: size=0 capacity=100
after resize: size=3 capacity=100
[] [] []Reserving is worth it when you know the final size, because it turns many reallocations into one.
The cost of not reserving
When a vector reallocates, it moves or copies every element it already holds. For a vector of a million records, that is a lot of work spread over the insertions.
#include
#include
#include
#include
int main() {
const int count = 200000;
auto start = std::chrono::steady_clock::now();
std::vector growing;
for (int i = 0; i < count; ++i) {
growing.push_back(i);
}
auto middle = std::chrono::steady_clock::now();
std::vector reserved;
reserved.reserve(count);
for (int i = 0; i < count; ++i) {
reserved.push_back(i);
}
auto finish = std::chrono::steady_clock::now();
auto grow_ms = std::chrono::duration_cast(middle - start).count();
auto reserve_ms = std::chrono::duration_cast(finish - middle).count();
std::cout << "growing: " << grow_ms << " ms\n";
std::cout << "reserved: " << reserve_ms << " ms\n";
return 0;
}The timings depend on the machine, but the reserved version is consistently faster, because it allocates once instead of dozens of times.
Iterator invalidation
Every reallocation invalidates all iterators, pointers and references into the vector. Using a stale one is undefined behaviour
#include
#include
#include
int main() {
std::vector parcels = {"p-001", "p-002"};
auto it = parcels.begin();
std::cout << "before: " << *it << '\n';
parcels.push_back("p-003"); // may reallocate
// *it is now undefined behaviour: it may point at freed memory.
// The safe version recomputes the iterator:
auto again = parcels.begin();
std::cout << "after: " << *again << '\n';
return 0;
}The output shows the recomputed iterator giving the right answer:
before: p-001
after: p-001There is a useful rule of thumb: if you modify the container's size, any iterator you were holding may be invalidated. Erasing an element invalidates the iterator at and after that position; inserting invalidates everything at and after the insertion point.
erase, insert and clear
#include
#include
#include
int main() {
std::vector parcels = {"p-001", "p-002", "p-003", "p-004"};
parcels.erase(parcels.begin() + 1); // remove the second
std::cout << "after erase: ";
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
parcels.insert(parcels.begin(), "p-000");
std::cout << "after insert: ";
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
parcels.clear();
std::cout << "after clear: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
return 0;
}The output shows each operation and the fact that clear keeps the capacity:
after erase: p-001 p-003 p-004
after insert: p-000 p-001 p-003 p-004
after clear: size=0 capacity=4Shrinking a vector
Nothing in the standard library automatically returns unused capacity to the allocator. A vector that grew to a million elements and shrank to ten still holds a million elements' worth of memory.
std::shrink_to_fit is a non-binding request that the vector release any unused capacity. A copy-and-swap is the guaranteed way to do it.
#include
#include
int main() {
std::vector parcels;
for (int i = 0; i < 1000; ++i) {
parcels.push_back(i);
}
std::cout << "before: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
parcels.resize(10);
std::cout << "after resize: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
std::vector tight(parcels.begin(), parcels.end());
parcels.swap(tight);
std::cout << "after swap: size=" << parcels.size()
<< " capacity=" << parcels.capacity() << '\n';
return 0;
}The output shows the capacity staying put after a resize and only shrinking when the data is copied into a fresh vector:
before: size=1000 capacity=1024
after resize: size=10 capacity=1024
after swap: size=10 capacity=10The swap trick is worth knowing because it is the only portable way to guarantee the capacity actually drops.
Vector versus the other sequence containers
A vector is not always the best sequence container, and the differences are about where the elements live.
std::vector— contiguous elements, constant-time random access, cheap appending, expensive insertion in the middle because everything has to be moved.std::deque— elements in blocks, constant-time access, cheap insertion at both ends, no contiguous guarantee.std::list— one node per element, constant-time insertion and erasure anywhere, no random access.std::forward_list— singly linked, the smallest node, no.size()and only forward iteration.
Insertion in the middle of a vector is the case that surprises people. Inserting one element at the front of a vector of a million elements moves a million elements. The same insertion into a list moves a pointer.
#include
#include
#include
int main() {
std::vector vector_parcels(5, 1);
std::list list_parcels(5, 1);
vector_parcels.insert(vector_parcels.begin(), 99);
list_parcels.insert(list_parcels.begin(), 99);
std::cout << "vector front: " << vector_parcels.front() << '\n';
std::cout << "list front: " << list_parcels.front() << '\n';
std::cout << "vector size: " << vector_parcels.size() << '\n';
std::cout << "list size: " << list_parcels.size() << '\n';
return 0;
}The output shows both front insertions succeeding, with the difference lying in the cost rather than the result:
vector front: 99
list front: 99
vector size: 6
list size: 6The rule is simple: use a vector unless you have a specific reason not to. A reason would be frequent insertion or erasure in the middle of a large collection, or a need to keep pointers to elements stable.
Quick reference
- Size is how many elements there are; capacity is how many fit without reallocating.
- Growth is geometric, so
ninsertions cost aboutlog nreallocations. reservesets the capacity;resizesets the size.- Reserve when you know the final size, especially for large containers.
- Every reallocation invalidates iterators, pointers and references.
eraseandinsertinvalidate iterators at and after the affected position.clearempties a vector but keeps its capacity.
Try it yourself: build a vector of a thousand parcel records and time the construction with and without a [[reserve]]. Then print the capacity after every insertion and watch the growth pattern. Finally, take an iterator into the middle of the vector, insert an element and use the old iterator again to see how the behaviour changes.