Iterator categories and invalidation

Learning objectives

• Explain why algorithms accept iterators rather than container-specific indexes.
• Distinguish the main iterator categories and their capabilities.
• Recognise common vector, deque, and map iterator invalidation rules.
• Avoid using an iterator after an operation invalidates it.

Prerequisites: arrays, vector, and basic loops. This lesson introduces iterator operations before discussing invalidation rules.

Iterator categories

An iterator is a handle used to read, write, or move through a sequence. The category describes which operations are supported. More capable categories support everything less capable categories support, plus additional operations.

Category	Typical capability	Example
Input	Read forward, usually once through a range	istream_iterator
Output	Write forward, usually once through a range	ostream_iterator
Forward	Read repeatedly while moving forward	forward_list
Bidirectional	Move forward and backward	list, map
Random access	Jump by an offset and compare distances	vector, deque
Contiguous	Random access with adjacent elements contiguous in memory	vector, array

Version note: input, output, forward, bidirectional, and random-access are the traditional iterator categories. C++20 also formalizes iterator concepts and adds the contiguous concept. A contiguous iterator has random-access operations and refers to elements stored contiguously in memory. The table is a learning summary; an iterator's exact concept requirements are specified by the standard library.

For example, std::sort needs random-access iterators, so it works with vector and array, but not with list. A list provides its own sort() member function.

Half-open ranges

std::vector<int> values{4, 8, 2, 9};
auto first = values.begin();
auto last = values.end(); // one past the final element
// The range is [first, last)

The first iterator is included; the last is excluded. An empty range has equal begin and end iterators. Never dereference end().

Iterator invalidation

An iterator is not a permanent reference to an element. A container operation can invalidate it, meaning it must no longer be used. Rules differ by container and operation.

• vector: reallocation invalidates all iterators, pointers, and references to its elements. Insert or erase can invalidate iterators at or after the affected position.
• deque: insertion and erasure have more complicated invalidation rules; do not assume vector rules apply.
• list: inserting does not invalidate existing iterators; erasing invalidates only iterators to erased elements.
• map/set: insertion preserves existing iterators; erasing invalidates iterators to erased elements.

A safe erase loop

for (auto it = values.begin(); it != values.end(); ) {
    if (*it % 2 == 0) {
        it = values.erase(it); // use the iterator returned by erase
    } else {
        ++it;
    }
}

For vector, erase returns the next valid iterator. Do not increment the erased iterator again.

Complexity connection

Iterator category can determine which algorithms are available and how fast they can be. Advancing a random-access iterator by 100 positions is constant time; advancing a list iterator by 100 positions requires 100 steps.

Common mistakes

• Assuming iterators remain valid after vector growth.
• Dereferencing an iterator after erasing its element.
• Passing list iterators to std::sort.
• Confusing an iterator with an integer index.

Practice

1. Which iterator category does vector provide?
2. Why can't std::sort sort a list?
3. What does vector reallocation invalidate?
4. Write a loop that erases all negative values without using an invalid iterator.

Show solutions

1. Contiguous iterators, which also satisfy random-access capabilities.
2. List iterators are bidirectional, not random access; use list::sort().
3. All iterators, pointers, and references to its elements.
4. Use the iterator returned by erase when erasing; otherwise increment normally.

Summary

Iterator categories describe supported operations. Container mutations may invalidate iterators, so check the relevant container rule and use returned iterators from erase operations.

References

• cppreference: iterators
• cppreference: vector invalidation
• cppreference: list