85. Пользуйтесь правильным алгоритмом поиска

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, не являющейся членом).

Ссылки

[Austern99] §13.2-3 • [Bentley00] §13 • [Meyers01] §34, §45 • [Musser01] §22.2 • [Stroustrup00] §17.1.4.1, §18.7.2