vector: size, capacity and growth

A vector has a size, the number of elements in it, and a capacity, the number it can hold before it has to allocate. push_back with size() < capacity() constructs the new element in the spare space: no allocation. With size() == capacity() it must grow:

1. allocate a new buffer, larger by a constant factor;
2. move (or copy, see Module 2) every element into it;
3. destroy the old elements and free the old buffer.

libstdc++ and libc++ double the capacity; MSVC grows by one and a half times.

With geometric growth, the total cost of n pushes is O(n): the copies at each reallocation form a geometric series that sums to less than twice the final size. So the average cost per push is constant. That is what amortised O(1) means.

It says nothing about a single push. The push that triggers a reallocation of a vector of a million orders does a million moves and an allocation large enough to come straight from the kernel. On a hot path, that one push is a latency spike, and averages do not help a strategy that missed a fill during it.

• reserve(n) at start-up allocates capacity for n elements once. Pushes up to n never reallocate. Size it for the busiest day you have seen, with margin, and treat exceeding it as an event worth logging.
• Reuse. clear() destroys the elements and keeps the capacity, so a vector reused across messages stops allocating after warm-up.
• Fixed capacity. If the bound is hard, use a type that cannot grow, such as std::array with a count, or a fixed-capacity vector, and decide explicitly what happens when it is full.
• Fail loudly. In test builds, assert that the capacity did not change in the hot path.

• resize(n) changes the size, constructing or destroying elements; it reallocates only if n exceeds the capacity.
• shrink_to_fit() is a non-binding request to reduce the capacity to the size. Implementations do it by reallocating, so it is itself an allocation and a copy, and calling it on a reused buffer guarantees the next push reallocates.
• insert and erase in the middle shift every later element. For small trivially copyable elements this is a fast memmove; for large ones it is not.

push_back(x) copies or moves an existing object into the vector. emplace_back(args...) constructs the element in place from constructor arguments.

std::vector<Quote> v;
v.reserve(1 << 20);
v.push_back(Quote{4711, seq, 101250, 5, 0});   // constructs a temporary, then moves it
v.emplace_back(4711, seq, 101250, 5, 0);       // constructs in place (C++20 allows this for aggregates)

For a small trivially copyable struct the difference is nothing after optimisation. For types with expensive moves, or that cannot be moved, emplace_back avoids the temporary. Neither changes the allocation behaviour: both reallocate when the vector is full.

std::vector<bool> is not a container of bool. It is specialised to pack bits, so operator[] returns a proxy object rather than a bool&, you cannot take the address of an element, and writes to different elements from different threads race because they share a byte. Use std::vector<char> or std::vector<std::uint8_t> when you want one byte per flag.