Contiguous Iterator Detection

Contiguous iterator detection

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.

How to check whether iterators form a contiguous memory zone?

Leaving aside your sample function, you can never be completely sure that iterators will form a contiguous memory without checking the address of every element between the two.

A reasonable sanity test, though, would be to just check if the memory area between the two is the same as the count between the two:

assert(&*last - &*first == last - first &&
    "Iterators must represent a contiguous memory region");

How to deduce contiguous memory from iterator

A) No. It just means that a valid mapping of the kind F(iterator +/- n) = iterator.next/prev.....n exists. This does not imply contiguous allocation at all. ( bounds do apply)

B) No. It depends on the implementation. For instance, you might not know what kind of data structure might be received if there is a 2 level of indirection.

The good news?, you need not bother at all. Between the cache and the branch prediction that happens, you would not need to optimize it at all. During run time, The cache line will be filled with the block of contiguous memory you intend to copy, thus it is going to be very fast, and memmove or memcpy will not help much.

You do not guarantee much with modern processors that are going to pipeline your instructions at run time, and they would know if it is contiguous or not.

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

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

Is There an Example of an Iterator Which Wouldn't use ptrdiff_t as its difference_type?

A basic output iterator, with std::ostream_iterator being one example, may not need a difference type at all.

Since it's meant to be a "fire and forget" sort of iterator, it usually doesn't make much sense to obtain a difference between two such iterators. The mere act of writing to one copy may invalidate all other copies. So it will not need to define a difference type, and should not be forced to do so artificially (or have the type forced on it).

Iterator concepts are weaker than the corresponding named requirements, which ones apply to the non-range standard algorithms?

Do they still use the same iterator requirements in C++20 as they were pre-C++20, or did the requirements for them get relaxed to match the concepts?

The existing std:: algorithms still use the named requirements. For instance, [alg.find] has both:

template<class InputIterator, class T>
  constexpr InputIterator find(InputIterator first, InputIterator last,
                               const T& value);

and

template<input_­iterator I, sentinel_­for<I> S, class T, class Proj = identity>
  requires indirect_­binary_­predicate<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
template<input_­range R, class T, class Proj = identity>
  requires indirect_­binary_­predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr borrowed_iterator_t<R>
    ranges::find(R&& r, const T& value, Proj proj = {});

The same is true for all the algorithms.

---

Note that there is a proposal to change this: Ranges views as inputs to non-Ranges algorithms. That paper would change the named requirements to become in line with the concepts (note that it would not change the std:: algorithms to accept sentinels).

---

Related Topics