Эффективное использование STL, Мейерс Скотт

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

на обложку

Мейерс Скотт

Шрифт:

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

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

предназначена для выполнения со множествами операций с линейным временем. Почему этим алгоритмам нужны сортированные интервалы? Потому что в противном случае они не справятся со своей задачей за линейное время. Начинает прослеживаться некая закономерность — алгоритмы требуют передачи сортированных интервалов для того, чтобы обеспечить лучшее быстродействие, невозможное при работе с несортированными интервалами. В дальнейшем мы лишь найдем подтверждение этой закономерности.