Скотт Мейерс - Эффективное использование STL
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.
Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей
Предположим, мы динамически создаем ряд объектов Widget и сохраняем полученные указатели в векторе:
class Widget {
public:
…
bool isCertified() const; // Функция сертификации объектов Widget
}
vector<Widget*> v; // Создать вектор и заполнить его указателями
… // на динамически созданные объекты Widget
v.push_back(new Widget);
…
Поработав с v в течение некоторого времени, вы решаете избавиться от объектов Widget, не сертифицированных функцией Widget, поскольку они вам не нужны. С учетом рекомендаций, приведенных в совете 43 (по возможности использовать алгоритмы вместо циклов), и того, что говорилось в совете 32 о связи remove и erase, возникает естественное желание использовать идиому erase-remove, хотя в данном случае используется алгоритм remove_if:
v.erase(remove_if(v.begin(), v.end(), // Удалить указатели на объекты
not1(mem_fun(&Widget::isCertified))), // Widget, непрошедшие
v.end()); // сертификацию.
// Информация о mem_fun
// приведена в совете 41.
Внезапно у вас возникает беспокойство по поводу вызова erase, поскольку вам смутно припоминается совет 7 — уничтожение указателя в контейнере не приводит к удалению объекта, на который он ссылается. Беспокойство вполне оправданное, но в этом случае оно запоздало. Вполне возможно, что к моменту вызова erase утечка ресурсов уже произошла. Прежде чем беспокоиться о вызове erase, стоит обратить внимание на remove_if.
