Эффективное использование STL - [22]

Для блоковых контейнеров (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, после чего содержимое двух контейнеров меняется местами:

АссоцКонтейнер с;//с - один из стандартных
…                     // ассоциативных контейнеров
АссоцКонтейнер goodValues: // Временный контейнер для хранения
                                // элементов, оставшихся после удаления
remove_copy_if(c.begin(), c.end(), // Скопировать оставшиеся элементы
 inserter(goodValues,              // из с в goodValues
 goodValues.end()), badValue);
с.swap(goodValues);// Поменять содержимое с и goodValues

У подобного решения имеется недостаток — необходимость копирования элементов, остающихся после удаления. Такое копирование может обойтись дороже, чем нам хотелось бы.

От этих затрат можно избавиться за счет непосредственного удаления элементов из исходного контейнера. Но поскольку в ассоциативных контейнерах отсутствует функция, аналогичная remove_if, придется перебирать все элементы с в цикле и принимать решение об удалении текущего элемента.

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

АссоцКонтейнер с;
…
for(АссоцКонтейнер::iterator i=cbegin(); // Наглядный, бесхитростный
    i!=cend();                                // и ошибочный код, который
    ++i) {                                    // стирает все элементы с
 if (badValue(*i)) c.erase(i);                // для которых badValue
}                                             // возвращает true.
                                              // Не поступайте так!

Выполнение этого фрагмента приводит к непредсказуемым результатам. При стирании элемента контейнера все итераторы, указывающие на этот элемент, становятся недействительными. Таким образом, после возврата из c.erase(i) итератор i становится недействительным. Для нашего цикла это фатально, поскольку после вызова erase итератор i увеличивается (++i в заголовке цикла for).

Проблема решается просто: необходимо позаботиться о том, чтобы итератор переводился на следующий элемент с перед вызовом