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

#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. Понятно, что невалидный итератор, но почему же тогда иногда работает?

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

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

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

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

Ну вот.
Видимо дело в том, что при удалении первого элемента меняется мнимый элемент "перед первым", т.е. 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 != ), - причем, валится после первой же итерации.....

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

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

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

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



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

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

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

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

а ещё удобнее так

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

    //удаление без предиката
    my_list.remove(3);

    //удаление с предикатом (ну это на случай более сложных сравнений. Сейчас это излишество)
    struct pred
    {
        td_my_list::value_type m_val;

        pred(td_my_list::value_type m_val):m_val(m_val)
        {
        }

        bool operator()(td_my_list::value_type& elem)const
        {
            return elem==m_val;
        }
    };

    my_list.remove_if(pred(3));

Насколько я понимаю, изначальный код упрощенный. И проблема как раз в сочетании обхода в обратном порядке и удаления элементов.

а зачем нужен именно обратный обход ?

Затем, что задача такая! А если серьезно, алгоритм такой, что в хвосте списка как раз лежат элементы для удаления. Приведенный тобой код не относится к задаче вообще, извини. Задача как раз про удаление элементов во время обхода списка. Конечно же, здесь указан упрощенный код, а так-то во время обхода могут делаться и другие операции со списком.

ну ладно ) извиняться не за что вроде ))

а что мешает изначально инверсно хранить элементы ? Что мешает применить vector ?

насчёт других операций - тоже аргумент непонятен.

Огласил бы задачу, что гадаем

Задача оглашена в названии темы. Удаление элементов из списка в цикле! Операции добавления и удаления самые важные в данной задаче, потому и используется список. Где гадание? Не понимаю, зачем спорить, если проблема объяснена четко и ясно. Проблема выделена в упрощенный тестовый наглядный код. Какие дополнительные задачи решаются - неважно на данный момент.

спокойнее ) Всё важно. Я же не для того, чтобы поспорить, а ради истины ))


от этого как раз надо плясать. Ну а когда чисто абстрактная задача - она решается ровно одной строкой (цикл там есть, загляни в исходники)


и это не аргумент для выбора списка. Ты не сказал КАК и ЧТО ты добавляешь и удаляешь.

Если всё остаётся на уровне школьной задачки, то считаем задачу решённой, ок.

Ее в принципе не существует, потому и, получается, что спор ради спора. Любую задачу можно решить множеством способов. Понятное дело, что не всегда принимается оптимальный вариант, но есть куча побочных факторов, не относящихся прямо к задаче, которые влияют на выбор решения. В данном случае, приводится очевидный кусок кода слегка в упрощенном варианте. Цикл сделан не случайно, так как в реальной задаче сравнение на удаляемый элемент не такое простое, требующее знать отдельные части структуры, которая является элементом списка (конечно же, там не список простых чисел! ). И даже в упрощенном варианте видна проблема, которую и решают.

А тема и не о выборе контейнера

ага, тема про цикл ))

В общем, в результате изучения Стандарта (D_K спасибо за ссылку на 24.4.1) у меня сложилось устойчивое впечатление, что "падающий" код - это следствие косяков конкретных реализаций. Стандарт устанавливает только требования к интерфейсу reverse_iterator, но ничего не говорит о его внутреннем устройстве; это абсолютно нормально. Равным образом, в Стандарте нет требования (requirement) о том, что reverse_iterator обязательно должен содержать iterator, указывающий на предыдущий элемент, - тот самый, который становится невалидным в нашем коде, и основывать свою работу на нем. Таким образом, это остается на усмотрение разработчиков реализации....

К сожалению, в большинстве случаев мы сильно ограничены в выборе реализаций STL.
Теоретически, код из поста #10 не противоречит Стандарту и абсолютно валиден (и это тот же самый совет Мейерса #28, только записанный немного подробнее). Однако в конкретных реализациях мы видим, что он не работает. Увы.

Влад, а как же

Ну и дальше все операции через current расписаны...

Тут бы я не согласился. Вот этот самый current - исключительно деталь внутренней реализации реверсивного итератора. И, в то же время, Стандарт иллюстрирует effects через current, но не дает никаких указаний о содержимом current после операций типа erase/insert и о моментах его обновления. В то же время, в Ст.23.2.2.3 (напоминает "Матф. 18:13", не правда ли? :-) ) явно указывает:
Effects: Invalidates only the iterators and references to the erased elements.
Учтем, что в этот момент reverse_iterator не указывает на erased element, а о его внутреннем устройстве (в том числе, о protected членах) я, как "внешний" пользователь, вообще ничего знать не обязан. :-) А нежелательные эффекты возникают из-за излишне прямолинейного копирования иллюстративного кода в Стандарте - в программный код. Т.е., я имею в виду, что код должен следовать требованиям Стандарта по принципу "включая, но не ограничиваясь". А вот это, видимо, выполняется не во всех реализациях.

Дискуссия по этому вопросу и возражения приветствуются!

ИМХО. Стандарт, в первую очередь, предназначен для реализаций языка.
И по-моему, вот из этого:

следует, что итератор станет невалидным...

Кроме того, Iteratir current - это protected-член. Соответственно, это часть интерфейса наследования.

если вкратце, то erase превращает итератор в так называемое singular value. можно представить его как аналог NULL для указателей. это значение, не принадлежащее ни одному контейнеру. поэтому после erase итератор становится невалиден и постфиксная операция iter++ будет невалидна. а вот если взять префиксный плюс (++iter) прямо внутри вызова erase, то всё будет ok, потому что сначала итератор изменится, а его "старое" значение будет скопировано, копия будет использована в erase и перейдёт в singular value.

Iron Bug, так не об этом речь. reverse_iterator'ы обсуждаем.

именно об этом. реверс-итератор ничем принципиально не отличается от обычного итератора и у него при вызове erase точно также будут работать префиксные плюсы и не будут работать постфиксные.

Iron Bug, как вы собираетесь делать erase с reverse_iterator'ом? Это возможно только через метод base(), возвращающий обычный итератор.

и чем же он плох? просто erase сам по себе не принимает обратный итератор. но сам итератор от этого ничуть не страдает.

вот обычный метод, который работает, удаляя элементы в обратном порядке.

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> data;
    for(int i=0; i<1000; i++)
    {
        data.push_back(i);
    }
    list<int>::reverse_iterator iter;
    iter = data.rbegin();
    do
    {
        data.erase(--iter.base());
    }
    while(iter != data.rend());
    cout << data.size() << endl;
    return 0;
}

Неясно, к чему это.