A std::vector grows by allocating a bigger block, by copying or moving the elements into it and by releasing the old one. That strategy gives you a constant-time push_back on average, but it costs memory and it invalidates the iterators and the references. Knowing when the vector reallocates is the difference between the code that works and the code that mysteriously breaks.
The previous lesson in this module covered "What Does the Standard Template Library Give You?", and the next lesson in this module is about "Which Map and Set Variants Fit Which Job?".
Capacity and size
A vector has a size, which is the number of the elements that it holds, and a capacity, which is the number of the elements that it can hold without reallocating.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> 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=4And the exact capacities are implementation defined, but the pattern is always the same. The 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, it moves or copies the elements across and it frees the old block. Most of the implementations grow geometrically, so the number of the reallocations for n insertions is logarithmic rather than linear.
#include <iostream>
#include <vector>
int main() {
std::vector<int> 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: 5And sixteen insertions caused five reallocations. The alternative, which is to grow by one each time, would have caused fifteen.
reserve and resize
The reserve changes the capacity without changing the size. The resize changes the size, and it adds the default-constructed elements if it grows.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> 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 the capacity without the elements, and the resize adding three empty strings.
after reserve: size=0 capacity=100
after resize: size=3 capacity=100
[] [] []The cost of not reserving
When a vector reallocates, it moves or copies every element that it already holds. For a vector of a million records that is a lot of work spread over the insertions.
#include <chrono>
#include <iostream>
#include <string>
#include <vector>
int main() {
const int count = 200000;
auto start = std::chrono::steady_clock::now();
std::vector<int> growing;
for (int i = 0; i < count; ++i) {
growing.push_back(i);
}
auto middle = std::chrono::steady_clock::now();
std::vector<int> 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<std::chrono::milliseconds>(middle - start).count();
auto reserve_ms = std::chrono::duration_cast<std::chrono::milliseconds>(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 of the iterators, the pointers and the references into the vector. Using a stale one is undefined behaviour.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> 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-001And there is a useful rule of thumb. If you modify the size of the container, then any iterator that you were holding may be invalidated.
erase, insert and clear
Erasing an element invalidates the iterator at and after that position, and inserting invalidates everything at and after the insertion point.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> 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 the 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 the unused capacity to the allocator. A vector that grew to a million elements and shrank to ten still holds a million elements' worth of the memory. The std::shrink_to_fit is a non-binding request that the vector releases any unused capacity. A copy-and-swap is the guaranteed way to do it.
#include <iostream>
#include <vector>
int main() {
std::vector<int> 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<int> 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=10Vector versus the other sequence containers
A vector is not always the best sequence container, and the differences are about where the elements live.
the container the elements the access the insertion
------------------ ---------------- ------------------ ---------------
std::vector one block random access expensive in
is constant the middle
std::deque blocks random access cheap at both
is constant ends
std::list one node each no random access cheap anywhere
std::forward_list one node each forward only cheap anywhere
and it is the but there is no
smallest
And the 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 <iostream>
#include <list>
#include <vector>
int main() {
std::vector<int> vector_parcels(5, 1);
std::list<int> 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 of the front insertions succeeding, with the difference lying in the cost and not in the result.
vector front: 99
list front: 99
vector size: 6
list size: 6And the rule is simple. You use a vector unless you have a specific reason not to. A reason would be the frequent insertion or the erasure in the middle of a large collection, or the need to keep the pointers to the elements stable.
Quick reference
- The size is how many elements there are, and the capacity is how many fit without reallocating.
- The growth is geometric, so n insertions cost about the logarithm of n reallocations.
- The reserve sets the capacity and the resize sets the size.
- Reserve when you know the final size, and especially for the large containers.
- Every reallocation invalidates the iterators, the pointers and the references.
- The erase and the insert invalidate the iterators at and after the affected position, and the clear empties 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.