Iterators and Algorithms: How the Pieces Connect

Zara wrote a careful search for a vector of exam marks. She tested it on an empty vector first, as she always does, and it passed. Then her team switched the marks to a deque, and she sighed: she would have to write the search again.

She did not. Her search was std::find, and std::find does not know what a vector is. It only knows how to walk from one iterator to another. Change the container and the same line keeps working.

This lesson is about that walk. It connects every container in Lesson 3 to every algorithm in this track. So it is the one picture worth seeing move.

You already know one iterator: the pointer

In C you walked an array with a pointer. You started at the first element, read it with *p, moved with ++p, and stopped at a pointer one past the last element. That pointer is an iterator: something that points at an element and can move to the next one.

In STL code that walk always has the same shape. Here it is with every part named; Example 1 then shows it with plain pointers.

for (auto it = c.begin(); it != c.end(); ++it) { use(*it); }

#include <iostream>

int main()
{
    int marks[] = {72, 45, 90, 61};
    int *first = marks;
    int *last = marks + 4;
    std::cout << "marks:";
    for (int *p = first; p != last; ++p) std::cout << ' ' << *p;
    std::cout << '\n';
}

marks: 72 45 90 61

begin() and end(): the same walk over any container

Every STL container hands out two iterators. begin() points at the first element. end() points one past the last element, the same empty slot as last above. You never read from end(); you only stop when you reach it.

A container's iterator is not always a plain pointer. A list iterator follows a link to the next node, and a deque iterator may hop from one block of memory to the next. But all of them answer the same three requests: read (*it), move (++it), and compare (it != end).

Here is the walk, moving. Step through it on the vector first, then on the deque. Watch the last step: the iterator lands on end(), the loop stops, and nothing is read there.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {72, 45, 90, 61};
    std::cout << "v:";
    for (auto it = v.begin(); it != v.end(); ++it) std::cout << ' ' << *it;
    std::cout << '\n';
    std::cout << "size from the iterators: " << (v.end() - v.begin()) << '\n';
}

v: 72 45 90 61
size from the iterators: 4

The half-open range [begin, end)

Two iterators, first and last, describe a range: every element from first up to, but not including, last. Mathematicians write that as [first, last), a half-open range: the square bracket means "included" and the round one means "not included".

Why not make end() point at the last element instead? Three reasons, and you have already seen two of them.

• The count is a subtraction. end() - begin() is the number of elements, with no + 1 to remember.
• Empty needs no special case. In an empty container, begin() == end(). The loop condition is false at once, and every algorithm does nothing, correctly. Zara's empty-vector test passes without any extra code.
• "Not found" has a home. std::find returns end() when the value is not there, a position that can never be a real answer.

So a range always means "from here, up to but not including there". Every algorithm in the track takes its range this way.

One algorithm, every container

An algorithm receives two iterators and walks between them. It never receives the container. So it cannot tell, and does not care, whether the elements sit in a vector, a deque or a plain array. The only thing it needs is an iterator that can do what the algorithm asks of it.

#include <algorithm>
#include <iostream>

int main()
{
    int marks[] = {72, 45, 90, 61};
    std::sort(marks, marks + 4);
    std::cout << "sorted:";
    for (int m : marks) std::cout << ' ' << m;
    std::cout << '\n';
}

sorted: 45 61 72 90

Now four algorithms on a vector. sort puts the range in order, and find returns an iterator to a value (or end()). count counts a value, and reverse turns the range back to front.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> c = {61, 72, 45, 90, 45};
    std::sort(c.begin(), c.end());
    auto it = std::find(c.begin(), c.end(), 72);
    std::cout << "72 found: " << (it != c.end()) << '\n';
    std::cout << "45 count: " << std::count(c.begin(), c.end(), 45) << '\n';
    std::reverse(c.begin(), c.end());
    std::cout << "reversed:";
    for (int x : c) std::cout << ' ' << x;
    std::cout << '\n';
}

72 found: 1
45 count: 2
reversed: 90 72 61 45 45

#include <algorithm>
#include <deque>
#include <iostream>

int main()
{
    std::deque<int> c = {61, 72, 45, 90, 45};
    std::sort(c.begin(), c.end());
    auto it = std::find(c.begin(), c.end(), 72);
    std::cout << "72 found: " << (it != c.end()) << '\n';
    std::cout << "45 count: " << std::count(c.begin(), c.end(), 45) << '\n';
    std::reverse(c.begin(), c.end());
    std::cout << "reversed:";
    for (int x : c) std::cout << ' ' << x;
    std::cout << '\n';
}

72 found: 1
45 count: 2
reversed: 90 72 61 45 45

Part of a container is a range too

Because an algorithm takes any two iterators, you can hand it part of a container. v.begin() + 3 is "three steps in", so [v.begin(), v.begin() + 3) is the first three elements.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {90, 72, 61, 45, 10};
    std::sort(v.begin(), v.begin() + 3);
    std::cout << "first three sorted:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    std::vector<int> empty;
    std::sort(empty.begin(), empty.end());
    std::cout << "empty: begin == end is " << (empty.begin() == empty.end()) << '\n';
}

first three sorted: 61 72 90 45 10
empty: begin == end is 1

That gives the one rule this whole track keeps: an algorithm never knows which container it is walking. It knows two iterators, and the job.

for (auto it = v.begin(); it <= v.end(); ++it)
    std::cout << *it << ' ';

std::list<int> l = {3, 1, 2};
std::sort(l.begin(), l.end());

std::vector<int> a = {3, 1, 2};
std::vector<int> b = {9, 8};
std::sort(a.begin(), b.end());

Next you will open the reference every C++ programmer keeps open, and learn to read the cost it promises for every one of these operations.