Эффективное использование STL

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

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

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

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