Странное поведение с vector :: erase и std :: remove_if с конечным диапазоном, отличным от vector.end ()

Question

Мне нужно удалить элементы из середины std :: vector.

Итак, я попробовал:

struct IsEven {
    bool operator()(int ele)
    {
        return ele % 2 == 0;
    }
};

    int elements[] = {1, 2, 3, 4, 5, 6};
    std::vector<int> ints(elements, elements+6);

    std::vector<int>::iterator it = std::remove_if(ints.begin() + 2, ints.begin() + 4, IsEven());
    ints.erase(it, ints.end());

После этого я ожидаю, что вектор ints будет иметь: [1, 2, 3, 5, 6].

В отладчике Visual studio 2008 после строки std::remove_if элементы ints модифицируются, я полагаю, что я нахожусь в каком-то неопределенном поведении здесь.

Итак, как мне удалить элементы из диапазона вектора?

Answer 1

Редактировать: Извините, оригинальная версия была неправильной. Исправлено.

Вот что происходит. Ваш ввод для remove_if:

1  2  3  4  5  6
      ^     ^
    begin  end

А алгоритм remove_if просматривает все числа от begin до end (включая begin, но исключая end) и удаляет все элементы между ними, которые соответствуют вашему предикату. Поэтому после запуска remove_if ваш вектор выглядит следующим образом

1  2  3  ?  5  6
      ^  ^
  begin  new_end

Где ? - это значение, которое я не считаю детерминированным, хотя, если оно гарантированно будет чем-либо, оно будет 4. И new_end, который указывает на новый конец введенной вами последовательности ввода , с соответствующими элементами теперь удаленными, это то, что возвращается std::remove_if. Обратите внимание, что std::remove_if не затрагивает ничего, кроме той последовательности, которую вы ему дали. Это может иметь больше смысла с более расширенным примером.

Скажите, что это ваш ввод:

1  2  3  4  5  6  7  8  9  10
      ^              ^
    begin           end

После std::remove_if вы получите:

1  2  3  5  7  ?  ?  8  9  10
      ^        ^
    begin      new_end

Подумайте об этом на мгновение. Что он сделал, так это удалил 4 и 6 из подпоследовательности, а затем сдвинул все в подпоследовательности вниз, чтобы заполнить удаленные элементы, а затем переместил итератор end на новый конец та же подпоследовательность. Цель состоит в том, чтобы удовлетворить требование, чтобы полученная последовательность (begin, new_end] совпадала с подпоследовательностью (begin, end], которую вы передали, но с некоторыми удаленными элементами. или за end, который вы прошли, осталось нетронутым.

От чего вы хотите избавиться, так это все, что находится между конечным итератором, который был возвращен, и исходным конечным итератором, который вы ему дали . Это ? «мусорные» значения. Таким образом, ваш вызов удаления должен быть:

ints.erase(it, ints.begin()+4);

Призыв к erase, который у вас есть, просто стирает все, что находится за концом подпоследовательности, для которой вы выполняли удаление, а это не то, что вам нужно.

Что усложняет это, так это то, что алгоритм remove_if на самом деле не вызывает erase() для вектора и не изменяет размер вектора в любой точке. Он просто перемещает элементы и оставляет некоторые «мусорные» элементы после окончания подпоследовательности, которую вы попросили обработать. Это кажется глупым, но единственная причина, по которой STL делает это таким образом, состоит в том, чтобы избежать проблемы с недействительными итераторами, которые были дважды вызваны (и иметь возможность работать с вещами, которые не являются контейнерами STL, например, с массивами). *

Answer 2

Поведение не странное - вы стираете неправильный диапазон. std::remove_if перемещает элементы, которые он «удаляет», в конец диапазона ввода. В этом случае вам нужно сделать следующее:

ints.erase(it, ints.begin() + 4 /* your end of range */);

Из C ++ в двух словах:

Шаблон функции remove_if «удаляет» элементы, для которых возвращается pred false из диапазона [первый, последний). Возвращаемое значение - один за новым конец диапазона. Относительный порядок из предметов, которые не удалены стабильный.

Ничего не стирается из нижележащий контейнер; вместо этого предметы справа назначены новые позиции, чтобы они перезаписали элементы, для которых pred возвращает false. Смотрите рисунок 13-13 (под remove_copy) для примера процесса удаления.

Answer 3

Стирание элементов в std::vector делает недействительными итераторы после удаленного элемента, поэтому вы не можете использовать «чужие» функции, которые принимают диапазоны. Вам нужно сделать это по-другому.

EDIT:

В общем, вы можете использовать тот факт, что стирание одного элемента «сдвигает» все элементы на дальнейшие позиции на одну позицию назад. Примерно так:

for (size_t scan = 2, end = 4; scan != end; )
  {
     if (/* some predicate on ints[scan] */)
       {
         ints.erase (ints.begin () + scan);
         --end;
       }
     else
       ++scan;
  }

Обратите внимание, что std::vector не подходит для стирания элементов в середине. Вам следует подумать о чем-то еще (std::list?), Если вы делаете это часто.

РЕДАКТИРОВАТЬ 2:

Как поясняется в комментариях, первый абзац не соответствует действительности. В таком случае std::remove_if должен быть более эффективным, чем то, что я предложил в первом редактировании, поэтому не обращайте внимания на этот ответ. (Сохраняя для комментариев.)