Каждый раз, когда в связанный список включается новый элемент, необходимо присвоить значения указателям next и prev нового узла. Кроме того, необходимо задать указатель next предыдущего узла (назовем его узлом В) и указатель prev следующего узла (назовем его узлом А).
Предположим, в список была вставлена серия новых узлов вызовами одноэлементной версии insert. Во всех узлах, кроме последнего, значение next будет задаваться дважды — сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель prev узла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются numValues узлов, будет выполнено numValues - 1 лишних присваиваний указателю next вставленных узлов и numValues-1 лишних присваиваний указателю prev узла А, то есть в общей сложности 2*(numValues-l) лишних операций присваивания. Конечно, присваивание указателю обходится недорого, но зачем вообще платить, если можно обойтись без этого?
Наверное, вы уже поняли, что без лишних присваиваний действительно можно обойтись. Для этого достаточно воспользоваться интервальной формой insert контейнера list. Функция заранее знает, сколько узлов будет вставлено в список, что позволяет сразу присвоить каждому указателю правильное значение.
Таким образом, для стандартных последовательных контейнеров выбор между одноэлементной и интервальной вставкой отнюдь не сводится к стилю программирования. Для ассоциативных контейнеров критерий эффективности уже не столь убедителен, хотя проблема лишних вызовов функций существует и в этом случае. Кроме того, некоторые специализированные разновидности интервальной вставки могут оптимизироваться и в ассоциативных контейнерах, хотя, насколько мне известно, подобные оптимизации пока существуют лишь в теории. Конечно, к тому моменту, когда вы будете читать эту книгу, теория может воплотиться на практике, и тогда интервальная вставка в ассоциативных контейнерах действительно будет превосходить одноэлементную вставку по эффективности. В любом случае она никогда не будет работать менее эффективно, поэтому вы ничего не теряете.
Если отвлечься от соображений эффективности, остается непреложный факт: вызовы интервальных функций более компактны, а программа становится более наглядной, что упрощает ее долгосрочное сопровождение. Даже этих двух причин вполне достаточно для того, чтобы отдать предпочтение интервальным функциям, а выигрыш в эффективности можно рассматривать как бесплатное приложение.
После столь пространных рассуждений о чудесах интервальных функций было бы уместно привести краткую сводку таких функций. Если вы заранее знаете, какие функции контейнеров существуют в интервальных версиях, вам будет проще определить, когда ими можно воспользоваться. В приведенных ниже сигнатурах тип iterator в действительности означает тип итератора для данного контейнера, то есть контейнер::iterator. С другой стороны, тип InputIterator означает любой допустимый итератор ввода.
•Интервальные конструкторы. У всех стандартных контейнеров существуют конструкторы следующего вида:
контейнер::контейнер( InputIterator begin, // Начало интервала InputIterator end); // Конец интервала
При передаче этому конструктору итераторов istream_iterator и isreambuf_ iterator (совет 29) иногда встречается одна из самых удивительных ошибок С++, вследствие которой компилятор интерпретирует эту конструкцию как объявление функции, а не как определение нового объекта контейнера. В совете 6 рассказано все, что необходимо знать об этой ошибке, в том числе и способы ее преодоления.
•Интервальная вставка. Во всех стандартных последовательных контейнерах присутствует следующая форма insert:
void контейнер::insert(iterator position. // Позиция вставки
InputIterator begin, // Начало интервала
InputIterator end); // Конец интервала
Ассоциативные контейнеры определяют позицию вставки при помощи собственных функций сравнения, поэтому в них предусмотрена сигнатура без параметра position:
void контейнер::insert(InputIterator begin, InputIterator end);