Чтение онлайн

на главную

Жанры

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

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

Многие программисты C++ считают, что циклы естественнее алгоритмов, а прочитать цикл проще, чем разбираться в

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

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

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

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

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

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

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

for (list<Widget>::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).

Если соображений эффективности недостаточно, существует и другой принципиальный фактор — правильность работы программы. В частности, при самостоятельном программировании циклов приходится следить за тем, чтобы итераторы (1) были действительными и (2) указывали на те элементы, на которые они должны указывать. Предположим, у нас имеется массив (возможно, из-за использования унаследованного интерфейса с языком C — см. совет 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
, поэтому последний вставленный элемент попадает в начало контейнера!

Поделиться:
Популярные книги

Бастард Императора

Орлов Андрей Юрьевич
1. Бастард Императора
Фантастика:
фэнтези
аниме
5.00
рейтинг книги
Бастард Императора

На границе империй. Том 10. Часть 1

INDIGO
Вселенная EVE Online
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 10. Часть 1

Имя нам Легион. Том 7

Дорничев Дмитрий
7. Меж двух миров
Фантастика:
боевая фантастика
рпг
аниме
5.00
рейтинг книги
Имя нам Легион. Том 7

Измена. Вторая жена мужа

Караева Алсу
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Вторая жена мужа

Буря империи

Сай Ярослав
6. Медорфенов
Фантастика:
аниме
фэнтези
фантастика: прочее
эпическая фантастика
5.00
рейтинг книги
Буря империи

Пенсия для морского дьявола

Чиркунов Игорь
1. Первый в касте бездны
Фантастика:
попаданцы
5.29
рейтинг книги
Пенсия для морского дьявола

На изломе чувств

Юнина Наталья
Любовные романы:
современные любовные романы
6.83
рейтинг книги
На изломе чувств

Тринадцатый II

NikL
2. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Тринадцатый II

Сирота

Шмаков Алексей Семенович
1. Светлая Тьма
Фантастика:
юмористическое фэнтези
городское фэнтези
аниме
5.00
рейтинг книги
Сирота

Законы Рода. Том 9

Flow Ascold
9. Граф Берестьев
Фантастика:
городское фэнтези
попаданцы
аниме
дорама
фэнтези
фантастика: прочее
5.00
рейтинг книги
Законы Рода. Том 9

Красноармеец

Поселягин Владимир Геннадьевич
1. Красноармеец
Фантастика:
боевая фантастика
попаданцы
4.60
рейтинг книги
Красноармеец

Огненный князь 4

Машуков Тимур
4. Багряный восход
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Огненный князь 4

Начальник милиции. Книга 5

Дамиров Рафаэль
5. Начальник милиции
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Начальник милиции. Книга 5

Инкарнатор

Прокофьев Роман Юрьевич
1. Стеллар
Фантастика:
боевая фантастика
рпг
7.30
рейтинг книги
Инкарнатор