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

Мейерс Скотт

list<int> li; // Создать список

… // Заполнить данными

li.remove(99); // Удалить все элементы со значением 99.

// Команда производит фактическое удаление

// элементов из контейнера, поэтому размер li

// может измениться

Честно говоря, выбор имени

remove

в данном случае выглядит непоследовательно. В ассоциативных контейнерах аналогичная функция называется

erase

, поэтому в контейнере

list

функцию

remove

тоже следовало

назвать

erase

. Впрочем, этого не произошло, поэтому остается лишь смириться. Мир, в котором мы живем, не идеален, но другого все равно нет. Как упоминается в совете 44, для контейнеров

list

вызов функции

remove

более эффективен, чем применение идиомы

erase/remove

.

Как только вы поймете, что алгоритм

remove

не может «по-настоящему» удалять объекты из контейнера, применение его в сочетании с

erase

войдет в привычку. Не забывайте, что

remove

— не единственный алгоритм, к которому относится это замечание. Существуют два других remove-подобных алгоритма:

remove_if

и

unique

.

Сходство между

remove

и

remove_if

настолько прямолинейно, что я не буду на нем останавливаться, но алгоритм

unique

тоже похож на

remove

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

unique

должен сопровождаться парным вызовом

erase

. В контейнере

list

также предусмотрена функция

unique

, производящая фактическое удаление смежных дубликатов. По эффективности она превосходит связку

erase-unique

.

Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей

Предположим, мы динамически создаем ряд объектов

Widget

и сохраняем полученные указатели в векторе:

class Widget {

public:

 …

 bool isCertified const; // Функция сертификации объектов Widget

}

vector<Widget*> v; // Создать вектор и заполнить его указателями

… // на динамически созданные объекты Widget

v.push_back(new Widget);

…

Поработав с

v

в течение некоторого времени, вы решаете избавиться от объектов

Widget

, не сертифицированных функцией

Widget

, поскольку они вам не нужны. С учетом рекомендаций, приведенных в совете 43 (по возможности использовать алгоритмы вместо циклов), и того, что говорилось в совете 32 о связи

remove

и

erase

, возникает естественное желание использовать идиому

erase-remove

, хотя в данном случае используется алгоритм

remove_if

:

v.erase(remove_if(v.begin, v.end, // Удалить указатели на объекты

 not1(mem_fun(&Widget::isCertified))), // Widget, непрошедшие

 v.end); // сертификацию.

// Информация о mem_fun

// приведена в совете 41.

Внезапно у вас возникает беспокойство по поводу вызова

erase

, поскольку вам смутно припоминается совет 7 — уничтожение указателя в контейнере не приводит к удалению объекта, на который он ссылается. Беспокойство вполне оправданное, но в этом случае оно запоздало. Вполне возможно, что к моменту вызова

erase

утечка ресурсов уже произошла. Прежде чем беспокоиться о вызове

erase

, стоит обратить внимание на

remove_if

.

Допустим, перед вызовом

remove_if

вектор

v

имеет следующий вид:

После вызова

remove_if

вектор выглядит примерно так (с итератором, возвращаемым при вызове

remove_if

):

Если подобное превращение кажется непонятным, обратитесь к совету 32, где подробно описано, что происходит при вызове

remove

(в данном случае —

remove_if

).

Причина утечки ресурсов очевидна. «Удаленные» указатели на объекты B и C были перезаписаны «оставшимися» указателями. На два объекта

Widget

не существует ни одного указателя, они никогда не будут удалены, а занимаемая ими память расходуется впустую.

После выполнения

remove_if

и

erase

ситуация выглядит следующим образом:

Здесь утечка ресурсов становится особенно очевидной, и к настоящему моменту вам должно быть ясно, почему алгоритмы

remove

и его аналоги (

remove_if

и

unique

) не рекомендуется вызывать для контейнеров, содержащих указатели на динамически выделенную память. Во многих случаях разумной альтернативой является алгоритм

partition

(см. совет 31).

Если без

remove

никак не обойтись, одно из решений проблемы заключается в освобождении указателей на несертифицированные объекты и присваивании им

null

перед применением идиомы

erase-remove

с последующим удалением из контейнера всех

null

– указателей:

void delAndNullifyUncertified(Widget*& pWidget) // Если объект *pWidget

{ // не сертифицирован,

 if (!pWidget->isCertified) { //удалить указатель

delete pWidget; //и присвоить ему null

pWidget = 0;

}

 for_each(v.begin, v.end, // Удалить и обнулить все указатели на

delAndNullifyUncertified); // все указатели на объекты, не прошедшие

// сертификацию

v.erase(remove(v.begin, v.end, // Удалить из v указатели null;

 static_cast<Widget*>(0)), // 0 преобразуется в указатель, чтобы C++

 v.end); // правильно определял тип третьего параметра

Приведенное решение предполагает, что вектор не содержит

null

– указателей, которые бы требовалось сохранить. В противном случае вам, вероятно, придется написать собственный цикл, который будет удалять указатели в процессе перебора. Удаление элементов из контейнера в процессе перебора связано с некоторыми тонкостями, поэтому перед реализацией этого решения желательно прочитать совет 9.