82

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?

8 Answers 8

72

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.

2
  • 2
    How to check if it is in the range after arithmetic operation?
    – Narek
    Commented Apr 29, 2015 at 14:01
  • 4
    @Narek You can't. Checking after an operation that might exhibit UB is always a losing strategy in C++. Commented Aug 28, 2019 at 7:02
16

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;
7

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.
}
6
  • Does this rely on contiguous storage allocation or will it also work for other containers?
    – sharptooth
    Commented Jun 29, 2009 at 11:43
  • 2
    It more has to do with how operator ++ is implemented for each type of iterator. "distance" counts how many ++ or -- would have to be executed to one iterator in order to reach the other. If I were you I would try it on all the types of container I expect and see what distance gives me.
    – Kostas
    Commented Jun 29, 2009 at 11:57
  • 1
    distance() works on any input, forward, bidirectional or random-access iterator, according to the standard (24.3.4) Commented Jun 29, 2009 at 12:40
  • 2
    distance is optimized for random-access iterators: it's complexity is O(1) as it does not count ++'s, but performs subtraction Commented Jun 30, 2009 at 6:40
  • 2
    @jalf "distance() works on any input iterator": you probably don't want to do that!
    – curiousguy
    Commented Sep 29, 2011 at 21:00
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();
1
  • it > vec.end() can be assumed to always be false. ++vec.end() is undefined behaviour
    – Caleth
    Commented Jan 26, 2018 at 12:25
1

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.

1

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

1

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) {...}
-2

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
2
  • Sorry, that's WRONG. As previously explained, a valid iterator cannot be past the one-past-the-end iterator, that is end().
    – curiousguy
    Commented Sep 29, 2011 at 21:06
  • 2
    This only works because the implementation of std::vector::iterator is actually a raw pointer. With another container the story may be completely different, it may even throw an exception when you try to go past end.
    – Sogartar
    Commented Apr 5, 2013 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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