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

Мейерс Скотт

При поиске заданной величины в интервале алгоритм

lower_bound

возвращает итератор, указывающий на первый экземпляр этой величины (в случае успешного поиска) или на правильную позицию вставки (в случае неудачи). Таким образом, алгоритм

lower_bound

отвечает на вопрос: «Присутствует ли заданное значение в интервале? Если присутствует, то где находится первый экземпляр, а если нет — где он должен находиться?». Как и в случае с алгоритмом

find

, результат

lower_bound

необходимо дополнительно проверить и убедиться в том, что он указывает на искомое значение. Но в отличие от

find

, его нельзя просто сравнить с конечным

итератором. Вместо этого приходится брать объект, идентифицированный алгоритмом

lower_bound

, и проверять, содержит ли он искомое значение.

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

lower_bound

примерно так:

vector<Widget>::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<Widget> vw;

…

sort(vw.begin, v.end);

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

typedef pair<VWIter, VWIter> 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<Timestamp> vt; // Создать вектор, заполнить данными

… // и отсортировать так, чтобы

sort(vt.begin, vt.end); // "старые" объекты предшествовали "новым"

Предположим, из

vt

требуется удалить все объекты, предшествующие некоторому пороговому объекту

ageLimit

. В данном случае не нужно искать в

vt

объект

Timestamp

, эквивалентный

ageLimit

, поскольку объекта с точно совпадающим значением может и не быть. Вместо этого в

vt

ищется граничная позиция, то есть первый элемент, не старший

ageLimit

. Задача решается элементарно, поскольку алгоритм

lowebound

предоставляет всю необходимую информацию: