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

Чтобы этот фрагмент работал, тип умного указателя (например, RCSP>) должен преобразовываться в соответствующий тип встроенного указателя (например 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 из библиотеки С, обеспечивают логарифмическое время поиска, но взамен вы должны предоставить им заранее отсортированные значения.

Вообще говоря, логарифмическое время поиска обеспечивается не всегда. Оно гарантировано лишь в том случае, если алгоритмам передаются итераторы произвольного доступа. Если алгоритм получает менее мощные итераторы (например, двусторонние), он выполняет логарифмическое число сравнений, но работает с линейной сложностью. Это объясняется тем, что без поддержки «итераторной математики» алгоритму необходимо линейное время для перемещения между позициями интервала, в котором производится поиск.