Скотт Мейерс - Эффективное использование STL

Для блоковых контейнеров ( 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).