C++ Iterators: Categories, Operations, iterator_traits and Invalidation Bugs

Iterator Basics

Iterator is an object that iterates over container elements. It is used as begin/end in range-based for and vector, and it’s the abstraction that lets the same algorithm code work identically whether it’s walking a contiguous array or a linked list.

Iterator concept diagram

graph LR
    A[Container] --> B[begin]
    A --> C[end]

    B --> D[Iter]
    D -->|++| E[Iter]
    E -->|++| F[Iter]
    F -->|++| C
    
    D -->|*| G[Elem 1]
    E -->|*| H[Elem 2]
    F -->|*| I[Elem 3]

#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    // begin/end
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // reverse
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";  // 5 4 3 2 1
    }
}

Notice end() is deliberately a past-the-end marker, not a pointer to the last valid element — v.end() for a 5-element vector conceptually points one slot past index 4, and the loop condition it != v.end() is what makes the half-open range [begin, end) work cleanly for an empty container too (begin() == end() immediately, zero iterations, no special-casing needed). rbegin()/rend() mirror this exactly but walk backward — rbegin() starts at the last element and rend() is one-before-the-first, so the same “stop when you reach end” loop shape works for both directions without rewriting the comparison logic.

The five iterator categories

Iterator Hierarchy

graph TD
    A[Input Iterator] --> C[Forward Iterator]
    B[Output Iterator] --> C
    C --> D[Bidirectional Iterator]
    D --> E[Random Access Iterator]
    E --> F[Contiguous Iterator C++20]
    
    A -.->|read-only| A1[istream_iterator]
    B -.->|write-only| B1[ostream_iterator]
    C -.->|one direction| C1[forward_list]
    D -.->|both directions| D1[list, set, map]
    E -.->|random access| E1[vector, deque, array]
    F -.->|contiguous memory| F1[vector, array, string]

Iterator function comparison table

iterator type	Read	writing	Forward	Reverse	random access	Example container
Input	✅	❌	✅	❌	❌	istream_iterator
Output	❌	✅	✅	❌	❌	ostream_iterator
Forward	✅	✅	✅	❌	❌	forward_list
Bidirectional	✅	✅	✅	✅	❌	list, set, map
Random Access	✅	✅	✅	✅	✅	vector, deque

This hierarchy is exactly why a generic algorithm like std::sort requires random-access iterators and refuses to compile against a std::list — sorting efficiently needs it + n-style jumps to do things like binary partitioning, which forward and bidirectional iterators simply don’t support (they can only be advanced one step at a time). std::list::sort exists as a member function precisely to work around this: it implements a merge sort that only ever needs bidirectional, one-step-at-a-time movement, at the cost of not being expressible as the generic free-function algorithm.

Input Iterator

// Read-only, single-pass
istream_iterator<int> in(cin);
istream_iterator<int> eof;

vector<int> v(in, eof);  // read input into a vector

An input iterator is explicitly single-pass — re-reading the same position twice isn’t guaranteed to give the same result, which matches how cin actually behaves (you can’t “rewind” standard input and read the same value again). This is a real constraint, not a technicality: a generic algorithm written to only require an input iterator must never dereference the same iterator position more than once, since doing so with something like istream_iterator may consume the next value from the stream instead.

Output Iterator

// Write-only
ostream_iterator<int> out(cout, " ");

vector<int> v = {1, 2, 3};
copy(v.begin(), v.end(), out);  // 1 2 3

std::copy here doesn’t know or care that its destination is printing to cout rather than writing into a container — it just calls *out = value; ++out; for each element, and ostream_iterator’s overloaded operator= is what turns that generic assignment into a cout << value << " ". This is the core trick behind the whole iterator abstraction: algorithms are written once against the iterator interface, and iterators like this one adapt that interface to wildly different underlying behavior.

Forward Iterator

// Read/write, can be traversed multiple times
forward_list<int> fl = {1, 2, 3};

for (auto it = fl.begin(); it != fl.end(); ++it) {
    *it *= 2;
}

Bidirectional Iterator

// Can move in both directions
list<int> l = {1, 2, 3, 4, 5};

auto it = l.end();
--it;  // now points to the last element
cout << *it << endl;  // 5

--l.end() is the idiomatic way to get “the last element” for a container whose iterators can’t jump arbitrary distances — l.end() - 1 doesn’t compile for list, because subtracting an integer requires random access, which a doubly-linked list’s iterators don’t have. --it only needs to move one node backward, which a bidirectional iterator can always do regardless of container layout.

Random Access Iterator

// Random access
vector<int> v = {1, 2, 3, 4, 5};

auto it = v.begin();
it += 3;  // jump 3 positions
cout << *it << endl;  // 4

cout << v[2] << endl;  // 3

Writing custom, filtering, and transforming iterators

A custom range iterator

class Range {
private:
    int current;
    int end;
    
public:
    class Iterator {
    private:
        int value;
        
    public:
        using iterator_category = forward_iterator_tag;
        using value_type = int;
        using difference_type = ptrdiff_t;
        using pointer = int*;
        using reference = int&;
        
        Iterator(int v) : value(v) {}
        
        int operator*() const { return value; }
        
        Iterator& operator++() {
            ++value;
            return *this;
        }
        
        bool operator!=(const Iterator& other) const {
            return value != other.value;
        }
    };
    
    Range(int start, int end) : current(start), end(end) {}
    
    Iterator begin() { return Iterator(current); }
    Iterator end() { return Iterator(this->end); }
};

int main() {
    for (int x : Range(0, 10)) {
        cout << x << " ";  // 0 1 2 ... 9
    }
}

Writing a class with begin() and end() member functions returning something that supports *, ++, and != is the entire requirement for range-based for to accept it — Range here isn’t a real container at all, it never stores the sequence 0-9 anywhere, it just generates each value on the fly from an increasing integer. This is the minimal shape behind Python-style range() generators in C++, and it’s why the five using type aliases (iterator_category through reference) matter beyond boilerplate: they’re what let generic STL algorithms (not just range-for) introspect what kind of iterator this is and what operations it safely supports.

A lazy filter iterator

template<typename Iter, typename Pred>
class FilterIterator {
private:
    Iter current;
    Iter end;
    Pred predicate;
    
    void advance() {
        while (current != end && !predicate(*current)) {
            ++current;
        }
    }
    
public:
    FilterIterator(Iter begin, Iter end, Pred pred)
        : current(begin), end(end), predicate(pred) {
        advance();
    }
    
    auto operator*() const { return *current; }
    
    FilterIterator& operator++() {
        ++current;
        advance();
        return *this;
    }
    
    bool operator!=(const FilterIterator& other) const {
        return current != other.current;
    }
};

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    auto isEven = [](int x) { return x % 2 == 0; };
    
    FilterIterator begin(v.begin(), v.end(), isEven);
    FilterIterator end(v.end(), v.end(), isEven);
    
    for (auto it = begin; it != end; ++it) {
        cout << *it << " ";  // 2 4 6 8 10
    }
}

advance() running inside both the constructor and operator++ is what makes this a lazy filter rather than one that copies matching elements into a new container up front — the iterator only ever looks as far ahead as needed to find the next element that satisfies predicate, skipping non-matching elements on demand as the caller advances through it. This is conceptually the same idea C++20 ranges’ views::filter formalizes into the standard library, just written by hand here to show what’s happening underneath.

A transforming iterator

template<typename Iter, typename Func>
class TransformIterator {
private:
    Iter current;
    Func transform;
    
public:
    TransformIterator(Iter it, Func f) : current(it), transform(f) {}
    
    auto operator*() const {
        return transform(*current);
    }
    
    TransformIterator& operator++() {
        ++current;
        return *this;
    }
    
    bool operator!=(const TransformIterator& other) const {
        return current != other.current;
    }
};

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    auto square = [](int x) { return x * x; };
    
    TransformIterator begin(v.begin(), square);
    TransformIterator end(v.end(), square);
    
    for (auto it = begin; it != end; ++it) {
        cout << *it << " ";  // 1 4 9 16 25
    }
}

Same lazy-evaluation idea as the filter iterator above, applied to transformation instead of skipping: operator* applies transform at the moment of dereference, not up front, so no intermediate vector<int> of squared values is ever materialized. This is the hand-rolled version of what std::views::transform gives you as a standard, composable building block in C++20 — the manual implementation here exists to make visible exactly what a “view” is doing under the hood.

advance, distance, next, and prev

Complexity per iterator category

function	Time Complexity	Support iterators	Description
advance(it, n)	O(1) ~ O(N)	all iterators	Move n spaces (modifies position)
distance(first, last)	O(1) ~ O(N)	Input or better	Distance between two iterators
next(it, n=1)	O(1) ~ O(N)	Forward or better	Return iterator n spaces ahead
prev(it, n=1)	O(1) ~ O(N)	Bidirectional ideal	Return iterator n spaces back
iter_swap(it1, it2)	O(1)	Forward or better	Swap two iterator values

vector<int> v = {1, 2, 3, 4, 5};

auto it = v.begin();

// Move forward
advance(it, 3);  // jump 3 positions
cout << *it << endl;  // 4

// Distance
auto dist = distance(v.begin(), v.end());
cout << dist << endl;  // 5

// Next/previous
auto next_it = next(it);
auto prev_it = prev(it);

The “O(1) ~ O(N)” complexity range in that table isn’t vague hand-waving — it’s a real, iterator-category-dependent difference you should be aware of. For a vector (random access), advance(it, 3) compiles down to it += 3, a single O(1) pointer addition. For a list (bidirectional only), the same call has to walk the linked list one node at a time, three ++ operations, making it O(n) in the distance advanced. The function call looks identical either way, which is convenient for generic code but means the same line can be instant or a real cost depending entirely on which container’s iterator you hand it.

advance vs next difference:

graph LR
    A[it = v.begin] --> B{Which?}
    
    B -->|advance it, 3| C[Modify it]
    C --> D[it = begin+3]
    
    B -->|next it, 3| E[Return new]
    E --> F[it = begin]
    E --> G[return = begin+3]

advance mutates its argument in place and returns nothing; next/prev leave the original iterator untouched and return a new one. Reach for advance when you’re stepping an iterator variable forward as part of ongoing traversal, and next/prev when you want to compute an offset position (like “the element after this one”) without disturbing the iterator you’re currently using — mixing them up doesn’t cause a compile error, just an easy-to-miss bug where you expected the original iterator to have moved and it didn’t (or vice versa).

Invalidation, end() dereference, and mismatched iterators

Using an invalidated iterator

// ❌ Iterator invalidation
vector<int> v = {1, 2, 3, 4, 5};

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);  // it is now invalid!
        // ++it;  // dangerous!
    }
}

// ✅ Use erase's return value
for (auto it = v.begin(); it != v.end();) {
    if (*it == 3) {
        it = v.erase(it);  // returns the next valid iterator
    } else {
        ++it;
    }
}

Dereferencing end()

// ❌ Dereferencing end()
vector<int> v = {1, 2, 3};
auto it = v.end();
// cout << *it << endl;  // undefined behavior

// ✅ Check against end() first
if (it != v.end()) {
    cout << *it << endl;
}

end() is a valid iterator value — you can compare it, copy it, hold onto it — but it doesn’t refer to any actual element, so dereferencing it reads memory that was never meant to be read as a container element. This distinction (valid to hold, invalid to dereference) is exactly why every safe traversal pattern in this guide checks it != end() before using *it, never after.

Mixing iterators from different containers

// ❌ Type mismatch
vector<int> v;
list<int> l;

// auto it = v.begin();
// it = l.begin();  // compile error

// ✅ Use the correct types
auto vit = v.begin();
auto lit = l.begin();

This is a compile-time error, not a runtime one, and that’s worth appreciating — vector<int>::iterator and list<int>::iterator are simply unrelated types with no conversion between them, so the mistake is caught before the program ever runs, unlike, say, the raw-pointer-based iteration patterns from older C-style code where mixing up array bounds could compile fine and fail silently at runtime.

iterator_traits

template<typename Iter>
void printIteratorInfo() {
    using traits = iterator_traits<Iter>;
    
    cout << "value_type: " << typeid(typename traits::value_type).name() << endl;
    cout << "difference_type: " << typeid(typename traits::difference_type).name() << endl;
    cout << "iterator_category: " << typeid(typename traits::iterator_category).name() << endl;
}

int main() {
    printIteratorInfo<vector<int>::iterator>();
}

iterator_traits exists as a layer of indirection specifically to handle raw pointers, which are perfectly valid iterators (a T* supports *, ++, !=, everything an iterator needs) but obviously have no nested ::value_type or ::iterator_category typedefs of their own — you can’t add member typedefs to a built-in pointer type. iterator_traits<T*> is partially specialized by the standard library to synthesize those typedefs for any pointer type, which is what lets generic algorithms written against iterator_traits<Iter>::value_type work uniformly whether Iter is a class-based iterator with its own typedefs or a plain pointer with none.

FAQ

Q1: When do you use iterators?

A:

• Container traversal
• STL algorithm
• Specify scope

Q2: Pointer vs Iterator?

A: Iterators are more abstract and safer.

Q3: What about iterator invalidation?

A:

• vector: When inserting/deleting
• list: only deleted elements
• map: only deleted elements

Q4: What about custom iterators?

A: Requires implementation of 5 typedefs and operators.

Q5: What is the iterator performance?

A: Inlined, similar to a pointer.

Q6: What are the iterator learning resources?

A:

• “Effective STL” (Scott Meyers)
• cppreference.com
• “The C++ Standard Library”

---

Related Articles

• C++ Range-Based For Guide
• std::vector in Practice
• The Composite Pattern in C++
• C++ Iterator Invalidation Error
• Tag Dispatching in C++: Overload Selection by Tag Types, vs if constexpr and Concepts

---