Подобные ловушки весьма зловредны, и Комитет по стандартизации постарался, чтобы вы заведомо не попадались в них. Уважайте их труд и никогда не создавайте контейнеры
auto_ptr
, даже если ваша платформа STL это позволяет.
Впрочем, это вовсе не исключает возможности создания контейнеров умных указателей. Контейнеры умных указателей вполне допустимы. В совете 50 описано, где найти умные указатели, хорошо работающие в контейнерах STL, просто
auto_ptr
не относится к их числу.
Совет 9. Тщательно выбирайте операцию удаления
Допустим,
у нас имеется стандартный контейнер STL
с
, содержащий числа типа
int
:
контейнер<int> с;
и вы хотите удалить из него все объекты со значением 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
, после чего содержимое двух контейнеров меняется местами:
АссоцКонтейнер<int> с;//с - один из стандартных
… // ассоциативных контейнеров
АссоцКонтейнер<int> goodValues: // Временный контейнер для хранения
// элементов, оставшихся после удаления
remove_copy_if(c.begin, c.end, // Скопировать оставшиеся элементы
inserter(goodValues, // из с в goodValues
goodValues.end), badValue);
с.swap(goodValues);// Поменять содержимое с и goodValues
У подобного решения имеется недостаток — необходимость копирования элементов, остающихся после удаления. Такое копирование может обойтись дороже, чем нам хотелось бы.
От этих затрат можно избавиться за счет непосредственного удаления элементов из исходного контейнера. Но поскольку в ассоциативных контейнерах отсутствует функция, аналогичная
remove_if
, придется перебирать все элементы с в цикле и принимать решение об удалении текущего элемента.
С концептуальной точки зрения эта задача несложна, да и реализуется она просто. К сожалению, решение, которое первым приходит в голову, редко бывает правильным. Вероятно, многие программисты предложат следующий вариант: