Iterators

What is an iterator?

An iterator is an abstraction for representing an item, element, value etc. in a collection or container of values that also has some notion how to get to a obtain or yield a new item from the container. In C++ iterators a lot like pointers in the sense that they hold some value, usually the location of it and has a means of either yielding the value for reading or allows for writing to that value.

Iterator Categories

There are 6 main iterator categories considered in C++. Each subsequent iterator category builds upon the previous categories requirements with increasingly more requirements.

Iterator Category	Valid Operations
Iterator Category	write	read	increment	multiple passes	decrement	random access	contiguous storage
Output	✅		✅
Input	might support writing	✅	✅
Forward (Satisfies Input)	✅	✅	✅	✅
Bidirectional (Satisfies Forward)	✅	✅	✅	✅	✅
Random Access (Satisfies Bidirectional)	✅	✅	✅	✅	✅	✅
Contiguous (Satisfies Random Access)	✅	✅	✅	✅	✅	✅	✅

Note: A pointer actually satisfies the Contiguous Iterator Category

Before C++20, there were empty structs used as tags to help categorise an iterator into its respective category. Since C++ there have been concepts introduces to perform this check more elegantly along with other iterator-related concepts to all for anything modelling an iterator to satisfy the constraints.

Obtaining Iterators

Almost all collections or containers have iterators to their first and last element. To obtain these iterator from any container kinds we call the std::begin() and std::end functions from the <iterator> header respectively. There are also constant and reverse and constant reverse versions of the functions.

#include <array>
#include <iostream>
#include <iterator>

auto main() -> int
{
    auto a = std::to_array<int>({1, 3, 4, 565, 868, 5, 46});
    
    std::cout << std::begin(a) << std::endl;
    std::cout << *std::begin(a) << std::endl;
    std::cout << std::end(a) << std::endl;
    std::cout << *(std::end(a) - 1) << std::endl;

    return 0;
}

Example

Iterator Functionalities

There are a few ways to interact with an iterator directly. One is to use the overloaded operators for the iterator object. Most iterators implement and overload the same operator set that is used by pointers. The other way is to use functions to interact with iterators, allowing for a more generic interface if a iterator doesn't support the common operator overload set and the implementer preferred to overload the functions. The only way to yield or write to the item held by an iterator is to use the dereference operator *.

Common Operator Interface

Operation
dereference	`*i`	`*i = v`	`v = *i`
increment	`i++`	`++i`
decrement	`i--`	`--i`
difference	`i - j`
advance	`i + n`	`i - n`
index	`i[n]`

Note: Where i is an iterator object

#include <array>
#include <iostream>
#include <iterator>

auto main() -> int
{
    auto a  = std::to_array<int>({1, 3, 4, 565, 868, 5, 46});
    auto it = std::begin(a);

    std::cout << *it << std::endl;
    std::cout << *(it++) << std::endl;
    std::cout << *(++it) << std::endl;
    std::cout << *(it--) << std::endl;
    std::cout << *(--it) << std::endl;
    std::cout << *(it + 4) << std::endl;
    std::cout << *(std::end(a) - 4) << std::endl;
    std::cout << it[6] << std::endl;

    auto v { *it };
    *it = 757657;
    std::cout << v << std::endl;
    std::cout << *it << std::endl;

    return 0;
}

Example

Iterator Functions

There are four functions involved in manipulating an object of iterator kind. These are used to move an iterator between elements.

std::next - Obtains the next iterator from the passed iterator. Can be passed an integral n to obtain the nth next iterator. If n is negative, the iterator must satisfy Bidirectional Iterator.
std::prev- Obtains the previous iterator from the pass iterator. Can be passed an integral to obtain the nth previous iterator. The iterator must satisfy the requirements of a Bidirectional Iterator.
std::distance - Obtains the number of increments required by the first iterator to reach the second iterator.
std::advance - Advances the passed iterator by n increments. If n is negative, the iterator must satisfy Bidirectional Iterator.

#include <array>
#include <iostream>
#include <iterator>

auto main() -> int
{
    auto a  = std::to_array<int>({1, 3, 4, 565, 868, 5, 46});
    auto it = std::begin(a);

    std::cout << *it << std::endl;
    std::cout << *std::next(it) << std::endl;
    std::cout << *std::prev(it) << std::endl;
    std::cout << *std::next(it, 4) << std::endl;

    auto end = std::end(a);

    std::cout << *std::next(end, -4) << std::endl;

    std::cout << std::distance(it, end - 3) << std::endl;

    std::advance(it, 3);
    std::cout << *it << std::endl;

    return 0;
}

Example

Sentinels

Iterators are able to move through a container indefinitely however this can lead to iterators being dereferenced for a value that doesn't belong to the container. To fix this, we need some notion of the end of a container. Sentinels are a kind that behaves like a marker representing the end of a container. There are many different things you can use as a sentinel from specific values that appear in a container (\0 is used as a sentinel for char slices in C), to iterators. Before C++20, the 'end' iterator was the most common sentinel kind used. The iterator holds the item that is one-past-the-end of a container. When another iterator reaches it the container has been exhausted. Since C++20, the notion of the end of a container has been formalised to be sentinels over 'end' iterators. This allows for containers to be infinite with an unreachable sentinel type or have regular bounds.

#include <array>
#include <iostream>
#include <iterator>

auto main() -> int
{
    auto a = std::to_array<int>({1, 3, 4, 565, 868, 5, 46});
    
    /// Uses the iterator obtained by `std::end` from `a` as sentinel
    for (auto it = std::begin(a); it != std::end(a); ++it)
        std::cout << *it << (std::distance(it, std::end(a)) - 1 ? ", " : "");

    return 0;
}

Example

Iterator Adaptors

There are a few iterator adaptors in the C++ standard library allowing for regular iterators, often supplied by container kind types have certain operational semantics. This include a reverse, inserter, counted and move iterators. This allows for efficient operations between containers and containers to be implemented through iterators. Many of these iterators come with a factory function (often prefixed with make_) that can make the desired iterator and perform the necessary argument type deductions.

High Performance Programming