3

In various places in the c++ Standard, the phrase:

Requires: [p, p + len) is a valid range.

(where p is a pointer, and len is a number) is used.

An alternate version for iterators is:

Requires: [first, last) is a valid range.

What does this mean?

Hatted Rooster
  • 35,759
  • 6
  • 62
  • 122
Marshall Clow
  • 15,972
  • 2
  • 29
  • 45

2 Answers2

4

I think the relevant part of the C++17 Standard is here

27.2.1 In general [ iterator.requirements.general ]

...

8 An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to elements of the same sequence.

9 Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.

So extracting the pertinent parts:

8 An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j...

9 ... Range [i, j) is valid if and only if j is reachable from i....

So it seems that a "valid range" is a pair of iterators that belong to the same container (or array), with j being farther along than i.

But also not forgetting:

in general, a range [i, j) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by j.

So all of the iterators between i and j (but not necessarily including j) must be "in the data structure" (ie. not out-of-bounds).

Community
  • 1
  • 1
Galik
  • 47,303
  • 4
  • 80
  • 117
  • Is `[nullptr, nullptr)` a valid range? – ceztko Jul 16 '21 at 13:47
  • 1
    @ceztko That is a very good question. IMO yes it is based on paragraph`8` quoted in my answer: _"An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j"._ In this case, the "finate sequence of applications" is _zero._ – Galik Jul 16 '21 at 14:06
  • On a couple of wild tests, the Microsoft STL implementation agrees, `[nullptr, nullptr)` is a valid range. For example `string(nullptr, 0)` or `string_view(nullptr, 0)`. – ceztko Jul 16 '21 at 14:23
  • 1
    @ceztko Actually those look fine according to my understanding of [cppreference.com](https://en.cppreference.com/w/cpp/string/basic_string/basic_string) – Galik Jul 16 '21 at 14:47
1

What this means is that everything between first inclusively and p+len or last exclusively must be valid.

This all hinges on the fact that C++ allows for past-the-end of arrays pointers to exist, as long as you only use them to refer to the "end" of the array without ever dereferencing them.

So If I have:

int my_array[10];

int* first = &my_array[0];
int* last = &my_array[10];

Then first and last represent a valid range, even if last technically points to nowhere valid.

The same principle applies to iterators, where the end() of a container is not actually part of the container's data at all.

This all may look fairly bizarre at first glance, but this way of representing ranges allows for dealing with empty ranges in a sane way.

  • 2
    What this also means is that you can form a range around a variable: `int a; int* begin = &a; int* end = &a + 1;` :) – Rakete1111 May 21 '18 at 18:34