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.)

Marshallmarshallese

Please add the c++ tag to all C++ questions, so that more users see the post. – Atwell

Hmm, your edit looks more like an answer. I'm a little confused as to what your question actually is right now; the title doesn't seem to match up either. Could you edit the question to make it clearer? – Atwell

Note that self-answering is good, and is better than editing an answer into your question. – Privett

@cigien: My "This is looking nicer!" is still a question: "This works, but is it guaranteed? is it best practice? in short, In C++20, how do I write a contiguous iterator?" So it doesn't really count as an "answer". Answers (to this question) need to have the force of authority and/or experience behind them. Otherwise it's still just hacks that happen to work. – Marshallmarshallese

Answer 1

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!

Marshallmarshallese

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.

Brunel

Could you flesh out your code snippet for pointer_traits<I>? Feel free to use the name of the MyIterator type I defined in the question. Note that MyIterator has an addr() const method. In particular, is it legit to specialize pointer_traits<MyIterator> containing only to_address, as currently shown, or are there more members that should be included in the specialization? Also, are you claiming that, in C++20, specializing pointer_traits<MyIterator> is the right way to write a contiguous iterator type? – Marshallmarshallese

@Quuxplusone: Either of these two solutions are "right": (1) Specialize pointer_traits and provide just static int* to_address(const MyIterator& i) { return i.addr(); } OR (2) Define int* MyIterator::operator->() const { return addr(); } and define MyIterator::element_type (to be an alias to int). Which you choose between (1) and (2) is up to you. In (1) you only need to_address, yes, no other members are needed. – Brunel

@Quuxplusone: Also I do not have enough reputation to reply to the answer above, but this statement of yours is correct: "giving your iterator an operator-> absolutely does not suffice in practice to make it count as a contiguous iterator". A contiguous iterator requires to_address(i) be valid. For to_address(i) to be valid, it requires that pointer_traits<I> be valid (whether that is the primary template, or your own specialization). – Brunel

Answer 3

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{});

Delict

"Satisfying #3 is primarily done with a template specialization:" ... followed by not a template specialization? That looks like an overload to me. – Privett

@Yakk-AdamNevraumont: Woops. Fixed. – Delict

You're not allowed to specialize std::to_address. – Muddle

@Barry: It's fixed now. I think. – Delict

Just int* operator-> const (iterators aren't deep const). And that's unfortunately not quite enough to make the primary template valid (see the other answer). – Muddle

I guarantee that this answer is wrong; giving operator->() a non-const overload is always wrong. Furthermore, giving your iterator an operator-> absolutely does not suffice in practice to make it count as a contiguous iterator. Even std::list<int>::iterator has an operator->. – Marshallmarshallese

@Quuxplusone: "giving your iterator an operator-> absolutely does not suffice in practice to make it count as a contiguous iterator" I never said that it was sufficient. Indeed, I listed several other requirements for contiguous iterator, which list::iterator does not fulfill. Adding operator-> merely addresses the std::to_address conversion. Which yes, list::iterator also can do. – Delict

@Quuxplusone: As evidence for why having operator-> is sufficient, see this part of the std::to_address. pointer_traits is not required, only an operator-> overload. – Delict

Will add that for compilers that don't give you nice diagnostics on what requirements aren't met and why, you can check individual concepts manually by checking the documentation and using static_asserts on them – Fenderson

"Yes, you may have to dig through 10+ layers of other concept definitions" This is a major pragmatic barrier to implementing these concepts in real projects with real deadlines. C++ is suffering from a lack of canonical pragmatic documentation. I'm coming up against increasing resistance to C++ in workplaces due to this. How can we fix this? – Feat

@sleep: Make books about programming profitable again. Nowadays, there's little motivation for the people with knowledge and understanding to take the time and effort to distill that knowledge into something that other programmers can understand. The best you get today are videos or conference presentations, which are rarely comprehensive. – Delict

Totally agree. I have a Packt subscription and just purchased a physical book on Range-V3, neither of which I'm satisfied with for learning ranges. Maybe the Cpp Alliance should start a wiki project that is a practical companion to cppreference.com? I also think that profit was not the major motive for a lot of the great C++ writers back in the day. Profit has become an imperative due to the constant acceleration and pressure of our economics. There used to be a spirit of sharing, adventure and exploration driving the literature, and dare I say it, joy. – Feat

Omg it just hit me what I miss about the pre-C++-11 days: I used to spend most of my time thinking about better code and algorithms, now I spend most of my time tracking down language details. – Feat