用数字序列有效地初始化std :: set [英] Efficiently initialise std::set with a sequence of numbers

问题描述

一个显而易见的(天真?)方法是:

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.

是否存在一种更优雅/更有效(或实际上)的方法来初始化带有数字序列的std::set?

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?

查看文档，我刚刚注意到接受迭代器指示插入位置的构造函数:

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.

推荐答案

在C ++ 03和C ++ 11之间，用作提示的正确迭代器已更改.对于C ++ 03，您想使用上一项的位置(就像您和大多数答复所显示的那样).

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).

在C ++ 11中，您要在要插入的项之后 的后面立即使用迭代器.当您按顺序插入时，这会使事情变得更简单:您始终使用your_container.end():

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

您当然可以使用算法(例如std::iota)或迭代器(例如boost::counting_iterator，如@pmr所述)来生成值，但是就插入本身而言，对于您想使用.end()作为提示而不是上一次插入返回的迭代器的当前实现.

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.

这篇关于用数字序列有效地初始化std :: set的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！