{ Начало функции

class BetweenValues:public unary function<int,bool> {...}

vector<int>: iterator i = find if(v.begin(). v.endO.

BetweenValues(x,y));

}; Конец функции

все равно ничего не получается, поскольку классы, определяемые внутри функций, являются локальными, а локальные классы не могут передаваться в качестве аргументов шаблонов (как функтор, передаваемый findif). Печально, но классы функторов и шаблоны классов функторов не разрешается определять внутри функций, как бы удобно это ни было.

В контексте борьбы между вызовами алгоритмов и циклами это означает, что выбор определяется исключительно содержимым цикла. Если алгоритм уже умеет делать то, что требуется, или нечто очень близкое, вызов алгоритма более нагляден. Если задача элементарно решается в цикле, а при использовании алгоритма требует сложных нагромождений адаптеров или определения отдельного класса функтора, вероятно, лзше ограничиться циклом. Наконец, если в цикле приходится выполнять очень длинные и сложные операции, выбор снова склоняется в пользу алгоритмов, потому что длинные и сложные операции лзше оформлять в отдельных функциях. После того как тело цикла будет перенесено в отдельную функцию, почти всегда удается передать эту функцию алгоритму (особенно часто - алгоритму for each) так, чтобы ползенный код был более наглядным и прямолинейным.

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

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

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

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

set<int> S: Создать множество

и занести в него миллион чисел

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

if(i!=s.end())...

set<int>: iterator i = find(s.begin(), s.endO. 727); Алгоритм find if(i!=s.end())...

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

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

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

Особенно ярко это различие проявляется при работе с контейнерами тар и multimap, потому что эти контейнеры содержат объекты pair, но их функции учитывают только значение ключа каждой пары. По этой причине функция count считает только пары с совпадающими ключами (естественно, совпадение опре-

деляется по критерию эквивалентности); значение, ассоциированное с ключом, игнорируется. Функции find, lower bound и т. д. поступают аналогично. Чтобы алгоритмы также ограничивались анализом ключа в каждой паре, вам придется выполнять акробатические трюки, описанные в совете 23 (что позволит заменить проверку равенства проверкой эквивалентности).

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

Таким образом, для стандартных ассоциативных контейнеров применение функций вместо одноименных алгоритмов обладает сразу несколькими преиму-шествами. Во-первых, вы ползаете логарифмическую сложность вместо линейной. Во-вторых, одинаковость двух величин проверяется по критерию эквивалентности, более естественному для ассоциативных контейнеров. В-третьих, при работе с контейнерами тар и multimap автоматически учитываются только значения ключей вместо полных пар (ключ, значение). Эти три фактора достаточно убедительно говорят в пользу функций классов.

Перейдем к функциям контейнера 1 i st, имена которых совпадают с именами алгоритмов STL. В этом слзае эффективность является практически единственным фактором. Алгоритмы, у которых в контейнере 1 i st существуют специализированные версии (remove, remove if, unique, sort, merge и reverse), копируют объекты, a 1 i st-версии ничего не копируют; они просто манипулируют указателями, соединяющими узлы списка. По алгоритмической сложности функции классов и алгоритмы одинаковы, но если предположить, что операции с указателями обходятся значительно дешевле копирования объектов, 1 i st-версии обладают лучшим быстродействием.

Следует помнить, что 1 i st-версии часто ведут себя иначе, чем их аналоги-алгоритмы. Как объясняется в совете 32, для фактического удаления элементов из контейнера вызовы алгоритмов remove, remove if и unique должны сопровождаться вызовами erase, однако одноименные функции контейнера 1 i st честно уничтожают элементы, и последующие вызовы erase не нужны.

Принципиальное различие между алгоритмом sort и функцией sort контейнера 1 i st заключается в том, что алгоритм неприменим к контейнерам 1 i st, поскольку ему не могут передаваться двусторонние итераторы 1 i st. Алгоритм merge также отличается от функции merge контейнера 1 i st - алгоритму не разрешено модифицировать исходные интервалы, тогда как функция list:: merge всегда модифицирует списки, с которыми она работает.

Теперь вы располагаете всей необходимой информацией. Столкнувшись с выбором между алгоритмом STL и одноименной функцией контейнера, предпочтение следует отдавать функции контейнера. Она почти всегда эффективнее работает и лучше интегрируется с обычным поведением контейнеров.