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

typedef pair 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 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 { // См. совет 40

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

  return lhs.name < rhs.name;

 }

};

list lp;

…

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

                           // PersonNameLess