"Эффективное использование STL" - читать интересную книгу автора (Мейерс Скотт)
Совет 9. Тщательно выбирайте операцию удаления
Допустим, у нас имеется стандартный контейнер STL с, содержащий числа типа int:
контейнерlt;intgt; с;
и вы хотите удалить из него все объекты со значением 1963. Как ни странно, способ решения этой задачи зависит от контейнера; универсального решения не существует.
Для блоковых контейнеров (vector, deque или string — см. совет 1) оптимальный вариант построен на использовании идиомы erase-remove (совет 32):
c.erase(remove(c.begin(), c.end(), 1963), // Идиома erase-remove хорошо
c.end()); // подходит для удаления элементов
// с заданным значением
// из контейнеров vector, string
//и deque
Приведенное решение работает и для контейнеров list, но как будет показано в совете 44, функция remove контейнера list работает эффективнее:
с.remove(1963); // Функция remove хорошо подходит для удаления
// элементов с заданным значением из списка
Стандартные ассоциативные контейнеры (такие как set, multiset, map и multimap) не имеют функции remove с именем remove, а использование алгоритма remove может привести к стиранию элементов контейнера (совет 32) и возможной порче его содержимого. За подробностями обращайтесь к совету 22, где также объясняется, почему вызовы remove для контейнеров map/multimap не компилируются никогда, а для контейнеров set/multiset — компилируются в отдельных случаях.
Для ассоциативных контейнеров правильным решением будет вызов erase:
c.erase(1963); // Функция erase обеспечивает оптимальное
// удаление элементов с заданным значением
// из стандартных ассоциативных контейнеров
Функция erase не только справляется с задачей, но и эффективно решает ее с логарифмической сложностью (вызовы remove в последовательных контейнерах обрабатываются с линейной сложностью). Более того, в ассоциативных контейнерах функция erase обладает дополнительным преимуществом — она основана на проверке эквивалентности вместо равенства (это важное различие рассматривается в совете 19).
Слегка изменим проблему. Вместо того чтобы удалять из с все объекты с заданным значением, давайте удалим все объекты, для которых следующий предикат (совет 39) возвращает true:
bool badValue(int х); // Возвращает true для удаляемых объектов
В последовательных контейнерах (vector, string, deque и list) достаточно заменить remove на remove_if:
c.erase(remove_if(c.begin(), c.end(), badValue), // Лучший способ уничтожения
c.end()); // объектов, для которых badValue
// возвращает true, в контейнерах
// vector, string и deque
с.remove_if(badValue); // Оптимальный способ уничтожения
// объектов, для которых badValue
// возвращает true, в контейнере
// list
Со стандартными ассоциативными контейнерами дело обстоит посложнее. Существуют два решения: одно проще программируется, другое эффективнее работает. В первом решении нужные значения копируются в новый контейнер функцией remove_copy, после чего содержимое двух контейнеров меняется местами:
АссоцКонтейнерlt;intgt; с;//с - один из стандартных
… // ассоциативных контейнеров
АссоцКонтейнерlt;intgt; goodValues: // Временный контейнер для хранения
// элементов, оставшихся после удаления
remove_copy_if(c.begin(), c.end(), // Скопировать оставшиеся элементы
inserter(goodValues, // из с в goodValues
goodValues.end()), badValue);
с.swap(goodValues);// Поменять содержимое с и goodValues
У подобного решения имеется недостаток — необходимость копирования элементов, остающихся после удаления. Такое копирование может обойтись дороже, чем нам хотелось бы.
От этих затрат можно избавиться за счет непосредственного удаления элементов из исходного контейнера. Но поскольку в ассоциативных контейнерах отсутствует функция, аналогичная remove_if, придется перебирать все элементы с в цикле и принимать решение об удалении текущего элемента.
С концептуальной точки зрения эта задача несложна, да и реализуется она просто. К сожалению, решение, которое первым приходит в голову, редко бывает правильным. Вероятно, многие программисты предложат следующий вариант:
if (badValue(*i)) c.erase(i); // для которых badValue
} // возвращает true.
// Не поступайте так!
Выполнение этого фрагмента приводит к непредсказуемым результатам. При стирании элемента контейнера все итераторы, указывающие на этот элемент, становятся недействительными. Таким образом, после возврата из c.erase(i) итератор i становится недействительным. Для нашего цикла это фатально, поскольку после вызова erase итератор i увеличивается (++i в заголовке цикла for).
Проблема решается просто: необходимо позаботиться о том, чтобы итератор переводился на следующий элемент с перед вызовом erase. Это проще всего сделать постфиксным увеличением i при вызове:
АссоцКонтейнерlt;intgt; с;
for(АссоцКонтейнерlt;intgt;::iterator i=c.begin();// Третья часть заголовка
i!=c.end(); // цикла for пуста; i теперь
/* пусто */) { // изменяется внутри цикла
if (badValue(*i)) c.erase(i++);// Для удаляемых элементов
else ++i; // передать erase текущее
} // значение i и увеличить i.
// Для остающихся элементов
// просто увеличить i
Новый вариант вызова erase работает, поскольку выражение i++ равно старому значению i, но у него имеется побочный эффект — приращение i. Таким образом, мы передаем старое (не увеличенное) значение i и увеличиваем i перед вызовом erase. Именно это нам и требовалось. Хотя это решение выглядит просто, лишь немногие программисты предложат его с первой попытки.
Пора сделать следующий шаг. Помимо простого удаления всех элементов, для которых badValue возвращает true, мы также хотим регистрировать каждую операцию удаления в журнале.
Для ассоциативных контейнеров задача решается очень просто, поскольку она требует лишь тривиальной модификации созданного цикла:
ofstream logFile;// Файл журнала
АссоцКонтейнерlt;intgt; с;
…
for(АссоцКонтейнерlt;intgt;::iterator i=c.begin();// Заголовок цикла остается
i!=c.end();) { // без изменений
if(badValue(*i)) {
logFilelt;lt;"Erasing "lt;lt;*ilt;lt;'\n'; // Вывод в журнал
c.erase(i++);// Удаление
} else ++i;
}
На этот раз хлопоты возникают с vector, string и deque. Использовать идиому erase/remove не удается, поскольку erase или remove_if нельзя заставить вывести данные в журнал. Более того, вариант с циклом for, только что продемонстрированный для ассоциативных контейнеров, тоже не подходит, поскольку для контейнеров vector, string и deque он приведет к непредсказуемым последствиям. Вспомните, что для этих контейнеров в результате вызова erase становятся недействительными все итераторы, указывающие на удаляемый элемент. Кроме того, недействительными становятся все итераторы после удаляемого элемента, в нашем примере — все итераторы после i. Конструкции вида i++, ++i и т. д. невозможны, поскольку ни один из полученных итераторов не будет действительным.
Следовательно, с vector, string и deque нужно действовать иначе. Мы должны воспользоваться возвращаемым значением erase, которое содержит именно то, что нам требуется — действительный итератор, который указывает на элемент, следующий за удаленным. Иначе говоря, программа выглядит примерно так:
for(ПослКонтейнерlt;intgt;::iterator = cbegin(); i != cend(); ) {
if (badValue(*i)) {
logFilelt;lt;"Erasing "lt;lt;*ilt;lt;'\n';
i=c.erase()); // Сохраняем действительный итератор i,
} // для чего ему присваивается значение,
else ++i; // возвращаемое функцией erase
}
Такое решение превосходно работает, но только для стандартных последовательных контейнеров. По весьма сомнительным причинам (совет 5) функция erase для стандартных ассоциативных контейнеров возвращает void. В этом случае приходится использовать методику с постфиксным приращением итератора, переданного erase. Кстати говоря, подобные различия между последовательными и ассоциативными контейнерами — один из примеров того, почему контейнерно-независимый код обычно считается нежелательным (совет 2).
Какое из этих решений лучше подойдет для контейнера list? Оказывается, в отношении перебора и удаления list может интерпретироваться как vector/string/deque или как ассоциативный контейнер — годятся оба способа. Обычно выбирается первый вариант, поскольку list, как и vector/string/deque, принадлежит к числу последовательных контейнеров. С точки зрения опытного программиста STL программа, в которой перебор и удаление из list производятся по правилам ассоциативных контейнеров, выглядит странно.
Подводя итог всему, о чем рассказывалось в этом совете, мы приходим к следующим заключениям.
Удаление всех объектов с заданным значением:
• контейнеры vector, string и deque: используйте идиому erase/remove;
Удаление всех объектов, соответствующих заданному предикату:
• контейнер vector, string и deque: используйте идиому erase/remove_if;
• контейнер list: используйте list::remove_if;
• стандартный ассоциативный контейнер: используйте remove_copy_if/swap или напишите цикл перебора элементов контейнера, но не забудьте о постфиксном приращении итератора, передаваемого при вызове erase.
Дополнительные операции в цикле (кроме удаления объектов):
• стандартный последовательный контейнер: напишите цикл перебора элементов, но не забывайте обновлять итератор значением, возвращаемым erase при каждом вызове;
• стандартный ассоциативный контейнер: напишите цикл перебора элементов с постфиксным приращением итератора, передаваемого при вызове erase.
Как видите, эффективное удаление элементов контейнера не сводится к простому вызову erase. Правильный подход зависит от того, по какому принципу отбираются удаляемые элементы, в каком контейнере они хранятся и какие дополнительные операции требуется выполнить при удалении. Действуйте осторожно и следуйте рекомендациям данного совета, и все будет нормально. Невнимательность обернется неэффективной работой или непредсказуемым поведением программы.