We can't find the internet
Attempting to reconnect
Something went wrong!
Attempting to reconnect
← Containers, Strings, Algorithms step 1 of 5
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. Preferemplace_backwhen 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.
Stuck?
C++ reference solution
Sign in to attempt this problem and reveal the reference solution.