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

int data[numValues]; // Предполагается, что numValues

// определяется в другом месте

vector v;

…

v.insert(v.begin().data, data+numValues); // Вставить int из data

// в начало v

Вероятно, решение с циклическим вызовом insertвыглядит примерно так:

vector::iterator insertLoc(v.begin());

for(int i=0; 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с n элементами требует n *numValuesвызовов функций: ( n -1) *numValuesвызовов оператора присваивания Widgetи numValuesвызовов копирующего конструктора Widget. Даже если эти вызовы будут подставляемыми, все равно остаются затраты на перемещение элементов numValuesраз.

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