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

Итак, внутренняя реализация алгоритмов построена на использовании циклов. Более того, благодаря разнообразию алгоритмов 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){

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

Если соображений эффективности недостаточно, существует и другой принципиальный фактор — правильность работы программы. В частности, при самостоятельном программировании циклов приходится следить за тем, чтобы итераторы (1) были действительными и (2) указывали на те элементы, на которые они должны указывать. Предположим, у нас имеется массив (возможно, из-за использования унаследованного интерфейса с языком С — см. совет 16), и вы хотите взять каждый элемент массива, прибавить к нему 41 и вставить в начало контейнера deque. При самостоятельном программировании цикла примерная реализация выглядит приблизительно так (следующий фрагмент представляет собой видоизмененный пример из совета 16):

// Функция получает указатель на массив.

// содержащий не более arraySize чисел типа double,

// и записывает в него данные.

// Возвращается количество записанных чисел.

size_t fillArray(double *pArray, size_t arraySize);

double data[maxNumDoubles]; // Определение локального массива

deque d;// Создать контейнер deque

// и заполнить его данными

size_t numDoubles = fillArray(data.maxNumDoubles): // Получение данных от функции

for (size_t i=0;i

d.insert(d.begin(),data[i]+41); //вставить в начало d значение

}//data[i]+41.

//Программа содержит ошибку!

Вообще говоря, этот пример работает — если вас устраивает, что вновь вставленные элементы следуют в порядке, обратном порядку соответствующих элементов data. Вставка производится в позиции d. begin(), поэтому последний вставленный элемент попадает в начало контейнера!