Скотт Мейерс - Эффективное использование STL
Следовательно, с 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.
Удаление всех объектов, соответствующих заданному предикату:
• контейнер vector, string и deque: используйте идиому erase/remove_if;
• контейнер list: используйте list::remove_if;
• стандартный ассоциативный контейнер: используйте remove_copy_if/swap или напишите цикл перебора элементов контейнера, но не забудьте о постфиксном приращении итератора, передаваемого при вызове erase.
Дополнительные операции в цикле (кроме удаления объектов):
• стандартный последовательный контейнер: напишите цикл перебора элементов, но не забывайте обновлять итератор значением, возвращаемым erase при каждом вызове;
• стандартный ассоциативный контейнер: напишите цикл перебора элементов с постфиксным приращением итератора, передаваемого при вызове erase.
Как видите, эффективное удаление элементов контейнера не сводится к простому вызову erase. Правильный подход зависит от того, по какому принципу отбираются удаляемые элементы, в каком контейнере они хранятся и какие дополнительные операции требуется выполнить при удалении. Действуйте осторожно и следуйте рекомендациям данного совета, и все будет нормально. Невнимательность обернется неэффективной работой или непредсказуемым поведением программы.
Совет 10. Помните о правилах и ограничениях распределителей памяти
Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных операционных системах (например, DOS и ее зловредных потомках), однако эта попытка провалилась. Распределители также должны были упростить разработку объектных диспетчеров памяти, но вскоре выяснилось, что такой подход снижает эффективность работы некоторых компонентов STL. Чтобы избежать снижения быстродействия. Комитет по стандартизации C++ включил в Стандарт положение, которое практически выхолостило объектные распределители памяти, но одновременно выражало надежду, что от этой операции их потенциальные возможности не пострадают.
Но это еще не все. Распределители памяти STL, как и operator new с operator new[], отвечают за выделение (и освобождение) физической памяти, однако их клиентский интерфейс имеет мало общего с клиентским интерфейсом operator new, operator new[] и даже malloc. Наконец, большинство стандартных контейнеров никогда не запрашивает память у своих распределителей. Еще раз подчеркиваю — никогда. В результате распределители производят довольно странное впечатление.
Впрочем, это не их вина, и, конечно же, из этого факта вовсе не следует делать вывод о бесполезности распределителей. Тем не менее, прежде чем описывать области применения распределителей (эта тема рассматривается в совете 11), я должен объяснить, для чего они не подходят. Существует целый ряд задач, которые только на первый взгляд могут решаться при помощи распределителей. Прежде чем вступать в игру, желательно изучить границы игрового поля, в противном случае вы наверняка упадете и получите травму. Кроме того, из-за экзотических особенностей распределителей сам процесс обобщения выглядит весьма поучительным и занимательным. По крайней мере, я на это надеюсь.
Перечень особенностей распределителей начинается с рудиментарных определений типов для указателей и ссылок. Как упоминалось выше, распределители изначально были задуманы как абстракции для моделей памяти, поэтому казалось вполне логичным возложить на них обеспечение определения типов (typedef) для указателей и ссылок в определяемой модели. В стандарте C++ стандартный распределитель объектов типа T (allocator<T>) предоставляет определения allocator<T>::pointer и allocator<T>::reference, поэтому предполагается, что пользовательские распределители также будут предоставлять эти определения.
Ветераны C++ немедленно почуют неладное, поскольку в C++ не существует средств для имитации ссылок. Для этого пришлось бы перегрузить operator. (оператор «точка»), а это запрещено. Кроме того, объекты, работающие как ссылки, являются примером промежуточных объектов (proxy objects), а использование промежуточных объектов приводит к целому ряду проблем, одна из которых описана в совете 18. Подробное описание промежуточных объектов приведено в совете 30 книги «More Effective C++».
В случае распределителей STL бессмысленность определений типов для указателей и ссылок объясняется не техническими недостатками промежуточных объектов, а следующим фактом: Стандарт разрешает считать, что определение типа pointer любого распределителя является синонимом T*, а определение типа reference — синонимом T&. Да, все верно, разработчики библиотек могут игнорировать определения и использовать указатели и ссылки напрямую! Таким образом, даже если вам удастся написать распределитель с новыми определениями для указателей и ссылок, никакой пользы от этого не будет, поскольку используемая реализация STL запросто сможет эти определения проигнорировать. Интересно, не правда ли?
Пока вы не успели осмыслить этот пример странностей стандартизации, я приведу следующий. Распределители являются объектами, из чего следует, что они могут обладать собственными функциями, вложенными типами и определениями типов (такими как pointer и reference). Однако в соответствии со Стандартом реализация STL может предполагать, что все однотипные объекты распределителей эквивалентны и почти всегда равны. Разумеется, это обстоятельство объяснялось вескими причинами. Рассмотрим следующий фрагмент:
template<typename T> // Шаблон пользовательского
// распределителя памяти
class SpecialAllocator{...};
typedef SpecialAllocator<Widget> SAW; // SAW = "SpecialAllocator
//for Widgets"
list<Widget.SAW> L1;
list<Widget.SAW> L2;
L1.splice(L1.begin(), L2);
Вспомните: при перемещении элементов из одного контейнера listв другой функцией splice данные не копируются. Стоит изменить значения нескольких указателей, и узлы, которые раньше находились в одном списке, оказываются в другом, поэтому операция врезки выполняется быстро и защищена от исключений. В приведенном примере узлы, ранее находившиеся в L2, после вызова splice перемещаются в L1.
Разумеется, при уничтожении контейнера L1 должны быть уничтожены все его узлы (с освобождением занимаемой ими памяти). А поскольку контейнер теперь содержит узлы, ранее входившие в L2, распределитель памяти L1 должен освободить память, ранее выделенную распределителем L2. Становится ясно, почему Стандарт разрешает программистам STL допускать эквивалентность однотипных распределителей. Это сделано для того, чтобы память, выделенная одним объектом-распределителем (таким как L2), могла безопасно освобождаться другим объектом-распределителем (таким как L1). Отсутствие подобного допущения привое бы к значительному усложнению реализации врезки и к снижению ее эффективности (кстати, операции врезки влияют и на другие компоненты STL, один из примеров приведен в совете 4).
