Creating an Iterator with C++20 Concepts for custom container

Question

C++20 introduces concepts, a smart way to put constraints on the types a template function or class can take in.

While iterator categories and properties remain the same, what changes is how you enforce them: with tags until C++17, with concepts since C++20. For example, instead of the std::forward_iterator_tag tag you would mark your iterator with the std::forward_iterator concept.

The same thing applies to all iterator properties. For example, a Forward Iterator must be std::incrementable. This new mechanism helps in getting better iterator definitions and makes errors from the compiler much more readable.

This piece of text it's taken from this article: https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp

But the author didn't upgrade the content on how to make a custom iterator on C++20 with concepts, it remains the <= C++17 tags version.

Can someone make an example on how to write a custom iterator for a custom container in a C++20 version with the concept features?

Answer 1

By and large, the C++20 way of defining iterators does away with explicitly tagging the type, and instead relies on concepts to just check that a given type happens to respect the iterator category's requirements.

This means that you can now safely duck-type your way to victory while supporting clean overload resolution and error messages:

struct my_iterator {
  // No need for tagging or anything special, just implement the required interface.
};

If you want to ensure that a given type fulfills the requirements of a certain iterator category, you static_assert the concept on that type:

#include <iterator>

static_assert(std::forward_iterator<my_iterator>);

Enforcing that a function only accepts a certain iterator category is done by using the concept in your template arguments.

#include <iterator>

template<std::forward_iterator Ite, std::sentinel_for<Ite> Sen>
void my_algorithm(Ite begin, Sen end) {
 // ...
}

std::sentinel_for<> is now used for the end iterator instead of using Ite twice. It allows to optionally use a separate type for the end iterator, which is sometimes convenient, especially for input iterators.

For example:

struct end_of_stream_t {};
constexpr end_of_stream_t end_of_stream{};

struct my_input_iterator {
  // N.B. Not a complete implementation, just demonstrating sentinels.
  some_stream_type* data_stream;

  bool operator==(end_of_stream_t) const { return data_stream->empty(); }
};

template<std::input_iterator Ite, std::sentinel_for<Ite> Sen>
void my_algorithm(Ite begin, Sen end) {
  while(begin != end) {
    //...
  }
}

void foo(some_stream_type& stream) {
  my_algorithm(my_input_iterator{&stream}, end_of_stream);
}

Answer 2

Putting this here as much for my own future benefit.
A minimal contiguous iterator, as you go farther down the tree of iterators, less and less of this becomes required, but you can't have a contiguous without at least this much

#include <iterator>

template<typename T>
struct Iterator {
  using iterator_concept [[maybe_unused]] = std::contiguous_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using element_type = T;
  using pointer = element_type *;
  using reference = element_type &;

  Iterator() = default;
  Iterator(pointer p) { _ptr = p; }

  reference operator*() const { return *_ptr; }
  pointer operator->() const { return _ptr; }

  Iterator &operator++() {
    _ptr++;
    return *this;
  }
  Iterator operator++(int) {
    Iterator tmp = *this;
    ++(*this);
    return tmp;
  }
  Iterator &operator+=(int i) {
    _ptr += i;
    return *this;
  }
  Iterator operator+(const difference_type other) const { return _ptr + other; }
  friend Iterator operator+(const difference_type value,
                            const Iterator &other) {
    return other + value;
  }

  Iterator &operator--() {
    _ptr--;
    return *this;
  }
  Iterator operator--(int) {
    Iterator tmp = *this;
    --(*this);
    return tmp;
  }
  Iterator &operator-=(int i) {
    _ptr -= i;
    return *this;
  }
  difference_type operator-(const Iterator &other) const {
    return _ptr - other._ptr;
  }
  Iterator operator-(const difference_type other) const { return _ptr - other; }
  friend Iterator operator-(const difference_type value,
                            const Iterator &other) {
    return other - value;
  }

  reference operator[](difference_type idx) const { return _ptr[idx]; }

  auto operator<=>(const Iterator &) const = default;

private:
  pointer _ptr;
};

int main() {
  static_assert(std::contiguous_iterator<Iterator<char>>);

  return 0;
}

Answer 3

All other answers gave you an idea on how to do it in C++20, and as they mentioned, nothing has really changed since C++17 besides using compiler assertion checks for the validity of the iterators. Anyway, here is the C++20 version of a forward_iterator. In this examples only the required operators are implemented, and for the sake of the illustration a custom constructor was added.

#include <iostream>
#include <iterator>

template <typename T>
class Integers {
public:
    struct Iterator {
    using difference_type = std::ptrdiff_t;
    using element_type = T; // element_type is a reserved name that must be used in the definition
    using pointer = element_type *;
    using reference = element_type &;

    private:
        pointer ptr, start, sentinel;
        static_assert(std::sentinel_for<decltype(sentinel), decltype(ptr)>);
    public:
        // Default constructor is required to pass forward_iterator assertion
        Iterator() { throw std::runtime_error("Not implemented"); }
        Iterator(pointer p, pointer s) : ptr(p), start(p), sentinel(s) {}
        reference operator*() const { return *ptr; }
        auto &operator++() { ptr++; return *this; }
        auto operator++(int) { auto tmp = *this; ++(*this); return tmp; }
        auto operator<=>(const Iterator &) const = default; // three-way comparison C++20
        auto begin() {return start;}
        auto end() {return sentinel;}
    };

    auto begin() { return iter.begin(); }
    auto end() { return iter.end(); }
    Integers() {
        T j = 1;
        for(auto i = begin(); i != end(); ++i)
            *i = j++;
    }
private:
    T m_data[5];
    static_assert(std::forward_iterator<Iterator>);
    Iterator iter = Iterator(m_data, std::end(m_data));
};

template <typename T>
void print(Integers<T>& integers) {
    bool firstIteration = true;
    for (auto i : integers) {
        if (firstIteration) {
            firstIteration = false;
        } else {
            std::cout << " ";
        }
        std::cout << i;
    }
    std::cout << std::endl;
}

int main() {
    Integers<int> container;
    static_assert(std::forward_iterator<decltype(container.begin())>);
    print(container);
    std::fill(container.begin(), container.end(), 3);
    print(container);
}

Here you can check the code working as expected https://godbolt.org/z/o6ad3Knc7

And anyway, the output of the code should be:

1 2 3 4 5
3 3 3 3 3