Узел В

Вставляемые узлы

Узел А

next

prev

Данные

> next

prev

Данные

next

prev

Данные

next

prev

Данные

next

prev

Данные

Здесь вставляются дополнительные узлы

Предположим, в список была вставлена серия новых узлов вызовами одноэлементной версии insert. Во всех узлах, кроме последнего, значение next будет задаваться дважды - сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель prev узла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются numVal ues узлов, будет выполнено numVal ues 1 лишних присваиваний указателю next вставленных узлов и numVal ues-1 лишних присваиваний указателю prev

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

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

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

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

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

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

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

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

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

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

контейнер::конгейнер(Input Iterator begin. Начало интервала Inputlterator end): Конец интервала

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

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

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

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

void конгейнер:;insert(Input Iterator begin, Inputlterator end):

Рассматривая возможности замены одноэлементных вызовов insert интервальными версиями, не забывайте, что некоторые одноэлементные варианты маскируются под другими именами. Например, push f ront и push back заносят в контейнер отдельный элемент, хотя в их названии отсутствует слово i nsert. Если в программе встречается циклический вызов push f ront/pushback или алгоритм (например, сору), которому в качестве параметра передается front i nserter или back i nserter, перед вами потенциальный кандидат для применения интервальной формы i nsert.

Интервальное удаление. Интервальная форма 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, Inputlterator end):

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