動的にソートされた STL コンテナ

StackOverflow https://stackoverflow.com/questions/67426

  •  09-06-2019
  •  | 
  •  

質問

私は STL についてはかなり初心者なので、動的に並べ替え可能なコンテナがあるかどうか疑問に思っていました。現時点での私の考えは、さまざまなソートアルゴリズムと組み合わせてベクターを使用することですが、ソートされたベクターにエントリを挿入する（おそらく）線形の複雑さを考えると、より適切な選択があるかどうかはわかりません。

「動的」を明確にするために、実行時に並べ替え順序を変更できるコンテナを探しています。昇順に並べ替えてから、後で降順に再並べ替えます。

役に立ちましたか？

解決

単一の値を昇順または降順で並べ替えることがわかっている場合は、set が役に立ちます。逆方向に「並べ替え」たい場合は、逆反復子を使用します。

オブジェクトが複雑で、オブジェクト内のメンバー フィールドに基づいてさまざまな方法で並べ替える場合は、ベクトルを使用して並べ替えた方がよいでしょう。挿入をすべて一度に実行してから、sort を 1 回呼び出すようにしてください。それが不可能な場合は、オブジェクトの大規模なコレクションに対しては、ベクトルよりも deque の方が良い選択肢になる可能性があります。

興味があればそうなると思います それ 最適化のレベルを高めるには、実際のデータを使用してコードをプロファイリングする方がよいでしょう。(これはおそらくここにいる人ができる最高のアドバイスです:1 回だけ実行するのであれば、挿入のたびに sort を呼び出しても問題ないかもしれません。)

他のヒント

std::map を見てください。

std::map<keyType, valueType>

マップは、keyType に指定された < 演算子に基づいて並べ替えられます。

または 

std::set<valueType>

テンプレート引数の < 演算子にも基づいて並べ替えられますが、要素の重複は許可されません。

あるよ

std::multiset<valueType>

これは std::set と同じことを行いますが、同一の要素を許可します。

詳細については、Josuttis の「The C++ Standard Library」を強くお勧めします。これは std ライブラリの最も包括的な概要であり、非常に読みやすく、不明瞭な情報とそれほど不明瞭ではない情報がぎっしりと詰まっています。

また、17/26 で言及されているように、Meyers による Effects Stl も一読の価値があります。

が欲しいようですね マルチインデックスコンテナ. 。これにより、コンテナを作成し、そのコンテナにそのコンテナ内の項目をたどるさまざまな方法を伝えることができます。コンテナーは項目の複数のリストを保持し、それらのリストは挿入/削除のたびに更新されます。

本当にコンテナを再ソートしたい場合は、 std::sort 任意の機能 std::deque, std::vector, 、または単純な C スタイルの配列でも構いません。この関数はオプションの 3 番目の引数を受け取り、内容を並べ替える方法を決定します。

の stl そのようなコンテナは提供しません。次のいずれかをサポートして独自の定義を行うことができます。 set/multiset または vector, ただし、ソート関数が変更されるたびに、次のいずれかを呼び出して再ソートする必要があります。 sort （のために vector）または新しいコレクションを作成することによって（ set/multiset).

昇順のソート順から降順のソート順に変更したいだけの場合は、呼び出してコンテナ上で逆反復子を使用できます。 rbegin() そして rend() の代わりに begin() そして end(). 。両方 vector そして set/multiset リバーシブルのコンテナなので、どちらにも使えます。

std::set 基本的には仕分けされたコンテナです。

必ずセット/マップを使用する必要があります。hazzen が言うように、O(log n) の挿入/検索が得られます。ソートされたベクトルではこれは得られません。二分探索を使用すると O(log n) find を取得できますが、項目を挿入 (または削除) すると、ベクトル内のすべての既存の項目がシフトされる可能性があるため、挿入は O(n) になります。

それはそれほど単純ではありません。私の経験では、挿入/削除は検索よりも頻繁に使用されません。ソートされたベクトルの利点は、必要なメモリが少なく、キャッシュに優しいことです。STL マップと互換性のあるバージョン (前にリンクしたものなど) があれば、簡単に切り替えて、あらゆる状況に最適なコンテナを使用できます。

理論的には、連想コンテナ (セット、マルチセット、マップ、マルチマップ) が最適なソリューションとなるはずです。

実際には、入力する要素の平均数によって異なります。要素が 100 個未満の場合は、次の理由からベクトルがおそらく最適なソリューションです。- 継続的な割り当ての回避の回避 - データの局所性のためにキャッシュフレンドリーなこれらの利点は、おそらく継続的なソートを上回るでしょう。明らかに、挿入と削除を行う必要がある回数にも依存します。フレームごとの挿入/削除を行うつもりですか?

より一般的には:パフォーマンスが重要なアプリケーションについて話しているのでしょうか?

時期尚早に最適化しないように注意してください...

答えはいつものように、それは状況次第です。

set そして multiset 項目をソートしておくのに適していますが、通常は追加、削除、フェッチのバランスのとれたセット向けに最適化されています。手動の検索操作がある場合は、ソート vector より適切な場合がありますので、使用してください lower_bound 要素を検索します。

また、実行時に別の順序で再ソートするという 2 番目の要件は、実際には次のことを意味します。 set そして multiset 述語は実行時に変更できないため、適切ではありません。

したがって、ソートされたベクトルをお勧めします。ただし、同じ述語を渡すことを忘れないでください lower_bound 間違った述語を渡した場合、結果は未定義になり、間違っている可能性が高くなります。

セットとマルチセットは基礎となるバイナリ ツリーを使用します。<= 演算子は独自に使用するために定義できます。これらのコンテナは自動的にソートされた状態を維持するため、ソートパラメータを切り替える場合には最適な選択ではない可能性があります。かなりの量のリソースを使用する場合は、ベクトルとリストがおそらく最適です。一般に list には独自のソート (通常はマージソート) があり、ベクトルに対して stl 二分探索アルゴリズムを使用できます。挿入が優勢な場合、リストはベクターよりも優れたパフォーマンスを発揮します。

STL マップと STL セットはどちらもソートされたコンテナーです。

Doug T のおすすめの本を次に紹介します。Josuttis STL 本は、学習本としても参考書としても私がこれまで見た中で最高のものです。

効果的なSTL また、STL の内部の詳細と、何をすべきか、何をすべきではないかを学ぶのに最適な本です。

「STL 互換」ソート済みベクトルについては、A を参照してください。Alexandrescu の Assoc からのベクトル ロキ.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top