STL: Set of natural numbers from A to B

Question

I want to add natural numbers from A to B in a set. Currently I am inserting each and every number from A to B, one by one in the set like this,

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

But it takes O(n) time (here n = (B - A)+1). Is there any pre-defined way in STL to do it in O(1) time?

Thanks

Answer 1

Allocating memory to hold n number is always going to be in at least O(n) so I think you're out of luck.

Answer 2

No. The shortest amount of time it takes to fill a container with sequential values is O(n) time.

Answer 3

Technically I believe this is O(n log n) because the set.insert function is log n. O(n) is the best you can do I think but for that you would need to use an unsorted container like a vector or list.

Answer 4

O(1) is only true for default constructor.
O(n) for the copy constructors and sorted sequence insertion using iterators.
O(log n!) for unsorted sequence insertion using iterators.

Answer 5

With the STL set container you will never get O(1) time. You may be able to reduce the running time by using the set(InputIterator f, InputIterator l, const key_compare& comp) constructor and passing in a custom iterator that iterates over the given integer range. The reason this may run faster (depends on stl implementation, compiler, etc) is that you are reducing the call stack depth. In your snippet, you go all the way down from your .insert() call to the actual insertion and back for each integer. Using the alternate constructor, your increment operation is moved down into the frame in which the insertion is performed. The increment operation would now have the possible overhead of a function call if your compiler can't inline it. You should benchmark this before taking this approach though. It may be slower if your stl implementation has a shallow call stack for .insert().

In general though, if you need a set of a contiguous range of integers, you could see massive performance gains by implementing a specialized set class that can store and compare only the upper and lower bounds of each set.

Answer 6

Well, if you want to complately out of the box, you could design a "lazy-loaded" array, custom to this task. Basically, upon access, if the value had not been previously set, it would determine the correct value.

This would allow the setup to be O(1) (assuming inintialize the "not previously set" flags is itself O(1)), but wouldn't speed up the overall operation -- it would just scatter that time over the rest of the run (It would probably take longer overall).