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

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

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

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

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

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

Каждый раз, когда в связанный список включается новый элемент, необходимо присвоить значения указателям nextи prevнового узла. Кроме того, необходимо задать указатель nextпредыдущего узла (назовем его узлом B) и указатель prevследующего узла (назовем его узлом A).

Предположим, в список была вставлена серия новых узлов вызовами одноэлементной версии insert. Во всех узлах, кроме последнего, значение nextбудет задаваться дважды — сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель prevузла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются numValuesузлов, будет выполнено numValues-1лишних присваиваний указателю nextвставленных узлов и numValues-1лишних присваиваний указателю prevузла А, то есть в общей сложности 2*(numValues-l)лишних операций присваивания. Конечно, присваивание указателю обходится недорого, но зачем вообще платить, если можно обойтись без этого?