Странное поведение с вектором:: стирание и станд.:: remove_if с диапазоном конца, отличающимся от vector.end ()
Я должен удалить элементы с середины станд.:: вектор.
Таким образом, я попробовал:
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 изменяются, я предполагаю, что я в своего рода неопределенное поведение здесь.
Так, как я удаляю элементы из Диапазона вектора?
3 ответа
Редактировать: Извините, исходная версия этого была неправильной. Фиксированный.
Вот что происходит. Ваш ввод в 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 ]] подпоследовательность, которую вы передали, но с удаленными некоторыми элементами. Все, что находится на конце или за ним, остается нетронутым.
То, от чего вы хотите избавиться, это ] все между конечным итератором, который был возвращен, и исходным конечным итератором, который вы ему дали . Это «мусорные» значения ? . Итак, ваш вызов стирания должен быть:
ints.erase(it, ints.begin()+4);
вызов erase , который вы только что удалили, удаляет все, что находится за пределами подпоследовательности, для которой вы выполнили удаление, а это не то, что вам здесь нужно.
Это усложняет то, что Алгоритм remove_if на самом деле не вызывает erase () для вектора и не изменяет размер вектора в любой точке. Он просто сдвигает элементы ar ound и оставляет некоторые «мусорные» элементы после окончания подпоследовательности, которую вы просили обработать. Это кажется глупым, но вся причина того, что STL делает это таким образом, заключается в том, чтобы избежать проблемы с недействительными итераторами, которые вызываются дважды (и иметь возможность работать на вещах, которые не являются контейнерами STL, такими как необработанные массивы).
Поведение не странное - вы стираете неправильный диапазон. std :: remove_if перемещает элементы, которые он «удаляет», в конец диапазона ввода. В этом случае вам нужно сделать следующее:
ints.erase(it, ints.begin() + 4 /* your end of range */);
Из C ++ в двух словах:
Шаблон функции remove_if «удаляет» элементы, для которых pred возвращает false из диапазона [первый, последний). Возвращаемое значение - один за новым концом диапазона. Относительный порядок элементов, которые не удаляются, является стабильным.
Фактически ничего не стирается из нижележащего контейнера ; вместо этого элементы справа назначаются новым позициям , поэтому они перезаписывают элементы , для которых pred возвращает false. См. рисунок 13-13 (в разделе remove_copy ) для примера процесса удаления.
Удаление элементов в std :: vector делает недействительными итераторы после удаленного элемента, поэтому вы не можете использовать «чужие» функции, которые принимают диапазоны. Вам нужно сделать это по-другому.
РЕДАКТИРОВАТЬ:
В общем, вы можете использовать тот факт, что стирание одного элемента "сдвигает" все элементы в следующих позициях на один назад. Примерно так:
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 должен быть более эффективным, чем то, что я предлагал в первом редактировании, поэтому проигнорируйте этот ответ. (Сохраняю это для комментариев.)