使用一系列数字有效地初始化std :: set

Question

一个明显的(天真的？)方法是:

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与柜台一起宣布会很好并给我们一个干净的范围,但这需要structhackery,我发现有点混淆.

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