Удаление элементов из списка std::list в цикле Опции

[AD]

Вот тестовый код:

#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    std::list<int> my_list;
    my_list.push_back(3);
    my_list.push_back(2);
    my_list.push_back(3);
    my_list.push_back(4);
    my_list.push_back(5);
    my_list.push_back(3);
    my_list.push_back(7);

    int n = 0;

    cout << "Before removing:\n";
    for(list<int>::iterator i=my_list.begin(); i!=my_list.end(); ++i, ++n)
    {
        cout << "list[" << n + 1 << "] " << *i << endl;
    }

    int j = 0;
    for(list<int>::reverse_iterator i=my_list.rbegin(); i!=my_list.rend();)
    {
        if(*i == 3)
        {
            cout << "iteration " << j + 1 << endl;
            ++i;
            my_list.erase(i.base());
            ++j;
        }
        else
            ++i;
    }

    cout << "After removing:\n";
    n = 0;
    for(list<int>::iterator i=my_list.begin(); i!=my_list.end(); ++i, ++n)
    {
        cout << "list[" << n + 1 << "] " << *i << endl;
    }
}

Интересен он следующим. Если заменить первый элемент на неудаляемый (например push_back(1)), то программа нормально выполняется. Если же тестировать указанную версию, то варианты - разные. На моей машине с Ubuntu g++ 4.6.1 он падает. На машине другого форумчанина он тоже падает, как в MSVC, так и в g++ 4.7.1, а вот у третьего форумчанина с g++ 4.6.3 этот код не падает. Что же это? Сразу говорю, что берется старый стандарт, т.е. не 2011. Понятно, что невалидный итератор, но почему же тогда иногда работает?

[D_K]

Должно работать.
Работает не только у меня, но и у ideone.com: http://ideone.com/8kpis

[AD]

Должно работать.

Должно, но не работает!

Мда... Опишу вариант, в котором оно будет работать:

#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    list<int> my_list;
    my_list.push_back(3);
    my_list.push_back(2);
    my_list.push_back(3);
    my_list.push_back(4);
    my_list.push_back(5);
    my_list.push_back(3);
    my_list.push_back(7);

    int n = 0;

    cout << "Before removing:\n";
    for(list<int>::iterator i=my_list.begin(); i!=my_list.end(); ++i, ++n)
    {
        cout << "list[" << n + 1 << "] " << *i << endl;
    }

    list<int>::reverse_iterator r_end(my_list.rend());
    int j = 0;
    for(list<int>::reverse_iterator i=my_list.rbegin(); i!=r_end;)
    {
        if(*i == 3)
        {
            cout << "iteration " << j + 1 << endl;
            ++i;
            my_list.erase(i.base());
            ++j;
        }
        else
            ++i;
    }

    cout << "After removing:\n";
    n = 0;
    for(list<int>::iterator i=my_list.begin(); i!=my_list.end(); ++i, ++n)
    {
        cout << "list[" << n + 1 << "] " << *i << endl;
    }
}

Разница в коде лишь в том, что итератор окончания вынесен за цикл:

list<int>::reverse_iterator r_end(my_list.rend());
//....
    for(list<int>::reverse_iterator i=my_list.rbegin(); i!=r_end;)

[D_K]

Ну вот.
Видимо дело в том, что при удалении первого элемента меняется мнимый элемент "перед первым", т.е. rend().
Допустим мы указываем reverse_iterator'ом на элемент перед rend(). Далее мы инкрементируем итератор(переходим на rend()). Вызываем base() - получаем итератор на первый элемент, удаляем его, после чего rend() в списке начинает ссылаться на что-то другое, чем ссылался ранее, но наш-то итератор продолжает указывать на предыдущий rend...
Теперь надо выяснить, регламентирует ли это стандарт.

[Влад]

Код из сообщения #3 успешно отрабатывает в GCC 4.7.1 и валится в MSVC++ 2010 (конкретно, валится тут: for(list<int>::reverse_iterator i=my_list.rbegin(); i!=r_end; ) на вызове operator != ), - причем, валится после первой же итерации.....

Сообщение отредактировал Влад - 18.10.2012, 16:05

[D_K]

На самом деле через reverse_iterator'ы нельзя удалять таким способом, т.к. по стандарту они работают с обычным итератором, который указывает на предыдущий(с точки зрения revers'а) элемент. А мы как раз его и удаляем. Соответственно reverse_iterator содержит ссылку на невалидный итератор.

[Влад]

Гм. Не подкинешь ссылочку на соответствующий пункт? Потому что я пока не нашел.... :-(
У меня пока складывается впечатление, что это конкретная реализация содержит "просто итератор", который указывает на предыдущий (с точки зрения revers'а) элемент, и вот этот-то просто итератор - да, становится невалидным. Поэтому и падает.

Интересно, что у Мейерса в Совете 28 приведен именно такой способ удаления элемента - с использованием (++ri).base().

[D_K]

Я исхожу из описания std::reverse_iterator(24.4.1 в старом стандарте), т.к. в описании std::list явно указано typedef std::reverse_iterator<iterator> reverse_iterator

Интересно, что у Мейерса в Совете 28 приведен именно такой способ удаления элемента - с использованием (++ri).base().

Ну если ты потом не используешь ri, то все хорошо

[Iron Bug]

юзать i = my_list.erase(i) или my_list.erase(i++).
прочие варианты будут давать неверные указатели.

[D_K]

Ну почему же. Должно работать и так:

 
...
   for(list<int>::reverse_iterator i=my_list.rbegin(); i!=my_list.rend();)
    {
        if(*i == 3)
        {
            cout << "iteration " << j + 1 << endl;
            list<int>::reverse_iterator rm = i;
            my_list.erase((++rm).base());
            ++i;
            ++j;
        }
        else
            ++i;
    }
...