Совет 45. Различайте алгоритмы count, find, binary search, lower bound, upper bound и equaLrange

Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary search, lower bound, upperbound и equal range. Как же принять верное решение?

Очень просто. Основными критериями должны быть скорость и простота.

Временно предположим, что границы интервала поиска обозначены итераторами. Слзай с поиском во всем контейнере будет рассмотрен ниже.

При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами binary search, lower bound, upper bound и equal range для проведения быстрого поиска (обычно с логарифмической сложностью - см. совет 34). Если интервал не отсортирован, выбор ограничивается линейными алгоритмами count, count if, f i nd и f i nd i f. В дальнейшем описании i f-версии алгоритмов count и f i nd игнорируются, как и разновидности binary search, 1ower bound, upper bound и equal range, которым при вызове передается предикат. Алгоритм поиска выбирается по одним и тем же соображениям независимо от того, используете ли вы стандартный предикат или задаете свой собственный.

Итак, в несортированных интервалах выбор ограничивается алгоритмами count и find. Эти алгоритмы решают несколько отличающиеся задачи, к которым следует присмотреться повнимательнее. Алгоритм count отвечает на вопрос: Присутствует ли заданное значение, и если присутствует - то в каком количестве экземпляров? . Для алгоритма f i nd вопрос звучит так: Присутствует ли заданное значение, и если присутствует - то где именно?

Допустим, вы просто хотите проверить, присутствует ли в списке некоторое значение w класса Wi dget. При использовании алгоритма count решение выглядит так:

list<Widget> Iw; Список объектов Widget

Widget w; Искомое значение класса Widget

if (count(lw.begin().lw.end().w)){

Значение w присутствует в Iw

} else {

Значение не найдено

В приведенном фрагменте продемонстрирована стандартная идиома: применение count для проверки существования. Алгоритм count возвращает либо ноль, либо положительное число; в программе ненулевое значение интерпретируется как логическая истина, а ноль - как логическая ложь. Возможно, следующая конструкция более четко выражает суть происходящего:

if (countdw.beginC).Iw.endO.w)!=0)...

Некоторые программисты предпочитают эту запись, но неявное преобразование, как в приведенном выше примере, встречается достаточно часто.

Решение с алгоритмом find выглядит чуть сложнее, поскольку возвращаемое значение приходится сравнивать с конечным итератором списка:

i f(find(lw.begin().Iw.endC),w)!=1w.end()){

} else { }

В контексте проверки существования идиоматическое использование count чуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку find при обнаружении искомого значения немедленно прекращает поиск, а count продолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные хлопоты, связанные с программированием find.

Впрочем, простой проверки существования во многих слзаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find:

list<Widget>::iterator i = finddw.beginO.lw.endO.w); if (1!=lw.end()){

Успешный поиск, i указывает на первый экземпляр

} else {

Значение не найдено

При работе с сортированными интервалами существуют и другие варианты, и им определенно стоит отдать предпочтение. Алгоритмы count и find работают с линейной сложностью, тогда как алгоритмы поиска в сортированных интервалах (binary search, lower bound, upper bound и equal range) обладают логарифмической сложностью.

Переход от несортированных интервалов к сортированным влечет за собой изменение критерия сравнения двух величин. Различия между критериями подробно описаны в совете 19, поэтому я не стану повторяться и замечу, что алгоритмы count и f i nd используют критерий равенства, а алгоритмы bi nary search, 1 ower bound, upperbound и equal range основаны на критерии эквивалентности.

Присутствие величины в сортированном интервале проверяется алгоритмом binarysearch. В отличие от функции bsearch из стандартной библиотеки С (а значит, и стандартной библиотеки С++), алгоритм binary search возвращает только bool. Алгоритм отвечает на вопрос: Присутствует ли заданное значение в интервале? , и возможны только два ответа: да и нет . Если вам понадобится дополнительная информация, выберите другой алгоритм.

Пример применения binary search к сортированному вектору (преимущества сортированных векторов описаны в совете 23):

vector<Widget> vw: Создать вектор, заполнить

данными и отсортировать

sortCvw.beginO .vw.endO):

Значение не найдено

} else { }

В большинстве случаев такая конструкция работает, но в действительности она содержит ошибку. Присмотритесь к проверяемому условию:

if (i!=vw.end()&&*i=w){

В этом условии проверяется равенство, тогда как lower bound использует при поиске критерий эквивалентности. Как правило, результаты проверки по двум критериям совпадают, но, как показано в совете 19, это не всегда так. В таких ситуациях приведенный выше фрагмент не работает.

Чтобы исправить ошибку, необходимо убедиться в том, что итератор, полученный от 1 ower bound, указывает на объект со значением, эквивалентным искомому. Проверку можно выполнить вручную (в совете 19 показано, как это делается, а в совете 24 приведен пример ситуации, когда такое решение оправданно), однако сделать это непросто, поскольку при этом должна использоваться та же функция сравнения, как и при вызове 1 owerbound. В общем случае мы имеем дело с произвольной

Widget w: Искомое значение

i f(bi nary search(vw.begi n().vw.end().w)) {

Значение w присутствует в vw

} else {

Значение не найдено

Если у вас имеется сортированный интервал и вы ищете ответ на вопрос; Присутствует ли заданное значение в интервале, и если присутствует - то где именно? , следует использовать алгоритм equal range, хотя на первый взгляд кажется, что вам нужен алгоритм 1 owerbound. Вскоре мы вернемся к equal range, а пока проанализируем поиск в интервалах с применением алгоритма 1 ower bound.

При поиске заданной величины в интервале алгоритм lowerbound возвращает итератор, указывающий на первый экземпляр этой величины (в слзае успешного поиска) или на правильную позицию вставки (в случае неудачи). Таким образом, алгоритм lower bound отвечает на вопрос: Присутствует ли заданное значение в интервале? Если присутствует, то где находится первый экземпляр, а если нет - где он должен находиться? . Как и в случае с алгоритмом find, результат lower bound необходимо дополнительно проверить и убедиться в том, что он указывает на искомое значение. Но в отличие от f i nd, его нельзя просто сравнить с конечным итератором. Вместо этого приходится брать объект, идентифицированный алгоритмом 1 ower bound, и проверять, содержит ли он искомое значение.

Многие программисты используют 1 ower bound примерно так:

vector<Widget>::iterator i=1ower bound(vw.begin().vw.endO.w):

if (i!=vw.endO&&*i=w){ Убедиться в том, что i указывает

на объект, и этот объект имеет искомое значение. Ошибка!!!!

Значение найдено, i указывает на первый экземпляр объекта с этим значением