issue with std::advance on std::sets

Question

I've stumbled upon what I believe is a bug in the stl algorithm advance.

When I'm advancing the iterator off of the end of the container, I get inconsistent results. Sometimes I get container.end(), sometimes I get the last element. I've illustrated this with the following code:

#include <algorithm>
#include <cstdio>
#include <set>

using namespace std;
typedef set<int> tMap;

int main(int argc, char** argv)
{
    tMap::iterator i;
    tMap the_map;

    for (int i=0; i<10; i++)
        the_map.insert(i);

#if EXPERIMENT==1
    i = the_map.begin();
#elif EXPERIMENT==2
    i = the_map.find(4);
#elif EXPERIMENT==3
    i = the_map.find(5);
#elif EXPERIMENT==4
    i = the_map.find(6);
#elif EXPERIMENT==5
    i = the_map.find(9);
#elif EXPERIMENT==6
    i = the_map.find(2000);
#else
    i = the_map.end();
#endif

    advance(i, 100);

    if (i == the_map.end())
        printf("the end\n");
    else
        printf("wuh? %d\n", *i);

    return 0;
}

Which I get the following unexpected (according to me) behavior in experiment 3 and 5 where I get the last element instead of the_map.end().

[tim@saturn advance]$ uname -srvmpio
Linux 2.6.18-1.2798.fc6 #1 SMP Mon Oct 16 14:37:32 EDT 2006 i686 athlon i386 GNU/Linux
[tim@saturn advance]$ g++ --version
g++ (GCC) 4.1.1 20061011 (Red Hat 4.1.1-30)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[tim@saturn advance]$ g++ -DEXPERIMENT=1 advance.cc
[tim@saturn advance]$ ./a.out
the end
[tim@saturn advance]$ g++ -DEXPERIMENT=2 advance.cc
[tim@saturn advance]$ ./a.out
the end
[tim@saturn advance]$ g++ -DEXPERIMENT=3 advance.cc
[tim@saturn advance]$ ./a.out
wuh? 9
[tim@saturn advance]$ g++ -DEXPERIMENT=4 advance.cc
[tim@saturn advance]$ ./a.out
the end
[tim@saturn advance]$ g++ -DEXPERIMENT=5 advance.cc
[tim@saturn advance]$ ./a.out
wuh? 9
[tim@saturn advance]$ g++ -DEXPERIMENT=6 advance.cc
[tim@saturn advance]$ ./a.out
the end
[tim@saturn advance]$ g++ -DEXPERIMENT=7 advance.cc
[tim@saturn advance]$ ./a.out
the end
[tim@saturn advance]$

From the sgi website (see link at top), it has the following example:

list<int> L;
L.push_back(0);
L.push_back(1);

list<int>::iterator i = L.begin();
advance(i, 2);
assert(i == L.end());

I would think that the assertion should apply to other container types, no?

What am I missing?

Thanks!

Answer 1

There is no bug in the STL advance algorithm.

It's undefined what happens if you advance past the end of a collection.

Undefined behavior is a common concept in C/C++, the results are always valid for undefined behavior, because... it is undefined behavior.

You will likely have a bug in your program if you do something that gives undefined behavior.

Answer 2

You are advancing the iterator past the end of the container. From the documentation:

If n > 0 it is equivalent to executing ++i n times

You don't have 100 elements in the container, but you are advancing the iterator 100 positions. It's not going to stop when it hits the end of the container because it doesn't know where the end of the container is.

Answer 3

When I'm advancing the iterator off of the end of the container, ...

... you get undefined behavior. Whatever happens then, is fine according to the C++ standard. That could be much worse than inconsistent results.

Answer 4

What you are missing is that in the example the list contains exactly two elements. If you advance from the beginning of a two-item list by 2 steps, you should be at the end of the list. That's what the example asserts.

If you were to advance by more than two steps, you'd be in the undefined behavior land, and the assertion no longer makes any sense.