Скотт Мейерс - Эффективное использование STL
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).
