Вероятно, решение с циклическим вызовом

выглядит примерно так:

Обратите внимание на сохранение значения, возвращаемого при вызове

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

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

После создания экземпляра шаблона решение с

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

Первая потеря обусловлена лишними вызовами функций. Естественно, последовательная вставка

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

Подстановка не спасает от второго вида затрат, обусловленных неэффективностью перемещения существующих элементов

на итоговые позиции после вставки. Каждый раз, когда включает в новый элемент, все элементы после точки вставки смещаются на одну позицию, освобождая место. Элемент в позиции p перемещается в позицию p+1 и т. д. В нашем примере элементов вставляются в начало . Следовательно, каждый элемент, находившийся в до вставки, сдвигается в общей сложности на позиций. Но при каждом вызове элемент сдвигается только на одну позицию, поэтому это потребует перемещений. Если до вставки вектор содержал n элементов, количество перемещений будет равно n. В нашем примере вектор содержит числа типа , поэтому перемещение сведется к простому вызову , но если бы в хранились пользовательские типы вроде , то каждое перемещение было бы сопряжено с вызовом оператора присваивания или копирующего конструктора данного типа (в большинстве случаев вызывался бы оператор присваивания, но перемещения последнего элемента вектора обеспечивались бы вызовом копирующего конструктора). Таким образом, в общем случае последовательная вставка новых объектов в начало с n элементами требует n вызовов функций: (n– 1) вызовов оператора присваивания и вызовов копирующего конструктора . Даже если эти вызовы будут подставляемыми, все равно остаются затраты на перемещение элементов раз.

С другой стороны, Стандарт требует, чтобы интервальные функции

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

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

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

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