векторы: rend () аннулируется функцией erase ()

Question

Согласно спецификации C ++ (23.2.4.3), vector :: erase () делает недействительными только «все итераторы и ссылки после точки стирания»

Таким образом, при использовании reverse_iterators для передачи по всем элементам вектора удаление на текущем итераторе должно не приводить к тому, что член rend () становится недействительным.

Этот код будет работать под G ++, но обеспечит исключение времени выполнения в Windows (VS2010):

#include <vector>

using namespace std;

int main()
{
    vector<int> x;
    x.push_back(1);
    x.push_back(2);
    x.push_back(3);

    //Print
    for(vector<int>::const_iterator i = x.begin(); i != x.end(); ++i)
        printf("%d\n", *i);

    //Delete second node
    for(vector<int>::reverse_iterator r = x.rbegin(); r != x.rend(); ++r)
        if(*r == 2)
            x.erase((r+1).base());

    //Print
    for(vector<int>::const_iterator i = x.begin(); i != x.end(); ++i)
        printf("%d\n", *i);

    return 0;
}

Интересна ошибка:

Выражение: векторный итератор не может быть уменьшен

Задано в строке второго цикла for при втором запуске. Уменьшение относится к внутреннему «текущему» элементу итератора reverse_iterator, который уменьшается при каждом увеличении reverse_iterator.

Может кто-нибудь объяснить это поведение, пожалуйста?

Спасибо.

EDIT

Мне кажется, этот пример кода лучше показывает, что проблема не в r, а в rend ():

//Delete second node
for(vector<int>::reverse_iterator r = x.rbegin(); r != x.rend();)
{
    vector<int>::reverse_iterator temp = r++;

    if(*temp == 2)
        x.erase((temp+1).base());
}

И ошибки с vector iterators incompatible в цикле for при входе после стирания.

Answer 1

Ваша программа вызывает неопределенное поведение.Следовательно, ни один компилятор не является правильным.

В соответствии со стандартом std::vector<int>::reverse_iterator является typedef для std::reverse_iterator<std::vector<int>::iterator>.Реализация std::reverse_iterator<Iter> определена как имеющая protected член Iter current;, а все другие члены и функции reverse_iterator определены на основе поведения члена current.

Так что предположиму нас есть r == reverse_iterator(i), где i является действительным итератором в std::vector<int> x;.Каждый из них гарантируется Стандартом.

r.current == i
(r+1).current == (i-1)
(r+1).base() == (i-1)

При вызове x.erase((r+1).base()); все итераторы после i-1 становятся недействительными.Конечно, это включает в себя i, и, следовательно, также r.current.

Следующее, что ваша программа пытается оценить, это ++r.Это выражение указано как имеющее эффект --r.current;.Но поскольку r.current признан недействительным, это выражение является неопределенным поведением;и так же ++r.

Answer 2

A reverse_iterator часто является просто оберткой вокруг обычного итератора, и поэтому увеличение обратного итератора, вероятно, уменьшает на единицу ниже. Точно так же rbegin вернет итератор, который следует за всеми элементами в контейнере, и поэтому он будет аннулирован таким же образом.

Answer 3

Вот гораздо лучший способ сделать то, что вы пытаетесь сделать:

struct CustomRemove
{
    bool operator()(int i)
    {
        return (i == 2);
    }
};

int main()
{
    std::vector<int> x;
    x.push_back(1);
    x.push_back(2);
    x.push_back(3);

    CustomRemove custom_remove;

    std::copy(x.begin(), x.end(), std::ostream_iterator<int>(std::cout, "\n"));
    x.erase(std::remove_if(x.begin(), x.end(), custom_remove), x.end());
    std::copy(x.begin(), x.end(), std::ostream_iterator<int>(std::cout, "\n"));

    return 0;
}

Answer 4

Обратный итератор внутренне сохраняет нормальный итератор в позиции после его текущей позиции. Это должно быть сделано, потому что в противном случае rend () пришлось бы возвращать что-то перед begin (), что невозможно. Таким образом, вы в конечном итоге случайно аннулируете свой итератор base ().

Answer 5

Поскольку (r+1).base() и r фактически указывают на один и тот же элемент, удаление (r+1).base() фактически делает недействительным r. Скорее всего, g ++ просто использует указатель под капотом, поэтому все работает правильно.

Если вы пытаетесь удалить совпадающие элементы из вектора, гораздо лучше использовать remove или remove_if.