51

std::list<std::pair>とはどう違いstd::mapますか？findリストの方法もありますか？

4

7 に答える 7

127

std::map<X, Y>：

  • はキーに関して順序付けられた構造です（つまり、キーを反復処理すると、キーは常に増加します）。
  • 一意のキー（Xs）のみをサポート
  • キーによってキーと値のペアを見つける高速find()メソッド（ ）を提供しますO(log n)
  • インデックス演算子map[key]を提供します。これも高速です

std::list<std::pair<X, Y> >：

  • Xは、 sとsのペアの単純なシーケンスですY。それらはあなたがそれを入れた順序のままです。
  • 複製をいくつでも保持できます
  • aで特定のキーを見つけることlistはO(N)（特別な方法ではありません）
  • メソッドを提供しますsplice。
于 2010-08-02T16:38:58.760 に答える
23

std::pair

std::pairfirst と second と呼ばれる 2 つの項目に限定されたテンプレート化されたタプル構造です。

std::pair<int, std::string> myPair ;
myPair.first = 42 ;
myPair.second = "Hello World" ;

std::pairは、STL (およびその他のコード) によって「汎用コンテナー」として使用され、別の を再定義することなく、2 つの値を同時に集約しますstruct。

std::map

std::mapテンプレート化された連想コンテナで、キーと値を関連付けます。最も簡単な (しかしより効率的ではない) 例は次のとおりです。

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;
// ...
std::string strText ;  // strText is ""
strText = myMap[111] ; // strText is now "Hello World"
strText = myMap[42] ;  // strText is now "Fourty Two"
strText = myMap[23] ;  // strText is now "" (and myMap has
                       // a new value "" for key 23)

std::pairとstd::map

注: これは元の未編集の質問に対する回答です。

関数は、std::map効率を維持するために同時にキーと値に反復子を返す必要があります...したがって、明らかな解決策は、反復子をペアに返すことです。

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;

myMap.insert(std::make_pair(23, "Bye")) ;

std::map<int, std::string>::iterator it = myMap.find(42) ;
std::pair<int, std::string> keyvalue = *it ;    // We assume 42 does
                                                // exist in the map
int key = keyvalue.first ;
int value = keyvalue.second ;

std::list<std::pair<A,B> >とstd::map<A,B>

注：質問の編集後に編集されました。

したがって、一見すると、ペアのマップとペアのリストは同じように見えます。しかし、そうではありません。

マップは、提供されたファンクターによって本質的に順序付けられますが、リストは [A,B] のペアを配置した場所に保持します。これにより、マップの挿入は O(log n) になりますが、リスト内の生の挿入は一定の複雑さです (挿入する場所を検索することは別の問題です)。

ペアのリストを使用してマップの動作をある程度シミュレートできますが、リストはアイテムの連鎖リストであるのに対し、マップは通常アイテムのツリーとして実装されることに注意してください。したがって、二分法のようなアルゴリズムは、リストよりもマップの方がはるかに高速に機能します。

したがって、マップ内のアイテムの検索は O(log n) ですが、順序付けられていないリストでは O(n) です。また、リストが順序付けされていて、二分法を使用したい場合は、アイテムのリストのトラバーサルがアイテムごとに行われるため、期待されるパフォーマンスの向上は得られません。

(私が 1 年前に取り組んだプロジェクトでは、注文されたアイテムのリストを同じ注文されたアイテムのセットに置き換えたところ、パフォーマンスが向上しました。マップと同じ内部ツリー構造を持つセットは、同じブーストだと思います。ここに適用されます）

于 2010-08-02T16:33:29.783 に答える
3

（明確化後に編集）

std::map高速検索用に最適化されています。find内部構造を使用して優れたパフォーマンスを提供する独自の方法があります。一般に、キーのみを検査しlog(N)ます。ここで、N はマップ内のアイテムの数です。

std::list<std::pair>は単純な連結リストであるため、要素ごとのトラバーサルのみをサポートします。別のアルゴリズムを使用するか、メンバーのみを調べてのセマンティクスによりよく一致させるカスタム述語を使用できますが、それは非常に遅くなります。実際、失敗した検索についてはリスト内のすべてのペアを調べる必要があり、成功したペアについては平均で半分を調べます。std::findstd::find_iffirststd::map::find

于 2010-08-02T16:23:30.430 に答える
3

std:pairちょうど 2 つのオブジェクトを保持します。 std:map対になったオブジェクトのコレクションを保持します。

見つけるものがないため、ペアで find() を使用することはできません。必要なオブジェクトは、pair.Firstまたはpair.Second

更新: と の違いを意味していると仮定するmap<>と: Map は、メンバー list<pair<> >の高速検索のために実装する必要があります。単純な線形リストしかありません。リスト内のアイテムを検索するには、リスト全体を実行する必要があります。ただし、 std::find() は両方で機能します。keylist

于 2010-08-02T16:23:39.537 に答える
1

STLマップは連想配列であり、通常は内部にハッシュマップとして実装されます。STLマップを反復処理する場合は、STLペアが返されます。

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
        map<string, int> myMap;
        myMap["myKey"] = 1337;

        map<string, int>::iterator myIterator = myMap.begin();

        pair<string, int> myPair = *myIterator;

        cout<<"the key \""<<myPair.first<<"\" maps to the value of "<<myPair.second<<endl;
        cout<<"the key \"myKey"\" maps to the value of "<<myMap["myKey"]<<endl;
        return 0;
}

STL（ブール値をベクトルやその他の奇妙なものに格納することを除いて）は、車輪の再発明をせずにプログラムで使用したい多くのデータ構造機能を実装しているため、完全なSTLAPIリファレンスをグーグルで読んで読むことをお勧めします。

于 2010-08-02T16:38:26.943 に答える
0

std::pair は、正確に 2 つのオブジェクトをグループ化するためのものです (たとえば、「ページ上の座標」は X と Y で構成されています)。

std::map は、あるオブジェクト セットから別のオブジェクト セットへのマッピングです。

ペアで find メソッドを使用しようとする意味はありません。たとえその find メソッドが存在しないペアクラスに存在していたとしても、順序がわかっている 2 つのもののリストで何かを見つけることのポイントは何でしょうか。

ただし、それが必要な場合は、 std::pair をマップ値として使用できます。

于 2010-08-02T16:24:36.807 に答える