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

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

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

После этого вставляется новый элемент. В совете 14 также говорится о том, что при заполнении всей памяти многие реализации векторов удваивают свою емкость, поэтому вставка numValuesновых элементов может привести к тому, что новая память будет выделяться со временем log 2numValues. В совете 14 упоминается о существовании реализации, обладающей таким поведением, поэтому последовательная вставка 1000 элементов может привести к 10 операциям выделения памяти с побочными затратами на копирование элементов). С другой стороны, интервальная вставка может вычислить объем необходимой памяти еще до начала вставки (если ей передаются прямые итераторы), поэтому ей не придется выделять новую память больше одного раза. Как нетрудно предположить, экономия может оказаться довольно существенной.

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

Из стандартных последовательных контейнеров остается только list, но и в этом случае интервальная форма insertобладает преимуществами перед одноэлементной. Конечно, такой фактор, как лишние вызовы функций, продолжает действовать, но из-за некоторых особенностей связанных списков проблемы с копированием и выделением памяти отсутствуют. Вместо них возникает другая проблема: многократные избыточные присваивания указателям nextи prevдля некоторых узлов списка.