CODEWITHSUNDEEP
c++c++20c++-conceptsstd-ranges
康桓瑋
康桓瑋

Reputation: 42736

Can C++20 range adaptors refine the range concept of underlying range?

Consider the following simple range:

struct my_range {
  int* begin();
  int* end();
  const int* data();
};

Although this class has a data() member, according to the definition of contiguous_range in [range.refinements]:

template<class T>
  concept contiguous_­range =
    random_­access_­range<T> && contiguous_­iterator<iterator_t<T>> &&
    requires(T& t) {
      { ranges::data(t) } -> same_­as<add_pointer_t<range_reference_t<T>>>;
    };

ranges::data(t) will directly call the my_range's member function data() and return const int*, but since my_range::begin() returns int*, this makes add_pointer_t<range_reference_t<my_range>> to be int*, so the last requires-clause is not satisfied, so that my_range is not a contiguous_range.

However, when I apply some range adaptors to my_range, it can construct a contiguous_range (goldbot):

random_access_range auto r1 = my_range{};
static_assert(!contiguous_range<my_range>);
contiguous_range auto r2 = r1 | std::views::take(1);

This is because take_view inherits view_interface, and the view_interface::data() only constrains the derived's iterator to be contiguous_iterator.

Since my_range::begin() returns int* which models contiguous_iterator, so view_interface::data() is instantiated and returns to_address(ranges::begin(derived)) which is int*, this makes both take_view::data() and begin() return int*, so r2 satisfies the last requires-clause and models contiguous_range.

Here, the range adaptors seem to refine the range concept of the underlying range, that is, converting a random_access_range to a contiguous_range, which seems to be dangerous since it makes ranges::data(r2) can return a modifiable int* pointer:

std::same_as<const int*> auto d1 = r1.data();
std::same_as<int*> auto d2 = r2.data();

I don't know if this refinement is allowed? Can this be considered a defect of the standard? Or is there something wrong with the definition of my_range?

Upvotes: 2

Views: 160

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 473272

I would not consider this a defect. The iterator/range model treats iterators as the truth. Several kinds of ranges deliberately have more functionality than just being a pair of iterators of some kind. This is because said functionality is materially useful and users of a range of a particular kind should expect to be able to use it. But this also leaves open the possibility of defining an incoherent range: where the iterator concept is stronger than the range concept because the range lacks certain functionality expected of the iterator concept.

If someone creates an incoherent range type, any functionality that operates on such a range (views, but also algorithms) has 3 options:

  1. Believe the iterators.
  2. Believe the range.
  3. Error out.

Now for algorithms, if the algorithm wants to use the data member, it makes sense that it will believe the range. That is where the member is after all.

But for a view, does it make sense to believe the range? Views don't store copies of ranges. After all, a range can be a container. They instead store and operate on iterators and sentinels. They therefore treat ranges as just a way to get an iterator/sentinel pair.

When a view defines itself as a particular range type, it therefore manufactures the ancillary functional of the range from what it stores: the iterator/sentinel pair. And most such things are pretty simple to manufacture. The data member of a contiguous_range can be manufactured by using std::to_address (a requirement of being a contiguous_iterator) on the result of begin().

So when given an incoherent range, it would actually be harder to filter such things out based on the original range type. Particularly in light of view_interface, which only sees the new view type, not the range it is built from.

After all, not all views are built from other ranges. iota_view is a view, but it isn't built from anything. But its iterators are random access; so too is its range. single_view is likewise not built from a "range"; it treats a single object as a single-element contiguous range. And subrange is built from an iterator/sentinel pair, not a range.

So either views built from other ranges would have to have their own special view_interface... or you create circumstances where views are just better than their original ranges. Or you error out.

It should also be noted that the current behavior is 100% safe. No code will be functionally broken by having a view be stronger than the range it was built from. After all, your not-quite-contiguous_range type still provides non-const access to the elements. The user just has to work a bit harder for it.

Upvotes: 1

Related Questions