Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase

Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase

Начнем с краткого обзора remove, поскольку этот алгоритм вызывает больше всего недоразумений в STL. Прежде всего необходимо рассеять все сомнения относительно того, что делает алгоритм remove, а также почему и как он это делает. Объявление remove выглядит следующим образом:

template<class ForwardIterator.class T>

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

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

Попробуем разобраться, как происходит удаление элементов из контейнера. Существует только один способ — вызов соответствующей функции контейнера, почти всегда некоторой разновидности erase (контейнер list содержит пару функций удаления элементов, имена которых не содержат erase). Поскольку удаление элемента из контейнера может производиться только вызовом функции данного контейнера, а алгоритм remove не может определить, с каким контейнером он работает, значит, алгоритм remove не может удалять элементы из контейнера. Этим объясняется тот удивительный факт, что вызов remove не изменяет количества элементов в контейнере:

vector<int> v;

v.reserve(10);

for(int =l;i<=10;++i){

v.push_back(i);

};

// Создать vector<int> и заполнить его

// числами 1-10 (вызов reserve описан

// в совете 14)

cout << v.size(); // Выводится число 10

v[3]=v[5]=v[9]=99; // Присвоить 3 элементам значение 99

remove(v.begin(),v.end(),99); // Удалить все элементы со значением 99

cout <<v. Size(); // Все равно выводится 10!

Чтобы понять смысл происходящего, необходимо запомнить следующее: Алгоритм remove «по настоящему» ничего не удаляет, потому что не может. На всякий случай повторю: ...потому что не может!

Алгоритм remove не знает, из какого контейнера он должен удалять элементы, а без этого он не может вызвать функцию «настоящего» удаления.

Итак, теперь вы знаете, чего алгоритм remove сделать не может и по каким причинам. Остается понять, что же он все-таки делает.

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

В рассмотренном выше примере вектор v перед вызовом remove выглядел следующим образом:

Предположим, возвращаемое значение remove сохраняется в новом итераторе с именем newEnd:

vector<int>::iterator newEnd(remove(v.begin (),v.end (), 99));

После вызова вектор v принимает следующий вид:

Вопросительными знаками отмечены значения элементов, «концептуально» удаленных из v, но продолжающих благополучно существовать.

Раз «оставшиеся» элементы v находятся между v.begin() и newEnd, было бы логично предположить, что «удаленные» элементы будут находиться между newEnd и v.end(). Но это не так Присутствие «удаленных» элементов в v вообще не гарантировано. Алгоритм remove не изменяет порядок элементов в интервале так, чтобы «удаленные» элементы сгруппировались в конце — он перемещает «остающиеся» элементы в начало. Хотя в Стандарте такое требование отсутствует, элементы за новым логическим концом интервала обычно сохраняют свои старые значения. Во всех известных мне реализациях после вызова remove вектор v выглядит так:

Как видите, два значения «99», ранее существовавших в v, исчезли, а одно осталось. В общем случае после вызова remove элементы, удаленные из интервала, могут остаться в нем, а могут исчезнуть. Многие программисты находят это странным, но почему? Вы просите remove убрать некоторые элементы, алгоритм выполняет вашу просьбу. Вы же не просили разместить удаленные значения в особом месте для последующего использования... Так в чем проблема? (Чтобы предотвратить потерю значений, вместо remove лучше воспользоваться алгоритмом partition, описанным в совете 31.)

На первый взгляд поведение remove выглядит довольно странно, но оно является прямым следствием принципа работы алгоритма. Во внутренней реализации remove перебирает содержимое интервала и перезаписывает «удаляемые» значения «сохраняемыми». Перезапись реализуется посредством присваивания.

Алгоритм remove можно рассматривать как разновидность уплотнения, при этом удаляемые значения играют роль «пустот», заполняемых в процессе уплотнения. Опишем, что происходит с вектором v из нашего примера.

1.Алгоритм remove анализирует v[0], видит, что данный элемент не должен удаляться, и перемещается к v[1]. То же самое происходит с элементами v[1] и v[2],

2.Алгоритм определяет, что элемент v[3] подлежит удалению, запоминает этот факт и переходит к v[4]. Фактически v[3] рассматривается как «дыра», подлежащая заполнению.

3.Значение v[4] необходимо сохранить, поэтому алгоритм присваивает v[4] элементу v[3], запоминает, что v[4] подлежит перезаписи, и переходит к v[5]. Если продолжить аналогию с уплотнением, элемент v[3] «заполняется» значением v[4], а на месте v[4] образуется новая «дыра».

4.Элемент v[5] исключается, поэтому алгоритм игнорирует его и переходит к v[6]. При этом он продолжает помнить, что на месте v[4] остается «дыра», которую нужно заполнить.

5.Элемент v[6] сохраняется, поэтому алгоритм присваивает v[6] элементу v[4], вспоминает, что следующая «дыра» находится на месте v[5], и переходит к v[7].

6.Аналогичным образом анализируются элементы v[7], v[8] и v[9]. Значение v[7] присваивается элементу v[5], а значение v[8] присваивается элементу v[6]. Элемент v[9] игнорируется, поскольку находящееся в нем значение подлежит удалению.

7.Алгоритм возвращает итератор для элемента, следующего за последним «оставшимся». В данном примере это элемент v[7].

Перемещения элементов в векторе v выглядят следующим образом:

Как объясняется в совете 33, факт перезаписи некоторых удаляемых значений имеет важные последствия в том случае, если эти значения являются указателями. Но в контексте данного совета достаточно понимать, что remove не удаляет элементы из контейнера, поскольку в принципе не может этого сделать. Элементы могут удаляться лишь функциями контейнера, отсюда следует и главное правило настоящего совета: чтобы удалить элементы из контейнера, вызовите erase после remove.

Элементы, подлежащие фактическому удалению, определить нетрудно — это все элементы исходного интервала, начиная с нового «логического конца» интервала и завершая его «физическим» концом. Чтобы уничтожить все эти элементы, достаточно вызвать интервальную форму erase (см. совет 5) и передать ей эти два итератора. Поскольку сам алгоритм remove возвращает итератор для нового логического конца массива, задача решается прямолинейно:

vector<int> v;//См. ранее

v.erase(remove(v.begin().v.end(),99),v.end()); // Фактическое удаление

// элементов со значением 99 cout << v.size():

// Теперь выводится 7

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

list<int> li;// Создать список

// Заполнить данными

li.remove(99);// Удалить все элементы со значением 99.

// Команда производит фактическое удаление

// элементов из контейнера, поэтому размер li

// может измениться

Честно говоря, выбор имени remove в данном случае выглядит непоследовательно. В ассоциативных контейнерах аналогичная функция называется erase, поэтому в контейнере list функцию remove тоже следовало назвать erase. Впрочем, этого не произошло, поэтому остается лишь смириться. Мир, в котором мы живем, не идеален, но другого все равно нет. Как упоминается в совете 44, для контейнеров list вызов функции remove более эффективен, чем применение идиомы erase/remove.

Как только вы поймете, что алгоритм remove не может «по-настоящему» удалять объекты из контейнера, применение его в сочетании с erase войдет в привычку. Не забывайте, что remove — не единственный алгоритм, к которому относится это замечание. Существуют два других remove-подобных алгоритма: remove_if и unique.

Сходство между remove и remove_if настолько прямолинейно, что я не буду на нем останавливаться, но алгоритм unique тоже похож на remove. Он предназначен для удаления смежных повторяющихся значений из интервала без доступа к контейнеру, содержащему элементы интервала. Следовательно, если вы хотите действительно удалить элементы из контейнера, вызов unique должен сопровождаться парным вызовом erase. В контейнере list также предусмотрена функция unique, производящая фактическое удаление смежных дубликатов. По эффективности она превосходит связку erase-unique.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

5.1.5.2. Использование ISO С: remove()

Из книги автора

5.1.5.2. Использование ISO С: remove() ISO С предоставляет для удаления файлов функцию remove(); она предназначена в качестве обшей функции, годной для любой системы, поддерживающей ISO С, а не только для Unix и GNU/Linux:#include <stdio.h> /* ISO С */int remove(const char *pathname);Хотя технически это не системный


Сопровождайте поля форм пояснениями

Из книги автора

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


Создание подобных объектов

Из книги автора

Создание подобных объектов Команда OFFSET осуществляет создание подобных объектов (эквидистант) с заданным смещением. Она вызывается из падающего меню Modify ? Offset или щелчком на пиктограмме Offset на панели инструментов Modify.Можно строить подобные отрезки, дуги, окружности,


84. Предпочитайте вызовы алгоритмов самостоятельно разрабатываемым циклам

Из книги автора

84. Предпочитайте вызовы алгоритмов самостоятельно разрабатываемым циклам РезюмеРазумно используйте функциональные объекты. В очень простых случаях написанные самостоятельно циклы могут оказаться более простым и эффективным решением. Тем не менее, вызов алгоритма


19.2.1.6. Сопровождайте заплаты документацией

Из книги автора

19.2.1.6. Сопровождайте заплаты документацией Данный момент очень важен. Если заплата вносит заметные пользователям дополнения или изменяет функции программы, то необходимо включить данные изменения в соответствующие man-страницы и другие файлы документации к заплате. Не


19.2.1.7. Сопровождайте заплату пояснениями

Из книги автора

19.2.1.7. Сопровождайте заплату пояснениями Заплата должна включать в себя пояснительную записку, объясняющую необходимость или практическую пользу заплаты с точки зрения ее создателя. Данное пояснение адресовано не пользователям программного обеспечения, а его куратору,


19.2.1.6. Сопровождайте заплаты документацией

Из книги автора

19.2.1.6. Сопровождайте заплаты документацией Данный момент очень важен. Если заплата вносит заметные пользователям дополнения или изменяет функции программы, то необходимо включить данные изменения в соответствующие man-страницы и другие файлы документации к заплате. Не


19.2.1.7. Сопровождайте заплату пояснениями

Из книги автора

19.2.1.7. Сопровождайте заплату пояснениями Заплата должна включать в себя пояснительную записку, объясняющую необходимость или практическую пользу заплаты с точки зрения ее создателя. Данное пояснение адресовано не пользователям программного обеспечения, а его куратору,


Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей

Из книги автора

Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей Предположим, мы динамически создаем ряд объектов Widget и сохраняем полученные указатели в векторе:class Widget {public:bool isCertified() const; // Функция сертификации объектов Widgetvector<Widget*> v; //


Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов

Из книги автора

Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов Некоторые контейнеры содержат функции, имена которых совпадают с именами алгоритмов STL. Так, в ассоциативных контейнерах существуют функции count, find, lower_bound, upper_bound и equal_range, а в контейнере list


Удалить (Remove)

Из книги автора

Удалить (Remove) template ‹class ForwardIterator, class T›ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);template ‹class ForwardIterator, class Predicate›ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);remove устраняет все элементы, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие


Создание подобных объектов

Из книги автора

Создание подобных объектов Команда OFFSET осуществляет создание подобных объектов (эквидистант) с заданным смещением. Она вызывается из падающего меню Modify ? Offset или щелчком на пиктограмме Offset на панели инструментов Modify.Можно строить подобные отрезки, дуги, окружности,


12.6.2. Операция list::remove()

Из книги автора

12.6.2. Операция list::remove() void list::remove( const elemType &value );Операция remove() удаляет все элементы с заданным значением:ilist1.remove( 1


Создание подобных объектов

Из книги автора

Создание подобных объектов Команда OFFSET осуществляет создание подобных объектов (эквидистант) с заданным смещением. Она вызывается из падающего меню Modify ? Offset или щелчком на пиктограмме Offset на панели инструментов Modify.Можно строить подобные отрезки, дуги, окружности,


Создание подобных объектов

Из книги автора

Создание подобных объектов Команда OFFSET осуществляет создание подобных объектов (эквидистант) с заданным смещением. Она вызывается из падающего меню Modify ? Offset или щелчком на пиктограмме Offset на панели инструментов Modify.Можно строить подобные отрезки, дуги, окружности,