суббота, октября 29, 2005

std::remove и std::remove_if на самом деле ничего не удаляют

Два алгоритма из STL, remove и remove_if помогают удалять элементы из последовательных контейнеров, то есть из vector, string, deque и list.
Помощь заключается в том, что эти алгоритмы сдвигают элементы и возвращают итератор на начало мусора. Удалять мусор нужно отдельно, remove и remove_if не удаляют физически объекты из контейнера.

Например, пускай у нас есть vector <int>, содержащий следующие значения.
1 2 3 1 2 3 1 2 3

Если вызвать
remove( v.begin(), v.end(), 2 )
//удалить элемент со значением 2 из контейнера v


получится
1 3 1 3 1 3 ? ? ?
где ? - некий мусор. Итератор, который возвратит remove, указывает на первый мусорный элемент, в данном случае на третий с конца. Мусорные элементы могут иметь те же значения, что и до вызова remove, то есть 1 2 3, а могут иметь и любые другие, на это полагаться не стоит. Размер контейнера остается неизменным.

Чтобы избавиться от мусора, можно вызвать erase. Обычно оба вызова записывают одной строкой и получается что-то вроде.
v.erase( remove( v.begin(), v.end(), 2 ), v.end() );

Для list алгоритмы std::remove и std::remove_if работают крайне неэффективно. Поэтому в list есть собственная реализация удаления объектов, list::remove и она быстрая. Элементы там не двигаются, а лишь переставляются ссылки. erase вызывать уже не нужно, потому что list::remove уничтожает ненужные элементы сам.

Почему remove и remove_if работают именно так? Что мешает удалять элементы сразу и не мучаться лишний раз, вызвая erase? Дело в том, что remove не может определить из какого контейнера к нему пришли итераторы, а, следовательно, не может корректно удалить элементы из этого контейнера. Нельзя удалить элементы из контейнера или добавить элементы в контейнер, если на этот контейнер каким-либо образом не была передана ссылка.

Ссылки по теме:
Table of Contents: the Standard Template Library
GotW #51: Extending the Standard Library - Part I
comp.lang.c++.moderated "delete elements in associative container"
comp.lang.c++.moderated "The list.erase(remove...) idiom, doing half the job???"
comp.lang.c++.moderated "Two new STL Questions"

12 коммент.:

Анонимный комментирует...

Респект и Уважуха!

Анонимный комментирует...

Мейерс "Эффективное использование STL" совет 33.

pure virtual комментирует...

Как раз залип в отладке на этом моменте. Спасибо за разъяснение!=)

Chumak комментирует...

Все же list::remove() тоже не удаляет мусор, и для list тоже нужно вызывать erase() после remove(), верно?

Анонимный комментирует...

Cаттер "Стандарты программирования на с++"
совет 82

Анонимный комментирует...

Подниму темку.

И Мейерс, и Саттер пишут, что алгоритм remove не знает от переданного итератора, к какому контейнеру он относится. А зачем это знать? От итератора можно узнать тип контейнера и тип элемента, к примеру, vector::iterator. Зная это, remove может (по идее) вызвать деструктор (если тип не встроенный) и в зависимости от типа самого контейнера произвести удаление элемента.

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

Мне кажется в этом реальная причина существования пары remove/erase, а не незнание контейнера. Зачем его знать... А так бы сдвинули элементы, а остальные удалили бы, без вызова erase. Но, повторюсь, имо, накладно это получится.

_Andrey_ комментирует...

А вместо erase() лучше делать resize(). Ведь эта операция существенно быстрее. Единственный недостаток - нужно знать, какое кол-во элементов удалилось с помощью remove().

Анонимный комментирует...

std::remove операции копирования вызывает у передвигаемых элементов, что у меня вызывает недоумение - зачем? Может кто популярно объяснит?

Анонимный комментирует...

К предыдущему сообщению забыл добавить, что для std::vector копирование элементов при вызове std::remove происходит.

nictrace комментирует...

А почему нельзя делать сразу erase без всяких remove??

Alena комментирует...

nictrace

А почему нельзя делать сразу erase без всяких remove??

В erase передаются итераторы. Никаких условий там указывать нельзя. Для того, чтобы получить правильные итераторы, нужен remove.

Stirol Craft комментирует...

Аноним, открывший тему, а в каких других случаях remove работает иначе? Он всегда копирует элементы. На примере remove_if: те элементы последовательности, что не удовлетворяют предикату (3 аргументу) становятся на первое место, а те что удовлетворили (под удаление) становятся на последние и на начало этих элементов ссылается возвращаемый итератор, чтобы нам было проще удалить, это правда, но на практике такое не выходит, т.к. механизм немного сложнее: алгоритм обращается с элементами, удовлетворивших условия предиката, как со "свободными" местами и если далее встречает элемент - неудовлетворительный при необходимости перезаписывает их т.к. они "заслуживают" того места и в более сложной последовательности пример, куда сложнее получается.
И да кстати я сам не знаю что быстрее partition, а затем resize или же remove_if+erase