Эффективное использование STL

… // Значение не найдено, 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

Слегка изменим условия задачи. Допустим, требуется удалить все объекты, предшествующие или равные ageLimit. Для этого необходимо найти первый объект после ageLimit. Для решения задачи идеально подходит алгоритм 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 за последним
 lp.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 в худшем случае просматривает все элементы контейнера.