有效的初始化的std ::设置有数字的序列(Efficiently initialise std::

一个明显的（？幼稚）的做法是：

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

这是合理的可读性，但是从我的理解，而不是最佳的，因为它涉及到多次搜索的插入位置，并没有考虑的事实是，输入序列已经按顺序排列的。

是否有一个更优雅/有效（或实际）的初始化方式std::set有数字的序列？

或者，更一般地，一个人如何有效地插入条目的有序列表到一个集合？

---

更新：

通过文档看，我刚刚注意到，接受一个迭代器指示插入位置的构造函数：

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

这意味着这将是更有效：

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

这看起来合理，但我仍然开放给更多的建议。

Answer 1:

使用权迭代的提示已经C ++ 03和C ++ 11之间改变。 随着C ++ 03，您要使用上一个项目的位置（就像你和大多数的答复显示）。

在C ++ 11，你要使用的迭代器的项目你要插入一个之后 。 当你为了插入，这使事情变得简单一点：你总是使用your_container.end()

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

你可以，当然，使用算法（例如， std::iota ）或迭代器（例如， boost::counting_iterator ，如@pmr已经提到）来生成你的价值观，但只要插入自己去，对于当前执行要使用.end()作为提示，而不是由之前的插入返回的迭代器。

Answer 2:

最漂亮的是：

#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;
}

如果你的目标为原料的效率，使用暗示插入的版本可能会有所帮助：

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

能够声明hint与计数器将是很好，给我们一个干净的范围一起，但是这需要struct两轮牛车，我觉得有点混淆。

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++; });
}

这是（我认为），相当于你的第二个版本，但恕我直言看起来好多了。

C ++ 03的版本是：

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:

那么你可以使用insert()的版本set<>您可以在其中提供位置提示，其中元素可能会插入。

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

复杂性：该版本是在一般的对数，但如果分期常量x是由位置所指向的元素之后插入。

文章来源: Efficiently initialise std::set with a sequence of numbers