Скотт Мейерс - Эффективное использование STL
Итак, в несортированных интервалах выбор ограничивается алгоритмами count и find. Эти алгоритмы решают несколько отличающиеся задачи, к которым следует присмотреться повнимательнее. Алгоритм count отвечает на вопрос: «Присутствует ли заданное значение, и если присутствует — то в каком количестве экземпляров?». Для алгоритма find вопрос звучит так: «Присутствует ли заданное значение, и если присутствует — то где именно?»
Допустим, вы просто хотите проверить, присутствует ли в списке некоторое значение w класса Widget. При использовании алгоритма count решение выглядит так:
list<Widget> lw; // Список объектов Widget
Widget w; // Искомое значение класса Widget
…
if (count(lw.begin(), lw.end(), w)) {
… // Значение w присутствует в lw
} else {
… // Значение не найдено
}
В приведенном фрагменте продемонстрирована стандартная идиома: применение count для проверки существования. Алгоритм count возвращает либо ноль, либо положительное число; в программе ненулевое значение интерпретируется как логическая истина, а ноль — как логическая ложь. Возможно, следующая конструкция более четко выражает суть происходящего:
if (count(lw.begin(), lw.end(), w) != 0)…
Некоторые программисты предпочитают эту запись, но неявное преобразование, как в приведенном выше примере, встречается достаточно часто.
Решение с алгоритмом find выглядит чуть сложнее, поскольку возвращаемое значение приходится сравнивать с конечным итератором списка:
if (find(lw.begin(), lw.end(), w) != lw.end()) {
…
} else {
…
}
В контексте проверки существования идиоматическое использование count чуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку find при обнаружении искомого значения немедленно прекращает поиск, a count продолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные хлопоты, связанные с программированием find.
Впрочем, простой проверки существования во многих случаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find:
list<Widget>::iterator i = find(lw.begin(), lw.end(), w);
if (i!=lw.end()) {
… // Успешный поиск, i указывает на первый экземпляр
} else {
… // Значение не найдено
}
При работе с сортированными интервалами существуют и другие варианты, и им определенно стоит отдать предпочтение. Алгоритмы count и find работают с линейной сложностью, тогда как алгоритмы поиска в сортированных интервалах (binary_search, lower_bound, upper_bound и equal_range) обладают логарифмической сложностью.
Переход от несортированных интервалов к сортированным влечет за собой изменение критерия сравнения двух величин. Различия между критериями подробно описаны в совете 19, поэтому я не стану повторяться и замечу, что алгоритмы count и find используют критерий равенства, а алгоритмы binary_search, lower_bound, upper_bound и equal_range основаны на критерии эквивалентности.
Присутствие величины в сортированном интервале проверяется алгоритмом binary_search. В отличие от функции bsearch из стандартной библиотеки C (а значит, и стандартной библиотеки C++), алгоритм binary_search возвращает только bool. Алгоритм отвечает на вопрос: «Присутствует ли заданное значение в интервале?», и возможны только два ответа: «да» и «нет». Если вам понадобится дополнительная информация, выберите другой алгоритм.
Пример применения binary_search к сортированному вектору (преимущества сортированных векторов описаны в совете 23):
vector<Widget> vw; // Создать вектор, заполнить
… // данными и отсортировать
sort(vw.begin(), vw.end());
Widget w; // Искомое значение
…
if (binary_search(vw.begin(), vw.end(), w)) {
… // Значение w присутствует в vw
} else {
… // Значение не найдено
}
Если у вас имеется сортированный интервал и вы ищете ответ на вопрос: «Присутствует ли заданное значение в интервале, и если присутствует — то где именно?», следует использовать алгоритм equal_range, хотя на первый взгляд кажется, что вам нужен алгоритм lower_bound. Вскоре мы вернемся к equal_range, а пока проанализируем поиск в интервалах с применением алгоритма lower_bound.
При поиске заданной величины в интервале алгоритм 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);
