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

Совет 5. Используйте интервальные функции вместо одноэлементных

Совет 5. Используйте интервальные функции вместо одноэлементных

Есть два вектора, 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 раз.

С другой стороны, Стандарт требует, чтобы интервальные функции insert перемещали существующие элементы контейнера непосредственно в итоговые позиции, то есть по одному перемещению на элемент. Общие затраты составят n перемещений (numValues для копирующего конструктора типа объектов в контейнере, остальное — для оператора присваивания этого типа). По сравнению с одноэлементной версией интервальная версия insert выполняет на n*(numValues-1) меньше перемещений. Только задумайтесь: при numValues=100 интервальная форма insert выполняет на 99% меньше перемещений, чем эквивалентный код с многократно повторяющимися вызовами одноэлементной формы insert!

Прежде чем переходить к третьей категории затрат, стоит сделать небольшое замечание. То, что написано в предыдущем абзаце — правда, только правда и ничего, кроме правды, но это не вся правда. Интервальная форма insertможет переместить элемент в конечную позицию за одну операцию только в том случае, если ей удастся определить расстояние между двумя итераторами без перехода. Это возможно почти всегда, поскольку такой возможностью обладают все прямые итераторы, а они встречаются практически повсеместно. Все итераторы стандартных контейнеров обладают функциональными возможностями прямых итераторов — в том числе и итераторы нестандартных хэшированных контейнеров (совет 25). Указатели, играющие роль итераторов в массивах, тоже обладают этой возможностью. В общем-то, из всех стандартных итераторов она не присуща только итераторам ввода и вывода. Следовательно, все сказанное выше справедливо в том случае, если итераторы, передаваемые интервальной форме insert, не являются итераторами ввода (скажем, istream_iterator — см. совет 6). Только в этом случае интервальной форме insertприходится перемещать элементы на свои итоговые места по одной позиции, вследствие чего преимущества интервальной формы теряются (для итераторов вывода эта проблема вообще не возникает, поскольку итераторы вывода не могут использоваться для определения интервала insert).

Мы подошли к третьей категории затрат, от которых страдают неразумные программисты, использующие многократную вставку отдельного элемента вместо одной вставки целого интервала. Эти затраты связаны с выделением памяти, хотя они также имеют неприятные аспекты, относящиеся к копированию. Как объясняется в совете 14, когда вы пытаетесь вставить элемент в вектор, вся память которого заполнена, вектор выделяет новый блок памяти, копирует элементы из старой памяти в новую, уничтожает элементы в старой памяти и освобождает ее.

После этого вставляется новый элемент. В совете 14 также говорится о том, что при заполнении всей памяти многие реализации векторов удваивают свою емкость, поэтому вставка numValues новых элементов может привести к тому, что новая память будет выделяться со временем log₂numValues. В совете 14 упоминается о существовании реализации, обладающей таким поведением, поэтому последовательная вставка 1000 элементов может привести к 10 операциям выделения памяти с побочными затратами на копирование элементов). С другой стороны, интервальная вставка может вычислить объем необходимой памяти еще до начала вставки (если ей передаются прямые итераторы), поэтому ей не придется выделять новую память больше одного раза. Как нетрудно предположить, экономия может оказаться довольно существенной.

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

Из стандартных последовательных контейнеров остается только list, но и в этом случае интервальная форма insert обладает преимуществами перед одноэлементной. Конечно, такой фактор, как лишние вызовы функций, продолжает действовать, но из-за некоторых особенностей связанных списков проблемы с копированием и выделением памяти отсутствуют. Вместо них возникает другая проблема: многократные избыточные присваивания указателям next и prev для некоторых узлов списка.

Каждый раз, когда в связанный список включается новый элемент, необходимо присвоить значения указателям next и prev нового узла. Кроме того, необходимо задать указатель next предыдущего узла (назовем его узлом B) и указатель prev следующего узла (назовем его узлом A).

Предположим, в список была вставлена серия новых узлов вызовами одноэлементной версии insert. Во всех узлах, кроме последнего, значение next будет задаваться дважды — сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель prev узла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются numValues узлов, будет выполнено numValues-1 лишних присваиваний указателю next вставленных узлов и numValues-1 лишних присваиваний указателю prev узла А, то есть в общей сложности 2*(numValues-l) лишних операций присваивания. Конечно, присваивание указателю обходится недорого, но зачем вообще платить, если можно обойтись без этого?

Наверное, вы уже поняли, что без лишних присваиваний действительно можно обойтись. Для этого достаточно воспользоваться интервальной формой insert контейнера list. Функция заранее знает, сколько узлов будет вставлено в список, что позволяет сразу присвоить каждому указателю правильное значение.

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

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

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

• Интервальные конструкторы. У всех стандартных контейнеров существуют конструкторы следующего вида:

контейнер::контейнер(InputIterator begin, // Начало интервала
                     InputIterator end); // Конец интервала

При передаче этому конструктору итераторов istream_iterator и istreambuf_iterator (совет 29) иногда встречается одна из самых удивительных ошибок C++, вследствие которой компилятор интерпретирует эту конструкцию как объявление функции, а не как определение нового объекта контейнера. В совете 6 рассказано все, что необходимо знать об этой ошибке, в том числе и способы ее преодоления.

• Интервальная вставка. Во всех стандартных последовательных контейнерах присутствует следующая форма insert:

void контейнер::insert(iterator position, // Позиция вставки
                       InputIterator begin, // Начало интервала
                       InputIterator end); // Конец интервала

Ассоциативные контейнеры определяют позицию вставки при помощи собственных функций сравнения, поэтому в них предусмотрена сигнатура без параметра position:

void контейнер::insert(InputIterator begin, InputIterator end);

Рассматривая возможности замены одноэлементных вызовов insert интервальными версиями, не забывайте, что некоторые одноэлементные варианты маскируются под другими именами. Например, push_front и push_back заносят в контейнер отдельный элемент, хотя в их названии отсутствует слово insert. Если в программе встречается циклический вызов push_front/push_back или алгоритм (например, copy), которому в качестве параметра передается front_inserter или back_inserter, перед вами потенциальный кандидат для применения интервальной формы insert.

• Интервальное удаление. Интервальная форма erase существует в каждом стандартном контейнере, но типы возвращаемого значения отличаются для последовательных и ассоциативных контейнеров. В последовательных контейнерах используется следующий вариант сигнатуры:

iterator контейнер::erase(iterator begin, iterator end);

В ассоциативных контейнерах сигнатура выглядит так:

void контейнер::erase(iterator begin, iterator end);

Чем обусловлены различия? Утверждается, что в ассоциативных контейнерах возврат итератора (для элемента, следующего за удаленным) привел бы к неприемлемому снижению быстродействия. Мне и многим другим это утверждение кажется сомнительным, но Стандарт есть Стандарт, а в нем сказано, что версии erase для последовательных и ассоциативных контейнеров обладают разными типами возвращаемого значения.

Многое из того, что говорилось в этом совете по поводу эффективности insert, относится и к erase. Интервальная форма erase также сокращает количество вызовов функций по сравнению с одноэлементной формой. При одноэлементном удалении элементы тоже сдвигаются на одну позицию к своему итоговой позиции, тогда как в интервальном варианте каждый элемент перемещается к итоговой позиции за одну операцию.

Но erase не присущ такой недостаток insert контейнеров vector и string, как многократные выделения памяти (конечно, для erase речь пойдет о многократном освобождении). Дело в том, что память, занимаемая vector и string, автоматически увеличивается для новых элементов, но при уменьшении количества элементов память не освобождается (в совете 17 рассказано о том, как уменьшить затраты освободившейся памяти в vector и string).

К числу особенно важных аспектов интервального удаления относится идиома erase-remove, описанная в совете 29.

• Интервальное присваивание. Как упоминалось в самом начале совета, во всех последовательных контейнерах предусмотрена интервальная форма assign:

void контейнер::assign(InputIterator begin, InputIterator end);

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

Оглавление книги