Why is the C++ sort range [first, last)?

Question

Maybe they want to help us, considering that arrays start at 0. So we might think that if we want to sort the first n elements, we go all the way to v[n] but in reality we only go to v[n-1]. So that would explain the fact that the function sorts up to last - 1. But in this case why doesn't it start at first - 1? At the begging we put 1 and we start from v[1] but then we put n and stop at v[n-1]. Why? If it would consider arrays indeed from one, it should include the last element. These are just my - probably stupid - thoughts? This is why I would appreciate a true explanation. Thanks!

Edit: Thank you all so much for your answers. I can see there are many advantages and everything looks more normal in this range. I will try to remember all your examples to make it clear in my mind.

Why not start at zero? You would lose an index value if you didn't use it. — wally, Apr 05 '18 at 18:23
Inclusive lower bounds and exclusive upper bounds are used in C++ throughout, so why make an exception for `sort`? — M Oehm, Apr 05 '18 at 18:26
It is not just sorting, the one past the end principle will follow you almost every where... One past the end has one advantage: You get the end of range always by start + size without having to subtract one - or, the other way round, you get the size by end - start without having to add one. — Aconcagua, Apr 05 '18 at 18:28
If I'm not mistaken, this pattern allows the internal looping to be more efficient by only checking equals rather than less than or equals for the limit. — tinstaafl, Apr 05 '18 at 18:29
I think this question id not asking why array indexes start at zero. Rather, it questions the logic behind standard library's decision to include the lower end, but exclude the upper end of a range. Voting to re-open. — Sergey Kalinichenko, Apr 05 '18 at 18:36
If the range were inclusive, how would you denote an empty range? — Jive Dadson, Apr 05 '18 at 19:14

score 3 · Answer 1 · answered Apr 05 '18 at 18:27

This is done for consistency with iterator semantics in all containers of the Standard C++ Library: begin() is always inclusive, while end() is always exclusive, because it "points" to the position immediately after the end of the container.

This is consistent with the behavior of pointers to array elements:

int data[SIZE];
int *begin = data;      // Inclusive
int *end = &data[SIZE]; // Exclusive

score 0 · Answer 2 · answered Apr 05 '18 at 19:07

Defining ranges this way makes it easy to work with sub-ranges. Here's a silly example:

void apply(int* begin, int* end, void (*f)(int)) {
    if (begin == end)
        ; // nothing to do
    else if (begin + 1 == end)
        f(*begin);
    else {
        int* mid = begin + (end - begin) / 2;
        apply(begin, mid, f);
        apply(mid, end, f);
    }
}

There are two important points here. First, detecting an empty range is simple: begin == end. Second, splitting into two ranges is equally simple. Just generate a middle point mid and use it as the end of each range: [begin, mid) and [mid, end) are two ranges that cover all the elements in the first range.

Now try writing code that does the same thing but uses either double-inclusive or double-exclusive ranges. Contrast and compare.

score 0 · Answer 3 · answered Apr 05 '18 at 19:19

Why is the C++ sort range [first, last)?

This is true for all iterator ranges, so I guess you're asking why are iterator ranges represented as [first, last) in general.

To answer (or rather, respond to) the question: Why not? Do you think that there is a better alternative? What is that alternative?

Let's assume that you would like to represent a range as [first, last]. This is how iterators would need to be treated:

Represent range with length 1. Let it be iterator:

representation - how to treat
[first, last)  - it, it + 1
[first, last]  - it, it

[first, last] has a more compact representation for single value. I can see why this would seem nice. But + 1 has a clear connection to the length of the range, which is nice too.

Represent range of length n:

[first, last)  - begin, begin + n
[first, last]  - begin, begin + n - 1

Here's where the connection to the length shows its greatness. [first, last) is simpler.

Represent empty range:

[first, last)  - it, it
[first, last]  - it + 1, it

This is really a big problem. [first, last] needs two different iterator values to represent an empty range. Consider a vector for example. You would need to use iterator to before first value, and iterator to after last value to represent it (since there are no values to point to).

Why is the C++ sort range [first, last)?

3 Answers3