Iterators: the glue between containers and algorithms

Why iterators?

A vector stores elements in a row, a set in a tree, a list in linked nodes. If every algorithm had to know every container's insides, the library would need hundreds of versions of sort and find. Iterators solve this. An iterator is a small object that behaves like a pointer: *it gives the element, ++it moves to the next one. Each container provides its own iterators, and algorithms only talk to iterators.

#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 << ' ';      // 10 20 30
    }
    auto it = v.begin();
    *it = 99;                          // change through the iterator
    std::cout << '\n' << v[0] << '\n'; // 99
}

The half-open range [begin, end)

end() does not point to the last element; it points one past it. It is a "stop here" marker and must never be dereferenced. This convention makes empty ranges easy (begin == end) and loop conditions simple (it != end).

Kinds of iterators

Algorithms ask for the category they need. std::sort needs random access, so you cannot std::sort a std::list (use list.sort() instead). std::find only needs to move forward, so it works everywhere.

const iterators and reverse iterators

std::vector<int> v = {1, 2, 3};
for (auto it = v.cbegin(); it != v.cend(); ++it) { /* *it is read-only */ }
for (auto it = v.rbegin(); it != v.rend(); ++it) std::cout << *it;   // 321

Map iterators

std::map<std::string, int> stock = {{"dal", 25}, {"rice", 40}};
auto it = stock.find("rice");
if (it != stock.end()) {
    std::cout << it->first << " = " << it->second << '\n';   // rice = 40
    it->second += 10;                                         // value can change; key cannot
}

Erasing while iterating

std::map<std::string, int> stock = {{"dal", 0}, {"rice", 40}, {"oil", 0}};
for (auto it = stock.begin(); it != stock.end(); ) {
    if (it->second == 0) it = stock.erase(it);   // erase returns the next valid iterator
    else ++it;
}
// stock now has only rice

Distance and advance

• std::distance(first, last) counts the steps between two iterators.
• std::next(it, n) and std::prev(it, n) give moved copies without changing it.
• For a vector, it - v.begin() is the index of the element.