Iterators and Algorithms

This section documents C++23 (ISO/IEC 14882:2024), as published by ISO/IEC JTC1/SC22/WG21 (wg21), verified against the freely available working draft N5046 (eel.is/c++draft) and cppreference.com.

This content was generated with the assistance of AI and should be verified against the working draft and cppreference.com before being relied on in production.

This section’s bibliography lists the reference material consulted while preparing these pages.

Iterator Categories

Algorithms are written against the weakest iterator category they need, so they work across the widest range of containers. Each category is a strict superset of the guarantees below it:

Iterator category hierarchy: input and output iterators at the base; forward iterators add multi-pass guarantees; bidirectional adds reverse traversal; random-access adds O(1) indexed jumps and iterator arithmetic

  • Input — single-pass, read-only (std::istream_iterator).

  • Output — single-pass, write-only (std::ostream_iterator, std::back_inserter).

  • Forward — multi-pass, read (std::forward_list::iterator).

  • Bidirectional — forward plus -- (std::list::iterator, std::map::iterator).

  • Random-access — bidirectional plus O(1) it + n/it[n] (std::vector::iterator, raw pointers).

  • Contiguous (C++20) — random-access plus a guarantee the elements are laid out contiguously in memory (std::vector::iterator, std::array::iterator, but not std::deque::iterator).

begin/end and Non-Member Access

#include <vector>
#include <iterator>

std::vector<int> v = {1, 2, 3};
auto it1 = v.begin();      // member function
auto it2 = std::begin(v);   // free function -- also works on a raw C array, which has no .begin() member
auto it3 = std::cbegin(v);   // always a const_iterator, even if v is non-const

Range-for (see Control Flow) uses the non-member begin/end internally, found via ADL — which is exactly why it works on raw arrays too.

<algorithm> and <numeric>

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 1, 4, 2};

    std::sort(v.begin(), v.end());                      // {1, 2, 3, 4, 5}
    auto it = std::find(v.begin(), v.end(), 3);           // iterator to the found 3
    bool has4 = std::binary_search(v.begin(), v.end(), 4);  // requires a sorted range: true
    auto maxIt = std::max_element(v.begin(), v.end());     // iterator to 5

    std::vector<int> a = {1, 3, 5}, b = {2, 3, 4}, result;
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result));  // {3}

    std::vector<int> seq(5);
    std::iota(seq.begin(), seq.end(), 1);                  // {1, 2, 3, 4, 5}
    std::fill(seq.begin(), seq.end(), 0);                    // {0, 0, 0, 0, 0}
    std::generate(seq.begin(), seq.end(), [n = 0]() mutable { return n++; });   // {0, 1, 2, 3, 4}

    int sum = std::accumulate(v.begin(), v.end(), 0);        // 15
    (void)it; (void)has4; (void)maxIt; (void)sum;
    for (int x : result) std::cout << x << ' ';
}

Insert Iterators

std::back_inserter/std::front_inserter/std::inserter adapt an output iterator so an algorithm can grow a container instead of overwriting a fixed range — used with std::set_intersection above, and idiomatic anywhere an algorithm’s output size isn’t known ahead of time:

#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> source = {1, 2, 3};
std::vector<int> destination;
std::copy(source.begin(), source.end(), std::back_inserter(destination));   // grows destination as needed,
                                                                               // instead of requiring it to
                                                                               // already have 3 elements

Writing a Random-Access Iterator

#include <iterator>
#include <cstddef>
#include <compare>

class IntRangeIterator {
public:
    using iterator_concept  = std::random_access_iterator_tag;
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = int;
    using difference_type   = std::ptrdiff_t;

    IntRangeIterator() = default;             // random-access iterators must be default-constructible
    explicit IntRangeIterator(int value) : value_(value) {}

    int operator*() const { return value_; }
    int operator[](difference_type n) const { return value_ + static_cast<int>(n); }

    IntRangeIterator& operator++() { ++value_; return *this; }
    IntRangeIterator  operator++(int) { auto copy = *this; ++value_; return copy; }
    IntRangeIterator& operator--() { --value_; return *this; }
    IntRangeIterator  operator--(int) { auto copy = *this; --value_; return copy; }

    IntRangeIterator& operator+=(difference_type n) { value_ += static_cast<int>(n); return *this; }
    IntRangeIterator& operator-=(difference_type n) { value_ -= static_cast<int>(n); return *this; }

    friend IntRangeIterator operator+(IntRangeIterator it, difference_type n) { return it += n; }
    friend IntRangeIterator operator+(difference_type n, IntRangeIterator it) { return it += n; }
    friend IntRangeIterator operator-(IntRangeIterator it, difference_type n) { return it -= n; }
    friend difference_type  operator-(const IntRangeIterator& a, const IntRangeIterator& b) {
        return a.value_ - b.value_;
    }

    bool operator==(const IntRangeIterator&) const = default;
    auto operator<=>(const IntRangeIterator&) const = default;

private:
    int value_ = 0;
};

static_assert(std::random_access_iterator<IntRangeIterator>);   // the tag is a promise -- check it

The full set matters: the random_access_iterator_tag above is a claim, and anything that trusts it (std::sort over such a range, std::prev, or the std::random_access_iterator concept itself) breaks if an operation is missing. Dropping any of --, +=, -=, operator[], post-increment or the relational operators makes the static_assert fail — which is exactly why it is worth writing down.

C++20’s std::iterator_traits can deduce most of these members automatically for a well-formed iterator, reducing the boilerplate above — see Ranges and Views for the concept-based (std::input_iterator, std::random_access_iterator, …​) way ranges validate an iterator type instead.

std::erase_if

C++20 unifies the "erase matching elements" idiom (previously the notoriously named erase-remove idiom) into one free function per container category:

#include <vector>
#include <algorithm>

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::erase_if(v, [](int x) { return x % 2 == 0; });   // {1, 3, 5} -- replaces
                                                        // v.erase(std::remove_if(v.begin(), v.end(), pred), v.end())

References