Два алгоритма из 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"
That IACR preprint
2 дня назад
Atom feed
13 коммент.:
Респект и Уважуха!
Мейерс "Эффективное использование 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 ничего не удаляют. Просто получаете новый конец и работаете до него. Привычно для тех, кто не разбалован шаблонными контейнерами.
Кстати, во множестве случаев и для контейнеров удалять не нужно помеченные для удаления элементы. Просто задайте новые границы для итерирования, чтобы не выполнять лишней работы.
Отправить комментарий