Iterators

Iterators are the glue between containers and algorithms. An iterator marks a position in a container and can move to the next element; every standard container provides them, so the same algorithm can work on a vector, a list, a set or an array.

begin and end

begin() points to the first element and end() points one past the last. Together they describe a half-open range [begin, end):

C++ 
#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 << ' ';       // * gives the element
    }
    std::cout << '\n';
}
Output
10 20 30

An iterator looks and behaves much like a pointer: *it reads the element, ++it moves on, and it->member accesses a member. The range-based for loop is shorthand for exactly this loop. Never dereference end() — there's no element there.

Why the extra position?

A one-past-the-end marker means an empty range is simply begin == end, and functions can report "not found" by returning end():

C++ 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> names{"Ana", "Ben", "Chloe"};
    auto it = std::find(names.begin(), names.end(), "Ben");
    if (it != names.end()) {
        std::cout << "found " << *it << " at index " << (it - names.begin()) << '\n';
    }
    if (std::find(names.begin(), names.end(), "Zoe") == names.end()) {
        std::cout << "Zoe not found\n";
    }
}
Output
found Ben at index 1
Zoe not found

Iterator categories

Containers offer different capabilities, and algorithms state which ones they need:

CategoryCan doContainers
Forward++it, read/writestd::forward_list, unordered containers
Bidirectionalalso --itstd::list, std::map, std::set
Random accessalso it + n, it[n], it2 - it1, <std::deque
Contiguousalso elements adjacent in memorystd::vector, std::array, std::string

That's why std::sort works on a vector but not a std::list (which has its own sort() member instead).

Reverse and const iterators

C++ 
#include <iostream>
#include <string>

int main() {
    std::string word = "stressed";
    for (auto it = word.rbegin(); it != word.rend(); ++it) std::cout << *it;
    std::cout << '\n';

    std::string copy(word.rbegin(), word.rend());     // construct from a range
    std::cout << copy << '\n';

    for (auto it = word.cbegin(); it != word.cend(); ++it) {
        // *it = 'x';   // error: const iterator, read-only
    }
}
Output
desserts
desserts

rbegin/rend walk backwards; cbegin/cend give read-only iterators.

Iterators into maps

A map's iterator points to a std::pair — use ->first for the key and ->second for the value:

C++ 
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> ages{{"Ana", 31}, {"Ben", 27}, {"Chloe", 35}};
    auto it = ages.find("Ben");
    it->second += 1;
    std::cout << it->first << " is now " << it->second << '\n';

    auto first_c = ages.lower_bound("C");    // first key >= "C"
    std::cout << "first name from C: " << first_c->first << '\n';
}
Output
Ben is now 28
first name from C: Chloe

Invalidation

Modifying a container can invalidate its iterators — using one afterwards is undefined behaviour. The classic bug is erasing inside a range-for loop. erase returns a valid iterator to the next element; use it:

C++ 
#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);   // erase returns the next valid position
        else ++it;
    }
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}
Output
1 3 5

For this particular job, C++20's std::erase_if(v, predicate) (lesson 18) is simpler still.

ContainerInvalidated by
vector, stringAny reallocation (growth); insert/erase invalidates from that point on
dequeInsertion anywhere; erasure in the middle
list, map, setOnly erasing that element
Unordered containersRehashing (growth); erasing that element

Helper functions

C++ 
#include <iostream>
#include <iterator>
#include <list>

int main() {
    std::list<char> letters{'a', 'b', 'c', 'd', 'e'};
    auto it = letters.begin();
    std::advance(it, 3);                                 // move 3 steps
    std::cout << *it << ' ' << *std::next(it) << ' ' << *std::prev(it) << ' '
              << std::distance(letters.begin(), it) << '\n';
}
Output
d e c 3

std::advance, std::next, std::prev and std::distance work for every iterator category, using the fastest method available.

Try it yourself

Use iterators to print the elements of a vector between the first and last occurrence of a marker value.

Try it yourself · main.cpp
Edit the code, copy it into main.cpp, then compile and run it with c++ -std=c++20 -Wall main.cpp -o main && ./main. How to set up a C++ compiler
Output
7 3 9
PreviousMore Containers