Half-open ranges

Why this matters

Most loops walk over a range. A range is a run of positions in a list, such as the third to the seventh item, or the rows of a table from row 10 up to row 20. Beginners often get the count wrong by one. The loop runs one time too many or one time too few, or a value is counted twice where two parts meet. These bugs are called off-by-one errors, because the answer is off by exactly one.

A half-open range is a way of writing a range so that most off-by-one errors cannot happen. Professional C++ code uses this style for most ranges. The begin() and end() pairs in the standard library, which you used with std::sort, follow the same rule.

This lesson covers only how to write the two ends of a range and how to use them. Loop invariants, which explain why a loop stays correct, are covered in the lesson on loop invariants. Sentinel loops, which stop on a special value, are covered in the sentinel lesson.

Two ways to write the same range

A position is the number of a slot in a list. The first slot is position 0, the next is position 1, and so on. C++ counts vector and array positions from zero.

Take the list of eight names from the first example:

Ada, Ben, Chen, Dara, Eli, Fay, Gus, Hana

Ada is at position 0 and Hana is at position 7. There are two common ways to name the three positions that hold Chen, Dara and Eli, which are positions 2, 3 and 4.

• A closed range, written [2, 4], includes both ends. The end position is still part of the range.
• A half-open range, written [2, 5), includes the start and leaves out the end. The square bracket on the left means "include this". The round bracket on the right means "stop before this".

The table compares the two.

With a closed range, the count needs a "plus one" to be right. With a half-open range, the count is just the end minus the start. That is the whole advantage. The formula end - start is right for every half-open range, including the empty one where start and end are equal. Python's range(2, 5) and slices such as names[2:5] use the same rule, so the habit carries over to other languages.

In C++, a half-open range becomes a loop with the condition i < end. The loop body runs for every position from the start up to the end, but not for the end itself:

for (int i = start; i < end; ++i) {
    // i takes the values start, start + 1, ..., end - 1
}

The operator ++i adds one to i. The condition uses <, not <=. Most of the mistakes in this lesson come from using <= where < was meant, or the other way round.

First example: the names in a range

The first program prints the names in the half-open range [2, 5). It then splits the whole list into chunks, and it shows the count for an empty range. It needs no input.

The output is:

length = 3
  position 2: Chen
  position 3: Dara
  position 4: Eli
chunk [0, 3) has 3 names: Ada Ben Chen
chunk [3, 6) has 3 names: Dara Eli Fay
chunk [6, 8) has 2 names: Gus Hana
closed [2, 4] has 3 items
half-open [2, 5) has 3 items
empty [4, 4) has 0 items

The first block shows end - start giving the length, and the loop visiting exactly positions 2, 3 and 4. The last two lines show that the closed version needs + 1 and the half-open version does not.

Splitting a list with no gaps and no overlaps

The chunk loop in the example is where half-open ranges pay off. The chunks are [0, 3), [3, 6) and [6, 8). Each chunk ends exactly where the next one starts. Position 3 belongs to the second chunk only. Position 6 belongs to the third chunk only. Nothing is missed and nothing is repeated.

Try the same split with closed ranges. The chunks become [0, 2], [3, 5] and [6, 7]. Now the next start is the previous end plus one. That extra step is easy to get wrong. If you write [3, 5] and then [5, 7], the position 5 is in both chunks, and the list is counted twice in that place.

The loop uses two lines to make the chunks:

• lo += 3 moves the start of the next chunk to the position after the last one.
• hi = min(lo + 3, n) sets the end. The min function from <algorithm> returns the smaller of two values. It stops the last chunk at the size of the list, n. The size is one past the last position, so the last chunk is half-open too. Its end is n, not n - 1.

A half-open range that is empty needs no special case. The range [4, 4) has 4 - 4 positions, which is zero. A loop for (int i = 4; i < 4; ++i) never runs. You do not need an if to check for an empty range first.

A harder example: finding a value in a sorted list

The second program does a binary search. A binary search looks for a value in a sorted list by checking the middle, then throwing away the half that cannot hold the answer. Each check cuts the range in half, so a list of a million values needs about 20 checks.

This program finds the first position whose value is at least a target. In the list {2, 4, 4, 4, 7, 9, 12}, the target 4 is first found at position 1. The target 5 has no exact match, but position 4 holds 7, which is the first value at least 5.

The search keeps the answer inside a half-open range [lo, hi). The variable hi starts at the size of the list, not at the size minus one, because the range that covers the whole list ends one past the last position. Each step checks the middle position mid:

• If v[mid] is smaller than the target, the answer is after mid, so lo becomes mid + 1.
• Otherwise mid is big enough, so the answer is mid or somewhere before it. The end moves to mid, which is not included, so hi becomes mid.

When lo equals hi, the range is empty and lo is the answer. The answer can be size, which means that no value is at least as big as the target.

The output is:

target 1: mine 0, std::lower_bound 0
target 4: mine 1, std::lower_bound 1
target 5: mine 4, std::lower_bound 4
target 12: mine 6, std::lower_bound 6
target 13: mine 7, std::lower_bound 7

The target 13 is bigger than every value, so both versions return 7, the size of the list. The standard function std::lower_bound uses the same rule. It takes v.begin() and v.end(), which is a half-open range.

The formula lo + (hi - lo) / 2 is used instead of (lo + hi) / 2. Both give the middle. The first form cannot overflow when lo and hi are very large, because it never adds two big numbers together.

Because mid is always less than hi, and hi is at most the size, the program never reads v[size]. A closed range would need an extra check for that case.

Overlapping time ranges

Half-open ranges also answer a common question in calendars: do two events overlap? Think of a meeting from 9 to 10 and a meeting from 10 to 11. The first one ends at 10 o'clock, and the second one starts at 10 o'clock. A person can go from one to the other without waiting. The two meetings do not overlap.

In half-open form, the first meeting is [9, 10) and the second is [10, 11). The two ranges overlap when each one starts before the other one ends. For the pair above, the test is 9 < 11 && 10 < 10, which is false. The second part is false because 10 is not less than 10.

The third program checks every pair of meetings and adds up their lengths.

The output is:

overlap: meeting 1 and meeting 2
sum of meeting lengths = 5
touching meetings, half-open rule: 0
touching meetings, closed rule:    1

Meeting 1 is [10, 11) and meeting 2 is [10, 12). They share the hour from 10 to 11, so the program reports an overlap. Meeting 0 is [9, 10) and it touches meeting 1 at 10, but it does not overlap, so the program reports nothing for that pair.

The sum of the lengths is 5. That number is not the busy time of the day. The hour from 10 to 11 is counted once for meeting 1 and once for meeting 2. The busy time, with that hour counted once, is 4 hours. Adding lengths is correct only when the ranges do not overlap. The overlap check is what tells you when it is not.

The closed version prints 1 for the touching pair, which says the two meetings clash. A calendar that used closed ranges would refuse a meeting that starts the moment another one ends.

Writing a function that takes a range

When you write a function that works on part of a list, take a start and an end as parameters and use the half-open rule. Put the rule in a comment, so the next reader knows what the two numbers mean.

The function below sums the values at positions [start, end). It uses std::accumulate from <numeric>. That function takes two iterators, which are objects that point at positions in a list, and it adds up the values from the first one up to, but not including, the second. The iterators come from v.begin() + start and v.begin() + end, so the library follows the same rule as the loops above.

The function also uses assert. An assert is a check that stops the program with a message when its condition is false. It is a way to catch a bad call early, at the place where the bad numbers were passed in.

The output is:

[0, 6) sum = 105
[1, 4) sum = 45
[3, 3) sum = 0
[2, 3) sum = 15

The range [0, 6) covers the whole vector, so its end is v.size(). The empty range [3, 3) gives 0, with no special case in the code. The range [1, 4) adds positions 1, 2 and 3, which are 10, 15 and 20.

Passing a range to a library function

Many library functions take a start and a length, and some take a start and an end. You must check which one a function wants. std::string::substr takes a start position and a length. It does not take an end.

To get the half-open range [2, 5) from a string, the length is 5 - 2, which is 3. The mistake is to pass 5 as the second argument. The program below does both calls on the word half-open. The letters are at positions 0 to 8: h, a, l, f, minus, o, p, e, n.

The output is:

substr(2, 3) = lf-
substr(2, 5) = lf-op

The first call gives the three letters at positions 2, 3 and 4. The second call gives five letters, which runs past the range.

Common mistakes

Using <= with the end

The most common mistake is writing <= where < belongs. The loop below checks each position of a vector of three numbers. It goes one position past the end, which is position 3.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> v = {10, 20, 30};
    for (size_t i = 0; i <= v.size(); ++i) {   // wrong: should be <
        cout << v.at(i) << "\n";
    }
    return 0;
}

The at function checks the position before it reads the value. If the position is bad, the program stops with this message:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)

The message says that the position asked for, __n, is 3, and the vector has size 3. The valid positions are 0, 1 and 2. In this run, the lines 10, 20 and 30 did not appear before the message. The next lesson explains why output can go missing when a program stops early.

If you use v[i] instead of v.at(i), C++ does not check the position. The program may print a wrong value, crash later, or appear to work. A bug that does not stop the program is harder to find, so use at while you are learning, and switch to [] only when you are sure the index is valid.

Passing a start that is after the end

If a caller passes start greater than end, the range is backwards and has no valid meaning. The sum_range function above has an assert for that case. Here the call asks for [4, 2):

#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
 
long long sum_range(const vector<int>& v, size_t start, size_t end) {
    assert(start <= end && end <= v.size());
    return accumulate(v.begin() + start, v.begin() + end, 0LL);
}
 
int main() {
    vector<int> v = {5, 10, 15, 20, 25, 30};
    cout << "[4, 2) sum = " << sum_range(v, 4, 2) << "\n" << flush;
    return 0;
}

The program stops with this message, and the file name is the name the file was saved under, here sum_range.cpp:

sum_range: sum_range.cpp:8: long long int sum_range(const std::vector<int>&, size_t, size_t): Assertion `start <= end && end <= v.size()' failed.

The message names the line where the check failed. Without the check, accumulate would start after its end, so it would never reach the end and would keep reading past the vector. That is undefined behaviour: the program may crash or print a wrong number. Compiling with -DNDEBUG removes asserts, so the check is meant for development and testing.

Using unsigned numbers for lengths

size_t is an unsigned type. It holds only zero and positive numbers. When a subtraction would go below zero, it wraps around to a huge number. The program below uses an end that is smaller than its start.

#include <cstddef>
#include <iostream>
using namespace std;
 
int main() {
    size_t start = 5;
    size_t end = 2;
    cout << "end - start = " << end - start << "\n";
    return 0;
}

The output on a 64-bit system is:

end - start = 18446744073709551613

That number is 2 to the power of 64, minus 3. A loop that uses this as a length would try to run for that many steps. Use int or long long for lengths when a range might be backwards, or check that start <= end before you subtract.

Mixing the two styles

Suppose you want the names at positions 2, 3 and 4, and you write the loop as a closed range but with a half-open condition:

for (int i = 2; i < 4; ++i) {   // prints positions 2 and 3 only
    cout << names[i] << "\n";
}

This loop prints Chen and Dara, and it misses Eli. The end 4 is treated as excluded, so position 4 is not visited. Decide which style you are using, then write the condition to match. For a closed range [2, 4], the condition is i <= 4. For the half-open range [2, 5), the condition is i < 5.

Passing the end where a length is wanted

The substr example above shows the mistake. A function that asks for a length will take the number you pass as the count of items. Read the function's description before you call it, and compute end - start when the function wants a length.

Starting the search range at the last position

The binary search above starts hi at the size. A common error is to copy the closed-range habit and start at the last position, size - 1, while keeping the half-open loop condition. The program below does that.

The output is:

target 1: 0
target 4: 1
target 5: 4
target 12: 6
target 13: 6

The answer for target 13 should be 7, the size, because no value is that big. The program says 6, which is the position of 12. That is a wrong answer with no error message. The fix is to start hi at v.size(), as the working version does.

Practice

Exercise 1. How many positions are in the range [3, 9)? How many are in [5, 5)?

Show the answer

The range [3, 9) has 9 - 3 = 6 positions, which are 3, 4, 5, 6, 7 and 8. The range [5, 5) has 5 - 5 = 0 positions.

Exercise 2. A vector v holds ten numbers. Write a loop that prints the values at positions 4, 5 and 6, using the half-open range [4, 7).

Show the answer

Use the condition i < 7:

for (size_t i = 4; i < 7; ++i) {
    cout << v[i] << "\n";
}

Exercise 3. A list has 10 items. You want to process them in groups of 4. Write each group as a half-open range.

Show the answer

The groups are [0, 4), [4, 8) and [8, 10). The last group has 10 - 8 = 2 items, so its end is the size of the list, not 12.

Exercise 4. Two bookings are [13, 15) and [14, 16). Do they overlap? What about [15, 16) and [13, 15)?

Show the answer

The first pair overlaps. The check 13 < 16 && 14 < 15 is true, and the two bookings share the hour 14. The second pair does not overlap. The check 15 < 15 && 13 < 16 is false, because 15 is not less than 15.

Exercise 5. The word is interval, with letters at positions 0 to 7: i, n, t, e, r, v, a, l. What does substr(2, 3) return, and which half-open range does that call describe?

Show the answer

It returns ter. The call describes the half-open range [2, 5), because the length 3 starts at position 2 and ends before position 5.

Summary

• A half-open range [start, end) includes start and leaves out end.
• The number of positions in the range is always end - start.
• Consecutive ranges such as [0, 3) and [3, 6) cover every position once, with no gap and no overlap.
• Use i < end in the loop condition, not i <= end.
• Two half-open ranges overlap only when each one starts before the other one ends.
• Check whether a library function wants an end or a length before you call it.