Skip to content
Tutorials Center
My learning

Topics

Lesson 96 of 171 ยท The Standard Library (STL)

std::vector in Depth

How std::vector really works - geometric growth and amortized cost, reserve and shrink_to_fit, emplace_back vs push_back, erase-remove, std::erase and vector<bool>.

You already know how to use std::vector from the std::vector lesson: push_back, indexing, size() and capacity(). This lesson opens the hood. A vector is three pointers (start of the buffer, end of the elements, end of the buffer) and a handful of rules about when it allocates, when it moves elements, and when your iterators stop being valid. Knowing those rules is what separates code that is "fine on my machine" from code that stays fast with ten million elements.

You'll measure the growth strategy and see why appending is amortized constant time, count real heap allocations, learn when emplace_back beats push_back (and when it doesn't), understand what std::remove actually does, and meet the strange std::vector<bool> specialization that every C++ programmer trips over once.

What a vector is in memory

A std::vector<T> object itself is small: on GCC it's 24 bytes on a 64-bit machine, three pointers. The elements live in one contiguous heap block that the vector owns. Contiguity is the whole point:

  • v[i] is a single address computation, so random access is O(1).
  • Elements sit next to each other, so looping over them is cache-friendly; this is why a vector usually beats a linked list even for jobs where the list "should" win (see std::deque, std::list and std::forward_list).
  • v.data() gives you a T* you can pass to C APIs that expect an array, and a vector converts directly to a std::span.

The block has room for capacity() elements, of which the first size() are alive. The slots after size() are raw memory: no objects exist there yet, which is why writing v[size()] is undefined behavior even when the capacity is larger.

Growth strategy and amortized cost

When you push_back into a full vector, it must allocate a bigger block, move (or copy) every existing element across, destroy the old elements and free the old block. That costs O(n). If the vector grew by a fixed amount, say 10 slots each time, pushing n elements would cost about nยฒ/20 element moves: quadratic. Instead every major library grows geometrically, multiplying the capacity by a constant factor (2 in GCC and Clang's libraries, 1.5 in Microsoft's).

With doubling, the reallocations for n pushes move 1 + 2 + 4 + โ€ฆ + n/2 elements in total, which is less than n. Spread over n pushes, that's fewer than one extra move per element. The occasional expensive push is "paid for" by the many cheap ones, so we say push_back is amortized O(1). Let's count it by watching the capacity change and counting how often the move constructor runs:

C++ Counting reallocations and element moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

A hundred thousand pushes trigger only 18 reallocations, and each element was relocated about 1.3 times on average; the ratio stays below 2 however large n gets. With reserve, there's a single allocation up front and zero relocations. Two lessons follow:

  • Appending to a vector is cheap even without reserve. Don't litter code with reserve calls where the size is unknown.
  • When you do know the final size (you're copying or transforming another container, or you just read a count from input), reserve removes all the reallocations and keeps references valid while you fill the vector.

Why noexcept moves matter here

Relocation uses the element's move constructor only if it is noexcept (or if the type can't be copied). Otherwise the vector copies every element on each growth, to keep the strong exception guarantee of push_back. Delete the noexcept from Tracked above and run again: the move counter drops to zero because the copy constructor does all the work. Move Semantics shows this in detail. Classes that follow the rule of zero get noexcept moves for free.

The reserve trap

Calling reserve inside a loop with a slightly larger number each time destroys the geometric growth: GCC allocates exactly what you ask for, so v.reserve(v.size() + 1) before every push turns appending back into an O(nยฒ) operation. Reserve once, up front, or not at all.

Shrinking: clear, shrink_to_fit and swap

A vector never gives memory back on its own. clear(), erase(), pop_back() and resize() to a smaller size destroy elements but keep the capacity, because the most common next step is to fill the vector again. If a vector briefly held a million elements and will stay small, release the memory explicitly:

C++ Giving memory back

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

shrink_to_fit is officially a request, though every mainstream library honors it by reallocating to exactly size() elements. The swap trick guarantees the release and still appears in older code. The last loop shows the opposite habit: when a vector is a scratch buffer reused every frame or every request, clear() and refill, and the allocator is never touched after the first round.

emplace_back vs push_back

push_back(x) takes an already constructed T and copies or moves it into the new slot. emplace_back(args...) forwards its arguments to T's constructor and builds the element directly in the slot. For a type that's expensive to move, or not movable at all, that difference matters:

C++ What push_back and emplace_back construct

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

For an existing object, push_back and emplace_back do the same thing. The win from emplace_back comes only when you pass constructor arguments, and even then it saves one move, which is nearly free for most types. So prefer clarity:

  • Use push_back(value) when you already have the value.
  • Use emplace_back(args...) when you would otherwise write push_back(T{args...}), or when T can't be moved.

Two subtle differences cut the other way:

  • emplace_back can call explicit constructors, because it constructs directly. std::vector<std::vector<int>> grid; grid.emplace_back(1'000'000); silently adds a vector of a million zeros, while grid.push_back(1'000'000) fails to compile, which is what you'd want if that was a typo.
  • emplace_back can't deduce a braced list: orders.emplace_back({"desk", 2}) doesn't compile, while push_back({"desk", 2}) does.

emplace_back also returns a reference to the new element (since C++17), handy for auto& o = orders.emplace_back("pen", 9);. Its sibling emplace(pos, args...) constructs at any position.

Inserting and erasing in the middle

A vector is fast at the back and slow everywhere else. insert(pos, x) and erase(pos) must shift every element after pos by one slot, so they're O(n โˆ’ pos). Erasing the first element of a million-element vector moves 999,999 elements. Patterns that avoid the cost:

  • Batch your inserts. v.insert(pos, first, last) or v.insert_range(pos, range) (C++23) shift the tail once for the whole batch, instead of once per element.
  • Swap and pop when order doesn't matter. To remove element i, move the last element into slot i and pop_back(): O(1).
  • Remove many elements in one pass with the erase-remove idiom or std::erase_if, described next.
  • If you truly need cheap insertion at the front, a std::deque gives O(1) at both ends.

The erase-remove idiom and std::erase

std::remove and std::remove_if from <algorithm> have misleading names. They work through iterators and can't change the container's size, so they don't remove anything. Instead they shift the elements you want to keep to the front, in order, and return an iterator to the new logical end. Whatever is left after that iterator is in a valid but unspecified (moved-from) state. You then call the container's erase to chop off the tail:

C++ What remove really does

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

After std::remove, the size is still 7: the kept values 3, 7, 9, 4 sit at the front, and the last three slots hold leftovers (here, the old values, since moving an int is a copy). Forgetting the erase is a classic bug: the "removed" elements are still counted in size().

In C++20 and later, write std::erase(v, value) and std::erase_if(v, predicate). They do the same single pass, can't be half-written, return the number of removed elements, and exist for every standard container (for node-based containers they call the right member functions). Each pass is O(n), compared with O(nยฒ) for calling v.erase(it) in a loop. With ranges, std::ranges::remove returns a subrange, so the idiom becomes v.erase(std::ranges::remove(v, 0).begin(), v.end());, but std::erase is still shorter.

Iterator invalidation rules

Because elements can move, operations that change a vector invalidate iterators, pointers and references into it. Memorize this short table (the full story is in Iterators):

Operation What becomes invalid
push_back, emplace_back, insert, emplace, resize, reserve that reallocate Everything
The same operations without reallocation Only positions at or after the insertion point (and end())
erase, pop_back The erased elements and everything after them (and end())
clear Everything
swap of two vectors Nothing: iterators now refer into the other vector

v.erase(it) returns an iterator to the element after the erased one; use it if you must erase in a hand-written loop (it = v.erase(it); instead of ++it). And a sneaky one: v.push_back(v[0]) is fine (the library handles self-references), but const int& first = v[0]; v.push_back(1); use(first); is undefined behavior if the push reallocated.

The vector oddity

std::vector<bool> is not a container of bools. The standard specializes it to pack eight values into each byte, which saves memory but breaks the normal rules:

  • v[i] returns a proxy object (std::vector<bool>::reference), not a bool&. You can't bind a bool& to an element or take &v[i].
  • auto x = v[i]; makes x a proxy that still refers into the vector, not a copy of the value.
  • for (auto& b : flags) doesn't compile; for (auto b : flags) gives proxies; for (bool b : flags) copies values.
  • There's no data() returning bool*, and different elements share bytes, so two threads writing different elements race with each other.
C++ vector of bool hands out proxies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The comment marks the line that would not compile; uncomment it to see GCC's error. When you want ordinary container semantics, use std::vector<char> or std::vector<std::uint8_t> (one byte per flag), or std::deque<bool>, which is not specialized. For a fixed number of bits known at compile time, std::bitset is the clearer tool. std::vector<bool> is fine when you only need a large, dense, single-threaded bit array, such as a sieve of Eratosthenes, and you only read and write through v[i].

Other details professionals rely on

  • at(i) checks bounds and throws std::out_of_range; v[i] doesn't check. GCC can add checks to [] in debug builds with -D_GLIBCXX_ASSERTIONS.
  • assign(n, value) and assign_range(r) (C++23) replace the contents but reuse the buffer when it's big enough.
  • resize(n) value-initializes new ints to zero; resize(n, value) fills with value.
  • Comparison: == compares sizes and elements; <, <=> compare lexicographically.
  • Element types must be movable or copyable to support growth; references can't be stored (use std::reference_wrapper or pointers). A vector of std::unique_ptr works because it's movable.
  • Never assume a growth factor. Code that relies on capacity being a power of two is broken on MSVC.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is push_back on a std::vector called amortized O(1)?

    Growing by a constant factor means the reallocations move fewer than about 2n elements in total, so the average cost per push is constant even though a single push can be O(n).
  2. 2. std::vector<int> v{1, 0, 2, 0}; std::remove(v.begin(), v.end(), 0); What is v.size() afterwards?

    std::remove only shifts the kept elements to the front and returns the new logical end. The size changes only when you call erase, or when you use std::erase(v, 0) instead.
  3. 3. Which call compiles but quietly does something different from push_back with the same argument?

    The vector(size_type) constructor is explicit, so push_back(1000) doesn't compile, but emplace_back calls it directly and adds a vector of 1000 zeros.
  4. 4. After std::vector<int> v(1000); v.clear();, what is true?

    clear destroys the elements but keeps the buffer for reuse. Call shrink_to_fit (or swap with an empty vector) to release it.
  5. 5. Why does for (auto& b : flags) fail to compile when flags is a std::vector<bool>?

    vector<bool> packs bits, so its iterators return proxy objects by value. Use auto, bool, or const auto& instead, or switch to vector<char>.

Summary

  • A vector owns one contiguous block; size() elements are alive, capacity() slots are allocated, and slots past size() hold no objects.
  • Growth is geometric (2ร— in GCC, 1.5ร— in MSVC), so push_back is amortized O(1). reserve once when you know the final size; never reserve(size() + 1) in a loop.
  • Shrinking operations keep the capacity. Use shrink_to_fit or the swap trick to release memory, and reuse cleared vectors as scratch buffers.
  • emplace_back(args...) builds in place; with an existing object it equals push_back. Beware that it can call explicit constructors.
  • std::remove doesn't change the size; pair it with erase, or use C++20's std::erase / std::erase_if. Swap-and-pop removes in O(1) when order doesn't matter.
  • Reallocation invalidates every iterator, pointer and reference; erase invalidates from the erased position onward.
  • std::vector<bool> stores bits and hands out proxies. Prefer vector<char>, deque<bool> or std::bitset when you need normal semantics.

Next: std::deque, std::list and std::forward_list, the sequence containers that trade contiguity for cheap insertion at the front or in the middle.