Почему вставка нескольких элементов в std :: set одновременно быстрее?

Question

Я читаю:

"Стандартная библиотека C ++: учебное пособие и справочник Николая М. Йосуттиса"

, и я нахожусь в разделео множествах и мультисетях.Я натолкнулся на строку, касающуюся вставки и удаления элементов:

«Вставка и удаление происходят быстрее, если при работе с несколькими элементами вы используете один вызов для всех элементов, а не несколько вызовов».

Я далек от мастера структур данных, но я знаю, что они реализованы с красно-черными деревьями.Из этого я не понимаю, как разработчики STL могли бы написать алгоритм для более быстрой вставки сразу нескольких элементов?

Может кто-нибудь пролить свет на то, почему эта цитата верна для меня?

Answer 1

Моей первой мыслью было, что оно может перебалансировать дерево только после вставки / удаления всего диапазона. Поскольку на практике вся операция встроена, это представляется более вероятным, чем количество вызовов функций.

Проверка заголовков GCC на моем локальном компьютере, похоже, это не так - и в любом случае, я не знаю, как найти компромисс между снижением активности перебалансировки и потенциально увеличенным временем поиска промежуточных вставок в несбалансированное дерево , сработает.

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

Answer 2

То, что вы читаете, как вы цитировали, неправильно. Вставка в std::set - это O (log n), если только вы не используете перегрузку insert() с итератором позиции, и в этом случае она амортизируется O (n), когда позиция действительна. Но , если вы используете перегрузку диапазона с отсортированными элементами , тогда вы получите O (n) вставку.

Answer 3

Есть две причины:

1) Выполнение одного вызова для нескольких элементов, а не в N раз больше вызовов.

2) Операция вставки проверяет для каждого вставленного элемента, существует ли уже другой элемент в контейнере с таким же значением. Это может быть оптимизировано при вставке нескольких элементов вместе.

Answer 4

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

Конечно, эта оптимизациявозможно только в том случае, если входные итераторы позволяют сортировать входной диапазон (т. е. если они случайные итераторы).

Answer 5

Управление памятью может быть хорошей причиной.В этом случае он может выделить память только один раз.Если все элементы вызываются раздельно, все вызовы пытаются распределить память раздельно.Как я знаю, большинство реализаций set и map пытаются удерживать память на одной странице или рядом друг с другом, чтобы минимизировать количество сбоев страниц.