vector: growth, capacity, and invalidation

size tracks objects; capacity tracks storage

Ordinary vector<T> stores elements contiguously, which fits sequential scans, random access, and interfaces that need a contiguous array. vector<bool> is a specialization; do not copy conclusions about ordinary element references or contiguous storage onto it. size() is the number of live elements and capacity() is how many elements can be held without reallocating. Both queries are constant time.

reserve(n) does not add elements. It reallocates only when n is greater than the current capacity, and after success the capacity is at least n. resize(n) changes the element count: shrinking destroys objects at the tail, growing constructs new ones. Under the default allocator, newly default-inserted vector<int> elements are zero. Reserved space still does not make v[v.size()] accessible, because no element the container may index exists there. Think of capacity as unused raw storage the container already owns, not as extra live objects waiting to be named.

Amortized constant is not every-call constant

A single append at the end has amortized constant complexity: the total cost of a sequence of appends can be averaged, yet the particular call that triggers reallocation may still move or copy every existing element. Common implementations grow by some factor, but the standard does not promise doubling, a starting capacity, or any specific growth sequence. Insertion in the middle still has to move the suffix; spare capacity does not turn that into a constant-time operation.

A single reserve is useful when the final size is known. Calling reserve(size()+1) before every append can force repeated relocations and destroy the usual growth efficiency. Shrinking with resize does not shrink capacity; shrink_to_fit is a non-binding request, not a promise to release down to an exact size. Complexity describes how cost grows with the number of elements. Expensive moves of the elements themselves still belong in the real cost, so a cheap integer vector and a vector of heavy objects do not have the same wall-clock profile even when both appends are amortized constant.

Treat the modification point as a validity boundary

Reallocation invalidates every element pointer, reference, iterator, and the old end(). Insertion that does not reallocate keeps those handles only for elements before the insertion point; a tail insert therefore keeps handles to existing elements, yet still invalidates the old end(). Erasure invalidates iterators and references at and after the erased position. Continue traversal with the new position erase returns.

The example first reserves capacity, then checks that a tail insert does not break a reference to the first element. Afterwards it obtains positions only through the container again. Do not dereference an old pointer to "test whether it was invalidated"—the access itself may be undefined behavior once invalidation has occurred. When you need to keep a business identity for a long time, a stable identifier is usually easier to maintain than depending on an element's address. If a later push_back might reallocate, treat every previously captured handle as spent unless you have already reserved enough capacity for that growth.

Pitfalls

• reserve only reserves storage; it does not make the capacity range a legal subscript range. Legal subscripts are always less than size.
• No reallocation is not the same as no invalidation: mid-sequence insertion, erasure, and the old end() each have their own rules.

Minimum C++11 · complete program · Download .cpp

#include <cassert>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{10, 20};
    values.reserve(4);
    assert(values.size() == 2 && values.capacity() >= 4);
    int* first = &values.front();
    values.push_back(30);
    assert(*first == 10);
    assert(first == &values.front());

    values.resize(5);
    assert(values[3] == 0 && values[4] == 0);
    values.resize(3);
    auto next = values.erase(values.begin() + 1);
    assert(next != values.end() && *next == 30);
    assert((values == std::vector<int>{10, 30}));
    std::cout << values[0] << ' ' << values[1] << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-vector.cpp -o example && ./example

Expected result

10 30

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Starting from an empty vector<int>, call reserve(100), then you need exactly 100 zeros. Should you append 100 times, or assign through subscripts? Give the most direct code.

Check the sources

• Working draft [vector.capacity]: reserve, resize, and reallocation
• Working draft [vector.modifiers]: insertion and erasure invalidation

Drafts and official chapters change. The version mark is only the example’s minimum.