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

Мейерс Скотт

v1.insert(v1.end, v2.begin+v2.size/2. v2.end);

Команда получается ненамного короче, но она к тому же ясно указывает на суть происходящего: данные вставляются в

v1

. Вызов

copy

означает примерно то же, но не столь очевидно. В данном случае важно не то, что элементы копируются, а то, что в

v1

добавляются новые данные. Функция

insert

прямо говорит об этом, а

copy

лишь сбивает с толку. Нет ничего особенно интересного в том факте, что данные где-то копируются, — собственно, вся библиотека STL построена на принципе копирования. Копирование играет настолько важную роль в STL, что ему посвящен совет 3.

Многие программисты STL

злоупотребляют функцией

copy

, поэтому только что данный совет стоит повторить: вызовы copy, в которых результирующий интервал задается итератором вставки, практически всегда следует заменять вызовами интервальных функций.

Вернемся к примеру с

assign

. Мы уже выяснили две причины, по которым интервальным функциям отдается предпочтение перед их одноэлементными аналогами.

• Написание кода с интервальными функциями обычно требует меньших усилий.

• Решения с интервальными функциями обычно выглядят более наглядно и логично.

Короче говоря, программы с интервальными функциями удобнее как писать, так и читать. О чем тут еще говорить?

Впрочем, некоторые склонны относить эти аргументы к стилю программирования, а вопросы стиля вызывают у программистов такую же жаркую полемику, как и тема выбора Лучшего В Мире Редактора (хотя о чем тут спорить? Всем известно, что это

Emacs

). Было бы неплохо иметь более универсальный критерий для сравнения интервальных функций с одноэлементными. Для стандартных последовательных контейнеров такой критерий существует: эффективность. При работе со стандартными последовательными контейнерами применение одноэлементных функций приводит к более частому выделению памяти, более частому копированию объектов и/или выполнению лишних операций по сравнению с реализацией, основанной на интервальных функциях.

Предположим, вы хотите скопировать массив

int

в начало

vector

(исходное размещение данных в массиве может объясняться тем, что данные были получены через унаследованный интерфейс с языком С. Проблемы, возникающие при объединении контейнеров STL с интерфейсом C, описаны в совете 16). Решение с интервальной функцией

insert

контейнера

vector

выглядит просто и бесхитростно:

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

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

vector<int> v;

…

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

// в начало v

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

insert

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

vector<int>::iterator insertLoc(v.begin);

for(int i=0; i<numValues; ++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<Widget>

с n элементами требует n

*numValues

вызовов функций: (n– 1)

*numValues

вызовов оператора присваивания

Widget

и

numValues

вызовов копирующего конструктора

Widget

. Даже если эти вызовы будут подставляемыми, все равно остаются затраты на перемещение элементов

numValues

раз.

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

insert

перемещали существующие элементы контейнера непосредственно в итоговые позиции, то есть по одному перемещению на элемент. Общие затраты составят n перемещений (

numValues

для копирующего конструктора типа объектов в контейнере, остальное — для оператора присваивания этого типа). По сравнению с одноэлементной версией интервальная версия

insert

выполняет на n

*(numValues-1)

меньше перемещений. Только задумайтесь: при

numValues=100

интервальная форма

insert

выполняет на 99% меньше перемещений, чем эквивалентный код с многократно повторяющимися вызовами одноэлементной формы

insert

!