проблема с std :: advance на std :: sets

Question

Я наткнулся на то, что, как мне кажется, является ошибкой в ​​ алгоритме stl advance .

Когда я продвигаю итератор за пределы контейнера, я получаю противоречивые результаты. Иногда я получаю container.end (), иногда я получаю последний элемент. Я проиллюстрировал это следующим кодом:

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

Какое неожиданное (по мне) поведение я получаю в эксперименте 3 и 5, где вместо 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]$

На веб-сайте sgi (см. Ссылку сверху) приведен следующий пример:

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

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

Я думаю, что утверждение должно применяться к другим типам контейнеров, не так ли?

Чего мне не хватает?

Спасибо!

Answer 1

Нет ошибки в алгоритме продвижения STL.

Неизвестно, что произойдет, если вы продвинетесь дальше конца коллекции.

Неопределенное поведение является распространенным понятием в C / C ++, результаты всегда действительны для неопределенного поведения, потому что ... это неопределенное поведение.

Вероятно, в вашей программе будет ошибка, если вы сделаете что-то, что вызовет неопределенное поведение.

Answer 2

Когда я продвигаю итератор от конца контейнера, ...

... вы получаете неопределенное поведение . Что бы ни случилось тогда, это нормально в соответствии со стандартом C ++. Это может быть намного хуже , чем противоречивые результаты.

Answer 3

Вы продвигаете итератор за конец контейнера. Из документации:

Если n> 0, это эквивалентно выполнению ++ i n раз

У вас нет 100 элементов в контейнере, но вы продвигаете итератор на 100 позиций. Он не остановится, когда достигнет конца контейнера, потому что не знает, где находится конец контейнера.

Answer 4

Что вам не хватает, так это то, что в примере список содержит ровно два элемента. Если вы продвинетесь от начала списка из двух пунктов на 2 шага, вы должны оказаться в конце списка. Это то, что утверждает пример.

Если бы вы продвинулись более чем на два шага, вы оказались бы в неопределенной области поведения, и утверждение больше не имеет никакого смысла.