Efficiently initialise std::set with a sequence of

Question

An obvious (naive?) approach would be:

std::set<int> s;
for (int i = 0; i < SIZE; ++i) {
    s.insert(i);
}

That's reasonable readable, but from what I understand, not optimal since it involves repeatedly searching for the insertion position and does not take advantage of the fact that the input sequence is already sorted.

Is there a more elegant/efficient (or a de facto) way of initialising an std::set with a sequence of numbers?

Or, more generically, how does one efficiently insert an ordered list of entries into a collection?

---

Update:

Looking through the docs, I've just noticed the constructor that accepts an iterator to indicate the position for insertion:

iterator insert ( iterator position, const value_type& x );

Which means this would be more efficient:

std::set<int> s;
std::set<int>::iterator it = s.begin();
for (int i = 0; i < SIZE; ++i) {
    it = s.insert(it, i);
}

That looks reasonably, but I'm still open to more suggestions.

Answer 1

Well you can use the insert() version of set<> in which you can provide the position as hint where the element might get inserted.

iterator insert ( iterator position, const value_type& x );

Complexity: This version is logarithmic in general, but amortized constant if x is inserted right after the element pointed by position.

Answer 2

The prettiest would be:

#include <set>
#include <boost/iterator/counting_iterator.hpp>

int main()
{
  const int SIZE = 100;
  std::set<int> s(boost::counting_iterator<int>(0), 
                  boost::counting_iterator<int>(SIZE));

  return 0;
}

If you aim for raw efficiency, using the hinted insert version could be helpful:

const int SIZE = 100;
std::set<int> s;
auto hint = s.begin();
for(int i = 0; i < SIZE; ++i)
  hint = s.insert(hint, i);

Being able to declaring hint along with the counter would be nice and give us a clean scope, but this requires struct hackery which I find a little obfuscating.

std::set<int> s;
for(struct {int i; std::set<int>::iterator hint;} 
      st = {0, s.begin()};
    st.i < SIZE; ++(st.i))
  st.hint = s.insert(st.hint, st.i);

Answer 3

#include <algorithm>
#include <set>
#include <iterator>

int main()
{
    std::set<int> s;
    int i = 0;
    std::generate_n(std::inserter(s, s.begin()), 10, [&i](){ return i++; });
}

This is (I think) equivalent to your second version, but IMHO looks much better.

C++03 version would be:

struct inc {
    static int i;
    explicit inc(int i_) { i = i_; }
    int operator()() { return i++; }
};

int inc::i = 0;

int main()
{
    std::set<int> s;
    std::generate_n(std::inserter(s, s.end()), SIZE, inc(0));
}

Answer 4

The right iterator to use as the hint has changed between C++03 and C++11. With C++03, you want to use the position of the previous item (just as you and most of the replies have shown).

In C++11, you want to use the iterator to the item immediately after the one you're about to insert. When you're inserting in order, this makes things a bit simpler: you always use your_container.end():

std::set<int> s;
for (int i = 0; i < SIZE; ++i) 
    s.insert(s.end(), i);

You can, of course, use an algorithm (e.g., std::iota) or iterator (e.g., boost::counting_iterator, as @pmr already mentioned) to generate your values, but as far as the insertion itself goes, for a current implementation you want to use .end() as the hint, rather than the iterator returned by the previous insertion.