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

Question

Hi!

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

It is simple. To avoid going beyond .end() simply avoid going beyond .end(). The situation is no different as in avoiding to use NULL pointer etc. Structure your code so that it never happens. E.g. use loops that use conditions like it != v.end() etc. Some popular standard library implementations detects these errors and let you know but you should not rely on it, only use it during testing/debugging.

Answer 2

Distance can't do this. When your container doesn't offer random access, it tries to reach end by advancing start, which will cause havoc when start overtook last.

You have to start from a valid starting point (i.e. by advancing start you can reach last) and check distance before each advance and only advance by an X<=(distance(first,last) in order not to overtake last.

Answer 3

I think you're trying to solve the wrong problem here.

Don't use advance in a way that could result in going past end. You would never use increment (a special form of advance) when your current iterator is pointing to end, so similarly you should never use advance unless your code already knows there are enough remaining elements in the container. If you aren't sure, you need to increment one at a time and check for end on each item. advance doesn't (and can't) do any checking for you as it would be a performance hit for code that doesn't need that functionality.

Instead, examine your code and figure out WHY a call to advance could cause it to run off the end of your container, and fix that problem with your code instead.

A little more context might give us a better chance to help.

Answer 4

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 5

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.

Answer 6

For one thing you could also write an iterator wrapper that stores the end iterator and checks critical operations.

For example using boost's iterator_facade for brevity and not checking for underflows.

#include <boost/iterator/iterator_facade.hpp>
#include <iterator>
#include <stdexcept>

template <class Iter>
class checked_iterator:
    public boost::iterator_facade<
        checked_iterator<Iter>,
        typename std::iterator_traits<Iter>::value_type,
        typename std::iterator_traits<Iter>::iterator_category
    >
{
    Iter it, end;
public:
    checked_iterator(Iter it, Iter end): it(it), end(end) {} 
    void increment() 
    { 
        if (it == end) { throw std::range_error("checked_iterator: increment beyond end"); }
        ++it;
    }
    void decrement()
    {
        //TODO: this is not checked
        --it;
    }
    bool equal(const checked_iterator& other) const
    {
        return it == other.it;
    }
    typename std::iterator_traits<Iter>::reference dereference() const 
    {
        if (it == end) { throw std::range_error("checked_iterator: dereference end"); }
        return *it;
    }
    void advance(typename std::iterator_traits<Iter>::difference_type n)
    {
        //TODO: not checked for underflow
        if (std::distance(it, end) < n) { throw std::range_error("checked_iterator: advance beyond end"); }
        it += n;
    }
    typename std::iterator_traits<Iter>::difference_type distance_to(const checked_iterator& other) const
    {
        return other.it - it;
    }
    Iter base() const { return it; }
};

//create checked_iterators from containers, could be overloaded for arrays
template <class Container>
checked_iterator<typename Container::iterator> checked_begin(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_begin(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::iterator> checked_end(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.end(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_end(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.end(), c.end());
}

Example test code:

#include <vector>
#include <list>
#include <iostream>
int main()
{
    typedef std::list<int> Container;
    try {
        Container v(10);
        checked_iterator<Container::iterator> it = checked_begin(v);
        std::advance(it, 6);
        std::cout << *it << '\n';
        std::advance(it, 4);
        std::cout << *it << '\n';
        const Container& r = v;
        checked_iterator<Container::const_iterator> cit = checked_begin(r);
        std::advance(cit, 11);
    }
    catch (const std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

---

As to implementing a safe_advance function, this could also distinguish between random access iterators and others, like std::advance for efficiency reasons:

#include <iterator>
#include <stdexcept>

namespace detail
{
    template <class Iter>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        std::random_access_iterator_tag
        )
    {
        if (end - it < n) throw std::range_error("advance beyond end (ra)");
        it += n;
    }

    template <class Iter, class Tag>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        Tag
        )
    {
        for (typename std::iterator_traits<Iter>::difference_type i = 0; i != n; ++i) {
            if (it == end) throw std::range_error("advance beyond end");
            ++it;
        }
    }
}

template <class Iter>
void safe_advance(Iter& it, Iter end, typename std::iterator_traits<Iter>::difference_type n)
{
    detail::safe_advance_aux(it, end, n, typename std::iterator_traits<Iter>::iterator_category());
}