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) または反復子 (例: @pmr が既に述べたように) を使用して値を生成できますが、挿入自体に関する限り、ヒントとしてboost::counting_iterator使用したい現在の実装については、.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ハッカーが必要で、少しわかりにくいと思います。

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

これは（私が思うに）あなたの 2 番目のバージョンと同等ですが、IMHO の方がずっと良く見えます。

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 に答える