Скотт Мейерс - Эффективное использование STL
При выборе алгоритма сортировки я рекомендую руководствоваться целью, а не соображениями быстродействия. Если выбранный алгоритм ограничивается строго необходимыми функциями и не выполняет лишней работы (например, partition вместо полной сортировки алгоритмом sort), то программа будет не только четко выражать свое предназначение, но и наиболее эффективно решать поставленную задачу средствами STL.
Совет 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.
