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

vector::iterator i =

find_if(v.begin(), v.end(), // Найти первое значение val.

compose2(logical_and0, // для которого одновременно

bind2nd(greater(),x).// истинны условия

bind2nd(less(),y))): // val>x. и val

Но даже если бы нестандартные компоненты не использовались, многие программисты полагают, что вызов алгоритма значительно уступает циклу по наглядности, и я склонен с ними согласиться (см. совет 47).

Вызов find_ifможно было бы упростить за счет выделения логики проверки в отдельный класс функтора.

template

class BetweenValues:

public unary_function{// См. совет 40

public:

BetweenValues(const T& lowValue, const T& highValue)

:lowVal(lowValue),highVal(highValue) {}

bool operator() (const T& val) const

{

return val>lowVal&&val

}

private:

T lowVal;

T highVal;

};

vector iterator i = find_if(v.begin().v.end(),

BetweenValues (x,y));

Однако у такого решения имеются свои недостатки. Во-первых, создание шаблона BetweenValuesтребует значительно большей работы, чем простое написание тела цикла. Достаточно посчитать строки в программе: тело цикла — одна строка, BetweenValues— четырнадцать строк. Соотношение явно не в пользу алгоритма. Во-вторых, описание критерия поиска физически отделяется от вызова. Чтобы понять смысл вызова find_if,необходимо найти определение BetweenValues,но оно должно располагаться вне функции, содержащей вызов find_if. Попытка объявить BetweenValues внутри функции, содержащей вызов find_if:

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

template

class BetweenValues:public unary_function {...4}

vector::iterator i = find_if(v.begin(), v.end(),

BetweenVa1ues(x,у));

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

не компилируется, поскольку шаблоны не могут объявляться внутри функций. Если попробовать обойти это ограничение посредством реализации BetweenValuesв виде класса:

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

class BetweenValues:public unary_function {...}

vector: iterator i = find_if(v.begin(). v.end().

BetweenValues(x.y));

}:// Конец функции

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

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

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

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

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

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

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

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

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

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

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