std::advance behavior when advancing beyond end of container

Question

What is the behavior of std::advance when you have say:

std::vector<int> foo(10,10);
auto i = foo.begin();
std::advance(i, 20);

What is the value of i? Is it foo.end()?

Michael Burr · Answer 1 · 2011-05-06T20:19:09.527

The standard defines std::advance() in terms of the types of iterator it's being used on (24.3.4 "Iterator operations"):

These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

The requirements for these operations on various iterator types are also outlined in the standard (in Tables 72, 74, 75 and 76):

For an input or forward iterator
```
++r precondition: r is dereferenceable
```

for a bidirectional iterator:

--r precondition: there exists s such that r == ++s

For random access iterators, the +, +=, -, and -= operations are defined in terms of the bidirectional & forward iterator prefix ++ and -- operations, so the same preconditions hold.

So advancing an iterator beyond the 'past-the-end' value (as might be returned by the end() function on containers) or advancing before the first dereferenceable element of an iterator's valid range (as might be returned by begin() on a container) is undefined behavior since you're violating the preconditions of the ++ or -- operation.

Since it's undefined behavior you can't 'expect' anything in particular. But you'll likely crash at some point (hopefully sooner rather than later, so you can fix the bug).

score 9 · Answer 2 · answered May 06 '11 at 20:00

According to the C++ Standard §24.3.4 std::advance(i, 20) has the same effect as for ( int n=0; n < 20; ++n ) ++i; for positive n. From the other side (§24.1.3) if i is past-the-end, then ++i operation is undefined. So the result of std::advance(i, 20) is undefined.

Mahesh · Accepted Answer · 2011-05-06T20:08:14.070

3

You are passing the foo size by advancing to 20th position. Definitely it is not end of the vector. It should invoke undefined behavior on dereferencing, AFAIK.

Edit 1:

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
     std::vector<int> foo(10,10) ;
     std::vector<int>::iterator iter = foo.begin() ;
     std::advance(iter,20);

     std::cout << *iter << "\n" ;

     return 0;
}

Output: 0

If it is the vector's last element, then it should have given 10 on iterator dereferencing. So, it is UB.

IdeOne Results

edited May 06 '11 at 20:08

answered May 06 '11 at 19:43

Mahesh

34,573
20
89
115

6

Your example is incorrect. Even if the iterator were clamped to `end()` it still wouldn't be pointing to anything valid. – Mark Ransom May 06 '11 at 20:07
@Mark Ransom - Instead, I should have said last element in the vector. Modified the terminology and thanks for notifying. – Mahesh May 06 '11 at 20:09
3

Mark's point is that advancing to just past the last element of the vector is well-defined (though you can't dereference that iterator). In other words using your example, if the `advance` line had been: `std::advance(iter,10)`, there wouldn't be UB at that point, though there would be when the `cout` expression was executed. So if `advance()` were specified to somehow 'stick' on `end()` when the iterator reaches that point, your example would still show UB, but not on the call to `advance()`. – Michael Burr May 06 '11 at 23:41

score 2 · Answer 4 · answered May 06 '11 at 19:59

That is probably undefined behavior. The only thing the standard says is:

Since only random access iterators provide + and - operators, the library provides two function templates advance and distance. These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

template <class InputIterator, class Distance> 
void advance(InputIterator& i, Distance n);

Requires: n shall be negative only for bidirectional and random access iterators. Effects: Increments (or decrements for negative n) iterator reference i by n.

score 1 · Answer 5 · edited May 23 '17 at 10:29

From the SGI page for std::advance:

Every iterator between i and i+n (inclusive) is nonsingular.

Therefore i is not foo.end() and dereferencing will result in undefined behavior.

Notes:

See this question for more details about what (non)singular means when referring to iterators.
I know that the SGI page is not the de-facto standard but pretty much all STL implementations follow those guidelines.

std::advance behavior when advancing beyond end of container

5 Answers5