Lesson 20 · Modern C++

Iterators and algorithms

An iterator marks one position in a container: *it reads the element there and ++it moves on. Two of them, begin() and end(), describe a range, and every standard algorithm works on a range instead of on a container. Walk an iterator along a five-element vector by hand, then watch std::find, std::sort and std::count do the same walk for you, see why "not found" means end(), why sort moves values but not iterators, and how growing a vector can leave old iterators pointing at nothing.

12 min10 steps5 questionsAdvanced

Fig 20 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01For std::vector<int> v{5, 2, 8, 2, 9}, where does v.end() point?

end() is one past the last element. It marks where the range stops, so loops test it != v.end() and never read *v.end(), which would be undefined behaviour.

02std::find(v.begin(), v.end(), 7) runs on a vector that holds no 7. What does it return?

Algorithms report "not found" by returning the end of the range they were given. Check the result against v.end() before you dereference it.

03p = std::find(b, e, 8) marks v[2]. Then std::sort(b, e) runs. What is *p now?

std::sort swaps values between positions; it does not move the vector's memory, so p stays valid and still marks the third place. After sorting {5, 2, 8, 2, 9} that place holds 5.

04Why does std::sort(l.begin(), l.end()) not compile for a std::list?

Each algorithm states which iterator category it needs. std::sort jumps around the range, so it needs random access; a list offers its own member function, l.sort().

05You keep b = v.begin(), then call v.push_back(1) on a vector that is full. What about b?

When push_back needs more room than capacity(), the vector moves everything to a new block and every iterator into it is invalidated. Call v.begin() again afterwards.

Key terms

Glossary

Iterator: An object that marks one position in a container. *it reads the element there; ++it moves to the next one.
begin() / end(): Member functions that return iterators to the first element and to the position just past the last one.
Range [b, e): The elements from b up to, but not including, e. An empty range has b == e.
Dereference: Reading the element an iterator marks, written *it. Dereferencing end() is undefined behaviour.
Algorithm: A standard function such as std::find, std::sort or std::count that works on a range of iterators, not on a particular container.
Iterator category: What an iterator can do: step forward only, step both ways, or jump (random access). Each algorithm says which it needs.
Undefined behaviour: The language makes no promise about what happens: the program may crash, print garbage or seem to work.
Invalidation: When a container changes in a way that leaves old iterators pointing at nothing valid, for example a vector moving to a bigger block.

Fine print

Notes and sources

A vector's iterator behaves like a pointer to an element, and in practice it often holds one. The standard only promises what it can do (its iterator category: random access, and since C++17 also contiguous; C++20 added the std::contiguous_iterator concept), not how it is built.
end() is a position, not an element: reading *v.end() is undefined behaviour. Because ranges are half-open, an empty range is simply b == e, and the number of elements is e - b.
std::sort does not promise to keep equal values in their old order (std::stable_sort does); for equal ints you cannot tell the difference. It makes O(N log N) comparisons.
Each algorithm says which iterators it needs. std::find only reads forward, so it works on every container. std::sort needs random-access iterators, so std::sort on a std::list does not compile; a list has its own l.sort().
push_back invalidates every iterator to the vector if it has to grow (the new size is larger than capacity()), and always invalidates end(). Other operations, such as insert and erase, have their own rules on cppreference.
The program on the card is real C++20. Build it with g++ -std=c++20 iter.cpp -o iter (or clang++) and run ./iter: it prints 26 2, then 5.

Quiz Unlocks after the last step.