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

list 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::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 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, а пока проанализируем поиск в интервалах с применением алгоритма lower_bound.

При поиске заданной величины в интервале алгоритм lower_boundвозвращает итератор, указывающий на первый экземпляр этой величины (в случае успешного поиска) или на правильную позицию вставки (в случае неудачи). Таким образом, алгоритм lower_boundотвечает на вопрос: «Присутствует ли заданное значение в интервале? Если присутствует, то где находится первый экземпляр, а если нет — где он должен находиться?». Как и в случае с алгоритмом find, результат lower_boundнеобходимо дополнительно проверить и убедиться в том, что он указывает на искомое значение. Но в отличие от find, его нельзя просто сравнить с конечным итератором. Вместо этого приходится брать объект, идентифицированный алгоритмом lower_bound, и проверять, содержит ли он искомое значение.