Особенно ярко это различие проявляется при работе с контейнерами
map
и
multimap
, потому что эти контейнеры содержат объекты
pair
, но их функции учитывают только значение ключа каждой пары. По этой причине функция
count
считает только пары с совпадающими ключами (естественно, «совпадение» определяется по критерию эквивалентности); значение, ассоциированное с ключом, игнорируется. Функции
find
,
lower_bound
и т. д. поступают аналогично. Чтобы алгоритмы также ограничивались анализом ключа в каждой паре, вам придется выполнять акробатические трюки, описанные в совете 23 (что позволит заменить проверку равенства проверкой эквивалентности).
С другой стороны, если вы стремитесь к максимальной эффективности, то фокусы
совета 23 в сочетании с логарифмической сложностью поиска алгоритмов из совета 34 могут показаться не такой уж высокой ценой за повышение быстродействия. А если вы очень сильно стремитесь к максимальной эффективности, подумайте об использовании нестандартных хэшированных контейнеров (см. совет 25), хотя в этом случае вы также столкнетесь с различиями между равенством и эквивалентностью.
Таким образом, для стандартных ассоциативных контейнеров применение функций вместо одноименных алгоритмов обладает сразу несколькими преимуществами. Во-первых, вы получаете логарифмическую сложность вместо линейной. Во-вторых, «одинаковость» двух величин проверяется по критерию эквивалентности, более естественному для ассоциативных контейнеров. В-третьих, при работе с контейнерами
map
и
multimap
автоматически учитываются только значения ключей вместо полных пар (ключ, значение). Эти три фактора достаточно убедительно говорят в пользу функций классов.
Перейдем к функциям контейнера
list
, имена которых совпадают с именами алгоритмов STL. В этом случае эффективность является практически единственным фактором. Алгоритмы, у которых в контейнере
list
существуют специализированные версии (
remove
,
remove_if
,
unique
,
sort
,
merge
и
reverse
), копируют объекты, a
list
– версии ничего не копируют; они просто манипулируют указателями, соединяющими узлы списка. По алгоритмической сложности функции классов и алгоритмы одинаковы, но если предположить, что операции с указателями обходятся значительно дешевле копирования объектов,
list
– версии обладают лучшим быстродействием.
Следует помнить, что
list
– версии часто ведут себя иначе, чем их аналоги-алгоритмы. Как объясняется в совете 32, для фактического удаления элементов из контейнера вызовы алгоритмов
remove
,
remove_if
и
unique
должны сопровождаться вызовами
erase
, однако одноименные функции контейнера
list
честно уничтожают элементы, и последующие вызовы
erase
не нужны.
Принципиальное различие между алгоритмом
sort
и функцией
sort
контейнера
list
заключается в том, что алгоритм неприменим к контейнерам
list
, поскольку ему не могут передаваться двусторонние итераторы
list
. Алгоритм
merge
также отличается от функции
merge
контейнера
list
— алгоритму не разрешено модифицировать исходные интервалы, тогда как функция
list::merge
всегда модифицирует списки, с которыми она работает.
Теперь вы располагаете всей необходимой информацией. Столкнувшись с выбором между алгоритмом STL и одноименной функцией контейнера, предпочтение следует отдавать функции контейнера. Она почти всегда эффективнее работает и лучше интегрируется с обычным поведением контейнеров.
Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range
Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов:
count
,
find
,
binary_search
,
lower_bound
,
upper_bound
и
equal_range
. Как же принять верное решение?
Очень просто. Основными критериями должны быть скорость и простота.
Временно предположим, что границы
интервала поиска обозначены итераторами. Случай с поиском во всем контейнере будет рассмотрен ниже.
При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами
binary_search
,
lower_bound
,
upper_bound
и
equal_range
для проведения быстрого поиска (обычно с логарифмической сложностью — см. совет 34). Если интервал не отсортирован, выбор ограничивается линейными алгоритмами count,
count_if
,
find
и
find_if
. В дальнейшем описании
_if
– версии алгоритмов
count
и
find
игнорируются, как и разновидности
binary_search
,
lower_bound
,
upper_bound
и
equal_range
, которым при вызове передается предикат. Алгоритм поиска выбирается по одним и тем же соображениям независимо от того, используете ли вы стандартный предикат или задаете свой собственный.
Итак, в несортированных интервалах выбор ограничивается алгоритмами
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);