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

Каждый раз, когда в связанный список включается новый элемент, необходимо присвоить значения указателям 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);

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

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

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

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

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

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

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

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

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

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