Ch8.4: Iterator Algorithms

Overview

Algorithms operate on iterators. They do not know or care about the underlying container; they only require certain iterator capabilities.

In this chapter, you will learn:

• how algorithms depend on iterator categories
• which algorithms require which iterator strengths
• how to reason about algorithm preconditions
• how contiguous iterators enable fast paths
• how to detect iterator and range capabilities with if constexpr
• how iterator algorithms and ranges algorithms relate

1. Algorithms depend on iterator capabilities

Every algorithm has minimum iterator requirements. These requirements determine whether the algorithm can:

• read elements
• write elements
• traverse multiple times
• move backward
• jump to arbitrary positions

Stronger iterator categories enable stronger algorithms.

2. The capability ladder for algorithms

input_iterator
    ↓
forward_iterator
    ↓
bidirectional_iterator
    ↓
random_access_iterator
    ↓
contiguous_iterator

Each step adds new algorithmic possibilities.

3. Algorithms requiring input_iterator

These algorithms only need to read elements once, moving forward:

• find
• count
• for_each

They work on the weakest readable iterators.

4. Algorithms requiring forward_iterator

These algorithms require multiple passes over the same elements:

• remove
• unique
• replace

A forward_iterator guarantees multi-pass traversal.

5. Algorithms requiring bidirectional_iterator

These algorithms require backward movement:

• reverse
• rotate (bidirectional version)

6. Algorithms requiring random_access_iterator

These algorithms require constant-time jumps:

• sort
• nth_element
• binary_search

Random access enables indexing and partitioning.

Iterator algorithms

Iterator algorithms operate directly on iterator pairs:

::std::sort(vec.begin(), vec.end());

This form requires a random_access_iterator.

Ranges algorithms

Ranges algorithms can also accept iterator pairs:

::std::ranges::sort(vec.begin(), vec.end());

Or the entire range directly:

::std::ranges::sort(vec);

Both forms require the same iterator category.

Algorithms with comparison objects

Algorithms can accept comparison objects from <functional>. These work with both iterator algorithms and ranges algorithms.

Iterator algorithm form:

::std::sort(vec.begin(), vec.end(), ::std::greater<>{});

Ranges algorithm form (iterator pair):

::std::ranges::sort(vec.begin(), vec.end(), ::std::ranges::greater{});

Ranges algorithm form (entire range):

::std::ranges::sort(vec, ::std::ranges::greater{});

The comparison object does not change the iterator category requirements.

7. Algorithms benefiting from contiguous_iterator

A contiguous_iterator allows the compiler to reason about memory layout. This enables optimizations such as:

• vectorized operations
• memcpy-class fast paths
• loop unrolling

Pointers to object types and ::fast_io::vector<T> iterators are contiguous_iterators.

8. fast_io containers and iterator algorithms

::fast_io::vector<T> provides contiguous iterators. Algorithms that require random access or benefit from contiguity will use the strongest available path.

Other fast_io containers follow the same iterator rules as their STL counterparts.

9. Detecting algorithm applicability with if constexpr

You can write algorithms that adapt to iterator or range strength. The type is deduced from the function parameter, and if constexpr selects the appropriate path at compile time.

Iterator version

template <typename It>
void analyze(It first, It last)
{
    if constexpr(::std::random_access_iterator<It>)
        print("iterator: random-access fast path\n");
    else
        print("iterator: generic path\n");
}

Calling it is straightforward:

int arr[]{1,2,3,4};
analyze(arr, arr + 4);                 // arr decays to int*

::fast_io::vector<int> vec{1,2,3,4};
analyze(vec.begin(), vec.end());       // deduces ::fast_io::vector<int>::iterator

Range version

You can also write an overload that accepts an entire range:

template <typename T>
void analyze(T& r)
{
    if constexpr(::std::ranges::random_access_range<T>)
        print("range: random-access fast path\n");
    else
        print("range: generic path\n");
}

Calling the range version:

analyze(vec);                          // detects random_access_range

Both overloads adapt automatically based on iterator or range category.

10. Common pitfalls

• using multi-pass algorithms on input_iterators
• using random-access algorithms on bidirectional_iterators
• invalidating iterators during modification
• passing overlapping ranges to algorithms that forbid them

Key takeaways

• Algorithms depend on iterator categories.
• Stronger iterators enable stronger algorithms.
• Contiguous iterators allow the fastest optimizations.
• Iterator algorithms and ranges algorithms both operate on iterators.
• Comparison objects from <functional> work with both forms.
• if constexpr allows algorithms to adapt to iterator or range strength.