What is half open range and off the end value

What do these terminologies mean in C++?

1. off the end value

2. half open range - [begin, off_the_end)

I came across them while reading about for loops.

Solution 1:

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)

Solution 2:

These aren't C++ specific terms, they are general maths terms.

[] and () denote whether the range is inclusive/exclusive of the endpoint:

• [ includes the endpoint
• ( excludes the endpoint
• [] = 'Closed', includes both endpoints
• () = 'Open', excludes both endpoints
• [) and (] are both 'half-open', and include only one endpoint

Most C++ for-loops cover a half-open range (you include the first element: e.g for int i=0;, but exclude the final element: i < foo, not i ≤ foo)

Solution 3:

As explained on other answers, half-open range is also a mathematical term and usage of this term in programming context, it is implied that the starting point is included and end point is excluded.

What does it actually mean in the context of programming in C/C++ ? Let's say, you are going to print the elements of an integer array. Speaking for the C language, because that you have no any run-time knowledge for the size of the array, you have two choice. Either you have to provide the size of the array and thus, the function signature will be as below;

void printArray(int * array, int size);

or you have to use the half-open range, which means, you have to provide both begin and end pointer (and function is going to process including the begin, excluding the end) additional to the array itself. And the function signature will be as below;

void printArray(int * array, int * begin, int * end);

To illustrate, here is an example for providing the size of the array;

#include <stdio.h>

void printArray(int * array, int size)
{
    printf("Array: ");

    for(int i = 0; i < size; i++)
        printf("%2d ", array[i]);

    printf("\n");
}

int main()
{
    int array[5] = { 1, 2, 3, 4, 5 };

    printArray(array, 5);

    return 0;
}

In the example above, we have passed two parameters to the printArray function as it is obvious on the function signature, the pointer to the first element of the array (or the array itself), and the size of the array.

However, as I have written above, we can also use the half-opening range in the function signature which can be seen as below;

#include <stdio.h>

void printArray(int * array, int * begin, int * end)
{
    printf("Array: ");

    for(int * index = begin; index != end; index++)
        printf("%2d ", *index);

    printf("\n");
}

int main()
{
    int array[5] = { 1, 2, 3, 4, 5 };

    printArray(array, array, array+5);

    return 0;
}

Both of the code will produce the same output as can be seen below;

Array:  1  2  3  4  5

As you can see, the printArray function prints the function for the range [begin, end). The index which is actually is a pointer to the elements of the integer array, starts from begin, and it includes the begin and the for-loop ends up when index equals to the end pointer, excluding to process the end. This i called half-open range.

Half-open range is the C++ convention.