How to efficiently insert a range of consecutive i

问题:

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?

回答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.

回答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

回答3:

std::set is a type of binary-search-tree, which means an insertion costs O(lgn) on average,

c++98:If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container.

c++11:If N elements are inserted, Nlog(size+N). Implementations may optimize if the range is already sorted.

I think the C++98 implement will trace the current insertion node and check if the next value to insert is larger than the current one, in which case there's no need to start from root again.

in c++11, this is an optional optimize, so you may implement a skiplist structure, and use this range-insert feture in your implement, or you may optimize the programm according to your scenarios

回答4:

Taking the hint provided by aksham, I see the answer is:

#include <boost/iterator/counting_iterator.hpp>

std::set<int> mySet;

// Insert [34 - 75):
mySet.insert(boost::counting_iterator<int>(34),
             boost::counting_iterator<int>(75));

回答5:

It's not clear why you specifically want to insert using iterators to specify a range.

However, I believe you can use a simple for-loop to insert with the desired O(n) complexity.

Quoting from cppreference's page on std::set, the complexity is:

If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container.

So, using a for-loop:

std::set<int> mySet;
for(int i = 34; i < 75; ++i) 
  mySet.insert(i);