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

Особенно ярко это различие проявляется при работе с контейнерами map и multimap, потому что эти контейнеры содержат объекты pair, но их функции учитывают только значение ключа каждой пары. По этой причине функция count считает только пары с совпадающими ключами (естественно, «совпадение» определяется по критерию эквивалентности); значение, ассоциированное с ключом, игнорируется. Функции find, lower_bound и т. д. поступают аналогично. Чтобы алгоритмы также ограничивались анализом ключа в каждой паре, вам придется выполнять акробатические трюки, описанные в совете 23 (что позволит заменить проверку равенства проверкой эквивалентности).

С другой стороны, если вы стремитесь к максимальной эффективности, то фокусы совета 23 в сочетании с логарифмической сложностью поиска алгоритмов из совета 34 могут показаться не такой уж высокой ценой за повышение быстродействия. А если вы очень сильно стремитесь к максимальной эффективности, подумайте об использовании нестандартных хэшированных контейнеров (см. совет 25), хотя в этом случае вы также столкнетесь с различиями между равенством и эквивалентностью.

Таким образом, для стандартных ассоциативных контейнеров применение функций вместо одноименных алгоритмов обладает сразу несколькими преимуществами. Во-первых, вы получаете логарифмическую сложность вместо линейной. Во-вторых, «одинаковость» двух величин проверяется по критерию эквивалентности, более естественному для ассоциативных контейнеров. В-третьих, при работе с контейнерами шар и 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 и одноименной функцией контейнера, предпочтение следует отдавать функции контейнера. Она почти всегда эффективнее работает и лучше интегрируется с обычным поведением контейнеров.

Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: 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 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) !=w.end()){

...

} else {

...

}

В контексте проверки существования идиоматическое использование count чуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку find при обнаружении искомого значения немедленно прекращает поиск, a count продолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные хлопоты, связанные с программированием find.