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

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

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

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