What happens if you increment an iterator that is equal to the end iterator of an STL container

Question

What if I increment an iterator by 2 when it points onto the last element of a vector? In this question asking how to adjust the iterator to an STL container by 2 elements two different approaches are offered:

• either use a form of arithmetic operator - +=2 or ++ twice
• or use std::advance()

I've tested both of them with VC++ 7 for the edge case when the iterator points onto the last element of the STL container or beyond:

vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();
advance( it, 2 );
bool isAtEnd = it == vec.end(); // true
it++; // or advance( it, 1 ); - doesn't matter
isAtEnd = it == vec.end(); //false
it = vec.begin();
advance( it, 3 );
isAtEnd = it == vec.end(); // false

I've seen may times an advise to compare against vector::end() when traversing the vector and other containers:

for( vector<int>::iterator it = vec.begin(); it != vec.end(); it++ ) {
    //manipulate the element through the iterator here
}

Obviously if the iterator is advanced past the last element inside the loop the comparison in the for-loop statement will evaluate to false and the loop will happily continue into undefined behaviour.

Do I get it right that if I ever use advance() or any kind of increment operation on an iterator and make it point past the container's end I will be unable to detect this situation? If so, what is the best practice - not to use such advancements?

Answer 1

Following is the quote from Nicolai Josuttis book:

Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined

In other words, the responsibility of maintaining the iterator within the range lies totally with the caller.

Answer 2

Perhaps you should have something like this:

template <typename Itr>
Itr safe_advance(Itr i, Itr end, size_t delta)
{
    while(i != end && delta--)
        i++;
    return i;
}

You can overload this for when iterator_category<Itr> is random_access_iterator to do something like the following:

return (delta > end - i)? end : i + delta;

Answer 3

You could use the "distance" function between your iterator (it) and the iterator at vec.begin() and compare it with the vector's size (obtained by size()).

In that case your for loop would look like this:

for (vector<int>::iterator it = vec.begin(); distance(vec.begin(), it) < vec.size(); ++it)
{
     // Possibly advance n times here.
}

Answer 4

The code that Marijn suggests is just slightly wrong (as curiousguy pointed out).

The correct version of the last line is:

bool isPastEnd = it >= vec.end();

Answer 5

container.end() -- the element just past the end -- is the only defined exterior value.

A checked iterator will fault on what is essentially an out-of-range access, but that isn't terribly helpful (especially as the default behaviour is to end the program).

I think the best practice is "don't do that" -- either check every value of the iterator (preferably in something wrapped as a filter), and only operate on interesting entries, or use the index explicitly with

for(int i = 0; i < vec.size(); i+=2) {...}

Answer 6

You could also do more comparisons in your for statement:

for( vector<int>::iterator it = vec.begin(); it != vec.end() && it+1 != vec.end(); it+=2 ) {
    //manipulate the element through the iterator here
}

I don't know how this would perform vs Kostas's suggestion, but it feels like it would be better for a small increment. Of course it would be pretty unmaintainable for a large increment since you need a check for each, but it is another option.

I would definitely avoid it if at all possible. If you really need to increment by 2 values at a time, then consider having a vector of std::pair or a vector of a struct with 2 elements.

Answer 7

I suggest you to take a look at Boost.Range.
It might be safer to use.
It will also be in C++0x.

Answer 8

Even though this question is half a year old, it might still be useful to mention the use of comparison operators > and < to check if you iterated past the end (or the start when iterating back) of the container. For example:

vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();

it+=10; //equivalent to advance( it, 10 )
bool isPastEnd = it > vec.end(); //true