STLのmapとpairとunordered_map常用関数の詳細

11756 ワード

STLのmapとpairとunordered_map常用関数の詳細
一、mapの概要
mapはSTLの関連コンテナで、1対1(最初はキーワードと呼ぶことができ、各キーワードはmapに1回しか現れず、2番目はキーワードの値と呼ぶことができる)のデータ処理能力を提供します.この特性のため、1対1のデータを処理するときにプログラミングに高速チャネルを提供する可能性があります.ここでmap内部データの組織について説明すると、map内部には赤と黒の木(厳密な意味ではないバランスの二叉木)が自作されており、この木はデータ に対する機能を持っているので、map内部のすべてのデータが秩序正しく、後で秩序のメリットを見ることができます.
周知のように、配列を定義する場合、例えば(int array[10])、array[0]=25、array[1]=10は、実は1つのマッピングであり、0—>25,1—>10は、0を25にマッピングし、1を10にマッピングする.この1つ1つの対応関係がマッピングであり、配列については、彼の下付き文字とその下付き文字の対応する値がマッピング関係であるが、この関係はデッドボードであり、map、この容器、map ( STL ) ( STL )がある.
二、mapの定義と初期化(挿入)
  • 1つのmapを個別に定義する:
  • //         
    #include 
    map mp;
    
  • typename 1はキー値のデータ型
  • typename 2は値のデータ型
  • 文字列が整数配列にマッピングされている場合、キー値はstringタイプを使用する必要があり、char配列は使用できません.これはcharが配列としてキー値として使用できないためです.
  • mapのキーと値はSTLのコンテナであり、setを1文字列にマッピングする
  • map,string> mp;
    

    三、mapの要素のアクセス
  • mapのコンテナ値は、下付きおよび反復器でアクセス可能.
  • 下付きアクセスmapキー値は一意
  • #include 
    #include 
    #include 
    using namespace std;
    int main()
    {
        map mp;
        mp['c']=20;
        mp['c']=30;   //        ,           
        cout<
  • 反復器でmapにアクセスする反復器は他のSTL容器と同じ
  • map::iterator it;
    //      it     ,      it->first       it->second     
    
  • 次に例を示します:PS: 3 :
  • //                 
    #include 
    #include 
    #include 
    using namespace std;
    int main()
    {
        map mp;
        char key;
        int val;
        int t=5;
        while(t--)
        {
            cin>>key>>val;
            mp[key]=val;
        }
        //           
        for(map::iterator it=mp.begin();it!=mp.end();it++)
        {
            cout<first<second<

    実は細心の仲間は、その出力結果がキー値で昇順にソートされていることを発見しました.C++11中にはunordered_mapがあり、 の代わりにmap が実現し、その が実現しました.以下にご紹介します.
    #include 
    #include 
    #include 
    using namespace std;
    int main()
    {
        map mp;
        char key;
        int val;
        int t=5;
        while(t--)
        {
            cin>>key>>val;
            mp.insert(make_pair(key,val));   //  make_pair   
        }
        for(map::iterator it=mp.begin();it!=mp.end();it++)
        {
            cout<first<second<
    #include 
    #include 
    #include 
    using namespace std;
    int main()
    {
        map mp;
        char key;
        int val;
        int t=5;
        while(t--)
        {
            cin>>key>>val;
            mp.insert(pair(key,val));  //   pair   
        }
        for(map::iterator it=mp.begin();it!=mp.end();it++)
        {
            cout<first<second<
    #include 
    #include 
    #include 
    using namespace std;
    int main()
    {
        map mp;
        char key;
        int val;
        int t=5;
        while(t--)
        {
            cin>>key>>val;
            mp.insert(pair(key,val)); 
        }
        //         for  ,  C++11     
        for(auto it=mp.begin();it!=mp.end();it++)
        {
            cout<first<second<
  • insert関数で挿入value_typeデータ、次に例を挙げて説明
  • #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student2"));
        for(map::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
            cout<first<second<

    四.map常用関数解析
  • find()find関数でデータ出現位置を特定し、返される反復器を返します.データ出現時、データが存在する位置の反復器を返します.mapに検索するデータがなければ、返される反復器はend関数が返す反復器に等しく、手順説明:
  • #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student2"));
        map::iterator pter=mapStudent.find(2);
        cout<first<second<
  • erase()要素を削除するには、1つの要素を削除する方法と、1つの区間の要素を削除する方法の2つがあります.
  • 個々の要素を削除する:
  • mp.erase(it)、itは削除する要素の反復器
    #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student2"));
        map::iterator pter=mapStudent.find(2);
        mapStudent.erase(pter);
        for(map::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
            cout<first<second<
  • キー値による要素の削除:


  • #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student2"));
        map::iterator pter=mapStudent.find(2);
        mapStudent.erase(2);
        for(map::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
            cout<first<second<

    2.erase(first,last)は、区間全体の要素を削除できます.削除区間は[first,last]です.
    #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student3"));
        mapStudent.insert(map::value_type(4,"student4"));
        mapStudent.insert(map::value_type(5,"student5"));
        mapStudent.insert(map::value_type(6,"student6"));
        mapStudent.insert(map::value_type(7,"student7"));
        map::iterator pter=mapStudent.find(4);
        mapStudent.erase(pter,mapStudent.end());
        for(map::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
            cout<first<second<
  • size()は、mapにおけるマッピング対数を取得できる.
  • #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student3"));
        mapStudent.insert(map::value_type(4,"student4"));
        mapStudent.insert(map::value_type(5,"student5"));
        mapStudent.insert(map::value_type(6,"student6"));
        mapStudent.insert(map::value_type(7,"student7"));
        cout<
  • clear()、すべての要素を空にしてください.
  • #include 
    #include 
    #include 
    using namespace std;
    int main() {
        map mapStudent;
        mapStudent.insert(map::value_type(1,"student1"));
        mapStudent.insert(map::value_type(2,"student2"));
        mapStudent.insert(map::value_type(3,"student3"));
        mapStudent.insert(map::value_type(4,"student4"));
        mapStudent.insert(map::value_type(5,"student5"));
        mapStudent.insert(map::value_type(6,"student6"));
        mapStudent.insert(map::value_type(7,"student7"));
        mapStudent.clear();
        cout<

    mapとunordered_map(c++11)の使用
    unordered_mapの使い方はmapと同じで、insert、size、countなどの操作が提供されており、中の要素もpairタイプで保存されている.その下地実装は全く異なり、上で説明したが .
    mapとunordered_mapの違い
    導入するヘッダファイルが異なる
    map: #include < map >
    unordered_map: #include < unordered_map >
    

    内部実装メカニズムが異なるmap:map内部に赤黒木(赤黒木は非厳密平衡二叉探索木であり、AVLは厳密平衡二叉探索木である)が実装されている、赤黒ツリーは自動ソート機能を持つため、map内部のすべての要素が整列しており、赤黒ツリーの各ノードはmapの要素を表している.そのため、mapに対する検索、削除、追加などの一連の操作は赤黒ツリーに対する操作に相当する.mapの要素は二叉検索ツリーによる(別名二叉ルックアップツリー、二叉ソートツリーと呼ばれ、左サブツリー上のすべてのノードのキー値がルートノードのキー値よりも小さく、右サブツリーのすべてのノードのキー値がルートノードのキー値よりも大きいことを特徴とする)に格納されており、中順遍歴を使用してキー値を小さいものから大きいものに遍歴することができる.unordered_map:unordered_map内部にハッシュテーブルが実現されている(ハッシュ・リストとも呼ばれ、キー値をHashテーブルの1つの位置にマッピングしてレコードにアクセスすることで、検索の時間的複雑度はO(1)に達することができ、大量のデータ処理に広く応用されている).そのため、その要素の配列順序は無秩序である.ハッシュ・テーブルの詳細な紹介
    メリットとデメリットと適用箇所map:
    メリット:
    秩序性、これはmap構造の最大の利点であり、その要素の秩序性は多くの応用の中で多くの操作赤黒樹を簡略化し、内部で1つの赤黒書を実現することでmapの多くの操作をlgnの時間複雑度の下で実現することができるため、効率は非常に高い欠点:空間占有率が高く、map内部で赤黒樹を実現したため、運行効率を高めたが、各ノードに親ノード、子ノード、赤/黒の性質を追加で保存する必要があり、各ノードに多くのスペースを消費させます.
    適用箇所:順序が要求される問題に対してmapを使用するとより効率的になります.
    unordered_map:
    利点:内部にハッシュ・テーブルが実装されているため、検索速度が非常に速いという欠点があります.ハッシュ・テーブルの作成に時間がかかる場合:検索問題に対してunordered_mapがより効率的になるため、検索問題に遭遇した場合、unordered_mapの合計を考慮することがよくあります.
    メモリ占有率の問題は、赤と黒のツリーVS hashテーブルに変換されるか、unorder_mapが占有するメモリが高いかのいずれかです.ただし、unordered_mapの実行効率はmapよりも高く、unordered_mapまたはunordered_setコンテナについては、そのコンテナを作成するときに入力される順序と必ずしも同じではありません.なぜなら、遍歴はハッシュテーブルの前後に順次遍歴されるからです
    #include 
    #include 
    #include 
    using namespace std;
    int main() {
        unordered_map mapStudent;
        mapStudent.insert(unordered_map::value_type(2,"student2"));
        mapStudent.insert(unordered_map::value_type(4,"student4"));
        mapStudent.insert(unordered_map::value_type(5,"student5"));
        mapStudent.insert(unordered_map::value_type(3,"student3"));
        mapStudent.insert(unordered_map::value_type(7,"student7"));
        mapStudent.insert(unordered_map::value_type(6,"student6"));
        mapStudent.insert(unordered_map::value_type(1,"student1"));
        for(auto it=mapStudent.begin();it!=mapStudent.end();it++)
            cout<first<second<