What Is Half Open Range and Off the End Value

What is half open range and off the end value

A half-open range is one which includes the first element, but excludes the last one.

The range [1,5) is half-open, and consists of the values 1, 2, 3 and 4.

"off the end" or "past the end" refers to the element just after the end of a sequence, and is special in that iterators are allowed to point to it (but you may not look at the actual value, because it doesn't exist)

For example, in the following code:

char arr[] = {'a', 'b', 'c', 'd'};

char* first = arr
char* last = arr + 4;

first now points to the first element of the array, while last points one past the end of the array. We are allowed to point one past the end of the array (but not two past), but we're not allowed to try to access the element at that position:

// legal, because first points to a member of the array
char firstChar = *first;
// illegal because last points *past* the end of the array
char lastChar = *last;

Our two pointers, first and last together define a range, of all the elements between them.

If it is a half open range, then it contains the element pointed to by first, and all the elements in between, but not the element pointed to by last (which is good, because it doesn't actually point to a valid element)

In C++, all the standard library algorithms operate on such half open ranges. For example, if I want to copy the entire array to some other location dest, I do this:

std::copy(first, last, dest)

A simple for-loop typically follows a similar pattern:

for (int i = 0; i < 4; ++i) {
    // do something with arr[i]
}

This loop goes from 0 to 4, but it excludes the end value, so the range of indices covered is half-open, specifically [0, 4)

One-sided form of the half-open range operator

Your operator is not a right operator:

var d = 0<.. /// Swift doesn't have this operator

If you want that you need more then 0 then use below:

var d = 1...
var d = 2...
var d = 3...

For more detail, You can check this link: https://docs.swift.org/swift-book/LanguageGuide/BasicOperators.html

Representing intervals or ranges?

I was hoping someone would give me a link to a nice paper that E.W. Dijkstra wrote on the topic. I managed to plug just the right search terms into Google, and found the link I was looking for. The paper is "Why numbering should start at 0" and also covers why ranges should be represented with a half open interval [begin, end).

The basic argument has several pieces:

1. Direct experience with a programming environment (the programming language Mesa at Xerox PARC) that had support for all 4 different choices resulted in people standardizing on [start, end) because of frequent errors made with all the other choices.
2. If you have an interval that starts at 0, having the start be -1 or something similar is just awkward and broken. This argues strongly for the interval starting at begin (i.e. all the begin <= x choices).
3. The math for determining the interval size, for computing the start of the next adjacent interval, and a whole bunch of other similar things just works out nicely if end is one past start. For example, the size is end - begin. And end is the begin of the next adjacent interval. There are fewer chances for off-by-one errors in your calculations.
   
   • On a related note, the empty range is [begin, begin), and very obvious. It would have to be the rather awkward [begin, begin - 1] if it were closed on both sides. This is especially awkward of your range begins at 0.

Why boost uniform_int_distribution takes a closed range (instead of a half-open range, following common C++ usage)?

Only with closed ranges, you can create a uniform_int_distribution, that produces any integer:

uniform_int_distribution<int> dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());

If this would be a half-open range, you could never reach std::numeric_limits<int>::max(), but only std::numeric_limits<int>::max() - 1.

It's the same situation for std::uniform_int_distribution in the C++11 standard library.

Half-open ranges for iterators are common, because one can easily express empty ranges (by setting begin == end). This doesn't make sense for distributions.

---

Reference: Stephan T. Lavavej mentions this exact reason in his talk "rand() Considered Harmful" at Going Native 2013 (around minute 14). This talk is about C++11 <random>, but of course the same reasoning applies to boost as well.

Swift Range behaving like NSRange and not including endIndex

Range objects Range<T> in Swift are, by default, presented as a half-open interval [start,end), i.e. start..<end (see HalfOpenInterval IntervalType).

You can see this if your print your range variable

let range = Range<Int>(start: 0, end: 2)
print(range) // 0..<2

Also, as Leo Dabus pointed out below (thanks!), you can simplify the declaration of Range<Int> by using the half-open range operator ..< directly:

let range = 0..<2
print(range) // 0..<2  (naturally)

Likewise, you can declare Range<Int> ranges using the closed range operator ...

let range = 0...1
print(range) // 0..<2 

And we see, interestingly (in context of the question), that this again verifies that the default representation of Ranges are by means of the half-open operator.

---

That the half-open interval is default for Range is written somewhat implicitly, in text, in the language reference for range:

Like other collections, a range containing one element has an endIndex
that is the successor of its startIndex; and an empty range has
startIndex == endIndex.

Range conforms, however, to CollectionType protocol. In the language reference to the latter, it's stated clearly that the startIndex and endIndex defines a half-open interval:

The sequence view of the elements is identical to the collection view.
In other words, the following code binds the same series of values to
x as does for x in self {}:

for i in startIndex..<endIndex {
    let x = self[i]
}

To wrap it up; Range is defined as half-open interval (startIndex ..< endIndex), even if it's somewhat obscure to find in the docs.

---

See also

• Swift Language Guide - Basic Operators - Range Operators

Swift includes two range operators, which are shortcuts for expressing
a range of values.

...

The closed range operator (a...b) defines a range that runs from a to
b, and includes the values a and b. The value of a must not be greater
than b.

...

The half-open range operator (a..< b) defines a range that runs from a
to b, but does not include b. It is said to be half-open because it
contains its first value, but not its final value.

Why are Standard iterator ranges [begin, end) instead of [begin, end]?

The best argument easily is the one made by Dijkstra himself:

• You want the size of the range to be a simple difference end − begin;

• including the lower bound is more "natural" when sequences degenerate to empty ones, and also because the alternative (excluding the lower bound) would require the existence of a "one-before-the-beginning" sentinel value.

You still need to justify why you start counting at zero rather than one, but that wasn't part of your question.

The wisdom behind the [begin, end) convention pays off time and again when you have any sort of algorithm that deals with multiple nested or iterated calls to range-based constructions, which chain naturally. By contrast, using a doubly-closed range would incur off-by-ones and extremely unpleasant and noisy code. For example, consider a partition [n₀, n₁)[n₁, n₂)[n₂,n₃). Another example is the standard iteration loop for (it = begin; it != end; ++it), which runs end - begin times. The corresponding code would be much less readable if both ends were inclusive – and imagine how you'd handle empty ranges.

Finally, we can also make a nice argument why counting should start at zero: With the half-open convention for ranges that we just established, if you are given a range of N elements (say to enumerate the members of an array), then 0 is the natural "beginning" so that you can write the range as [0, N), without any awkward offsets or corrections.

In a nutshell: the fact that we don't see the number 1 everywhere in range-based algorithms is a direct consequence of, and motivation for, the [begin, end) convention.

What is the past-the-end iterator in STL C++?

The functions begin() and end() define a half open range([begin, end)), which means:

The range includes first element but excludes the last element. Hence, the name past the end.

The advantage of an half open range is:

1. It avoids special handling for empty ranges. For empty ranges, begin() is equal to
   end() .

2. It makes the end criterion simple for loops that iterate over the elements: The loops simply
   continue as long as end() is not reached

---

Related Topics