Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is a contiguous_range always a sized_range?

I have the following question concerning the ranges library in C++20:

Let std::ranges::contiguous_range<T> for an arbitrary type T.

Can I assume std::ranges::sized_range<T>?

like image 751
plexando Avatar asked Oct 19 '20 18:10

plexando


3 Answers

No, not every contiguous_range is a sized_range.

The simplest example is a null-terminated string. It's contiguous, but we don't know its size in O(1) time. And we can easily represent such a thing using sentinels:

struct ntbs_sentinel {
    bool operator==(char const* p) const {
        return *p == '\0';
    }
};

struct ntbs {
    char const* p;
    char const* begin() const { return p; }
    ntbs_sentinel end() const { return {}; }
};

static_assert(std::ranges::contiguous_range<ntbs>);
static_assert(!std::ranges::sized_range<ntbs>);

Another example would be, given some std::string object s and some predicate p, either:

  • s | std::views::take_while(p)
  • s | std::views::drop_while(p)

The resulting range here is still contiguous, but we don't know where it ends (in the first case) or where it starts (in the second) so we don't know what its size is.

like image 171
Barry Avatar answered Nov 17 '22 11:11

Barry


Being a contiguous_range<T> is insufficient to be considered a sized_range<T>, due to the presence of a sentinel. However, if you combine contiguous_range<T> with common_range<T> (which requires that the sentinel is an iterator), then sized_range<T> must also be true.

Here's the logic. A contiguous_range<T> is also a random_access_range<T>. And a random_access_range<T> means in part that random_access_iterator<iterator_t<T>> is true. common_range<T> means that is_same<iterator_t<T>, sentinel_t<T>>. Therefore, random_access_iterator<sentinel_t<T>> must also be true.

Now, random_access_iterator<It> imposes a requirement that std::sized_sentinel_for<I, I> is true. Since iterator_t<T> and sentinel_t<T> are the same type, this means that std::sized_sentinel_for<sentinel_t<T>, iterator_t<T>> must also be true.

So, let's look at sized_range<T>. This requires that std::ranges::size(t) is valid for a t of type T.

ranges::size<T> is valid if T models ranges::forward_range<T> (which it does) and sentinel_t<T> and iterator_t<T> models std::sized_sentinel_for<sentinel_t<T>, iterator_t<T>>.

Which as previously stated, it does.

like image 11
Nicol Bolas Avatar answered Nov 17 '22 10:11

Nicol Bolas


No.

contiguous_range is:

template<class T>
concept contiguous_range =
  ranges::random_access_range<T> &&
  std::contiguous_iterator<ranges::iterator_t<T>> &&
  requires(T& t) {
    { ranges::data(t) } ->
      std::same_as<std::add_pointer_t<ranges::range_reference_t<T>>>;
  };

and, as you can see, it requires random_access_range, which is:

template<class T>
concept random_access_range =
  ranges::bidirectional_range<T> && std::random_access_iterator<ranges::iterator_t<T>>;

which, on the other hand, requires bidirectional_range, which is:

template<class T>
concept bidirectional_range =
  ranges::forward_range<T> && std::bidirectional_iterator<ranges::iterator_t<T>>;

which requires forward_range, that is:

template<class T>
concept forward_range =
  range::input_range<T> && std::forward_iterator<ranges::iterator_t<T>>;

and that requires input_range, so it needs:

template<class T>
concept input_range =
  ranges::range<T> && std::input_iterator<ranges::iterator_t<T>>;

while range only requires that std::ranges::begin() and std::ranges::end() are valid for given T.


You can play a similar game with those std::XXX_iterators. Nowhere there is anything for std::ranges::size (which enables sized_range).

like image 7
Fureeish Avatar answered Nov 17 '22 09:11

Fureeish