Кстати говоря, если при чтении ответа вы произнесли «Чего-чего?» или что-нибудь в этом роде, читайте внимательно, потому что речь пойдет об очень полезных вещах.
Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции
assign
, о которой многие программисты попросту забывают. Функция assign
поддерживается всеми стандартными последовательными контейнерами (vector, string, deque
и list
). Каждый раз, когда вам требуется полностью заменить содержимое контейнера, подумайте, нельзя ли добиться желаемой цели присваиванием. Если вы просто копируете один контейнер в другой контейнер того же типа, задача решается функцией operator=
. Но, как показывает приведенный пример, существует также функция assign
, которая позволяет заполнить контейнер новыми данными в тех случаях, когда operator=
не подходит.Во-вторых, эта задача показывает, почему интервальные функции лучше своих одноэлементных аналогов. Интервальной называется функция контейнера, которая, подобно алгоритмам STL, определяет интервал элементов для выполняемой операции при помощи двух параметров-итераторов. Без интервальной функции нам пришлось бы создавать специальный цикл:
vector v1,v2; // Предполагается, что v1 и v2 -
// векторы объектов Widget
vl.clear():
for (vector::const_iterator ci=v2.begin()+v2.size()/2;
ci != v2.end();
++ci)
v1.push_back(*ci):
В совете 43 подробно объясняется, почему использовать явные циклы не рекомендуется, но и без этого ясно, что написание этого фрагмента потребует больше усилий, чем простой вызов
assign
. Цикл также отрицательно влияет на быстродействие, но к этой теме мы вернемся позже.Одно из возможных решений заключается в том, чтобы последовать совету 43 и воспользоваться алгоритмом:
vl.clear();
copy(v2.begin()+v2.size()/2.v2.end().back_inserter(v1));
Но и этот вариант требует больших усилий, чем простой вызов
assign
. Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова сору
(см. совет 43). В результате потенциальное снижение быстродействия не исчезает (вскоре мы поговорим об этом). А сейчас я хочу ненадолго отвлечься от темы и заметить, что практически все случаи использования сору, когда приемный интервал задается итератором вставки (inserter, back_inserter
или front_inserter
), могут — и должны — заменяться вызовами интервальных функций. Например, вызов сору заменяется интервальной версией insert
:vl.insert(vl.end(),v2.begin()+v2.size()/2.v2.end());
Команда получается ненамного короче, но она к тому же ясно указывает на суть происходящего: данные вставляются в v1. Вызов
сору
означает примерно то же, но не столь очевидно. В данном случае важно не то, что элементы копируются, а то, что в v1
добавляются новые данные. Функция insert
прямо говорит об этом, а сору лишь сбивает с толку. Нет ничего особенно интересного в том факте, что данные где-то копируются, — собственно, вся библиотека STL построена на принципе копирования. Копирование играет настолько важную роль в STL, что ему посвящен совет 3.Многие программисты STL злоупотребляют функцией
сору
, поэтому только что данный совет стоит повторить: вызовы сору, в которых результирующий интервал задается итератором вставки, практически всегда следует заменять вызовами интервальных функций.Вернемся к примеру с
assign
. Мы уже выяснили две причины, по которым интервальным функциям отдается предпочтение перед их одноэлементными аналогами.•Написание кода с интервальными функциями обычно требует меньших усилий.
•Решения с интервальными функциями обычно выглядят более наглядно и логично.
Короче говоря, программы с интервальными функциями удобнее как писать, так и читать. О чем тут еще говорить?
Впрочем, некоторые склонны относить эти аргументы к стилю программирования, а вопросы стиля вызывают у программистов такую же жаркую полемику, как и тема выбора Лучшего В Мире Редактора (хотя о чем тут спорить? Всем известно, что это
Emacs
). Было бы неплохо иметь более универсальный критерий для сравнения интервальных функций с одноэлементными. Для стандартных последовательных контейнеров такой критерий существует: эффективность. При работе со стандартными последовательными контейнерами применение одноэлементных функций приводит к более частому выделению памяти, более частому копированию объектов и/или выполнению лишних операций по сравнению с реализацией, основанной на интервальных функциях.Предположим, вы хотите скопировать массив
int
в начало vector
(исходное размещение данных в массиве может объясняться тем, что данные были получены через унаследованный интерфейс с языком С. Проблемы, возникающие при объединении контейнеров STL с интерфейсом С, описаны в совете 16). Решение с интервальной функцией insert
контейнера vector
выглядит просто и бесхитростно: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(data.data+numValues.inserter(v.v.begin()));
После создания экземпляра шаблона решение с
сору
практически идентично решению с циклом, поэтому в своем анализе эффективности мы ограничимся вторым вариантом и будем помнить, что все сказанное в равной степени относится к решению с сору. В случае с циклом вам будет проще понять, чем обусловлены потери эффективности. Да, это именно «потери» во множественном числе, поскольку решение с одноэлементной версией insert сопряжено с тремя видами затрат, отсутствующими при использовании интервальной версии insert.Первая потеря обусловлена лишними вызовами функций. Естественно, последовательная вставка 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 хранились пользовательские типы вроде