How can you detect contiguous iterators, given that there is no std::contiguous_iterator_tag?

Question

C++17 introduced the concept of ContiguousIterator http://en.cppreference.com/w/cpp/iterator. However it doesn't seem that there are plans to have a contiguous_iterator_tag (in the same way we now have random_access_iterator_tag) reported by std::iterator_traits<It>::iterator_category.

Why is contiguous_iterator_tag missing?

Is there a conventional protocol to determine if an iterator is Contiguous? Or a compile time test?

In the past I mentioned that for containers if there is a .data() member that converts to a pointer to ::value type and there is .size() member convertible to pointer differences, then one should assume that the container is contiguous, but I can't pull an analogous feature of iterators.

One solution could be to have also a data function for contiguous iterators.

Of course the Contiguous concept works if &(it[n]) == (&(*it)) + n, for all n, but this can't be checked at compile time.

---

EDIT: I found this video which puts this in the more broader context of C++ concepts. CppCon 2016: "Building and Extending the Iterator Hierarchy in a Modern, Multicore World" by Patrick Niedzielski. The solution uses concepts (Lite) but at the end the idea is that contiguous iterators should implement a pointer_from function (same as my data(...) function).

The conclusion is that concepts will help formalizing the theory, but they are not magic, in the sense that someone, somewhere will define new especially named functions over iterators that are contiguous. The talk generalizes to segmented iterators (with corresponding functions segment and local), unfortunatelly it doesn't say anything about strided pointers.

---

EDIT 2020:

The standard now has

struct contiguous_iterator_tag: public random_access_iterator_tag { };

https://en.cppreference.com/w/cpp/iterator/iterator_tags

Chuipek

Why is contiguous_iterator_tag missing? ← because it will silently break pre-C++17 code that assumed std::vector::iterator is exactly a random access iterator? – Narco

@kennytm, Subtle reason. But if traits are correctly used (I think) one could make it backward compatible (e.g. if random_access_iterator derived from contiguous_iterator_tag). It would be unfortunate if the break would happen just because the trait was used incorrectly. – Chuipek

The situation doesn't seem to be promising. I think a possible idea could be to give a .data() member or a data(ContiguousIterator it) function for all contiguous iterators, this is in analogy to containers which currently have the .data() member when they are contiguous. – Chuipek

Well, what did they expect from ad hoc polymorphism? One motivation behind C++ was to avoid it. The whole iterator_tag thing should be banished into depredation. – Brussels

@JiveDadson I partially agree for the following reason. I came to the conclusion that the tags are a bad replacement for something that should be implemented by operator detection. For example if there is an operator++ then it is a forward iterator, if there is an operator+= then it is random access, if there is a data function then it is a contiguous iterator, etc. – Chuipek

Answer 1

Original answer

The rationale is given in N4284, which is the adopted version of the contiguous iterators proposal:

This paper introduces the term "contiguous iterator" as a refinement of random-access iterator, without introducing a corresponding contiguous_iterator_tag, which was found to break code during the Issaquah discussions of Nevin Liber's paper N3884 "Contiguous Iterators: A Refinement of Random Access Iterators".

Some code was broken because it assumed that std::random_access_iterator couldn't be refined, and had explicit checks against it. Basically it broke bad code that didn't rely on polymorphism to check for the categories of iterators, but it broke code nonetheless, so std::contiguous_iterator_tag was removed from the proposal.

Also, there was an additional problem with std::reverse_iterator-like classes: a reversed contiguous iterator can't be a contiguous iterator, but a regular random-access iterator. This problem could have been solved for std::reverse_iterator, but more user-defined iterator wrappers that augment an iterator while copying its iterator category would have either lied or stopped working correctly (for example Boost iterator adaptors).

C++20 update

Since my original answer above, std::contiguous_iterator_tag was brought back in the Ranges TS, then adopted in C++20. In order to avoid the issues mentioned above, the behaviour of std::iterator_traits<T>::iterator_category was not changed. Instead, user specializations of std::iterator_traits can now define an additional iterator_concept member type alias which is allowed to alias std::contiguous_iterator_tag or the previous iterator tags. The standard components has been updated accordingly in order to mark pointers and appropriate iterators a contiguous iterators.

The standard defines an exposition-only ITER_CONCEPT(Iter) which, given an iterator type Iter, will alias std::iterator_traits<Iter>::iterator_concept if it exists and std::iterator_traits<Iter>::iterator_category otherwise. There is no equivalent standard user-facing type trait, but ITER_CONCEPT is used by the new iterator concepts. It is a strong hint that you should use these iterator concepts instead of old-style tag dispatch to implement new functions whose behaviour depends on the iterator category. That said concepts are usable as boolean traits, so you can simply check that an iterator is a contiguous iterator as follows:

static_assert(std::contiguous_iterator<Iter>);

std::contiguous_iterator is thus the C++20 concept that you should use to detect that a given iterator is a random-access iterator (it also has a ranges counterpart: std::contiguous_range). It is worth noting that std::contiguous_iterator has a few additional constraints besides requiring that ITER_CONCEPT matches std::contiguous_iterator_tag: most notably it requires std::to_address(it) to be a valid expression returning a raw pointer type. std::to_address is a small utility function meant to avoid a few pitfalls that can occur when trying to retrieve the address where a contiguous iterator points - you can read more about the issues it solves in Helpful pointers for ContiguousIterator.

About implementing ITER_CONCEPT: it is worth nothing that implementing ITER_CONCEPT as described in the standard is only possible if you are the owner of std::iterator_traits because it requires detecting whether the primary instantiation of std::iterator_traits is used.

Emma

Excellent explanation. It is a sad scenario of all. I guess ContiguousIterator cannot be used programmatically, at least not for std::vector. – Chuipek

@Chuipek As is, ContiguousIterator is no more than a standardese term that helps to gather the different properties & guarantees of the contiguous standard collections' iterators. Unfortunately. std::contiguous_iterator_tag would have been great, but should have been there since the beginning :/ – Emma

We can hope that the situation will be improved when Concepts TS enters the standard. – Softpedal

@Oktalist, do you have a concrete idea on how Concepts will help? After all some has to "know" that a certain iterator is contiguous and that requires some kind of protocol. The protocol is there now, but it seems to impossible to extend with backwards compatibility. – Chuipek

@Chuipek No. Actually I should have said Ranges TS, which depends on Concepts, but in fact keeps the same old protocol. A new protocol from scratch would be the way forward IMHO, keeping the old one for BC. Ranges v3 introduces a ContiguousRange concept, but I'm not sure how it works. – Softpedal

@Oktalist, thanks, I know these papers mention code breaking but I don't see exactly what code is being broken. I agree that if that is the situation, it looks we have to start from scratch some category of concepts, and reimplementation of iterator_traits_v2. Also, knowing that an iterator is contiguous is really the first step, one needs to know the strides also (usually 1). So a parallel trait can do that job template<class It> class iterator_stride{}, (specialized only for contiguous iterators) with a member value (or value()). – Chuipek

@Softpedal The range-v3 ContiguousRange concept sidesteps completely the problem of identifying contiguous iterators by defining a ContiguousRange as a RandomAccessRange whose reference type is a true reference and for which the customization point ranges::data returns a pointer that dereferences to that same reference type. The only usage right now is the converting constructor for span, and ContiguousRange - since it doesn't assume the iterator type is contiguous - is only useful if the range also models SizedRange. – Dicker

youtu.be/N80hpts1SSk?t=2421 The solution uses concepts (Lite) but at the end the idea is that contiguous iterators should implement a pointer_from function (same as my data(...) function). – Chuipek

@Morwenn, thanks for the continous updates. This is going in the right direction. Next, strided iterators, How do I detect strided iterators? :) – Chuipek

@Chuipek There have been proposals for segmented & hierarchical iterators in the past, but they were deemed too complex to work. Strided things generally come up in SIMD and parallel algorithms discussions, but I don't think that there is anything proposing some kind of strided iterators. There is a strided view in Range-v3, but it wasn't proposed for C++20. The only strided component of the standard library so far is probably std::[g]slice_array but it doesn't seem to provide iterators. – Emma

@Morwenn, another example of strided iterator appears naturally on the realm of multidimensional arrays (when the arrays are implemented on contiguous memory). For example gitlab.com/correaa/boost-multi – Chuipek

The standard was update to have it: en.cppreference.com/w/cpp/iterator/iterator_tags. I think this can be accessed by iterator_concept (instead of iterator_category) to not break compatibility as you said. In perspective whether to celebrate or cry, I don't know. The reason I say this is because I think these tags are not as important as the corresponding traits-"functions" that make the tags useful (for example in this case, it should be accompanied by something like static std::iterator_traits<It>::data(It) to make it useful. Or potential concepts between Random & Contiguous. – Chuipek

@Chuipek Thanks, I updated the answer with a (hopefully accurate) summary of what C++20 offers wrt contiguous iterators. – Emma

Is it expected that the programmer of class MyContigIterator will crack open namespace std to write the needed overload of std::to_address(MyContigIterator)? That overload doesn't just magically show up, right? (It could have a default definition in terms of it.operator->(), for example, but the standard std::to_address doesn't have any default AFAICT.) – Kiser

@Kiser « If the expression std::pointer_traits<Ptr>::to_address(p) is well-formed, returns the result of that expression. Otherwise, returns std::to_address(p.operator->()) », so I guess that the standard function template works just fine if your iterator provides operator->. Actually I'm not sure. That's just weird. – Emma