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

Если вы согласны с тем, что вызовы алгоритмов обычно предпочтительнее циклов, а также с тем, что интервальные функции обычно предпочтительнее циклического вызова одноэлементных функций (см, совет 5), можно сделать интересный вывод: хорошо спроектированная программа C++, использующая STL, содержит гораздо меньше циклических конструкций, чем аналогичная программа, не использующая STL, и это хорошо. Замена низкоуровневых конструкций for, while и do высокоуровневыми терминами insert, find и foreach повышает уровень абстракции и упрощает программирование, документирование, усовершенствование и сопровождение программы.

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

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

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

set s; // Создать множество

…           // и занести в него

            // миллион чисел

set::iterator i = s.find(727); // Функция find контейнера

 if (i != s.end) …

 set::iterator i = find(s.begin, s.end, 727); // Алгоритм find

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