Skills101

AdvancedC++ Programming · Lesson 17 of 17 · Updated ·

Iterators in C++ — begin and end, Iterator Categories and Iterator Invalidation

In the STL lessons you wrote sort(v.begin(), v.end()) many times. What exactly are begin() and end()? They return iterators. An iterator is an object that points to an element of a container and can move to the next one. Iterators are the glue of the STL: algorithms like sort, find and accumulate never touch a container directly — they only see a pair of iterators. That is why one find works on a vector, a list and a set. Understanding iterators also prevents one of the most common C++ bugs: using an iterator after the container has changed.

1. begin, end and the basic loop

An iterator behaves much like a pointer:

OperationMeaning
*itthe element it points to
it->membera member of that element (same as (*it).member)
++itmove to the next element
it1 == it2, it1 != it2do they point to the same position?

v.begin() points to the first element. v.end() points one past the last element — it is a stop marker, not an element, and must never be dereferenced. For an empty container, begin() == end().

A vector of five marks with begin pointing at index 0 and end pointing one position past the last element at index 5; the range from begin to end covers all five elements

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> marks = {72, 85, 64, 90, 58};
    for (vector<int>::iterator it = marks.begin(); it != marks.end(); ++it)
        cout << *it << " ";
    cout << "\n";

    for (auto it = marks.begin(); it != marks.end(); ++it)
        *it += 5;                                   // grace marks: change through the iterator

    for (int m : marks) cout << m << " ";           // range-based for uses begin/end inside
    cout << "\n";
    cout << "count: " << (marks.end() - marks.begin()) << "\n";
    return 0;
}
72 85 64 90 58 
77 90 69 95 63 
count: 5

Writing vector<int>::iterator is long, so code usually says auto. The range-based for loop for (int m : marks) is shorthand: the compiler turns it into the iterator loop above. Use the range-based for when you visit every element; use iterators when you need the position itself (to erase, insert, or compare with another position).

The half-open range [begin, end) — start included, end excluded — is used everywhere in C++. It makes the number of elements simply end - begin, and an empty range simply begin == end.

2. The same loop on every container

Every STL container has begin() and end(), so the same pattern works on all of them. For a map, each element is a pair, so it->first is the key and it->second is the value.

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
    map<string, int> stock = {{"pen", 40}, {"book", 12}, {"bag", 5}};
    for (auto it = stock.begin(); it != stock.end(); ++it)
        cout << it->first << "=" << it->second << " ";
    cout << "\n";

    set<int> rolls = {104, 101, 103};
    for (auto it = rolls.rbegin(); it != rolls.rend(); ++it)   // reverse iterators
        cout << *it << " ";
    cout << "\n";

    vector<int> v = {3, 1, 4};
    for (auto it = v.cbegin(); it != v.cend(); ++it)           // const: read-only
        cout << *it;
    cout << "\n";
    return 0;
}
bag=5 book=12 pen=40 
104 103 101 
314
  • rbegin() / rend() give reverse iterators: ++ moves backwards.
  • cbegin() / cend() give const iterators: you can read *it but not assign to it. Use them when a loop should not change anything; the compiler then catches accidental writes.

3. Iterator categories

Not every iterator can do everything. A vector stores elements next to each other, so its iterator can jump it + 3 in one step. A list is a chain of nodes, so its iterator can only step one node at a time. The STL groups iterators into categories by what they can do:

CategoryExtra operationsContainers
Input / Outputread once / write once, ++istream, ostream iterators
Forward++, read many timesforward_list, unordered_map, unordered_set
Bidirectional++ and --list, set, map
Random access+ n, - n, it2 - it1, <, it[n]vector, deque, string, arrays

Each category can do everything the ones above it can. Algorithms state what they need. sort needs random access, so sort(myList.begin(), myList.end()) does not compile; list has its own member myList.sort() instead.

To move any iterator, use the helpers from <iterator>, which work for every category:

  • next(it, n) — a new iterator n steps ahead
  • prev(it, n) — n steps back (bidirectional or better)
  • advance(it, n) — move it itself n steps
  • distance(a, b) — number of steps from a to b
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main() {
    list<char> queue = {'A', 'B', 'C', 'D', 'E'};
    auto it = next(queue.begin(), 2);                // list has no it + 2
    cout << *it << "\n";
    advance(it, 1);
    cout << *it << " is at position " << distance(queue.begin(), it) << "\n";
    cout << *prev(queue.end()) << "\n";              // last element
    return 0;
}
C
D is at position 3
E

For a vector, next and distance take one step; for a list, they walk node by node, so they cost O(n). The code looks the same, but the speed does not.

4. Erasing while looping

Suppose we must remove every failing mark (below 40) from a vector. The obvious loop is wrong:

// WRONG: after erase(it), 'it' is invalid, and ++it is undefined behaviour
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it < 40) v.erase(it);

erase removes the element and shifts the later elements left. The iterator it now refers to a position that has been destroyed — it is invalidated. Using it again is undefined behaviour: it may skip elements, crash, or seem to work and fail later.

The fix: erase returns an iterator to the element after the removed one. Use it, and only do ++it when you did not erase:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {35, 72, 20, 18, 66, 39};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it < 40) it = v.erase(it);     // erase returns the next valid iterator
        else ++it;
    }
    for (int m : v) cout << m << " ";
    cout << "\n";

    vector<int> w = {35, 72, 20, 18, 66, 39};
    w.erase(remove_if(w.begin(), w.end(), [](int m) { return m < 40; }), w.end());
    for (int m : w) cout << m << " ";
    cout << "\n";
    return 0;
}
72 66 
72 66 

The second version is the erase–remove idiom. remove_if moves the elements to keep to the front and returns an iterator to the new logical end; erase then chops off the leftovers. It does the job in one pass, O(n), while erasing one by one from a vector can be O(n²) because each erase shifts the rest.

5. Iterator invalidation rules

Erasing is not the only danger. Any change to a container may invalidate iterators (and pointers and references) into it. The most important case: when a vector runs out of capacity, push_back moves all elements to a new, bigger block of memory, and every old iterator now points to freed memory.

Table of iterator invalidation: vector push_back invalidates all iterators when it reallocates, vector erase invalidates from the erased element onward, list and map insert invalidate nothing and erase invalidates only the erased element

ContainerInsertErase
vector, stringall, if it reallocates; otherwise those after the insert pointthe erased element and everything after it
dequeall iterators (in the middle: also references)at either end: only the erased element; in the middle: all
list, set, mapnoneonly the erased element
unordered_map, unordered_setall, if it rehashesonly the erased element

The practical rule: after changing a container, do not reuse old iterators unless you are sure the rules allow it. Get a fresh iterator, use the one returned by erase/insert, or, for a vector, call reserve() first if you know the final size.

Common mistakes

  • Dereferencing end(). It is one past the last element, not the last element.
  • Erasing inside a loop and then doing ++it on the erased iterator.
  • Keeping an iterator, pointer or reference into a vector across push_back.
  • Calling sort on a list (needs random access); use list::sort().
  • Comparing iterators from two different containers — the result is meaningless.
  • Using it < v.end() with a list or map iterator; use !=, which works for every category.

Quick recap

  • begin() is the first element, end() is one past the last: the half-open range [begin, end).
  • *it reads the element, it->x reads a member, ++it moves on; auto saves typing.
  • rbegin/rend walk backwards; cbegin/cend are read-only.
  • Categories: input/output, forward, bidirectional, random access. Algorithms need a minimum category.
  • next, prev, advance, distance work for every iterator.
  • Erase in a loop with it = v.erase(it), or use erase–remove.
  • Changing a container can invalidate iterators; vector reallocation invalidates all of them.

Practice what you learned

📝 Quiz: Iterators in C++5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →