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

В данном случае элементом является auto_ptr, поэтому в результате скопированному указателю auto_ptr (тому, который хранится в векторе) присваивается NULL. Более того, когда pivotValue выходит из области видимости, происходит автоматическое удаление объекта Widget, на который pivotValue ссылается. Итак, после вызова sort содержимое вектора изменяется и по меньшей мере один объект Widget удаляется. Вследствие рекурсивности алгоритма быстрой сортировки существует вероятность того, что сразу нескольким элементам вектора будет присвоено значение NULL и сразу несколько объектов Widget будут удалены, поскольку опорный элемент копируется на каждом уровне рекурсии. . ^ Подобные ловушки весьма зловредны, и Комитет по стандартизации постарался, чтобы вы заведомо не попадались в них. Уважайте их труд и никогда не создавайте контейнеры auto_ptr, даже если ваша платформа STL это позволяет.

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

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

АссоцКонтейнер с;//с - один из стандартных

// ассоциативных контейнеров

АссоцКонтейнер goodValues: // Временный контейнер для хранения

// элементов, оставшихся после удаления

remove_copy_i f(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 в заголовке цикла fo r).

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

АссоцКонтейнер с;

for(АссоцКонтейнер:: iterator i=c.begin();// Третья часть заголовка

i!=c.end(); // цикла for пуста; i теперь

/* пусто */) {// изменяется внутри цикла

if (badValue(*i)) c.erase(i++);// Для удаляемых элементов

else ++i;// передать erase текущее

}// значение i и увеличить i.

// Для остающихся элементов // просто увеличить i