How to efficiently insert a range of consecutive integers into a std::set?

Question

In C++, I have a std::set that I would like to insert a range of consecutive integers. How can I do this efficiently, hopefully in O(n) time where n is the length of the range?

I'm thinking I'd use the inputIterator version of std::insert, but am unclear on how to build the input iterator.

std::set<int> mySet;

// Insert [34 - 75):
mySet.insert(inputIteratorTo34, inputIteratorTo75);

How can I create the input iterator and will this be O(n) on the range size?

Answer 1

The efficient way of inserting already ordered elements into a set is to hint the library as to where the next element will be. For that you want to use the version of insert that takes an iterator:

std::set<int>::iterator it = mySet.end();
for (int x : input) {
   it = mySet.insert(it, x);
}

On the other hand, you might want to consider other containers. Whenever possible, use std::vector. If the amount of insertions is small compared to lookups, or if all inserts happen upfront, then you can build a vector, sort it and use lower_bound for lookups. In this case, since the input is already sorted, you can skip the sorting.

If insertions (or removals) happen all over the place, you might want to consider using std::unordered_set<int> which has an average O(1) insertion (per element) and lookup cost.

For the particular case of tracking small numbers in a set, all of which are small (34 to 75 are small numbers) you can also consider using bitsets or even a plain array of bool in which you set the elements to true when inserted. Either will have O(n) insertion (all elements) and O(1) lookup (each lookup), which is better than the set.

Answer 2

A Boost way could be:

 std::set<int> numbers(
 boost::counting_iterator<int>(0),
 boost::counting_iterator<int>(10));

A great LINK for other answers, Specially @Mani's answer