Iterators

An iterator is a handle on one element of a container, with enough operations to move to the next one. A loop with begin and end works on a vector, a list, a string and a file, which is why the algorithms of lesson 050 are written against iterators and not against containers.

The standard library has five categories of iterator, from a single-pass input iterator to a random access one that supports + and []. A vector's iterators are random access, a list's are bidirectional, and the algorithms that need more than a type provides fail to compile rather than at run time.

An iterator is also what a range-based for loop uses underneath, so the loop and the explicit iterator walk the same positions in the same order.

begin, end, ++ and *

begin() points at the first element and end() one past the last. The loop compares the two, dereferences with * and advances with ++, and it never needs the container's size.

The program prints a vector through its iterators and then uses std::distance to count the steps between begin and end. distance works for every category, while end - begin only works for random access iterators.

The end iterator is a position, not an element: dereferencing it is undefined. The half-open range [begin, end) is the convention every algorithm in the library follows.

An empty container has begin() == end(), and the loop simply does not run. That is the other reason the library uses a half-open range: emptiness needs no special case.

#include <iostream> #include <iterator> #include <vector> int main() { std::vector<int> values{10, 20, 30}; for (auto it = values.begin(); it != values.end(); ++it) { std::cout << *it << ' '; } std::cout << '\n'; std::cout << std::distance(values.begin(), values.end()) << '\n'; }

g++ -std=c++23 -Wall -Wextra begin_end.cpp -o begin_end
./begin_end

10 20 30
3

Random access

A vector's iterator supports +, -, [] and comparison, so an index is a distance from begin. The program moves two steps forward, reads one element by index and measures the distance from the start.

Those operations are what std::sort needs and what a list iterator cannot do. Code that writes it + 2 is written against random access iterators, and it will not compile for a list.

Generic code that only needs to move forward should use ++ and *, as the first section does. That is the style that works with every container.

#include <iostream> #include <vector> int main() { std::vector<int> values{10, 20, 30, 40, 50}; auto it = values.begin(); it += 2; std::cout << *it << ' ' << it[1] << '\n'; std::cout << (values.end() - values.begin()) << '\n'; }

g++ -std=c++23 -Wall -Wextra random_access.cpp -o random_access
./random_access

30 40
5

const iterators

A const container gives const iterators: cbegin() and cend() return them, and so does begin() on a const object. Dereferencing one reads the element, and assigning through it is an error.

The program walks a const vector and prints the values. The iterator type is std::vector<int>::const_iterator, which is a different type from iterator, and the compiler will not convert one into the other.

This is the const correctness of lesson 012 applied to iteration: a function that only reads takes const references and uses const iterators, and then it accepts const containers.

#include <iostream> #include <vector> int main() { const std::vector<int> values{1, 2, 3}; for (auto it = values.cbegin(); it != values.cend(); ++it) { std::cout << *it << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra const.cpp -o const_iter
./const_iter

1 2 3

insert and erase return an iterator

insert and erase take an iterator position and return an iterator to the element after the change. That return value is what makes it possible to erase while walking a container.

The program finds 30, erases it and inserts 25 where it was. The erase returns an iterator to 40, and the insert points at the new element.

Every erase may invalidate the iterators after the position, which is why the loop that erases uses the returned iterator instead of keeping the old one. Lesson 019 showed the same operations by index.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{10, 20, 30, 40}; auto it = std::find(values.begin(), values.end(), 30); it = values.erase(it); values.insert(it, 25); for (int value : values) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra insert.cpp -o insert_iter
./insert_iter

10 20 25 40

Writing through a const iterator

A const_iterator gives a reference to const, so assigning through it is rejected. The program takes cbegin() from a non-const vector and writes, which is exactly the mistake the const iterator exists to catch.

The error says the assignment writes to a read-only location and points at the dereference. The fix is begin() instead of cbegin() when the element really has to change.

The two iterator types also do not mix in a comparison: begin() and cend() come from different overloads and the compiler reports a type mismatch. Use one kind per loop.

#include <vector> int main() { std::vector<int> values{1, 2, 3}; auto it = values.cbegin(); *it = 5; return values[0]; }

g++ -std=c++23 -Wall -Wextra write_const.cpp -o write_const

write_const.cpp: In function 'int main()':
write_const.cpp:8:9: error: assignment of read-only location 'it.__gnu_cxx::__normal_iterator<const int*, std::vector<int> >::operator*()'
8 | *it = 5;
| ~~~~^~~

Exercises

1. Print a vector in reverse with rbegin() and rend(), and then with a reverse_iterator built from end().
2. Erase every even number from a vector with the returned-iterator loop and check the result.
3. Write a function that takes two iterators and returns the largest element between them.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev