What is Iterator in C++?

The header provides iterator categories, traits, adaptors, stream iterators, and free functions that bridge containers and algorithms.

Which C++ standard introduced Iterator?

Iterator was introduced in C++98.

What is the difficulty level of Iterator?

Iterator is considered Intermediate-level C++ material.

Iterator

<iterator>since C++98

The <iterator> header defines the category taxonomy, the iterator_traits type trait, adaptor types (reverse, insert, move, stream), and utility functions that let algorithms operate uniformly over any range — container, array, or stream — without coupling to a specific data structure.

Overview

Iterators are the glue between containers and algorithms. An algorithm accepts a half-open range [first, last) and operates through the iterator interface without knowing anything about the underlying data structure. The standard organises iterators into a capability hierarchy; algorithms specialise based on what an iterator can do — advance forward only, step backward, or jump by n in O(1).

#include <iterator> is needed explicitly for adaptors, stream iterators, and utility functions. Container and algorithm headers often pull it in transitively, but relying on that is fragile.

Iterator Categories

C++98 established five iterator categories. C++17 added a sixth (contiguous). C++20 restated the entire hierarchy as composable concepts. The ordering is strictly additive — each category subsumes the capabilities of the one above (output is a separate branch):

Category	Key Operations	Representative Types
Input	`++it`, `*it` (read, single-pass)	`std::istream_iterator`
Output	`++it`, `*it = v` (write, single-pass)	`std::ostream_iterator`, `back_inserter`
Forward	Input + multi-pass + default-constructible	`std::forward_list::iterator`
Bidirectional	Forward + `--it`	`std::list::iterator`, `std::map::iterator`
Random Access	Bidirectional + `it ± n`, `it[n]`, `<` ordering	`std::vector::iterator`, `std::deque::iterator`
Contiguous (C++17)	Random access + contiguous memory guarantee	`std::vector::iterator`, `T*`

The contiguous category was formalised as std::contiguous_iterator_tag in C++17 and as the std::contiguous_iterator concept in C++20.

Iterator Traits

std::iterator_traits<Iter> exposes five member type aliases for any iterator or raw pointer:

cpp

Godbolt

typename std::iterator_traits<Iter>::value_type        // element type
typename std::iterator_traits<Iter>::difference_type   // signed distance (usually ptrdiff_t)
typename std::iterator_traits<Iter>::pointer           // pointer to element
typename std::iterator_traits<Iter>::reference         // reference to element
typename std::iterator_traits<Iter>::iterator_category // one of the _tag types

Tag dispatch — routing overloads through the category tag — was the canonical C++98–17 technique for algorithm specialisation:

cpp

Godbolt

template<typename Iter>
typename std::iterator_traits<Iter>::difference_type
distance_impl(Iter first, Iter last, std::random_access_iterator_tag) {
    return last - first;  // O(1)
}

template<typename Iter>
typename std::iterator_traits<Iter>::difference_type
distance_impl(Iter first, Iter last, std::input_iterator_tag) {
    typename std::iterator_traits<Iter>::difference_type n = 0;
    while (first != last) { ++first; ++n; }
    return n;  // O(n)
}

template<typename Iter>
auto my_distance(Iter first, Iter last) {
    return distance_impl(first, last,
        typename std::iterator_traits<Iter>::iterator_category{});
}

In C++17, iterator_traits became SFINAE-friendly — instantiating it for a non-iterator type yields an empty specialisation rather than a hard error.

C++20 Iterator Concepts

C++20 supersedes tag dispatch with named concepts declared in <iterator>. They express the same category hierarchy as constraints, giving dramatically better diagnostics:

cpp

Godbolt

#include <iterator>

// Only instantiated for qualifying iterators — C++20
template<std::random_access_iterator Iter>
void quicksort(Iter first, Iter last);

// Requires clause form — C++20
template<typename Iter>
    requires std::bidirectional_iterator<Iter>
Iter find_last(Iter first, Iter last, const auto& value) {
    Iter result = last;
    for (auto it = first; it != last; ++it)
        if (*it == value) result = it;
    return result;
}

The concept hierarchy: std::contiguous_iterator ⊃ std::random_access_iterator ⊃ std::bidirectional_iterator ⊃ std::forward_iterator ⊃ std::input_iterator. Foundational building-block concepts include std::weakly_incrementable, std::incrementable, std::sentinel_for, and std::sized_sentinel_for.

Iterator Adaptors

Insert Iterators

Insert iterators convert assignment-through-iterator into container insertion, letting output-only algorithms populate containers without pre-sizing them:

cpp

Godbolt

#include <iterator>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>

std::vector<int> src{3, 1, 4, 1, 5, 9, 2, 6};
std::vector<int> positive;
std::deque<int>  reversed;
std::set<int>    unique_vals;

// Appends via push_back
std::copy_if(src.begin(), src.end(),
             std::back_inserter(positive), [](int x){ return x > 0; });

// Prepends via push_front (std::deque and std::list only — not std::vector)
std::copy(src.begin(), src.end(), std::front_inserter(reversed));

// Inserts at an arbitrary position via insert()
std::copy(src.begin(), src.end(), std::inserter(unique_vals, unique_vals.begin()));

Reverse Iterator

std::reverse_iterator<Iter> adapts any bidirectional iterator so that ++ moves backward. Containers expose rbegin()/rend() which return these wrappers:

cpp

Godbolt

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

// Equivalent to v.rbegin() / v.rend()
std::reverse_iterator rb(v.end());
std::reverse_iterator re(v.begin());

for (auto it = rb; it != re; ++it)
    std::cout << *it << ' ';  // 5 4 3 2 1

*rb dereferences to *(rb.base() - 1), not *rb.base(). This offset is intentional — rend() must be a valid (non-dereferenceable) sentinel — but it causes persistent off-by-one errors when converting between forward and reverse iterator positions.

Move Iterator (C++11)

std::move_iterator wraps any iterator such that dereferencing yields an rvalue reference, enabling move semantics in copy-based algorithms:

cpp

Godbolt

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

std::vector<std::string> src{"alpha", "beta", "gamma"};
std::vector<std::string> dst;
dst.reserve(src.size());

// C++11: moves each element rather than copying
std::copy(std::make_move_iterator(src.begin()),
          std::make_move_iterator(src.end()),
          std::back_inserter(dst));
// src elements are now valid-but-unspecified

Stream Iterators

std::istream_iterator<T> reads successive values from a stream via operator>>; a default-constructed instance serves as the end-of-stream sentinel. std::ostream_iterator<T> writes to a stream with an optional delimiter:

cpp

Godbolt

#include <iterator>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iostream>

std::istringstream ss{"3 1 4 1 5 9 2 6"};

// Parse all ints without an explicit loop
std::vector<int> data(
    std::istream_iterator<int>{ss},
    std::istream_iterator<int>{}
);

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

std::copy(data.begin(), data.end(),
          std::ostream_iterator<int>{std::cout, " "});
// Output: 1 1 2 3 4 5 6 9

Helper Functions

Function	Since	Complexity
`std::advance(it, n)`	C++98	O(1) random access, O(n) otherwise
`std::distance(first, last)`	C++98	O(1) random access, O(n) otherwise
`std::next(it, n=1)`	C++11	Returns copy advanced by n
`std::prev(it, n=1)`	C++11	Returns copy decremented by n; requires bidirectional
`std::begin(c)` / `std::end(c)`	C++11	Works for arrays and containers uniformly
`std::cbegin(c)` / `std::cend(c)`	C++14	Const variants
`std::rbegin(c)` / `std::rend(c)`	C++14	Reverse variants
`std::size(c)` / `std::empty(c)` / `std::data(c)`	C++17	Also work for arrays and `std::initializer_list`

Writing a Custom Iterator

Provide the five member type aliases; do not inherit from std::iterator<> (deprecated in C++17). In C++20, verify conformance with a static_assert:

cpp

Godbolt

#include <iterator>
#include <cstddef>

template<typename T>
class stride_iterator {
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;

    stride_iterator(T* ptr, std::ptrdiff_t stride) : ptr_(ptr), stride_(stride) {}

    reference operator*()  const { return *ptr_; }
    pointer   operator->() const { return ptr_; }
    reference operator[](difference_type n) const { return ptr_[n * stride_]; }

    stride_iterator& operator++()    { ptr_ += stride_; return *this; }
    stride_iterator  operator++(int) { auto t = *this; ++*this; return t; }
    stride_iterator& operator--()    { ptr_ -= stride_; return *this; }
    stride_iterator  operator--(int) { auto t = *this; --*this; return t; }

    stride_iterator& operator+=(difference_type n) { ptr_ += n * stride_; return *this; }
    stride_iterator& operator-=(difference_type n) { ptr_ -= n * stride_; return *this; }

    friend stride_iterator operator+(stride_iterator it, difference_type n) { return it += n; }
    friend stride_iterator operator+(difference_type n, stride_iterator it) { return it += n; }
    friend stride_iterator operator-(stride_iterator it, difference_type n) { return it -= n; }
    friend difference_type operator-(stride_iterator a, stride_iterator b)  {
        return (a.ptr_ - b.ptr_) / a.stride_;
    }

    bool operator==(const stride_iterator&) const = default;       // C++20
    auto operator<=>(const stride_iterator& o) const {             // C++20
        return ptr_ <=> o.ptr_;
    }

private:
    T*             ptr_;
    std::ptrdiff_t stride_;
};

static_assert(std::random_access_iterator<stride_iterator<int>>);  // C++20

Pre-C++20, validate by passing your type to std::sort or std::reverse in a unit test; there is no compile-time conformance check available.

Best Practices

Constrain algorithms on the weakest iterator category that actually satisfies your needs. Accepting only std::random_access_iterator when std::forward_iterator would do locks out valid inputs unnecessarily.
Prefer std::next/std::prev over in-place ++/-- to avoid mutating an iterator you still need.
In C++20 code, constrain with iterator concepts rather than tag-based std::enable_if — concepts compose naturally with ranges and produce cleaner error messages.
Never dereference last in a [first, last) range; it is a past-the-end sentinel, not a valid position.
Call std::distance on non-random-access ranges only when unavoidable — it is O(n) and easy to embed inside a loop accidentally.

Common Pitfalls

Reverse iterator off-by-one: *v.rbegin() is implemented as *(v.end() - 1), but rbegin().base() == v.end(). When converting a reverse iterator back to a forward position (e.g., to pass to an algorithm), you must subtract one from .base().

Iterator invalidation after mutation: Inserting into or erasing from std::vector or std::deque invalidates all iterators to that container. Storing iterators across mutations leads to undefined behaviour; re-obtain them after every structural change.

Forward-only containers and std::prev: std::forward_list and all unordered containers provide only forward iterators. Any code path that calls std::prev or uses rbegin()/rend() on them will fail to compile — the category mismatch is your signal to redesign the traversal.

Signed/unsigned mismatch: std::distance returns difference_type (a signed type). Comparing it against size_t or std::vector::size_type (unsigned) triggers mixed-sign warnings or silent wrap-around on underflow.