Why STL iterator ranges go [begin, end)

At first sight, it seems strange that STL iterators go [begin, end), including begin but not end in the range, but when you think about it more you realise that this is exactly the way conventional loops work.

STL iteration loop

A typical STL iteration loop goes:

for (it = begin; it != end; ++it) {
    // do something with *it
}

Note that:

  • The iterator end is not part of the range processed
  • After the end of the loop it is equal to end, i.e., one past the end of the range
  • The size of range traversed is endbegin

Now consider the following loops:

Loop over an array with an index

    int numbers[] = {1, 2, 3, 4, 5, 6};
    const size_t n = sizeof(numbers) / sizeof(int);
    int i;
    for (int i = 0; i < n; ++i) {
        std::cout << numbers[i] << "\n";
    }
    std::cout << i << "\n";

Here, our range of indices processed is [0, n).

  • numbers[n] is not part of the range processed
  • After the end of the loop, i is n, i.e., one past the end of the range
  • The size of range traversed is n - 0 = n , i.e., the end – the beginning

Loop over a string


    const char str[] = "The quick brown fox jumps over the lazy dog";
    for (i = 0; str[i] != '\0'; ++i) {
        std::cout << str[i] << "\n";
    }
    for (const char* c = str; c != '\0'; ++c) {
        std::cout << *str << "\n";
    }

A string is defined by [str[0], '\0'), or [*str, '\0')

  • The '\0' character is not part of the string
  • After the end of the loop, the pointer or index points to the '\0'.
  • The size of range traversed is (position of the '\0') – 0 = strlen(str), i.e., the end – the beginning

Loop over an array of pointers with sentinel

    const char* strings[] = {"apples", "pears", "bananas", "cherries", NULL};
    for (i = 0; strings[i] != NULL; ++i) {
        std::cout << strings[i] << "\n";
    }
    for (const char** pc = strings; *pc != NULL ; ++pc) {
        std::cout << *pc << "\n";
    }

Similarly, here the range is [strings[0], NULL), or [*strings, NULL)

  • The NULL is not considered part of the range processed
  • After the end of the loop, the pointer or index points to the NULL
  • The size of range traversed is (position of the NULL) – 0 = the position of the NULL, i.e., the end – the beginning

Hopefully, this has demonstrated that STL iterators have exactly the same semantics as ordinary loop variables.

I’ll leave the last word to E. W. Dijkstra, with his explanation of Why numbering should start at zero.

Related