Если контейнер указателей заменяется контейнером умных указателей с подсчетом ссылок, то все трудности, связанные с
remove
, исчезают, а идиома
erase-remove
может использоваться непосредственно:
template<typename T>
class RCSP{…}; // RCSP = "Reference Counting Smart Pointer"
typedef RCSP<Widget> RCSPW; // RCSPW = "RCSP to Widget"
vector<RCSPW> v; //
Создать вектор и заполнить его
… // умными указателями на динамически
v.push_back(RCSPW(new Widget)); // созданные объекты Widget
v.erase(remove_if(v.begin, v.end, // Удалить указатели на объекты
not1(mem_fun(&Widget::isCertified))), // Widget, не прошедшие
v.end); // сертификацию.
// Утечка ресурсов отсутствует!
Чтобы этот фрагмент работал, тип умного указателя (например,
RCSP<Widget>
) должен преобразовываться в соответствующий тип встроенного указателя (например
Widget*
). Дело в том, что контейнер содержит умные указатели, но вызываемая функция (например
Widget::isCertifed
) работает только со встроенными указателями. Если автоматическое преобразование невозможно, компилятор выдаст сообщение об ошибке.
Если в вашем программном инструментарии отсутствует шаблон умного указателя с подсчетом ссылок, попробуйте шаблон
shared_ptr
из библиотеки
Boost
. Начальные сведения о
Boost
приведены в совете 50.
Независимо от того, какая методика будет выбрана для работы с контейнерами динамически созданных указателей — умные указатели с подсчетом ссылок, ручное удаление и обнуление указателей перед вызовом
remove
– подобных алгоритмов или другой способ вашего собственного изобретения — главная тема данного совета остается актуальной: будьте внимательны при использовании
remove
– подобных алгоритмов с контейнерами указателей. Забывая об этой рекомендации, вы своими руками создаете предпосылки для утечки ресурсов.
Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы
Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма
remove
(см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом, алгоритм не применим к интервалам, определяемым итераторами ввода, а также к контейнерам
map/multimap
и некоторым реализациям
set/multiset
(см. совет 22). Аналогично, многие алгоритмы сортировки (см. совет 31) требуют итераторов произвольного доступа и потому не могут применяться к элементам списка.
При нарушении этих правил компилятор выдает длинные, невразумительные сообщения об ошибках (см. совет 49). Впрочем, существуют и другие, более сложные условия. Самым распространенным среди них является то, что
некоторые алгоритмы работают только с интервалами отсортированных значений. Данное требование должно неукоснительно соблюдаться, поскольку нарушение приводит не только к выдаче диагностических сообщений компилятора, но и к непредсказуемому поведению программы на стадии выполнения.
Некоторые алгоритмы работают как с сортированными, так и с несортированными интервалами, но максимальную пользу приносят лишь в первом случае. Чтобы понять, почему сортированные интервалы подходят лучше, необходимо понимать принципы работы этих алгоритмов.
Я знаю, что среди читателей встречаются приверженцы «силового запоминания». Ниже перечислены алгоритмы, требующие обязательной сортировки данных:
binary_search lower_bound
upper_bound equal_range
set_union set_intersection
set_difference set_symmetric_difference
merge inplace_merge
includes
Кроме того, следующие алгоритмы обычно используются с сортированными интервалами, хотя сортировка и не является обязательным требованием:
unique unique_copy
Вскоре будет показано, что в определении «сортированный интервал» кроется одно важное ограничение, но сначала позвольте мне немного прояснить ситуацию с этими алгоритмами. Вам будет проще запомнить, какие алгоритмы работают с сортированными интервалами, если вы поймете, для чего нужна сортировка.
Алгоритмы поиска
binary_search
,
lower_bound
,
upper_bound
и
equal_range
(см. совет 45) требуют сортированные интервалы, потому что их работа построена на бинарном поиске. Эти алгоритмы, как и функция
bsearch
из библиотеки C, обеспечивают логарифмическое время поиска, но взамен вы должны предоставить им заранее отсортированные значения.
Вообще говоря, логарифмическое время поиска обеспечивается не всегда. Оно гарантировано лишь в том случае, если алгоритмам передаются итераторы произвольного доступа. Если алгоритм получает менее мощные итераторы (например, двусторонние), он выполняет логарифмическое число сравнений, но работает с линейной сложностью. Это объясняется тем, что без поддержки «итераторной математики» алгоритму необходимо линейное время для перемещения между позициями интервала, в котором производится поиск.
Четверка алгоритмов
set_unon, set_inesection, set_diffeence
и
set_symmetric_difference
предназначена для выполнения со множествами операций с линейным временем. Почему этим алгоритмам нужны сортированные интервалы? Потому что в противном случае они не справятся со своей задачей за линейное время. Начинает прослеживаться некая закономерность — алгоритмы требуют передачи сортированных интервалов для того, чтобы обеспечить лучшее быстродействие, невозможное при работе с несортированными интервалами. В дальнейшем мы лишь найдем подтверждение этой закономерности.