In C++20, how do I write a contiguous iterator?

Question

C++20 has explicit library support for std::contiguous_iterator_tag. Some STL algorithms (e.g. std::copy) can perform much better on contiguous iterators. However, I'm unclear on exactly how the programmer is supposed to get access to this new functionality.

Let's suppose for the sake of argument that we have a completely conforming C++20 library implementation. And I want to write the simplest possible contiguous iterator.

Here's my first attempt.

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using reference = int&;
    using pointer = int*;
    using difference_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

namespace std {
    int *to_address(MyIterator it) {
        return it.operator->();
    }
}

static_assert(std::contiguous_iterator<MyIterator>);  // FAILS

This fails on both GCC/libstdc++ and MSVC/STL; but is it supposed to?

For my next attempt, I specialized pointer_traits<MyIterator>. MyIterator isn't actually a pointer, so I didn't put anything in pointer_traits except the one function that the library needs. This is my second attempt:

#include <iterator>

class MyIterator {
    ~~~
};

template<>
struct std::pointer_traits<MyIterator> {
    int *to_address(MyIterator it) {
        return it.operator->();
    }
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

Is this how I'm supposed to do it? It feels extremely hacky. (To be clear: my first failed attempt also feels extremely hacky.)

Am I missing some simpler way?

In particular, is there any way for MyIterator itself to warrant that it's contiguous, just using members and friends and stuff that can be defined right there in the body of the class? Like, if MyIterator is defined in some deeply nested namespace, and I don't want to break all the way out to the top namespace in order to open namespace std.

---

EDITED TO ADD: Glen Fernandes informs me that there is a simpler way — I should just add an element_type typedef, like this! (And I can remove 3 of iterator_traits' big 5 typedefs in C++20.) This is looking nicer!

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using element_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

---

Also, I've seen some stuff about using member typedef iterator_concept instead of iterator_category. Why might I ever want to provide MyIterator::iterator_concept? (I'm not asking for a full historical explanation here; just a simple best-practice guideline "nah forget about iterator_concept" or "yes provide it because it helps with X" would be nice.)

Answer 1

One of the main benefits of C++ concepts as a language feature is that the concept definition tells you what you need to provide. std::contiguous_iterator is no different. Yes, you may have to dig through 10+ layers of other concept definitions to get down to the basic terms you need to provide. But they are right there in the language.

To whit, a contiguous iterator is a random access iterator:

1. Whose tag is derived from contiguous_iterator
2. Whose reference_type is an lvalue reference to its value_type (ie: not a proxy iterator or generator).
3. For which the standard library function std::to_address can be called to convert any valid iterator (even one which is not dereferencable) into a pointer either to the element the iterator references or to the one-past-the-end pointer.

Unfortunately, satisfying #3 can't be done by specializing std::to_address directly. You have to use either specialize pointer_traits::to_address for your iterator type or give your iterator an operator-> overload.

The latter is easier to do and, despite operator-> not being otherwise required by std::contiguous_iterator, makes sense for such an iterator type:

class MyIterator
{
 ...
  int const *operator->() const;
};

FYI: Most compilers will give you more helpful error messages if you constrain a template based on the concept, rather than just static_asserting on it. Like this:

template<std::contiguous_iterator T>
void test(const T &t);

test(MyIterator{});

Answer 2

There are two ways to support std::to_address. One is:

namespace std {

template<>
struct pointer_traits<I> {
    static X* to_address(const I& i) {
        // ...
    }
};

}

Note the static above.

The second way, as Glen pointed out to you, is to simply define I::operator-> and to make sure the primary template of std::pointer_traits<I> is valid. This just requires that std::pointer_traits<I>::element_type is valid.

The answer by Nicol Bolas is incorrect because that is not how you customize std::to_address for a user-defined type. Since C++20 (because of P0551) it is forbidden to specialize function templates in namespace std that you're not explicitly allowed to.

You're not allowed to specialize std::to_address. You can provide std::pointer_traits<I>::to_address though, and std::to_address will call it if it exists.

Answer 3

The last version in my question seems to be the most correct. There is just one subtlety to watch out for:

• MyIterator::value_type should be the cv-unqualified type of the pointee, such that someone could write value_type x; x = *it;
• MyIterator::element_type should be the cv-qualified type of the pointee, such that someone could write element_type *ptr = std::to_address(it);

So for a const iterator, element_type isn't just a synonym for value_type — it's a synonym for const value_type! If you don't do this, things will explode inside the standard library.

Here's a Godbolt proof-of-concept. (It's not a complete ecosystem, in that really you'd want MyIterator to be implicitly convertible to MyConstIterator, and probably use templates to eliminate some of the repetition. I have a rambly blog post on that subject here.)

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using element_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

class MyConstIterator {
    const int *p_;
public:
    using value_type = int;
    using element_type = const int;
    using iterator_category = std::contiguous_iterator_tag;
    const int *operator->() const;
    const int& operator*() const;
    const int& operator[](int) const;
    MyConstIterator& operator++();
    MyConstIterator operator++(int);
    MyConstIterator& operator--();
    MyConstIterator operator--(int);
    MyConstIterator& operator+=(int);
    MyConstIterator& operator-=(int);
    friend auto operator<=>(MyConstIterator, MyConstIterator) = default;
    friend int operator-(MyConstIterator, MyConstIterator);
    friend MyConstIterator operator+(MyConstIterator, int);
    friend MyConstIterator operator-(MyConstIterator, int);
    friend MyConstIterator operator+(int, MyConstIterator);
};

static_assert(std::contiguous_iterator<MyConstIterator>);  // OK!