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