How Do Iterators Walk Containers?

Iterators walk containers in C++ by behaving like a pointer that knows where it is and how to move to the next element. Every container defines its own iterator type, and the algorithms are written against those types rather than against the containers. Understanding the categories of iterator explains why some algorithms work on a list and others do not.

What an iterator does

An iterator supports three things: dereferencing with * to read the element, incrementing with ++ to move on, and comparing with another iterator to test for equality.

#include 
#include 
#include 

int main() {
    std::vector parcels = {"p-001", "p-002", "p-003"};

    auto it = parcels.begin();
    while (it != parcels.end()) {
        std::cout << *it << '\n';
        ++it;
    }
    return 0;
}

The output shows the three parcels in order:

p-001
p-002
p-003

The .end() iterator marks one past the last element. It is never dereferenced; it is only compared against.

The categories

The standard library sorts iterators into five categories, each with more capabilities than the last.

• Input iterators — read-only, single pass. You can read the current element and move forward, but not go back or save the position.
• Output iterators — write-only, single pass. You can assign to the current position and move forward.
• Forward iterators — read and write, and you can traverse the sequence more than once.
• Bidirectional iterators — forward iterators plus the ability to move backwards.
• Random access iterators — bidirectional iterators plus jumping to any position in constant time.

A std::vector gives random access iterators. A std::list gives bidirectional ones. A std::forward_list gives forward ones. This is why std::sort works on a vector but not on a list: sorting needs random access.

#include 
#include 
#include 
#include 
#include 

int main() {
    std::vector parcels = {3, 1, 2};
    std::sort(parcels.begin(), parcels.end());
    std::cout << "vector sorted: " << parcels[0] << parcels[1] << parcels[2] << '\n';

    std::list route = {3, 1, 2};
    route.sort();          // the list has its own sort, which works fine
    auto it = route.begin();
    std::cout << "list sorted:   " << *it++;
    std::cout << *it++;
    std::cout << *it << '\n';

    std::forward_list chain = {3, 1, 2};
    chain.sort();
    std::cout << "forward_list sorted ok\n";
    return 0;
}

The output shows all three sorted, each with the algorithm the container supports:

vector sorted: 123
list sorted:   123
forward_list sorted ok

A reference is not an iterator

A reference is bound to an object and cannot be reseated. An iterator is a position that can be moved. They look similar but behave differently in ways that matter.

#include 
#include 
#include 

int main() {
    std::vector parcels = {"p-001", "p-002", "p-003"};

    auto& reference = parcels[0];
    auto iterator = parcels.begin();

    std::cout << "reference: " << reference << '\n';
    std::cout << "iterator:  " << *iterator << '\n';

    ++iterator;
    std::cout << "after ++:  " << *iterator << '\n';
    std::cout << "reference still: " << reference << '\n';
    return 0;
}

The output shows the iterator moving on while the reference stays where it was:

reference: p-001
iterator:  p-001
after ++:  p-002
reference still: p-001

Writing code that accepts any container

The most useful thing about iterators is that a function written in terms of them works with every container.

#include 
#include 
#include 
#include 

template 
void print_all(const Container& container) {
    for (auto it = container.begin(); it != container.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::vector parcels = {"p-001", "p-002"};
    std::list route = {"r-001", "r-002"};

    print_all(parcels);
    print_all(route);
    return 0;
}

The output shows one template handling two containers:

p-001 p-002 
r-001 r-002

Because the template takes the container type as a parameter rather than the element type, it works for any container of any element type.

Iterator adapters

The standard library provides adapters that turn a container into an iterator sequence or reshape one.

#include 
#include 
#include 
#include 
#include 

int main() {
    std::vector parcels = {1, 2, 3, 4, 5};

    std::vector doubled;
    std::transform(parcels.begin(), parcels.end(),
                   std::back_inserter(doubled),
                   [](int weight) { return weight * 2; });

    for (int weight : doubled) {
        std::cout << weight << ' ';
    }
    std::cout << '\n';

    std::vector first_three(parcels.begin(), parcels.begin() + 3);
    std::cout << "first three sum: "
              << std::accumulate(first_three.begin(), first_three.end(), 0) << '\n';
    return 0;
}

The output shows the transform writing into a new vector and the range being restricted:

2 4 6 8 10 
first three sum: 6

std::back_inserter is the important one. It turns an output iterator into a "push to the end" writer, which is how an algorithm can fill a container whose size it does not know in advance.

Common iterator mistakes

• Comparing iterators from different containers. The behaviour is undefined.
• Dereferencing .end(). Undefined behaviour; the end iterator points one past the last element.
• Using an iterator after the container changed size. It may have been invalidated.
• Mixing iterator types. A std::vector<int>::iterator and a std::vector<int>::const_iterator can be compared, but a vector iterator and a list iterator cannot.

Quick reference

• An iterator is a position: it supports *, ++ and comparison with .end().
• Five categories: input, output, forward, bidirectional and random access.
• The category decides which algorithms can be used with a container.
• A reference is fixed to an object; an iterator can be moved.
• Templates over the container type work with any container.
• std::back_inserter lets an algorithm write into a growing container.

Try it yourself: write a function that takes two iterators and returns the number of elements between them, then call it with the [[.begin()]] and [[.end()]] of a vector and of a list. Next, use [[std::transform]] with a [[std::back_inserter]] to double a vector into a second one. Finally, take an iterator, erase an element before it and use the old iterator again to see the invalidation.