Очень просто. Основными критериями должны быть скорость и простота.
Временно предположим, что границы интервала поиска обозначены итераторами. Случай с поиском во всем контейнере будет рассмотрен ниже.
При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами
binary_search
,
lower_bound
,
upper_bound
и
equal_range
для проведения быстрого поиска (обычно с логарифмической сложностью — см. совет 34). Если интервал не отсортирован, выбор ограничивается линейными алгоритмами count,
count_if
,
find
и
find_if
. В дальнейшем описании
_if
– версии алгоритмов
count
и
find
игнорируются, как и разновидности
binary_search
,
lower_bound
,
upper_bound
и
equal_range
, которым при вызове передается предикат. Алгоритм поиска выбирается по одним и тем же соображениям независимо от того, используете ли вы стандартный предикат или задаете свой собственный.
Итак, в несортированных интервалах выбор ограничивается алгоритмами
count
и
find
. Эти алгоритмы решают несколько отличающиеся задачи, к которым следует присмотреться повнимательнее. Алгоритм
count
отвечает на вопрос: «Присутствует ли заданное значение, и если присутствует — то в каком количестве экземпляров?». Для алгоритма
find
вопрос звучит так: «Присутствует ли заданное значение, и если присутствует — то где именно?»
Допустим, вы просто хотите проверить, присутствует ли в списке некоторое значение
w
класса
Widget
. При использовании алгоритма count решение выглядит так:
list<Widget> lw; // Список объектов Widget
Widget w; // Искомое значение класса Widget
…
if (count(lw.begin, lw.end, w)) {
… // Значение w присутствует в lw
} else {
… // Значение не найдено
}
В приведенном фрагменте продемонстрирована стандартная идиома: применение
count
для проверки существования. Алгоритм
count
возвращает либо ноль, либо положительное число; в программе ненулевое значение интерпретируется как логическая истина, а ноль — как логическая ложь. Возможно, следующая конструкция более четко выражает суть происходящего:
if (count(lw.begin, lw.end, w) != 0)…
Некоторые программисты предпочитают эту запись, но неявное преобразование, как в приведенном выше примере, встречается достаточно часто.
Решение с алгоритмом
find
выглядит чуть сложнее, поскольку возвращаемое значение приходится сравнивать с конечным итератором списка:
if (find(lw.begin, lw.end, w) != lw.end) {
…
} else {
…
}
В контексте проверки существования идиоматическое использование
count
чуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку
find
при обнаружении искомого значения немедленно прекращает поиск, a
count
продолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные
хлопоты, связанные с программированием
find
.
Впрочем, простой проверки существования во многих случаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find:
list<Widget>::iterator i = find(lw.begin, lw.end, w);
if (i!=lw.end) {
… // Успешный поиск, i указывает на первый экземпляр
} else {
… // Значение не найдено
}
При работе с сортированными интервалами существуют и другие варианты, и им определенно стоит отдать предпочтение. Алгоритмы
count
и
find
работают с линейной сложностью, тогда как алгоритмы поиска в сортированных интервалах (
binary_search
,
lower_bound
,
upper_bound
и
equal_range
) обладают логарифмической сложностью.
Переход от несортированных интервалов к сортированным влечет за собой изменение критерия сравнения двух величин. Различия между критериями подробно описаны в совете 19, поэтому я не стану повторяться и замечу, что алгоритмы
count
и
find
используют критерий равенства, а алгоритмы
binary_search
,
lower_bound
,
upper_bound
и
equal_range
основаны на критерии эквивалентности.
Присутствие величины в сортированном интервале проверяется алгоритмом
binary_search
. В отличие от функции
bsearch
из стандартной библиотеки C (а значит, и стандартной библиотеки C++), алгоритм
binary_search
возвращает только
bool
. Алгоритм отвечает на вопрос: «Присутствует ли заданное значение в интервале?», и возможны только два ответа: «да» и «нет». Если вам понадобится дополнительная информация, выберите другой алгоритм.
Пример применения
binary_search
к сортированному вектору (преимущества сортированных векторов описаны в совете 23):
vector<Widget> vw; // Создать вектор, заполнить
… // данными и отсортировать
sort(vw.begin, vw.end);
Widget w; // Искомое значение
…
if (binary_search(vw.begin, vw.end, w)) {
… // Значение w присутствует в vw
} else {
… // Значение не найдено
}
Если у вас имеется сортированный интервал и вы ищете ответ на вопрос: «Присутствует ли заданное значение в интервале, и если присутствует — то где именно?», следует использовать алгоритм
equal_range
, хотя на первый взгляд кажется, что вам нужен алгоритм
lower_bound
. Вскоре мы вернемся к
equal_range
, а пока проанализируем поиск в интервалах с применением алгоритма