C++ Iterators: Best practice to represent end of range - Last or Beyond-last?

Question

I am writing a library which deals a lot with sub-sequences of ordered containers.

So for example I have a container (1,2,3,4,5,6) and a user wants to access (3,4,5).

I am providing the subsequence by a pair of iterators, pointing to its first and last element respectively, i.e. 3 and 5.

Since the library is written in C++ and AFAIK the std convention is to have the last iterator point beyond the last element, I am wondering if what I am doing is good practice or wether I should return a pair of iterators, pointing to the first and beyond last element respectively, i.e. 3 and 6?

---

Also from a programming perspective, it complicates things when using std functionality, for example to count the number of elements, I have to do:

int elementCnt = std::distance(startIt, endIt) + 1;

Answer 1

Follow the standard - the end is the iterator past the one you want. This allows you to use all the standard algorithms and containers without problem.

It also means your users will be able to write the code they always have (eg for (x=startIt; x != endIt; x++) and this will work as expected.

If you change this behaviour and set the last iterator to the last element, all that goes out of the window and you might as well use a different nomenclature than iterators as you're effectively changing the way everyone will expect them to work.

Answer 2

With your convention:

• every function in the algorithm library should be used changing the upper bound of the range and it can be quite error prone
• it isn't easy to represent empty sequences (this was Dijkstra's argument in Why Numbering Should Start At Zero).
• you can easily incur in off-by-one errors (e.g. when you take a partition of a collection).

You should stay with half-closed ranges.

Answer 3

You wrote:

The std convention is to have the last iterator point beyond the last element

I think I can help your mental model by giving you two little replies (one section each).

• Don't think of it as beyond-last indexing, think of it as edge-based indexing
• Why edge-based indexing (right-open interval indexing) is nice

Don't think of it as beyond-last indexing, think of it as edge-based indexing

I've substantially simplified and C++ified this section thanks to a very helpful comment by Snowman:

C++ iterators are defined in terms of "which item will it retrieve next" instead of "to which item is it currently pointing?

So, it helps me to think of an iterators as resting not on an item, but on the edge just before it.

For sub-sequences with a start and a stop, instead of numbering the items, I mentally number the edges between the items. 0 is the edge before the first item. The startIt is the edge I start at; the stopIt is the edge I stop at.

The following picture is adapted from An informal introduction to Python.

   item    0   1   2   3   4   5
         +---+---+---+---+---+---+
         | P | y | t | h | o | n |
         +---+---+---+---+---+---+
iterator 0   1   2   3   4   5   6

So startIt = 2 and stopIt = 5 leads to t, h, o.

Why edge-based indexing (right-open interval indexing) is nice

You get some really nice properties:

• number of items in a subsequence: n = stop - start
• To create neighbouring subsequences, stop of one == start of the next.

Examples below. I'm using Python syntax below because I don't know C++. If somebody is willing to translate this section into C++ (Don't bother leaving the Python), I will be very grateful. Anyway, the notation is not important: just read [start:stop] as startIt and stopIt.

This is the container we'll be using

my_container = [ 'a', 'b', 'c', 'd' ]
## edges       ^    ^    ^    ^     ^
##             0    1    2    3     4

Access sub-sequences by slicing like c[start:stop] -- you get everything between edges 1 and 3.

my_container[1:3] == ['b', 'c']

To get a slice of length 3, I make sure stop = start + 3

my_container[1:4] == ['b', 'c', 'd']
# or do stop - start to find out how long the slice is:
4 - 1 == 3  # 3 elements in this slice.

I want one slice to start where the previous slice ends. So, I let the first slice end on edge x, and the second one start on edge x. This way I cleanly split the container in two.

my_container[0:3] == ['a', 'b', 'c']
my_container[3:4] == ['d']

Closing remark

Do read the essay by Edsger W. Dijkstra in manlio's answer. It's less than 700 words, with crystal-clear thinking and equally-clear handwriting (and a link to a html version inside).

Answer 4

The standard library uses one-past-the end pointers for good reason - stick to this pattern. The alternative leaves no good way to describe an empty range.

Also, unless you definitely need something different/special/written here, just use Boost.Range.

Answer 5

You should keep conventions (definitions) used in a programming language.

Example:

#include <iterator>

template< class Iterator>
class Range
{
    public:
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef Iterator iterator;

    Range(const iterator& first, const iterator& last) noexcept
    :   m_first(first), m_last(last)
    {}

    Range(iterator&& first, iterator&& last) noexcept
    :   m_first(std::move(first)), m_last(std::move(last))
    {}

    Range(Range&& other) noexcept
    :   m_first(std::move(other.m_first)),
        m_last(std::move(other.m_last))
    {}

    Range& operator = (Range&& other) noexcept {
        m_first = std::move(other.m_first);
        m_last = std::move(other.m_last);
        return *this;
    }

    iterator begin() const noexcept { return m_first; }
    iterator end() const noexcept { return m_last; }

    private:
    iterator m_first;
    iterator m_last;
};

template<typename T>
inline Range<T> range(T&& first, T&& last) noexcept {
    return Range<T>(std::forward<T>(first), std::forward<T>(last));
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = { 1,2,3,4,5,6 };
    for(auto i : range(v.begin() + 1, v.end() - 1))
        std::cout << i << '\n';
    for(auto i : range(v.end(), v.end()))
        std::cout << i << '\n';
}

Without sticking to the conventions, using libraries (algorithms) or language features (range based for) becomes cumbersome. Even worse, it may lead programmers expecting the common convention into to subtle errors. Also, there is no way to express an empty range if [first, last] are inclusive.