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

Мейерс Скотт

АссоцКонтейнер<int> с;

…

for(АссоцКонтейнер<int>::iterator i=cbegin; // Наглядный, бесхитростный

i!=cend; // и ошибочный код, который

++i) { // стирает все элементы с

 if (badValue(*i)) c.erase(i); // для которых badValue

} // возвращает true.

// Не поступайте так!

Выполнение этого

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

c.erase(i)

итератор

i

становится недействительным. Для нашего цикла это фатально, поскольку после вызова

erase

итератор

i

увеличивается (

++i

в заголовке цикла

for

).

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

erase

. Это проще всего сделать постфиксным увеличением i при вызове:

АссоцКонтейнер<int> с;

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

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

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

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

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

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

// Для остающихся элементов

// просто увеличить i

Новый вариант вызова

erase

работает, поскольку выражение

i++

равно старому значению

i

, но у него имеется побочный эффект — приращение

i

. Таким образом, мы передаем старое (не увеличенное) значение

i

и увеличиваем

i

перед вызовом

erase

. Именно это нам и требовалось. Хотя это решение выглядит просто, лишь немногие программисты предложат его с первой попытки.

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

badValue

возвращает

true

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

Для ассоциативных контейнеров задача решается очень просто, поскольку она требует лишь тривиальной модификации созданного цикла:

ofstream logFile;// Файл журнала

АссоцКонтейнер<int> с;

…

for(АссоцКонтейнер<int>::iterator i=c.begin;// Заголовок цикла остается

i!=c.end;) { // без изменений

 if(badValue(*i)) {

logFile<<"Erasing "<<*i<<'\n'; // Вывод в журнал

c.erase(i++);// Удаление

} else ++i;

}

На этот раз хлопоты возникают с

vector

,

string

и

deque

. Использовать идиому

erase/remove

не удается, поскольку

erase

или

remove_if

нельзя заставить вывести данные в журнал. Более того, вариант с циклом

for

, только что продемонстрированный для ассоциативных контейнеров, тоже не подходит, поскольку для контейнеров

vector

,

string

и

deque

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

erase

становятся недействительными все итераторы, указывающие на удаляемый элемент. Кроме того, недействительными становятся все итераторы после удаляемого элемента, в нашем примере — все итераторы после

i

. Конструкции вида

i++

,

++i

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

Следовательно, с

vector

,

string

и

deque

нужно действовать иначе. Мы должны воспользоваться возвращаемым значением erase, которое содержит именно то, что нам требуется — действительный итератор, который указывает на элемент, следующий за удаленным. Иначе говоря, программа выглядит примерно так:

for(ПослКонтейнер<int>::iterator = cbegin; i != cend; ) {

 if (badValue(*i)) {

logFile<<"Erasing "<<*i<<'\n';

i=c.erase); // Сохраняем действительный итератор i,

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

 else ++i; // возвращаемое функцией erase

}

Такое решение превосходно работает, но только для стандартных последовательных контейнеров. По весьма сомнительным причинам (совет 5) функция

erase

для стандартных ассоциативных контейнеров возвращает

void

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

erase

. Кстати говоря, подобные различия между последовательными и ассоциативными контейнерами — один из примеров того, почему контейнерно-независимый код обычно считается нежелательным (совет 2).

Какое из этих решений лучше подойдет для контейнера

list

? Оказывается, в отношении перебора и удаления

list

может интерпретироваться как

vector/string/deque

или как ассоциативный контейнер — годятся оба способа. Обычно выбирается первый вариант, поскольку

list

, как и

vector/string/deque

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

list

производятся по правилам ассоциативных контейнеров, выглядит странно.

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

Удаление всех объектов с заданным значением:

• контейнеры

vector

,

string

и

deque

: используйте идиому

erase/remove

;

• контейнер

list

: используйте

list::remove

;

• стандартный ассоциативный контейнер: используйте функцию

erase

.

Удаление всех объектов, соответствующих заданному предикату: