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

Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов

Некоторые контейнеры содержат функции, имена которых совпадают с именами алгоритмов STL. Так, в ассоциативных контейнерах существуют функции count, find, lower_bound, upper_bound и equal_range, а в контейнере list предусмотрены функции remove, remove_if, unique, sort, merge и reverse. Как правило, эти функции используются вместо одноименных алгоритмов, что объясняется двумя причинами. Во-первых, функции классов быстрее работают. Во-вторых, они лучше интегрированы с контейнерами (особенно ассоциативными), чем алгоритмы. Дело в том, что алгоритмы и одноименные функции классов обычно работают не совсем одинаково.

Начнем с ассоциативных контейнеров. Допустим, имеется множество set<int>, содержащее миллион значений, и вы хотите найти позицию первого вхождения числа 727, если оно присутствует. Ниже приведены два очевидных способа поиска:

set<int> s;// Создать множество
// и занести в него
// миллион чисел
set<int>::iterator i = s.find(727);// Функция find контейнера
f(i!=s.end())...
set<int>::iterator i = find(s.begin(), s.end(), 727); // Алгоритм find
f(i!=s.end())...

Функция класса find работает с логарифмической сложностью, поэтому независимо от того, присутствует ли число 727 в множестве или нет, set:: find в процессе поиска выполнит не более 40 сравнений, а обычно потребуется не более 20. С другой стороны, алгоритм find работает с линейной сложностью, поэтому при отсутствии числа 727 будет выполнено 1 000 000 сравнений. Впрочем, даже если число 727 присутствует, алгоритм find в процессе поиска выполняет в среднем 500 000 сравнений. Результат явно не в пользу алгоритма find.

Кстати, я не совсем точно указал количество сравнений для функции find, поскольку оно зависит от реализации, используемой ассоциативными контейнерами. В большинстве реализаций используются красно-черные деревья — особая разновидность сбалансированных деревьев с разбалансировкой по степеням 2. В таких реализациях максимальное количество сравнений, необходимых для поиска среди миллиона значений, равно 38, но в подавляющем большинстве случаев требуется не более 22 сравнений. Реализация, основанная на идеально сбалансированных деревьях, никогда не требует более 21 сравнения, но на практике по общему быстродействию идеально сбалансированные деревья уступают «красно-черным». По этой причине в большинстве реализаций STL используются «красно-черные» деревья.

Различия между функцией класса и алгоритмом find не ограничиваются быстродействием. Как объясняется в совете 19, алгоритмы STL проверяют «одинаковость» двух объектов по критерию равенства, а ассоциативные контейнеры используют критерий эквивалентности. Таким образом, алгоритм find ищет 727 по критерию равенства, а функция find — по критерию эквивалентности. Различия в критериях иногда приводят к изменению результата поиска. Например, в совете 19 было показано, как применение алгоритма find для поиска информации в ассоциативном контейнере завершается неудачей, тогда как аналогичный поиск функцией find привел бы к успеху! При работе с ассоциативными контейнерами функциональные формы find, count и т. д. предпочтительнее алгоритмических, поскольку их поведение лучше согласуется с другими функциями этих контейнеров. Вследствие различий между равенством и эквивалентностью алгоритмы не столь последовательны.

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

Совет 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) !=w.end()){
...
} else {
...
}

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

Впрочем, простой проверки существования во многих случаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find:

list<Widget>::iterator i = find(lw.begin(),lw.end(),w);
if (i!=lw.end()){
	// Успешный поиск, i указывает на первый экземпляр