Эффективное использование 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<Widget> lw:
for(list<Widget>::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<Widget>::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<double> d;// Создать контейнер deque
// и заполнить его данными
size_t numDoubles = fillArray(data.maxNumDoubles): // Получение данных от функции
for (size_t i=0;i<numDoubles;++i){ //Для каждого индекса i в data
d.insert(d.begin(),data[i]+41); //вставить в начало d значение
}//data[i]+41.
//Программа содержит ошибку!

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

Если изменение порядка не было предусмотрено (признайтесь, ведь не было!), проблему можно решить следующим образом:

deque<double>:: iterator insertLocaton = d.begin(); // Сохранить итератор
	// для начальной
	// позиции d
for (size_t =0;i<numDoubles;++i){ // Вставить значение data[i]+41
	d.insert(insertLocaton++,data[i]+41); // в позиции insertLocation
}// и увеличить insertLocation.
// Программа также содержит ошибку!

На первый взгляд кажется, что этот фрагмент решает сразу две проблемы — программа не только наращивает итератор, задающий позицию вставки, но и избавляется от необходимости заново вычислять begin при каждой итерации; тем самым решается второстепенная проблема повторяющихся вычислений, о которой говорилось выше. К сожалению, вместо этих двух проблем возникает третья — программа вообще перестает работать. При каждом вызове deque::insert все итераторы deque, включая insertLocation, становятся недействительными, поэтому второй и все последующие вызовы insert приводят к непредсказуемым последствиям.

После обнаружения этой проблемы (возможно, при помощи отладочного режима STL — см. совет 50) приходит в голову следующее решение:

deque<double>::iterator insertLocation = d.begin():// См. ранее
for (size_t i=0;i<numDoubles;++i){// Программа обновляет
	insertLocaton=	// итератор insertLocation
	d.insert(insertLocaton,data[i]+41); // при каждом вызове insert
	++insertLocation;	// и увеличивает его.
}

Программа делает именно то, что требовалось, но подумайте, как много времени понадобилось, чтобы прийти к верному решению! А теперь сравните со следующим вызовом transform: