基本的に、std::list が必要ですが、find() などの std::map プロパティを使用すると、必要なものを見つけるためにすべてのリスト エントリをループする必要がありますか?
3381 次
9 に答える
15
std::map のプロパティが必要な場合は、std::map を使用してみませんか? すべての要素をループするよりも効率的です。
于 2009-01-08T02:09:03.110 に答える
11
Checkout Boost.MultiIndexは、ポインター付きの複数のコンテナーを使用するよりも簡単で効率的です。
于 2009-01-08T02:42:50.827 に答える
9
コンテナが必要な場合：
1）挿入順序は重要ではありません（これはリストです）
2）検索速度は重要です。
次に、
std :: set <>于 2009-01-08T02:40:01.020 に答える
3
std::findまたはstd::find_ifを使用して、イテレータ範囲内の値の最初の位置を見つけます。
于 2009-01-08T02:09:23.983 に答える
3
検索時間が気になるけど順番は守りたいという場合は、同じデータを入れたコンテナを2つ持つとよいでしょう。
于 2009-01-08T02:13:25.240 に答える
2
std :: listの目的は、検索/検索しないことです。それがstd::mapの目的です。リストは、並べ替えアルゴリズムの挿入、抽出、移動、および使用に最適です。データを保存してランダムに見つける必要がある場合は、マップを使用してください。データの保存方法と保存場所を構造化する場合は、リストを使用してください。
于 2009-01-08T02:41:37.460 に答える
1
オプション1
ペアのマップではなく、単一の要素のマップが必要なようです。std::set<T>として実装されたアダプタである を使用しstd::map<T,void>ます。これは、すべての要素が一意になることを意味します。つまり、コンテナに重複はありません。また、要素が厳密に順序付けられないことも意味します。つまり、特定の時点での要素の位置に依存することはできません。次に、対数時間で要素の高速検索を実行するのfind()メンバー関数を使用できます。std::set<T>
オプション 2
最小または最大の要素にすばやくアクセスできるコンテナが必要な場合は、任意std::priority_queue<T,C>のコンテナCを使用できます。指定しない場合、使用されるデフォルトのコンテナはstd::vector<T>. 、およびアルゴリズムをstd::priority_queue<T>使用するため、基礎となるコンテナがランダム アクセス イテレータをサポートする必要があります。 この場合は十分ではありません。メンバー関数を使用して一定時間内に「最初の」(最大または最小) 要素にアクセスします。対数時間で動作するandメンバー関数を使用して、最初の要素をプッシュ アンド ポップします (実際には 2*log(n) です。これは、検索とバブルアップが必要なためです)。make_heap()push_heap()pop_heap()std::list<T>top()push()pop()
オプション 3
ペアを保持する単なるリストが必要な場合は、次のように宣言します。
std::list<std::pair<T> > the_list;
これにより、他のリンク リストの制限と利点を備えたリンク リストしか得られませんが、マップと同じようにペアが保持されます。したがって、標準アルゴリズムを使用してリストを操作します。ペアからキーまたは値を逆参照するには、このリストを使用して特殊な関数またはファンクターをアルゴリズムに渡す必要があるでしょう。
効率を気にせずにリスト内の項目を検索することだけが必要な場合はstd::find()、O(n) 時間でアルゴリズムを使用してこれを行うことができます。これはまさにこのアルゴリズムの目的であり、それよりも優れたものよりも優れたコンテナの線形時間検索機能を提供します。これは、ソートされていない配列やベクトル、リストなどで使用するものです。それ自体は遅くなりますが、代替手段よりもはるかに遅くなる可能性があるため、最後の手段にする必要があります。頻繁に検索しない場合、要素が最初の反復子の近くにあることがわかっている場合、コンテナーが小さい場合、より高速な代替手段がない場合などに、このアプローチを使用します。
于 2009-01-08T03:52:43.450 に答える
0
まったく同じものが必要だったので、リストとマップを組み合わせたものを書きました。これを map_list<> および hash_map_list<> と呼びます。基本的に、ソースコードを xmap.h と xlist.h に取り、2 つを組み合わせて xmap_list.h を作成しました。このクラスが機能する方法は、指定されたマップにキーを格納することですが、値を含むノードへのポインターとペアになっています。このノードには、マップを指す反復子が含まれています。ノードは別のリンクされたリストに保持されます。このように、マップ クラスで通常行うように find 関数を使用できますが、リスト クラスのように、挿入した順序で要素を反復処理することもできます。キー自体をリストのように繰り返すこともできます。最後の同等のリスト関数をすべて実装したわけではありませんが、最もよく使用する関数のほとんどはそこにあります (たとえば、カスタム アロケーターは扱いませんが、自分で簡単に追加できます)。find() 関数を使用した list<> のようなものです。
私がこれを書いたプロジェクトでは、最終的にはboost::multi_indexに移行しましたが、より軽量でstd::list<>に近いため、できる限り上記のmap_list<>クラスを使用しています。インターフェース。
コードをどこにもアップロードしていませんが、誰かがこの回答にコメントを追加したことがわかった場合は、どこかに投稿して、ここにその場所を書き留めます。
于 2009-08-27T11:26:24.387 に答える
0
@obecalpには良い答えがあります。boost MultiIndex は良い提案です。@Bklyn：「非常にばかげた」質問ではありません。
于 2009-08-24T19:46:19.793 に答える