Skip to content

← Containers, Strings, Algorithms step 1 of 5

Easy Primitives

The vector that moves everything, repeatedly

std::vector stores its elements in one contiguous block. That is where its speed comes from — the whole thing walks in cache order — and it is also why it cannot grow in place. When it runs out of room it allocates a bigger block, relocates every element into it, and frees the old one.

It does not do this one element at a time. It multiplies the capacity, typically doubling it, so n push_backs cost O(n) relocations in total rather than O(n²). That is what “amortised constant time” means, and it is the reason push_back in a loop is a reasonable thing to write.

Amortised is not free:

push_back x 8, starting empty:
  capacity 0 -> 1   move 0 existing
  capacity 1 -> 2   move 1
  capacity 2 -> 4   move 2
  capacity 4 -> 8   move 4
                    ---------
                    7 relocations, plus the 8 insertions

Nearly twice the element operations, four allocations instead of one, and every pointer, reference and iterator into the vector invalidated four times along the way.

reserve, when you know

std::vector<Item> out;
out.reserve(n);        // one allocation, and capacity stops changing

reserve sets capacity, not size. The vector is still empty afterwards; it simply has room. If you know how many elements are coming — and you usually do, or can count them in a cheap first pass — this turns n allocations into one.

reserve is not resize

This is the mistake that follows the lesson:

out.resize(n);            // n default-constructed elements, size == n
for (...) out.push_back(x);   // ...and now there are 2n
changes size constructs elements
reserve(n) no no
resize(n) yes yes

Use resize when you are about to assign by index. Use reserve when you are about to push_back.

Two more, briefly

  • emplace_back(args...) constructs the element in place from its constructor arguments; push_back(x) takes an object that already exists. Prefer emplace_back when you would otherwise build a temporary purely to hand it over.
  • shrink_to_fit() is a request. An implementation may ignore it.

Your task

std::vector<Item> filtered(std::vector<Item>& items, int threshold);

Move every item whose value is at least threshold into a new vector, in order, and return it. items keeps its size.

Item counts its own copies and moves, and the harness prints both. There should be exactly one move per kept item and no copies at all. The starter copies nothing and moves far too much.