Ch8.3: Iterator Categories

Overview

Iterators are the “cursors” that move through a range. A range produces iterators; an iterator represents a position inside a range.

Just like ranges, iterators form a capability hierarchy. Each stronger iterator category includes all capabilities of the weaker ones.

In this chapter, you will learn:

• the full iterator category hierarchy
• the readable chain from input_iterator to contiguous_iterator
• the separate writable branch output_iterator
• why pointers to object types are the strongest readable iterators
• why some pointers do not model any iterator category
• how to_address defines contiguity

1. The full iterator hierarchy

All iterator categories refine the base concept input_or_output_iterator. From there, the hierarchy splits into a readable chain and a separate writable branch:

input_or_output_iterator
│
├── input_iterator
│     │
│     ├── forward_iterator
│     │
│     ├── bidirectional_iterator
│     │
│     ├── random_access_iterator
│     │
│     └── contiguous_iterator   ← pointers to object types live here
│
└── output_iterator   (separate writable branch)

2. Ranges and iterators: how they relate

A range is an object that produces two iterators:

• a begin iterator (first position)
• an end iterator (one past the last position)

A range does not store positions. An iterator does not store a collection.

They are complementary:

• A range describes what you can traverse.
• An iterator describes where you are during traversal.

A range is defined by:

auto it  = begin(r);
auto end = end(r);

An iterator is defined by:

++it;   // move to next position
*it;    // access the element at that position

3. input_or_output_iterator

This is the root of the iterator hierarchy. Every iterator is either readable, writable, or both.

All other iterator categories refine this one.

4. input_iterator

The smallest readable iterator category. An input_iterator supports:

• reading elements once
• moving forward only
• single‑pass traversal

5. forward_iterator

A forward_iterator has all capabilities of an input_iterator and additionally supports:

• multiple passes over the same elements
• revisiting elements in the same order

6. bidirectional_iterator

A bidirectional_iterator has all capabilities of a forward_iterator and additionally supports:

• moving backward as well as forward

7. random_access_iterator

A random_access_iterator has all capabilities of a bidirectional_iterator and additionally supports:

• constant‑time jumps to any position
• indexing with it[n]

8. contiguous_iterator

A contiguous_iterator has all capabilities of a random_access_iterator and additionally guarantees that the elements it refers to occupy adjacent addresses in the program’s abstract address space.

When the iterator refers to a real element (not the end position), the following holds:

::std::to_address(it + 1) == ::std::to_address(it) + 1

Pointers as contiguous_iterators

Pointers to object types (such as int* or char*) are the canonical example of contiguous_iterators.

However, not all pointers are iterators:

• void* cannot be incremented or dereferenced as an element type
• function pointers cannot be incremented or dereferenced

Example: ::fast_io::vector<int>::iterator

void analyze_vector_iterator(::fast_io::vector<int>::iterator it)
{
    if constexpr(::std::contiguous_iterator<decltype(it)>)
        print("vector::iterator is a contiguous iterator\n");

    if constexpr(::std::random_access_iterator<decltype(it)>)
        print("vector::iterator is a random_access iterator\n");

    if constexpr(::std::bidirectional_iterator<decltype(it)>)
        print("vector::iterator is a bidirectional iterator\n");

    if constexpr(::std::forward_iterator<decltype(it)>)
        print("vector::iterator is a forward iterator\n");

    if constexpr(::std::input_iterator<decltype(it)>)
        print("vector::iterator is an input iterator\n");

    if constexpr(::std::output_iterator<decltype(it), int>)
        print("vector::iterator is an output iterator for int\n");
}

9. output_iterator (separate branch)

An output_iterator is the writable counterpart of an input_iterator. It allows writing elements but does not require reading from the iterator.

It is not part of the readable hierarchy.

10. Detecting iterator categories with if constexpr

void analyze_iterator(int* it)
{
    if constexpr(::std::contiguous_iterator<decltype(it)>)
        print("pointer is a contiguous iterator\n");

    if constexpr(::std::random_access_iterator<decltype(it)>)
        print("pointer is a random_access iterator\n");

    if constexpr(::std::bidirectional_iterator<decltype(it)>)
        print("pointer is a bidirectional iterator\n");

    if constexpr(::std::forward_iterator<decltype(it)>)
        print("pointer is a forward iterator\n");

    if constexpr(::std::input_iterator<decltype(it)>)
        print("pointer is an input iterator\n");

    if constexpr(::std::output_iterator<decltype(it), int>)
        print("pointer is an output iterator for int\n");
}

Key takeaways

• input_or_output_iterator is the root concept.
• The readable hierarchy goes from input_iterator up to contiguous_iterator.
• output_iterator is a separate writable branch.
• Pointers to object types are contiguous_iterators.
• void* and function pointers are not iterators.
• Ranges produce iterators; iterators represent positions.