11

std::setで要素のインデックスを見つける必要があります。このインデックスは、イテレータの最初からの距離として視覚化できます。1つの方法は次のとおりです。

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

これには明らかにO（n）時間がかかります。しかし、setによって内部的に実装されたバイナリ検索ツリーのルートからの距離は、O（log n）時間で見つけることができることがわかっています。

C ++セットのO（log n）時間でインデックスを見つけるために同じものを実装する方法はありますか？

4

5 に答える 5

4

この関数std::set<>::findを使用して要素を検索し、セットの最初の反復子までの距離xを計算できます。

std::distance(s.begin(), s.find(x))

ただし、コメントが示しているように、距離の実行時間は使用する反復子のタイプによって異なります。セットの場合、これは双方向反復子であり、距離は O(n) です。

于 2012-09-21T12:02:37.587 に答える
3

ソート済みを使用できますstd::vector<int>。ソートされている場合は、 で要素を見つけることができますO(log n)。そして一定時間で距離を求めることができますO(1)。

ソートされたベクトルとは、挿入するたびに（または多くの挿入後に）行うことを意味しますstd::sort(v.begin(), v.end());

内部の型std::set<T>がそれほど軽くないint場合は、両方を保持できます -std::set<T>と並べ替えられたイテレータのベクトルstd::vector<std::set<T>::iterator>。しかし、これらの構造を同期させることは簡単なことではありません。多分あなたはいくつかのような位置を追加できますTか？それとも、ソートするだけで、2番目はセット内std::set<std::pair<T,int>, comp_first_of_pair<T>>の位置を保持するためのものですか？comp_first_of_pairsetTint

ほんの少しのアイデア -O(1)距離のある時間を均等にするために...

于 2012-09-21T15:50:53.377 に答える
1

インデックスの計算が本当にボトルネックである場合、2つのオプションがあります。

  • インデックスを保存します。ノード自体または別ののいずれかstd::map。もちろん、これは、このキャッシュを最新の状態に保つ必要があることを意味します。
  • を使用しstd::vectorます。それは最初に見るかもしれないほど悪くはありません。ベクトルを常にソートしたままにしておくと、のように使用できますset。パフォーマンスはに似ていsetます。最大の欠点は、ノードが大量にコピーされる可能性があることです。（これは、ポインターを使用するboost:shared_ptrか、std::unique_ptr[c ++ 11のみ]を使用して補正できます） 。
    を使用して要素を検索しますstd::lower_bound。
    insert / push_backの代わりに、次のようにします。insert( lower_bound(b,e,x), x )
于 2012-09-25T07:37:22.177 に答える
1

双方向反復子でマテマティクスを使用することはできません。したがって、受け入れられる唯一の方法は、自分で数えることです（セットに挿入した X よりも小さいintの数）。

ただし、「データ収集」と「データ使用」の段階を明確に分離している場合は、おそらくstd::setを並べ替えられたstd::vectorに置き換える価値があります。維持するのは難しいですが、反復子マテマティクスを含む独自の利点があります (したがって、std::binary_searchを使用して O(log n) で検索し、 O(1) を使用して距離を取得できます)

于 2012-09-21T12:12:45.003 に答える