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"
Респект и Уважуха!
ОтветитьУдалитьМейерс "Эффективное использование STL" совет 33.
ОтветитьУдалитьКак раз залип в отладке на этом моменте. Спасибо за разъяснение!=)
ОтветитьУдалитьВсе же list::remove() тоже не удаляет мусор, и для list тоже нужно вызывать erase() после remove(), верно?
ОтветитьУдалитьCаттер "Стандарты программирования на с++"
ОтветитьУдалитьсовет 82
Подниму темку.
ОтветитьУдалитьИ Мейерс, и Саттер пишут, что алгоритм remove не знает от переданного итератора, к какому контейнеру он относится. А зачем это знать? От итератора можно узнать тип контейнера и тип элемента, к примеру, vector::iterator. Зная это, remove может (по идее) вызвать деструктор (если тип не встроенный) и в зависимости от типа самого контейнера произвести удаление элемента.
Теоретически это можно, я думаю, но тогда простой алгоритм remove превращается в монстра, который должен знать менеджеры памяти всех последовательных существующих контейнеров (ес-но, при появлении новых это все дело будет в remove разрастаться), что, в общем-то не есть хорошо - функция начинает выполнять слишком много задач. Сложно, трудная поддержка, небезопасно.
Мне кажется в этом реальная причина существования пары remove/erase, а не незнание контейнера. Зачем его знать... А так бы сдвинули элементы, а остальные удалили бы, без вызова erase. Но, повторюсь, имо, накладно это получится.
А вместо erase() лучше делать resize(). Ведь эта операция существенно быстрее. Единственный недостаток - нужно знать, какое кол-во элементов удалилось с помощью remove().
ОтветитьУдалитьstd::remove операции копирования вызывает у передвигаемых элементов, что у меня вызывает недоумение - зачем? Может кто популярно объяснит?
ОтветитьУдалитьК предыдущему сообщению забыл добавить, что для std::vector копирование элементов при вызове std::remove происходит.
ОтветитьУдалитьА почему нельзя делать сразу erase без всяких remove??
ОтветитьУдалитьnictrace
ОтветитьУдалитьА почему нельзя делать сразу erase без всяких remove??
В erase передаются итераторы. Никаких условий там указывать нельзя. Для того, чтобы получить правильные итераторы, нужен remove.
Аноним, открывший тему, а в каких других случаях remove работает иначе? Он всегда копирует элементы. На примере remove_if: те элементы последовательности, что не удовлетворяют предикату (3 аргументу) становятся на первое место, а те что удовлетворили (под удаление) становятся на последние и на начало этих элементов ссылается возвращаемый итератор, чтобы нам было проще удалить, это правда, но на практике такое не выходит, т.к. механизм немного сложнее: алгоритм обращается с элементами, удовлетворивших условия предиката, как со "свободными" местами и если далее встречает элемент - неудовлетворительный при необходимости перезаписывает их т.к. они "заслуживают" того места и в более сложной последовательности пример, куда сложнее получается.
ОтветитьУдалитьИ да кстати я сам не знаю что быстрее partition, а затем resize или же remove_if+erase
Алгоритмы работают также и со встроенными массивами, размер которых сократить нельзя, он константный и должен быть известен на момент компиляции. Вот реальная причина того, что remove и remove_if ничего не удаляют. Просто получаете новый конец и работаете до него. Привычно для тех, кто не разбалован шаблонными контейнерами.
ОтветитьУдалитьКстати, во множестве случаев и для контейнеров удалять не нужно помеченные для удаления элементы. Просто задайте новые границы для итерирования, чтобы не выполнять лишней работы.