20

一个明显的（天真的？）方法是：

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

这看起来很合理，但我仍然愿意接受更多建议。

4

5 回答 5

24

用作提示的正确迭代器在 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()用作提示的当前实现，而不是之前插入返回的迭代器。

于 2012-06-13T15:25:29.347 回答
13

最漂亮的应该是：

#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我觉得有点令人困惑的hackery。

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);
于 2012-06-13T14:42:06.810 回答
4 
#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));
}
于 2012-06-13T14:52:09.797 回答
3

好吧，您可以使用可以提供位置作为提示元素可能插入的位置的insert()版本。set<>

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

x复杂性：这个版本通常是对数的，但如果在位置指向的元素之后插入，则摊销常数。

于 2012-06-13T14:44:46.597 回答
2

这可以在一行代码中完成。lambda 捕获可以将变量初始化i为0，可变说明符允许i在 lambda 函数内更新：

generate_n( inserter( s, s.begin() ), SIZE, [ i=0 ]() mutable { return i++; });
于 2019-07-25T19:36:12.153 回答