6

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;
  • How would you represent the end of an empty range...? – Mehrdad Jul 23 '15 at 4:13
35

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.

  • Thank you for your convincing argument. The only worries I have is that accessing the first and the last element of a subsequence is a common operation, and when pointing beyond last, how should one provide a clean way of accessing the last element via the iterator? I only see --endIt; – 1v0 Jul 22 '15 at 20:19
  • 2
    @1v0 Using a reverse iterator? (rbegin and rend) – Williham Totland Jul 22 '15 at 23:07
  • @1v0 --endIt is fine. If you are in a situation where you don't want to use the -- operator (which permanently changes the iterator), you can also use std::prev(endIt) which will return an iterator to the last element. – Cort Ammon - Reinstate Monica Jul 23 '15 at 2:29
  • 1
    @1v0: Some of the STL containers provide a back() method that returns a direct reference to the last element in the set. If you need something that returns an iterator, add a method whose name doesn't conflict with method names in existing containers (e.g., last() or final()) but returns prev(endIt). – Blrfl Jul 23 '15 at 11:50
9

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.

5

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).

  • 1
    In other words, C++ iterators are defined in terms of "which item will it retrieve next" instead of "to which item is it currently pointing?" Good answer regardless. – user22815 Jul 23 '15 at 10:21
  • Thanks! I rewrote the first section based on your comment, and it's a lot clearer and a lot more C++-like now. – Esteis Jul 23 '15 at 10:59
0

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.