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

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.

---

Есть два вектора, v1 и v2. Как проще всего заполнить v1 содержимым второй половины v2? Только не надо мучительно размышлять над тем, что считать «половиной» при нечетном количестве элементов в v2. Просто постарайтесь быстро дать разумный ответ.

Время истекло! Если вы предложили

v1.assign(v2.begin()+v2.size()/2, v2.end())

или нечто похожее — поздравляю, пять баллов. Если в вашем ответе присутствуют вызовы более чем одной функции, но при этом он обходится без циклов, вы получаете «четверку». Если в ответе задействован цикл, вам есть над чем поработать, а если несколько циклов — значит, вы узнаете из этой книги много нового.

Кстати говоря, если при чтении ответа вы произнесли «Чего-чего?» или что-нибудь в этом роде, читайте внимательно, потому что речь пойдет об очень полезных вещах.

Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции assign, о которой многие программисты попросту забывают. Функция assign поддерживается всеми стандартными последовательными контейнерами (vector, string, deque и list). Каждый раз, когда вам требуется полностью заменить содержимое контейнера, подумайте, нельзя ли добиться желаемой цели присваиванием. Если вы просто копируете один контейнер в другой контейнер того же типа, задача решается функцией operator=. Но, как показывает приведенный пример, существует также функция assign, которая позволяет заполнить контейнер новыми данными в тех случаях, когда operator= не подходит.

Во-вторых, эта задача показывает, почему интервальные функции лучше своих одноэлементных аналогов. Интервальной называется функция контейнера, которая, подобно алгоритмам STL, определяет интервал элементов для выполняемой операции при помощи двух параметров-итераторов. Без интервальной функции нам пришлось бы создавать специальный цикл:

vector<Widget> v1,v2; // Предполагается, что v1 и v2 -

                      // векторы объектов Widget

…

v1.clear():

for (vector<Widget>::const_iterator ci=v2.begin()+v2.size()/2; ci != v2.end(); ++ci)

 v1.push_back(*ci);

В совете 43 подробно объясняется, почему использовать явные циклы не рекомендуется, но и без этого ясно, что написание этого фрагмента потребует больше усилий, чем простой вызов assign. Цикл также отрицательно влияет на быстродействие, но к этой теме мы вернемся позже.

Одно из возможных решений заключается в том, чтобы последовать совету 43 и воспользоваться алгоритмом:

v1.clear();

copy(v2.begin()+v2.size()/2, v2.end(), back_inserter(v1));

Но и этот вариант требует больших усилий, чем простой вызов assign. Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова copy (см. совет 43). В результате потенциальное снижение быстродействия не исчезает (вскоре мы поговорим об этом). А сейчас я хочу ненадолго отвлечься от темы и заметить, что практически все случаи использования copy, когда приемный интервал задается итератором вставки (inserter, back_inserter или front_inserter), могут — и должны — заменяться вызовами интервальных функций. Например, вызов copy заменяется интервальной версией insert:

v1.insert(v1.end(), v2.begin()+v2.size()/2. v2.end());

Команда получается ненамного короче, но она к тому же ясно указывает на суть происходящего: данные вставляются в v1. Вызов copy означает примерно то же, но не столь очевидно. В данном случае важно не то, что элементы копируются, а то, что в v1 добавляются новые данные. Функция insert прямо говорит об этом, а copy лишь сбивает с толку. Нет ничего особенно интересного в том факте, что данные где-то копируются, — собственно, вся библиотека STL построена на принципе копирования. Копирование играет настолько важную роль в STL, что ему посвящен совет 3.

Многие программисты STL злоупотребляют функцией copy, поэтому только что данный совет стоит повторить: вызовы copy, в которых результирующий интервал задается итератором вставки, практически всегда следует заменять вызовами интервальных функций.

Вернемся к примеру с assign. Мы уже выяснили две причины, по которым интервальным функциям отдается предпочтение перед их одноэлементными аналогами.

• Написание кода с интервальными функциями обычно требует меньших усилий.

• Решения с интервальными функциями обычно выглядят более наглядно и логично.

Короче говоря, программы с интервальными функциями удобнее как писать, так и читать. О чем тут еще говорить?

Впрочем, некоторые склонны относить эти аргументы к стилю программирования, а вопросы стиля вызывают у программистов такую же жаркую полемику, как и тема выбора Лучшего В Мире Редактора (хотя о чем тут спорить? Всем известно, что это Emacs). Было бы неплохо иметь более универсальный критерий для сравнения интервальных функций с одноэлементными. Для стандартных последовательных контейнеров такой критерий существует: эффективность. При работе со стандартными последовательными контейнерами применение одноэлементных функций приводит к более частому выделению памяти, более частому копированию объектов и/или выполнению лишних операций по сравнению с реализацией, основанной на интервальных функциях.

Предположим, вы хотите скопировать массив int в начало vector (исходное размещение данных в массиве может объясняться тем, что данные были получены через унаследованный интерфейс с языком С. Проблемы, возникающие при объединении контейнеров STL с интерфейсом C, описаны в совете 16). Решение с интервальной функцией insert контейнера vector выглядит просто и бесхитростно:

int data[numValues]; // Предполагается, что numValues

                     // определяется в другом месте

vector<int> v;

…

v.insert(v.begin().data, data+numValues); // Вставить int из data

                                          // в начало v

Вероятно, решение с циклическим вызовом insert выглядит примерно так:

vector<int>::iterator insertLoc(v.begin());

for(int i=0; i<numValues; ++i) {

 insertLoc = v.insert(insertLoc.data[i]);

}

Обратите внимание на сохранение значения, возвращаемого при вызове insert, до следующей итерации. Если бы значение insertLoc не обновлялось после каждой вставки, возникли бы две проблемы. Во-первых, все итерации цикла после первой повели бы себя непредсказуемым образом, поскольку в результате каждого вызова insert значение insertLoc становилось бы недействительным. Во-вторых, даже если бы значение insertLoc оставалось действительным, вставка всегда производилась бы в начале вектора (то есть в v.begin()), и в результате содержимое массива было бы скопировано в обратном порядке.

Попробуем последовать совету 43 и заменим цикл вызовом copy:

copy(data, data+numValues, inserter(v, v.begin()));

После создания экземпляра шаблона решение с copy практически идентично решению с циклом, поэтому в своем анализе эффективности мы ограничимся вторым вариантом и будем помнить, что все сказанное в равной степени относится к решению с copy. В случае с циклом вам будет проще понять, чем обусловлены потери эффективности. Да, это именно «потери» во множественном числе, поскольку решение с одноэлементной версией insertсопряжено с тремя видами затрат, отсутствующими при использовании интервальной версии insert.

Первая потеря обусловлена лишними вызовами функций. Естественно, последовательная вставка numValues элементов требует numValues вызовов insert. При вызове интервальной формы insert достаточно одного вызова функции, тем самым экономится numValues-1 вызов. Возможно, подстановка (inlining) избавит вас от этих затрат… а может, и нет. Уверенным можно быть лишь в одном: при использовании интервальной формы insert эти затраты заведомо отсутствуют.

Подстановка не спасает от второго вида затрат, обусловленных неэффективностью перемещения существующих элементов v на итоговые позиции после вставки. Каждый раз, когда insertвключает в v новый элемент, все элементы после точки вставки смещаются на одну позицию, освобождая место. Элемент в позиции p перемещается в позицию p+1 и т. д. В нашем примере numValues элементов вставляются в начало v. Следовательно, каждый элемент, находившийся в v до вставки, сдвигается в общей сложности на numValues позиций. Но при каждом вызове insert элемент сдвигается только на одну позицию, поэтому это потребует numValues перемещений. Если до вставки вектор v содержал n элементов, количество перемещений будет равно n*numValues. В нашем примере вектор v содержит числа типа int, поэтому перемещение сведется к простому вызову memmove, но если бы в v хранились пользовательские типы вроде Widget, то каждое перемещение было бы сопряжено с вызовом оператора присваивания или копирующего конструктора данного типа (в большинстве случаев вызывался бы оператор присваивания, но перемещения последнего элемента вектора обеспечивались бы вызовом копирующего конструктора). Таким образом, в общем случае последовательная вставка numValuesновых объектов в начало vector<Widget> с n элементами требует n*numValues вызовов функций: (n-1)*numValues вызовов оператора присваивания Widget и numValues вызовов копирующего конструктора Widget. Даже если эти вызовы будут подставляемыми, все равно остаются затраты на перемещение элементов numValues раз.