C++ Iterators

An iterator points at an element of a container, the way a pointer points at an element of an array. Iterators give every container, whether a vector, a list, a set or a map, the same way to be walked through, which is what lets the algorithms of the standard library work with all of them.

begin and end

begin() points at the first element. end() points one past the last element; it marks the end and must never be read. *it reads the element, ++it moves to the next one.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    auto it = v.begin();
    *it = 99;                 // change through the iterator
    std::cout << v[0] << " " << *(v.begin() + 2) << "\n";
    return 0;
}

10 20 30 
99 30

The range-based for loop uses begin and end behind the scenes. The type of an iterator is long (std::vector<int>::iterator), so auto is used almost always.

Different containers, same code

#include <iostream>
#include <list>
#include <set>
#include <string>

template <typename Container>
void printAll(const Container& c) {
    for (auto it = c.begin(); it != c.end(); ++it) std::cout << *it << " ";
    std::cout << "\n";
}

int main() {
    std::list<std::string> names = {"Asha", "Ravi"};
    std::set<int> numbers = {3, 1, 2};
    printAll(names);
    printAll(numbers);
    return 0;
}

Asha Ravi 
1 2 3 

Reverse iterators

rbegin() and rend() walk backwards:

#include <iostream>
#include <string>

int main() {
    std::string word = "stressed";
    std::string reversed(word.rbegin(), word.rend());
    std::cout << reversed << "\n";
    return 0;
}

desserts

Erasing while iterating

Erasing an element invalidates the iterator pointing at it. erase returns an iterator to the next element, which is what the loop must continue with:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) it = v.erase(it);   // continue from the next element
        else ++it;
    }
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

1 3 5 

Adding elements to a vector can also move all its elements and invalidate every iterator, so do not keep iterators across push_back. C++20's std::erase_if(v, condition) does the loop above in one line.

Good practice

Prefer the range-based for loop when you only visit every element; use iterators when you need a position, for example to erase, insert or hand a range to an algorithm. cbegin() and cend() give const iterators that cannot change the elements. Never use an iterator after the container has been changed in a way that invalidates it, such as push_back on a vector.

Practice exercises

1. Print a vector backwards with rbegin and rend.
2. Remove all names shorter than four letters from a list<string> while iterating.
3. Write a template that returns the sum of any container of numbers using iterators.