Скотт Мейерс - Эффективное использование STL

Многие программисты используют lower_boundпримерно так:

vector::iterator = lower_bound(vw,begin(), vw.end(), w);

if (i != vw.end() && *i == w){ // Убедиться в том, что i указывает

// на объект, и этот объект имеет искомое

// значение. Ошибка!!!!

… // Значение найдено, i указывает на первый

// экземпляр объекта с этим значением

} else {

… // Значение не найдено

}

В большинстве случаев такая конструкция работает, но в действительности она содержит ошибку. Присмотритесь к проверяемому условию:

if (i != vw.end() && *i == w) {

В этом условии проверяется равенство, тогда как lower_boundиспользует при поиске критерий эквивалентности. Как правило, результаты проверки по двум критериям совпадают, но, как показано в совете 19, это не всегда так. В таких ситуациях приведенный выше фрагмент не работает.

Чтобы исправить ошибку, необходимо убедиться в том, что итератор, полученный от lower_bound, указывает на объект со значением, эквивалентным искомому. Проверку можно выполнить вручную (в совете 19 показано, как это делается, а в совете 24 приведен пример ситуации, когда такое решение оправданно), однако сделать это непросто, поскольку при этом должна использоваться та же функция сравнения, как и при вызове lower_bound. В общем случае мы имеем дело с произвольной функцией (или объектом функции). При передаче lower_boundфункции сравнения эта же функция должна использоваться и в «ручной» проверке эквивалентности; следовательно, при изменении функции сравнения, передаваемой lower_bound, вам придется внести соответствующие изменения в проверку эквивалентности. В принципе, синхронизировать функции сравнения не так уж сложно, но об этом необходимо помнить, а при программировании хлопот и без этого хватает.

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

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

vector vw;

…

sort(vw.begin(), v.end());

typedef vector::iterator VWIter; // Вспомогательные

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, отсортированный от «старых» объектов к «новым»: