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

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

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

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

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

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

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

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

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

 i->redraw;

}

Я выделил условие завершения цикла, чтобы подчеркнуть, что при каждой итерации цикла будет выполнено сравнение с lw.end. Следовательно, при каждой итерации будет вызываться функция list::end. Однако вызывать эту функцию больше одного раза не нужно, поскольку цикл не модифицирует список. Но если взглянуть на вызов алгоритма, можно заметить, что end вызывается ровно один раз:

for_each(lw.begin, lw.end,  // lw.end вычисляется

 mem_fun_ref(&Widget::redraw)); // только один раз

Объективности ради замечу: авторы реализаций STL хорошо понимают, что функции begin и end (и другие функции — например, size) используются очень часто, и стараются оптимизировать их с расчетом на максимальную эффективность. Они почти всегда объявляют такие функции подставляемыми (inline) и стараются кодировать их так, чтобы большинство компиляторов могло избежать повторяющихся вычислений, выводя результаты из цикла. Впрочем, опыт показывает, что это не всегда им удается, и в таких случаях исключения повторяющихся вычислений вполне достаточно, чтобы алгоритмы имели преимущество по быстродействию перед циклами, закодированными вручную.

Но как было сказано выше, вывод лишних вычислений из цикла является второстепенным фактором, существуют два более важных. Первый важный фактор заключается в том, что разработчики библиотек могут воспользоваться знанием внутренней реализации контейнера и оптимизировать перебор так, как не сможет ни один пользователь библиотеки. Например, объекты во внутреннем представлении контейнера deque обычно хранятся в одном или нескольких массивах фиксированного размера. Перебор в этих массивах с использованием указателей производится быстрее, чем перебор на базе итераторов, однако он может использоваться только разработчиками библиотеки, поскольку они знают размер внутренних массивов и способ перехода от одного массива к другому. Некоторые версии STL содержат реализации алгоритмов, использующие внутренние структуры данных deque; эксперименты показали, что они работают примерно на 20% быстрее «обычных» реализаций.

Здесь важно не то, что реализации STL оптимизируются для deque (или другого конкретного типа контейнера), а то, что разработчики знают об устройстве контейнеров больше, чем простые пользователи, и могут применить свои знания при реализации алгоритмов. Отказываясь от алгоритмов в пользу циклов, вы не сможете пользоваться преимуществами оптимизации, основанной на знании внутреннего устройства структур данных.

Второй принципиальный аргумент заключается в том, что практически все алгоритмы STL (кроме самых элементарных) основаны на теоретических разработках, более сложных — а иногда гораздо более сложных, — нежели те, которые может предложить средний программист C++. Превзойти sort и его сородичей (см. совет 31) по эффективности практически невозможно; столь же эффективны алгоритмы поиска в сортированных интервалах (см. советы 34 и 45). Даже повседневные задачи вроде удаления объектов из блоковых контейнеров более эффективно решаются при помощи идиомы erase-remove, чем при помощи самостоятельно запрограммированных циклов (см. совет 9).