81. Предпочитайте операции с диапазонами операциям с отдельными элементами

81. Предпочитайте операции с диапазонами операциям с отдельными элементами

Резюме

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

Обсуждение

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

To же самое можно сказать и об операциях "повторить n раз", например, о конструкторе vector, который получает количество повторений и значение.

Примеры

Пример 1. vector::insert. Пусть вам надо добавить n элементов в vector v. Многократный вызов v.insert(position,x) может привести к неоднократному перераспределению памяти, когда вектор v имеет недостаточно места для размещения нового элемента. Что еще хуже, вставка каждого отдельного элемента имеет линейное время работы, поскольку она должна перенести ряд элементов, чтобы освободить требуемую позицию для вставляемого элемента, а это приводит к тому, что вставка n элементов при помощи последовательных вызовов имеет квадратичное время работы! Конечно, избежать проблемы множественного перераспределения памяти можно при помощи вызова reserve, но это не снизит количества перемещений элементов и квадратичное время работы такого алгоритма. Быстрее и проще ясно сказать, что вам надо: v.insert(position,first,last), где first и last — итераторы, определяющие диапазон элементов, которые должны быть добавлены в v. (Если first и last — входные итераторы, то возможности определить размер диапазона перед его действительным проходом нет, так что вектору v может потребоваться многократное перераспределение памяти; тем не менее, версия для вставки диапазона все равно скорее всего будет более производительной, чем вставка отдельных элементов.)

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

Ссылки

[Meyers01] §5 • [Stroustrup00] §16.3.8