Iterator in C++: a practical guide to traversal and design

Overview and definition

An iterator in C++ is a generalization of pointers that enables sequential traversal of elements in a range. It decouples algorithms from containers, so the same code can work across vectors, lists, maps, and custom collections. At the lowest level, iterators model concepts such as readable and writable references and support operations like dereferencing, increment, and comparison. This evergreen explanation covers core mechanics, standard iterator categories, common usage patterns, and best practices that remain useful across C++ revisions.

Core concepts and terminology

What is an iterator?

An iterator is an object that behaves similarly to a pointer, referring to a position within a container or to a sentinel value marking the end. It provides access to the element at that position via dereference and moves through the sequence via increment operators. Consistent iterator semantics make generic programming possible: algorithms written for iterators can operate on many container types without change.

Valid iterator operations

• *it — Dereference to access the referred element
• it++ or ++it — Advance the iterator
• it == other and it != other — Equality comparison
• it - other (random-access only) — Distance between iterators
• it + n and it - n (random-access only) — Offsetting

Iterator categories

The C++ standard defines five increasing-strength iterator categories. Each category unlocks additional operations, and containers expose the strongest category their design reasonably supports.

Input iterator

Readable and single-pass, useful for consuming streams or input sources. An input iterator is only guaranteed to be valid after increment and may be invalidated on further operations. Examples include std::istream_iterator. Use input iterators when you need to read data once without needing to move backward or write.

Output iterator

Write-only and single-pass, typically used for output operations. The only guaranteed valid operations are writing through the iterator and incrementing. Common with std::ostream_iterator for formatted output streams. Use output iterators when you only need to write data sequentially.

Forward iterator

Combines input and output capabilities with multi-pass guarantees. Once incremented, iterators remain valid and comparable, enabling traversal from a starting point. Many containers such as std::forward_list provide forward iterators. Forward iterators are suitable for algorithms that need stable references across multiple passes.

Bidirectional iterator

Extends forward iterators with decrement operations, allowing traversal in both directions. Supports operations like --it for moving backward in lists, maps, and sets. This category balances flexibility and performance for containers with efficient bidirectional navigation.

Random-access iterator

The strongest standard category, supporting constant-time advancement by an index, direct indexing with [], and pointer arithmetic. Vectors, arrays, and deques provide random-access iterators. Random-access enables efficient algorithms such as binary search and quick partitioning. When available, prefer random-access iterators for performance-critical code.

Common usage patterns

Range-based for loops

Range-based for loops internally use iterators. The loop begins with an iterator to the beginning of the container and compares each iterator against end. This works for any container that supplies begin and end methods.

Manual iteration

Explicit iteration with begin and end is common in generic code. For vectors and deques this is typically random-access; for lists and sets it is bidirectional. Prefer cbegin and cend when you do not need to modify elements.

Algorithm patterns

Standard algorithms such as std::sort, std::find, and std::transform accept iterator ranges. These algorithms rely on iterator categories to select efficient implementations. Providing the strongest category your container supports makes these algorithms faster.

Const correctness and iterator types

Use const iterators to prevent modification of container elements. cbegin and cend return const iterators even on non-const containers. Functions that should not modify elements should accept const iterator pairs to express intent and avoid accidental writes.

Iterator invalidation rules

Different containers invalidate iterators in different ways. Awareness of these rules is essential to avoid undefined behavior.

Vectors and deques

Insertion or reallocation can invalidate all iterators, pointers, and references. Appending may trigger reallocation; inserting in the middle invalidates iterators at and after the point of insertion.

Lists and sets

Insertion generally invalidates only iterators to the inserted element, while other iterators remain valid. Erasing invalidates only the erased iterators.

Maps

Insertion does not invalidate existing iterators; erase invalidates only the erased element. This makes maps safe to iterate during incremental updates.

Custom iterator types

Implementing custom iterators allows you to support range-based for loops and algorithms for non-standard data sources. At minimum you’ll model the required operations (dereference, increment, and comparison) and provide correct iterator traits. For many projects, using std::iterator and the iterator tags is sufficient, though C++17 and later prefer traits specialization with std::iterator_traits.

Best practices and recommendations

• Choose the strongest iterator category your container can reasonably provide.
• Prefer range-based for loops or algorithms over manual loops when clarity and safety matter.
• Use const iterators when elements must not be modified.
• Check iterator invalidation rules for your container before mutating.
• When writing generic code, rely on iterator traits and concepts to ensure correctness.

Key takeaways

• An iterator behaves like a pointer into or across a container, with defined operations and validity rules.
• Five standard categories—input, output, forward, bidirectional, random-access—express progressively stronger capabilities.
• Use const iterators and prefer algorithms to express intent and reduce errors.
• Understand container-specific iterator invalidation rules to avoid subtle bugs.
• Custom iterators and traits enable seamless integration with STL algorithms for non-standard containers.

References

Core guidance derived from ISO/IEC 14882:2020 and cppreference.com. Verify against your compiler documentation when targeting specific C++ standards. Prefer std::begin and std::end for generic code to support both arrays and containers.