Skip to content

Iterators

[Range-based for loop]
[Iterator concepts]
[Iterable range and generator classes]
[Iterator adapters (insert, stream, reverse iterators)]
[Combining two ranges/containers (ranges::views::zip)]

STL containers are navigated with use of iterators.

Old style example:

std::vector<int> v{1,2,3,4,5};
for (auto it = v.begin(); it != v.end(); ++it)
    std::cout << *it << '\n';

Range-based for loop

Prefer using the modern range-based for loop:

for (auto num : v)
    std::cout << num << '\n':

Behind the scenes the range-based for loop also uses iterators:

auto it{std::begin(v)};
auto end_it{std::end(v)};
for (; it!= end_it; ++it)
{
    auto num{*it};
    std::cout << num << '\n';
}

Remark:
the non-member functions std::begin()/end() also work with primitive arrays => range-based for loop is also possible for arrays.

Iterator concepts

With C++20 the iterator categories (e.g. “input iterator”, “forward iterator”) are now replaced by concepts (= named constraints) like “indirectly_writable”, “incrementable”, “input_iterator”, “forward_iterator”.

Example: template print method only accepting random access iterators:

template<typename T>
requires std::random_access_iterator<typename T::iterator>
void PrintContainer(const T& container)
{
    for (auto e : container)
        std::cout << std::format("{} ", e);
    std::cout << '\n';
    std::cout << First element: {}\n", container[0];
}

Iterable range and generator classes

Outside of simple containers iterators and range-based for loops are also possible for generator classes which produce a sequence of values.

The following class SequenceGenerator can be instructed to generate a sequence of values from a defined start point to a defined end point:

#include <iostream>
#include <format>
#include <algorithm> // minmax_element
#include <iterator> // forward_iterator_tag

template<typename T>
class SequenceGenerator
{
    T m_startVal{};
    T m_upperLimit{};
public:
    SequenceGenerator(T in_startVal, T in_upperLimit)
        :
        m_startVal(in_startVal),
        m_upperLimit(in_upperLimit)
    {}
    template<typename T> class iterator;
    iterator<T> begin() const { return iterator{ m_startVal }; }
    iterator<T> end() const { return iterator{ m_upperLimit }; }

    // Embedded iterator class, use traditional name "iterator"
    template<typename T>
    class iterator
    {
        // The iterator stores nothing but the current value
        T m_curValue;
    public:
        explicit iterator(T in_value = 0) : m_curValue(in_value) {}

        // minimum requirements for usage of range-based for loop are the following 3 operators:
        T operator*() const { return m_curValue; }
        iterator& operator++() { ++m_curValue; return *this; }
        bool operator!=(const iterator& other) const { return m_curValue != other.m_curValue; }

        // minimum requirements for a forward_iterator to allow usage of std::minmax_element
        bool operator==(const iterator& other) const { return m_curValue == other.m_curValue; }
        // required type definitions for implicitly used iterator_traits
        using iterator_concept = std::forward_iterator_tag;
        using iterator_category = std::forward_iterator_tag;
        using value_type = std::remove_cv_t<T>;
        using difference_type = std::ptrdiff_t;
        using pointer = const T*;
        using reference = const T&;
    };
};

Using the SequenceGenerator:

SequenceGenerator<int> iterableRange{20, 30};

for (auto val : iterableRange)
    std::cout << std::format("{} ", val);
std::cout << '\n';

auto [itMin, itMax] = std::minmax_element(iterableRange.begin(), iterableRange.end());
std::cout << std::format("minVal={}, maxVal={}", *itMin, *itMax);

Output:

20 21 22 23 24 25 26 27 28 29
minVal=20, maxVal=29

Iterator adapters (insert, stream, reverse iterators)

An iterator adapter is a class that looks like an iterator but does something else. Categories of STL iterator adapters:

  • insert iterators: insert elements into an container (std::back_inserter, std::front_inserter, std::inserter)
  • stream iterators: read from / write to a stream (std::ostream_iterator<int>, std::istream_iterator<int>)
  • reverse iterators: reverse the direction of an iterator (given for most containers by cont.rbegin(), cont.rend())

Helper function:

void PrintContainer(const auto& container, const std::string_view info = "")
{
    if (info.size()) std::cout << std::format("{}: ", info);
    for (auto e : container)
        std::cout << std::format("{} ", e);
    std::cout << '\n';
}

Example for insert iterators and stream iterators:

    std::deque<int> d0{0, 2, 4};
    std::deque<int> d1{1, 2, 3, 4, 5};
    std::deque<int> d2(d1.size()); // ensure same size as d1

    PrintContainer(d0, "d0");
    PrintContainer(d1, "d1");
    PrintContainer(d2, "d2");

    // std::copy requires that the target container has at least
    // the same number of elements as the source container
    std::copy(d1.begin(), d1.end(), d2.begin());
    PrintContainer(d2, "d2 after copy of d1");
    std::copy(d0.begin(), d0.end(), d2.begin());
    PrintContainer(d2, "d2 after copy of d0");

    // Iterator adpaters to insert new elements at end, at beginning or in the middle of a container,
    // methods like push_back on the target container are automatically called
    std::copy(d0.begin(), d0.end(), std::back_inserter(d2));
    PrintContainer(d2, "d2 after back_inserter of d0");
    std::copy(d1.begin(), d1.end(), std::front_inserter(d2));
    PrintContainer(d2, "d2 after front_inserter of d1");
    std::copy(d0.begin(), d0.end(), std::inserter(d2, d2.begin()+3));
    PrintContainer(d2, "d2 after inserter at target pos of d0");

    std::vector<double> v{1.1, 2.2, 3.3};
    std::cout << "Writing to std::out using ostream_iterator: ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<double>(std::cout, " "));
    std::cout << '\n';

    // Read from std::cin by calling "MyApp.exe < data.txt",
    // where data.txt contains 2 doubles 7.7 8.8
    std::copy(std::istream_iterator<double>(std::cin),
        std::istream_iterator<double>(), // end iterator
        std::back_inserter(v));
    PrintContainer(v, "after reading from cin");

Output:

d0: 0 2 4
d1: 1 2 3 4 5
d2: 0 0 0 0 0
d2 after copy of d1: 1 2 3 4 5
d2 after copy of d0: 0 2 4 4 5
d2 after back_inserter of d0: 0 2 4 4 5 0 2 4
d2 after front_inserter of d1: 5 4 3 2 1 0 2 4 4 5 0 2 4
d2 after inserter at target pos of d0: 5 4 3 0 2 4 2 1 0 2 4 4 5 0 2 4
Writing to std::out using ostream_iterator: 1.1 2.2 3.3
after reading from cin: 1.1 2.2 3.3 7.7 8.8

Sentinel = object that signals the end of an iterator of indeterminate length. When the iterator reaches end of data it will compare equal to the sentinel. Example: iterating over C string with terminating null char.

Combining two ranges/containers (ranges::views::zip)

Assume we have 2 containers with the same number of elements. We want a third container consisting of pairs made from the elements of both containers.

To allow output of std::pair via PrintContainer, we must define the following formatter:

// Allow output of std::pair via PrintContainer function
template<> struct std::formatter<std::pair<int,char>>
{
    // same code for most user defined types:
    template<typename ParseContext>
    constexpr auto parse(ParseContext& ctx) { return ctx.begin(); }

    // code to build specific output:
    template<typename FormatContext>
    auto format(const std::pair<int, char>& p, FormatContext& ctx)
    {
        return format_to(ctx.out(), "[{0}, {1}]", p.first, p.second);
    }
};

Simple but explicit code sufficient for most cases:

    std::deque<int> d{1, 2, 3, 4, 5};
    std::vector<char> v{'a', 'b', 'c', 'd', 'e'};
    PrintContainer(d, "d");
    PrintContainer(v, "v");

    auto itD = d.begin();
    auto itV = v.begin();
    auto itDEnd = d.end();
    auto itVEnd = v.end();

    std::vector<std::pair<int, char>> pairs;
    while (itD != itDEnd && itV != itVEnd)
    {
        pairs.emplace_back(*itD, *itV);
        ++itD;
        ++itV;
    }
    PrintContainer(pairs, "pairs");

Output:

d: 1 2 3 4 5
v: a b c d e
pairs: [1, a] [2, b] [3, c] [4, d] [5, e]

With use of std::ranges:vies::zip we can make the code even more simple:

    std::deque<int> d{1, 2, 3, 4, 5};
    std::vector<char> v{'a', 'b', 'c', 'd', 'e'};
    PrintContainer(d, "d");
    PrintContainer(v, "v");

    std::vector<std::pair<int, char>> pairs;
    for (auto [num, ch] : std::ranges::views::zip(d, v))
    {
        pairs.emplace_back(num, ch);
    }

    PrintContainer(pairs, "pairs after zip");

Remark: The elements returned by zip have type std::tuple<int&, char&> and can be assigned using structured binding.

As a third alternative we can define a special zip iterator adpater MyZipIterator which would allow the following syntax (which is quite similar to the usage of ranges::views::zip above):

std::deque<int> d{1, 2, 3, 4, 5};
std::vector<char> v{'a', 'b', 'c', 'd', 'e'};

std::vector<std::pair<int, char>> pairs;
for (auto [num,ch] : MyZipIterator(d, v))
{
    pairs.emplace_back(num, ch);
}

Here only some principles of the iterator class implementation for MyZipIterator are listed. The full description is available at [Bill Weinman, chapter 4, pages 133ff.].

  • The class stores for each of the containers the iterators for begin(), end() and the current iterator position
  • the central Method MyZipIterator::operator++() increments the internally stored iterator positions for both containers: ++itContainer1; ++itContainer2;
  • MyZipIterator::operator*() returns {*itContainer1, *itContainer2} which is the pair of values at the given iterator positions