STL: набор натуральных чисел от A до B

Question

Я хочу добавить натуральные числа от A до B в наборе.В настоящее время я вставляю каждое число от A до B, одно за другим в наборе, например,

set<int> s;
for(int j=A; j<=B; j++)
    s.insert(j);

Но это занимает O(n) время (здесь n = (B - A)+1)Есть ли какой-то заранее определенный способ в STL сделать это в O(1) раз?

Спасибо

Answer 1

Выделение памяти для хранения n числа всегда будет по крайней мере в O (n), поэтому я думаю, что вам не повезло.

Answer 2

С установленным контейнером STL вы никогда не получите O (1) раз.Вы можете сократить время выполнения, используя конструктор set(InputIterator f, InputIterator l, const key_compare& comp) и передавая пользовательский итератор, который выполняет итерацию по заданному целочисленному диапазону.Причина, по которой это может выполняться быстрее (зависит от реализации stl, компилятора и т. Д.), Заключается в том, что вы уменьшаете глубину стека вызовов.В своем фрагменте вы проходите весь путь от вызова .insert () до фактической вставки и обратно для каждого целого числа.Используя альтернативный конструктор, ваша операция приращения перемещается вниз во фрейм, в который выполняется вставка.Операция приращения теперь будет иметь возможные накладные расходы при вызове функции, если ваш компилятор не сможет встроить его.Вы должны сравнить это, прежде чем использовать этот подход.Это может быть медленнее, если ваша реализация stl имеет неглубокий стек вызовов для .insert ().

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

Answer 3

Технически я считаю, что это O(n log n), потому что функция set.insert равна log n. O(n) - лучшее, что вы можете сделать, я думаю, но для этого вам нужно будет использовать несортированный контейнер, такой как vector или list.

Answer 4

Нет. Наименьшее количество времени, которое требуется для заполнения контейнера последовательными значениями, составляет O(n) время.

Answer 5

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

Это позволило бы настройке быть O (1) (при условии, что инициализация «ранее не установленных» флагов сама по себе была O (1)), но не ускорила бы всю операцию - она ​​просто разбросала бы это время за остаток пути (в общем, это займет больше времени).

Answer 6

O(1) верно только для конструктора по умолчанию.
O(n) для конструкторов копирования и вставки отсортированной последовательности с использованием итераторов.
O(log n!) для вставки несортированной последовательности с использованием итераторов.