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

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

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

vector<Widget> vw:

sort (vw. begi nO.v.endO):

typedef vector<Widget>::iterator VWIter: Вспомогательные typedef pair<VWIter,VWIter> VWIterPair: определения типов

VWIterPair p = equal range(vw.begin(),vw.end().w):

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

непустой интервал... Значение найдено, р.first указывает на первый элемент интервала, а р.second - на позицию за последним элементом

} else {

Значение не найдено, р.first и р.second указывают на точку вставки искомого значения

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

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

VWIterPair р = equal range(vw.begin(),vw.end(),w): cout There are distanceCp.first,p.second) elements in vw equivalent to w. :

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

class Timestamp {...};

bool operator<(const TimestampS Ihs. Проверяет, предшествует ли

const TimestampS rhs): объект Ihs объекту rhs no времени

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

и отсортировать так, чтобы sortCvt.beginO.vt.endO); старые объекты предшествовали новым

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

Timestamp ageLimit;

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

vt.endO. предшествующие значению

ageLimit)); ageLimit

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

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

Vt.endO, предшествующие или ageLimit)); эквивалентные ageLimit

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

class Person { public:

const strings nameO const; };

struct PersonNameLess: public binary function<Person. Person, bool> { См. совет 40

bool operatorО(const Persons Ihs, const Persons rhs) const {

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

list<Person> Ip;

Ip.sortCPersonNameLessO); Отсортировать 1р по критерию

PersonNameLess

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

Person newPerson;

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

Ip.endO. объектом 1р. предшествующим

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

PersonNameLessO).

newPerson);

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

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

Со стандартными ассоциативными контейнерами (set, multiset, map, multimap) дело обстоит иначе. В них предусмотрены функции поиска, которые по своим возможностям обычно превосходят алгоритмы STL Превосходство функций контейнеров перед алгоритмами подробно рассматривается в совете 44; если говорить кратко - они быстрее работают и ведзгг себя более последовательно. К счастью, имена функций обычно совпадают с именами соответствующих алгоритмов, поэтому там, где речь идет об алгоритмах count, find, lower bound, upper bound и equal range, при поиске в ассоциативных контейнерах вместо них достаточно выбрать одноименную функцию. К сожалению, для алгоритма binary search парной функции не существует. Чтобы проверить наличие значения в контейнере set или тар, воспользуйтесь идиоматической ролью count как условия проверки:

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

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

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

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

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