Читать «Стандарты программирования на С++. 101 правило и рекомендация» онлайн - страница 134
Андрей Александреску
85. Пользуйтесь правильным алгоритмом поиска
Резюме
Данная рекомендация применима к поиску определенного значения в диапазоне. При поиске в неотсортированном диапазоне используйте алгоритмы find
/find_if
или count
/count_if
. Для поиска в отсортированном диапазоне выберите lower_bound
, upper_bound
, equal_range
или (реже) binary_search
. (Вопреки своему имени, binary_search
обычно — неверный выбор.)
Обсуждение
В случае неотсортированных диапазонов, find
/find_if
и count
/count_if
могут за линейное время определить, находится ли данный элемент в диапазоне, и если да, то где именно. Заметим, что алгоритмы find
/find_if
обычно более эффективны, поскольку могут завершить поиск, как только искомый элемент оказывается найден.
В случае сортированных диапазонов лучше использовать алгоритмы бинарного поиска — binary_search, lower_bound
, upper_bound
и equal_range
, которые имеют логарифмическое время работы. Увы, несмотря на свое красивое имя, binary_search
практически всегда бесполезен, поскольку возвращает всего лишь значение типа
bool, указывающее, найден искомый элемент или нет. Обычно вам требуется алгоритм lower_bound
или upper_bound
, или equal_range
, который выдает результаты обоих алгоритмов — и lower_bound
, и upper_bound
(и требует в два раза больше времени).
Алгоритм lower_bound
возвращает итератор, указывающий на первый подходящий элемент (если таковой имеется) или на позицию, где он мог бы быть (если такого элемента нет); последнее полезно для поиска верного места для вставки новых значений в отсортированную последовательность. Алгоритм upper_bound
возвращает итератор, указывающий на элемент, следующий за последним найденным элементом (если таковой имеется), т.е. на позицию, куда можно добавить следующий эквивалентный элемент; это полезно при поиске правильного места для вставки новых значений в отсортированную последовательность, чтобы поддерживать упорядоченность, при которой равные элементы располагаются в последовательности в порядке их вставки.
Для сортированных диапазонов в качестве быстрой версии count(first, last, value);
лучше использовать пару вызовов:
p = equal_range(first, last, value);
distance(p.first, p.second);
При поиске в ассоциативном контейнере лучше использовать вместо алгоритмов-не членов функции-члены с тем же именем. Функции-члены обычно более эффективны; например, функция-член count
выполняется за логарифмическое время (так что, кстати, нет никаких оснований заменять ее вызовом equal_range
с последующим distance, что имеет смысл для функции count, не являющейся членом).
Ссылки
86. Пользуйтесь правильным алгоритмом сортировки
Резюме
При сортировке вы должны четко понимать, как работает каждый из сортирующих алгоритмов, и использовать наиболее дешевый среди тех, которые пригодны для решения вашей задачи.