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

В нем создается контейнер multiset объектов Widget, упорядоченных по стандартному критерию. Строго говоря, упорядочение производится по критерию less, но большинство программистов будет полагать, что сортировка производится функцией operator< Не нужно обманывать их ожидания и подменять определение less. Если вы хотите использовать less (явно или косвенно), проследите за тем, чтобы этот критерий был эквивалентен operator< Если объекты должны сортироваться по другому критерию, создайте специальный класс функтора и назовите его как-нибудь иначе.

Программирование в STL

STL традиционно характеризуется как совокупность контейнеров, итераторов, алгоритмов и объектов функций, однако программирование в STL заключает в себе нечто большее. Этот термин означает, что программист способен правильно выбирать между циклами, алгоритмами или функциями контейнеров; знает, в каких случаях equal_range предпочтительнее lower_bound, когда lower_bound предпочтительнее find и когда find превосходит equal_range. Термин означает, что программист умеет повышать быстродействие алгоритма посредством замены функций эквивалентными функторами и избегает написания непереносимого или плохо читаемого кода. Более того, к этому понятию даже относится умение читать сообщения об ошибках компилятора, состоящие из нескольких тысяч символов, и хорошее знание Интернет-ресурсов, посвященных STL (документация, расширения и даже полные реализации).

Да, для программирования в STL необходимо много знать, и большая часть этой информации приведена в данной главе.

Совет 43. Используйте алгоритмы вместо циклов

Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет сводную величину, характеризующую интервал в целом (см. совет 37), а алгоритм partition делит элементы интервала на удовлетворяющие и не удовлетворяющие заданному критерию (см. совет 31). Чтобы алгоритм мог выполнить свою задачу, он должен проанализировать каждый объект в переданном интервале (или интервалах), для чего объекты в цикле перебираются от начала интервала к концу. Некоторые алгоритмы (такие как find и find_if) могут вернуть управление до завершения полного перебора, но и в этих алгоритмах задействован внутренний цикл. Ведь даже алгоритмы find и find_if должны проанализировать все элементы интервала, прежде чем принять решение об отсутствии искомого элемента.

Итак, внутренняя реализация алгоритмов построена на использовании циклов. Более того, благодаря разнообразию алгоритмов STL многие задачи, естественно кодируемые в виде циклов, могут решаться при помощи алгоритмов. Рассмотрим класс Widget с функцией redraw():

class Widget { public:

void redraw() const;

};

Если потребуется вызвать функцию redraw для всех объектов в контейнере list, это можно сделать в следующем цикле:

list lw:

for(list::iterator=lw.begin();i!=lw.end() :++i){ i->redraw();

}

С другой стороны, с таким же успехом можно воспользоваться алгоритмом for_each:

for_each(lw.begin(),lw.end().// Функция mem_fun_ref

mem_fun_ref(&Widget::redraw)); // описана в совете 41

Многие программисты С++ считают, что циклы естественнее алгоритмов, а прочитать цикл проще, чем разбираться в mem_fun_ref и получении адреса Widget:: redraw. Но в заголовке этого совета рекомендуется отдавать предпочтение алгоритмам. В сущности, заголовок означает, что вызов алгоритма предпочтительнее любого явно запрограммированного цикла. Почему?

По трем причинам.

•Эффективность:

алгоритмы обычно работают эффективнее, чем циклы, организованные программистами.

•Правильность: при написании циклов чаще встречаются ошибки, чем при вызове алгоритмов.

•Удобство сопровождения: алгоритмы часто порождают более наглядный и прямолинейный код, чем эквивалентные циклы.

Вся оставшаяся часть совета будет посвящена подробному анализу этих причин.

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

for (list::iterator=lw.begin();i!=1w.end():++i){