How to make sure iterators do not overpass end()?

Question

I have been using advance on some iterators, but I am afraid of a possible leapfrog above end(). I would like to make sure my iterators stay between the bounds, I thought of the distance but it seems it does not return what I would be expecting (non-positive values when iterators overpass end()). How would you make sure there is no leapfrog?

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main () {
  list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);

  list<int>::const_iterator first = mylist.begin();
  const list<int>::const_iterator last = mylist.end();

  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0
  advance(first, 1);
  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0

  return 0;
}

Here is the output:

The distance is: 10
The distance is: 0
The distance is: 10
The distance is: 0

Answer 1

advance() past end() results in undefined behaviour. You are going to have to test as you go per this snippet:

  template <class Iter, class Incr>
  void safe_advance(Iter& curr, const Iter& end, Incr n)
  {
    size_t remaining(std::distance(curr, end));
    if (remaining < n)
    {
      n = remaining;
    }
    std::advance(curr, n);
  }

You need to think about what happens when you don't move the full amount (curr returned as end().

Answer 2

It is inefficient to call distance or advance on anything other than models of RandomAccessIterator: the calls are O(n) where n represents the distance.

Also, the list is not truly a model of Sequence in that its size method is not guaranteed to be constant (or even amortized constant), indeed it could perfectly well be O(n).

Looking at the code (and if you cannot use anything else than a list) there are therefore two possibilities:

• Don't use advance, move one item at a time and check with end at each step.
• Compute the size once and for all at the beginning, then you know how much you can advance before invoking undefined behavior (you can keep a counter on the side, wrap the iterator etc...)

Let's act on this:

// Advance one at a time
// replace calls to advance by this function

typedef list<int>::const_iterator const_iterator;

const_iterator safe_advance(const_iterator it, const_iterator end, size_t n)
{
  for (size_t i = 0; i != n && it != end; ++i) { ++it; }
  return it;
}


// Precompute size
size_t const size = list.size();

size_t remaining = size;
const_iterator begin = list.begin();

size_t ad = std::min(10, remaining);
advance(begin, ad);
remaining -= ad;

ad = std::min(1, remaining);
advance(begin, ad);
remaining -= ad;

It is tedious to keep this count going though...

EDIT:

Addressing David's rightful concerns to generalize the solutions:

// Advance `it` from n, or up to end
// returns the number of steps that could not be performed
template <typename Iterator>
size_t safe_advance(Iterator& it, Iterator const& end, size_t n)
{
  size_t i = 0;
  for (; i != n && it != end; ++i, ++it);
  return n - i;
}

Note that for Bidirectional Iterators, advance is usable with negative distances, however this would require bringing in begin as well and would become really tedious. As such, I much prefer a second method:

template <typename BI>
size_t safe_reverse(BI& it, BI const& begin, size_t n)
{
  for (; n != 0 && it != begin; --n, --it);
  return n;
}

And finally, though I won't do it here, it would be good to specialize the templates for RandomAccessIterator since those operations can be done in O(1) with such ones.