STLのmapとpairとunordered_map常用関数の詳細
11756 ワード
STLのmapとpairとunordered_map常用関数の詳細
一、mapの概要
mapはSTLの関連コンテナで、1対1(最初はキーワードと呼ぶことができ、各キーワードはmapに1回しか現れず、2番目はキーワードの値と呼ぶことができる)のデータ処理能力を提供します.この特性のため、1対1のデータを処理するときにプログラミングに高速チャネルを提供する可能性があります.ここでmap内部データの組織について説明すると、map内部には赤と黒の木(厳密な意味ではないバランスの二叉木)が自作されており、この木はデータ
周知のように、配列を定義する場合、例えば(int array[10])、array[0]=25、array[1]=10は、実は1つのマッピングであり、0—>25,1—>10は、0を25にマッピングし、1を10にマッピングする.この1つ1つの対応関係がマッピングであり、配列については、彼の下付き文字とその下付き文字の対応する値がマッピング関係であるが、この関係はデッドボードであり、map、この容器、
二、mapの定義と初期化(挿入)1つのmapを個別に定義する: typename 1はキー値のデータ型 typename 2は値のデータ型 文字列が整数配列にマッピングされている場合、キー値はstringタイプを使用する必要があり、char配列は使用できません.これはcharが配列としてキー値として使用できないためです. mapのキーと値はSTLのコンテナであり、setを1文字列にマッピングする
三、mapの要素のアクセスmapのコンテナ値は、下付きおよび反復器でアクセス可能. 下付きアクセスmapキー値は一意 反復器でmapにアクセスする反復器は他のSTL容器と同じ 次に例を示します:
実は細心の仲間は、その出力結果がキー値で昇順にソートされていることを発見しました.insert関数で挿入
四.map常用関数解析個々の要素を削除する: mp.erase(it)、itは削除する要素の反復器 キー値による要素の削除:
2.erase(first,last)は、区間全体の要素を削除できます.削除区間は[first,last]です.size()は、mapにおけるマッピング対数を取得できる. clear()、すべての要素を空にしてください.
mapとunordered_map
unordered_mapの使い方はmapと同じで、insert、size、countなどの操作が提供されており、中の要素もpairタイプで保存されている.その下地実装は全く異なり、上で説明したが
mapと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コンテナについては、そのコンテナを作成するときに入力される順序と必ずしも同じではありません.なぜなら、遍歴はハッシュテーブルの前後に順次遍歴されるからです
一、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の定義と初期化(挿入)
//
#include
map,string> mp;
三、mapの要素のアクセス
#include
#include
map::iterator it;
// it , it->first it->second
PS: 3 :
//
#include
#include
実は細心の仲間は、その出力結果がキー値で昇順にソートされていることを発見しました.
C++11
中にはunordered_map
があり、
の代わりにmap
が実現し、その
、
が実現しました.以下にご紹介します.#include
#include
#include
#include
#include
#include
value_type
データ、次に例を挙げて説明#include
#include
四.map常用関数解析
find()
find関数でデータ出現位置を特定し、返される反復器を返します.データ出現時、データが存在する位置の反復器を返します.mapに検索するデータがなければ、返される反復器はend関数が返す反復器に等しく、手順説明:#include
#include
erase()
要素を削除するには、1つの要素を削除する方法と、1つの区間の要素を削除する方法の2つがあります.#include
#include
#include
#include
2.erase(first,last)は、区間全体の要素を削除できます.削除区間は[first,last]です.
#include
#include
#include
#include
#include
#include
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<