Разница между функциями partition() и remove() в С++

Ответ 1

remove [...] помещает "удаленные" элементы в начале последовательности

Что? Нет. И remove_if, и partition сначала помещают "хорошие" элементы. partition после этого помещает "плохие" элементы, тогда как remove_if не указывает, что происходит после него - это могут быть плохие элементы, но это могут быть и копии любых (хороших или плохих) элементов.

Например, если вы partition 1 2 3 4 5 на четном, вы можете получить 2 4 5 3 1 (обратите внимание, что каждый элемент происходит ровно один раз), тогда как если вы remove_if нечетные элементы, вы можете получить 2 4 3 4 5 (обратите внимание на дубликаты).

Ответ 2

remove_if не помещает удаленные элементы в любом месте; элементы после нового конца будут иметь свои старые значения, поэтому некоторые из удаленных элементов могут отсутствовать, а некоторые из сохраненных элементов могут быть дублированы. Это быстрее, чем partition, и может быть выполнено с помощью итераторов вперед, а partition требует двунаправленных итераторов.

Обновление: в С++ 0x, partition потребуются только итераторы вперед, но будет еще медленнее, если итераторы не двунаправлены.

Ответ 3

Если я правильно понял, remove фактически не меняет местами какие-либо элементы, а просто перемещает элементы, для которых предикат (в случае remove_if) имеет значение false для начала последовательности. Если у вас есть

a = [1,1,1,2,3]

и вызовите remove(a.begin(),a.end(),1), у вас будет

a = [2,3,1,2,3]

потом. remove возвращает итератор в третий элемент в этом случае (если я правильно помню...)

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

partition(a.begin(), a.end(), not_equal<int>(1)) дает

a = [2,3,1,1,1]

Ответ 4

Из стандартной библиотеки С++: учебник и справочник

remove() - удаляет элементы с заданным значением, логически только путем их перезаписи со следующими элементами, которые не были удалены. Не изменяйте количество элементов в диапазонах, в которых они работают. Вместо этого они возвращают положение нового "конца" диапазона

partition() - изменяет порядок элементов, чтобы элементы, соответствующие критерию, находились спереди

stable_partition() - То же, что и partition(), но сохраняет относительный порядок совпадающих и несовпадающих элементов

Ответ 5

partition - "группирует" элементы контейнера в соответствии с определенным предикатом (например, нечетные и четные числа в std::vector)

remove - удаляет определенное значение из контейнера; действительно, элементы перемещаются в конец исходного контейнера, возвращается итератор на новый конец и все доступные элементы "удалены"

EDIT:

remove - удаляет определенное значение из контейнера; элементы НЕ перемещаются в конец начального контейнера, как указано выше, возвращается итератор в новый конец, но итераторы в диапазоне [newEnd, last) по-прежнему разыскиваются, поэтому доступны, НО элементы, на которые они указывают, не указаны.