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

Question

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

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

score 17 · Accepted Answer

std::map を見たいと思うでしょう

std::map<keyType, valueType>

マップは、keyType に指定された < 演算子に基づいてソートされます。

または

std::set<valueType>

テンプレート引数の < 演算子でもソートされますが、要素の重複は許可されません。

あります

std::multiset<valueType>

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

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

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

score 10 · Accepted Answer

昇順と降順の単一の値でソートすることがわかっている場合は、setが友だちです。反対方向に「ソート」する場合は、逆イテレータを使用します。

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

そのレベルの最適化に興味がある場合は、実際のデータを使用してコードをプロファイリングする方がよいと思います。（これはおそらくここの誰もが与えることができる最良のアドバイスです：あなたがブルームーンで一度だけそれをしているなら、各挿入の後にソートを呼び出すことは問題ではないかもしれません。）

score 4 · Accepted Answer

multi-index containerが必要なようです。これにより、コンテナを作成し、コンテナ内のアイテムをトラバースするさまざまな方法をそのコンテナに伝えることができます。コンテナはアイテムの複数のリストを保持し、それらのリストは挿入/削除ごとに更新されます。

本当にコンテナを並べ替えたい場合は、任意の、、または単純な C スタイルの配列でstd::sort関数を呼び出すことができます。この関数は、オプションの 3 番目の引数を取り、コンテンツの並べ替え方法を決定します。std::dequestd::vector

score 3 · Accepted Answer

にはそのstlようなコンテナはありません。set/multisetaまたは aに裏打ちされた独自のものを定義できますが、( a の場合) を呼び出すか、新しいコレクションを作成する ( の場合)vectorことによって、ソート関数が変更されるたびに再ソートする必要があります。sortvectorset/multiset

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

score 2 · Accepted Answer

2

std::set基本的にソートされたコンテナです。

于 2008-09-15T21:59:40.280 に答える

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

実際には、入力する要素の平均数によって異なります。100未満の要素の場合、次の理由により、ベクトルがおそらく最良のソリューションです。連続ソート。明らかに、それはあなたがしなければならない挿入-削除の数にも依存します。フレームごとの挿入/削除を行いますか？

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

時期尚早に最適化しないことを忘れないでください...

score 1 · Accepted Answer

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

score 1 · Accepted Answer

答えはいつものように依存します。

setアイテムをmultisetソートしておくのに適していますが、通常、追加、削除、フェッチのバランスの取れたセットに最適化されています。マンリーな検索操作がある場合は、並べ替えvectorがより適切でありlower_bound、要素を検索するために使用します。

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

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

score 1 · Accepted Answer

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

score 0 · Accepted Answer

「STL 互換」のソート済みベクターについては、 Lokiの A. Alexandrescu の AssocVector を参照してください。

score 0 · Accepted Answer

STL マップとセットは、どちらも並べ替えられたコンテナーです。

私は Doug T の本の推薦に 2 番目です。Josuttis STL の本は、学習と参考書の両方として私が今まで見た中で最高です。

『 Effective STL』は、STL の内部の詳細と、何をすべきか、何をすべきでないかを学ぶための優れた本でもあります。

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

12 に答える 12

Related

Reference