Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range

Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range

Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary_search, lower_bound, upper_bound и equal_range. Как же принять верное решение?

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

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

При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами 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) !=w.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 из стандартной библиотеки С (а значит, и стандартной библиотеки С++), алгоритм 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, а пока проанализируем поиск в интервалах с применением алгоритма lower_bound.

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

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

vector<Widget>::iterator =lower_bound(vw,begin().vw.end(),w):

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

// на объект, и этот объект имеет искомое

// значение. Ошибка!!!!

// Значение найдено, i указывает на первый

// экземпляр объекта с этим значением

} else {

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

}

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

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

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

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

функцией (или объектом функции). При передаче lower_bound функции сравнения эта же функция должна использоваться и в «ручной» проверке эквивалентности; следовательно, при изменении функции сравнения, передаваемой lower_rbound, вам придется внести соответствующие изменения в проверку эквивалентности. В принципе, синхронизировать функции сравнения не так уж сложно, но об этом необходимо помнить, а при программировании хлопот и без этого хватает.

Существует простое решение: воспользуйтесь алгоритмом equal_range. Алгоритм возвращает пару итераторов; первый совпадает с итератором, возвращаемым lower_bound, а второй совпадает с итератором, возвращаемым upper_bound (то есть указывает в позицию за интервалом значений, эквивалентных искомому). Таким образом, алгоритм equal_range возвращает пару итераторов, обозначающих интервал значений, эквивалентных искомому. Согласитесь, имя алгоритма выбрано довольно удачно. Возможно, правильнее было бы назвать его equvalent_range, но и equal _range воспринимается неплохо.

Относительно возвращаемого значения equal_range необходимо сделать два важных замечания. Если два итератора совпадают, это говорит о том, что интервал пуст, а значение не найдено. По этому факту можно судить о том, было ли найдено совпадение. Пример:

vector<Widget> vw;

sort (vw.begin(), v.end());

typedef vector<Widget>::iterator VWIter; // Вспомогательные

typedef pair<VWIter,VWIter> VWIterPair: // определения типов

VWIterPar p = equal_range(vw.begin(),vw.end(),w);

if (p.first != p.second){// Если equal_range возвращает

// непустой интервал...

// Значение найдено, p.first

// указывает на первый элемент

// интервала, а p.second -

// на позицию за последним элементом

} else {

// Значение не найдено, p.first

// и p.second указывают на точку

// вставки искомого значения

}

В этом фрагменте используется только критерий эквивалентности, поэтому он всегда верен.

Другая особенность возвращаемого значения equal_range заключается в том, что расстояние между двумя итераторами равно количеству объектов в интервале, то есть количеству объектов, эквивалентных искомому объекту. В результате equal_range не только выполняет функции find для сортированных интервалов, но и заменяет count. Например, поиск в vw объектов Widget, эквивалентных w, с последующим выводом их количества может выполняться следующим образом:

VWIterPair р = equal_range(vw.begin(),vw.end(),w);

cout « "There are " « distance(p.first,p.second)

« " elements in vw equivalent to w.";

До настоящего момента предполагалось, что в интервале ищется некоторое значение, но есть ситуации, в которых возникает задача поиска граничной позиции. Предположим, у нас имеется класс Timestamp и вектор объектов Timestamp, отсортированный от «старых» объектов к «новым»:

class Timestamp {...};

bool operator<(const Timestamp& lhs. //Проверяет, предшествует ли

const Timestamp& rhs); // объект lhs объекту rhs по времени

vector<Timestamp> vt;// Создать вектор, заполнить данными

// и отсортировать так, чтобы

sort(vt.begin(),vt.end()); // "старые" объекты предшествовали "новым"

Предположим, из vt требуется удалить все объекты, предшествующие некоторому пороговому объекту ageLimit. В данном случае не нужно искать в vt объект Timestamp, эквивалентный ageLimit, поскольку объекта с точно совпадающим значением может и не быть. Вместо этого в vt ищется граничная позиция, то есть первый элемент, не старший ageLimit. Задача решается элементарно, поскольку алгоритм lowebound предоставляет всю необходимую информацию:

Timestamp ageLimit;

vt.erase(vt.begin().lower_bound(vt.begin(),// Удалить из vt все объекты,

vt.end(),// предшествующие значению

ageLimit));// ageLimit

Слегка изменим условия задачи. Допустим, требуется удалить все объекты, предшествующие или равные ageLmt. Для этого необходимо найти первый объект после ageLmt. Для решения задачи идеально подходит алгоритм upper_bound:

vt.erase(vt.begin(),upper_bound(vt.begin(). // Удалить из vt все объекты,

vt.end(), // предшествующие или

ageLimit));

// эквивалентные ageLimit

Алгоритм upper_bound также часто применяется при вставке в сортированные интервалы, когда объекты с эквивалентными значениями должны следовать в контейнере в порядке вставки. Рассмотрим сортированный список объектов Person, в котором объекты сортируются по имени:

class Person { public:

const string& name() const;

}

struct PersonNameLess:

public binary_function<Person, Person, bool> { // См. совет 40

bool operator()(const Person& lhs, const Person& rhs) const

{

return lhs.name()<rhs.name();

}

list<Person> lp;

lp.sort(PersonNameLess());// Отсортировать lp по критерию

// PersonNameLess

Чтобы список сортировался требуемым образом (по имени, с хранением эквивалентных имен в порядке вставки), можно воспользоваться алгоритмом upper_ bound для определения позиции вставки:

Person newPerson;

lp.insert(upper_bound(lp.begin(),// Вставить newPerson за последним

Ip.end(), // объектом lр. предшествующим

newPerson, // или эквивалентным newPerson

PersonNameLess()).

newPerson);

Приведенное решение работоспособно и достаточно удобно, но не стройте иллюзий насчет того, что оно каким-то волшебным способом обеспечивает поиск точки вставки в контейнер list с логарифмической сложностью. Как объясняется в совете 34, при работе с list поиск занимает линейное время, но при этом выполняется логарифмическое количество сравнений.

До настоящего момента рассматривался только случай, когда поиск осуществляется в интервале, определяемом парой итераторов. Довольно часто работать приходится со всем контейнером вместо интервала. В этом случае необходимо различать последовательные и ассоциативные контейнеры. Для стандартных последовательных контейнеров (vector, string, deque и list) достаточно следовать рекомендациям, изложенным ранее, используя начальный и конечный итераторы контейнера для определения интервала.

Со стандартными ассоциативными контейнерами (set, multiset, map, multimap) дело обстоит иначе. В них предусмотрены функции поиска, которые по своим возможностям обычно превосходят алгоритмы STL Превосходство функций контейнеров перед алгоритмами подробно рассматривается в совете 44; если говорить кратко — они быстрее работают и ведут себя более последовательно. К счастью, имена функций обычно совпадают с именами соответствующих алгоритмов, поэтому там, где речь идет об алгоритмах count, find, lower_bound, upper_bound и equal_range, при поиске в ассоциативных контейнерах вместо них достаточно выбрать одноименную функцию. К сожалению, для алгоритма binary_search парной функции не существует. Чтобы проверить наличие значения в контейнере set или map, воспользуйтесь идиоматической ролью count как условия проверки:

set<Widget> s;// Создать множество, заполнить данными

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

if (s.count(w)) { // Существует значение, эквивалентное w

} else {

// Эквивалентное значение не существует

}

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

Тем не менее при подсчете объектов в ассоциативных контейнерах count надежно занимает свою нишу. В частности, вызов count предпочтительнее вызова equal_range с последующим применением distance к полученным итераторам. Во-первых, само название функции подсказывает ее смысл — слово count означает «подсчет». Во-вторых, count упрощает работу программиста, поскольку ему не приходится создавать пару и передавать ее компоненты при вызове distance. В-третьих, count работает чуть быстрее.

Попробуем подвести итог всему, о чем говорилось в настоящем совете. Информация собрана в следующей таблице.

Алгоритм Функция контейнера
Что вы хотите узнать Несортированный интервал Сортированный интервал Для set и map Для multiset и multimap
Присутствует ли заданное значение? find binary_search count find
Присутствует ли заданное значение? И если присутствует, то где находится первый объект с этим значением? find equal_range find find или lower_bound (см. ранее)
Где находится первый объект со значением, не предшествующим заданному? find_if lower_bound lower_bound lower_bound
Где находится первый объект со значением, следующим после заданного? find_if upper_bound upper_bound upper_bound
Сколько объектов имеют count equal_range count count
заданное значение?
Где находятся все equal_range equal_range equal_ Find (итеративный вызов)
объекты с заданным range
значением?

Несколько странно выгладит частое присутствие equal_range в столбце, относящемся к сортированным интервалам. Оно связано с особой ролью проверки эквивалентности при поиске. Использование lower_bound и upper_bound чревато ошибочной проверкой равенства, а при использовании equal_range более естественно выглядит проверка эквивалентности. Во второй строке предпочтение отдается equal_range еще по одной причине: equal_range работает с логарифмическим временем, а вызов find связан с линейными затратами времени.

Для контейнеров multiset и multimap в качестве возможных кандидатов для поиска первого объекта с заданным значением указаны два алгоритма, find и lower_ bound. Обычно для решения этой задачи выбирается find — возможно, вы обратили внимание, что именно этот алгоритм указан в таблице для контейнеров set и map. Однако multi -контейнеры не гарантируют, что при наличии нескольких элементов с заданным значением find найдет первый элемент в контейнере; известно лишь то, что будет найден один из этих элементов. Если вы действительно хотите найти первый объект с заданным значением, воспользуйтесь lower_bound и выполните вручную вторую часть проверки эквивалентности, описанной в совете 19 (без этой проверки можно обойтись при помощи equal _range, но вызов equal range обходится дороже, чем вызов lower_bound).

Выбрать между count, find, binary_search, lower_bound, upper_bound и equal_range несложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

count()

Из книги автора

count() Функция count подсчитывает число узлов в наборе узловnumber count(node-set)Функция принимает набор узлов и возвращает количество узлов в этом наборе. Следующий пример применения функции count мы уже рассматривали в главе 6. В этом случае набор узлов образован из всех элементов


find.exe

Из книги автора

find.exe Местонахождение: Windowssystem32 Описание: Find String (grep) Utility Поиск заданной строки текста в файле или нескольких файлах. После поиска в заданных файлах команда find выведет на экран все строки из этих файлов, содержащие заданный образец. Синтаксис:find [/v] [/c] [/n] [/i] "строка"


Shadow count

Из книги автора

Shadow count Число файлов Shadow, которые определены для данной базы данных. Как известно, файлы Shadow представляют собой зеркальные подобия основной базы данных. Ранее предназначенные для предохранения базы данных от неожиданной поломки жесткого диска, теперь они в основном


SEMAPHORE COUNT

Из книги автора

SEMAPHORE COUNT Параметры в ibconfig V4_LOCK_SEM_COUNT 32ANY_LOCK_SEM_COUNT 32


Internet Connection Count

Из книги автора

Internet Connection Count Сегодня существует масса способов подключиться к сети Интернет. Это можно сделать и через обычный модем (кстати, встроенный в любой ноутбук), и посредством высокоскоростных технологий (ADSL и спутниковая связь), и через мобильный телефон. Владельцы ноутбуков


Правило 34: Различайте наследование интерфейса и наследование реализации

Из книги автора

Правило 34: Различайте наследование интерфейса и наследование реализации Внешне простая идея открытого наследования при ближайшем рассмотрении оказывается состоящей из двух различных частей: наследования интерфейса функций и наследования их реализации. Различие


Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы

Из книги автора

Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма remove (см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом,


Совет 43. Используйте алгоритмы вместо циклов

Из книги автора

Совет 43. Используйте алгоритмы вместо циклов Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет


Подсчет (Count)

Из книги автора

Подсчет (Count) template ‹class InputIterator, class T, class Size›void count(InputIterator first, InputIterator last, const T& value, Size& n);template ‹class InputIterator, class Predicate, class Size›void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);count добавляет к n число итераторов i в диапазоне [first, last), для которых соблюдаются следующие


Алгоритм binary_search()

Из книги автора

Алгоритм binary_search() template class ForwardIterator, class Type boolbinary_search( ForwardIterator first,ForwardIterator last, const Type &value );template class ForwardIterator, class Type boolbinary_search( ForwardIterator first,ForwardIterator last, const Type &value,Compare comp );binary_search() ищет значение value в отсортированной последовательности, ограниченной парой итераторов [first,last).


Алгоритм count()

Из книги автора

Алгоритм count() template class InputIterator, class Type iterator_traitsInputIterator::distance_typecount( InputIterator first,InputIterator last, const Type& value );count() сравнивает каждый элемент со значением value в диапазоне, ограниченном парой итераторов [first,last), с помощью оператора равенства. Алгоритм возвращает число элементов,


Алгоритм equal_range()

Из книги автора

Алгоритм equal_range() template class ForwardIterator, class Type pair ForwardIterator, ForwardIterator equal_range( ForwardIterator first,ForwardIterator last, const Type &value );template class ForwardIterator, class Type, class Compare pairForwardIterator, ForwardIterator equal_range( ForwardIterator first,ForwardIterator last, const Type &value,Compare comp );equal_range() возвращает пару итераторов: первый представляет


Алгоритм lower_bound()

Из книги автора

Алгоритм lower_bound() template class ForwardIterator, class Type ForwardIteratorlower_bound( ForwardIterator first,ForwardIterator last, const Type &value );template class ForwardIterator, class Type, class Compare ForwardIteratorlower_bound( ForwardIterator first,ForwardIterator last, const Type &value,class Compare );lower_bound() возвращает итератор, указывающий на первую позицию в отсортированной


Алгоритм upper_bound()

Из книги автора

Алгоритм upper_bound() templateclass ForwardIterator, class Type ForwardIteratorupper_bound( ForwardIterator first,ForwardIterator last, const Type &value );template class ForwardIterator, class Type, class Compare ForwardIteratorupper_bound( ForwardIterator first,ForwardIterator last, const Type &value,Compare comp );upper_bound() возвращает итератор, указывающий на последнюю позицию в отсортированной


Функция count

Из книги автора

Функция count number count(node-set)Функция count возвращает число узлов, которое входит во множество, переданное ей в качестве аргумента.ПримерДля того чтобы подсчитать количество всех элементов второго уровня, можно воспользоваться выражением count(/*/*). Например, для входящего


Методы Count

Из книги автора

Методы Count Описание методовМетоды приведены для последовательности sequence of T. function Count(): integer; Возвращает количество элементов в последовательности. function Count(predicate: T->boolean): integer; Возвращает число, представляющее количество элементов последовательности,