基本メモ:STLのmapの詳細
13708 ワード
MapはSTLの関連コンテナで、1対1(最初はキーワードと呼ぶことができ、各キーワードはmapに1回しか現れず、2番目はキーワードの値と呼ぶことができる)のデータ処理能力を提供します.この特性のため、1対1のデータを処理するときにプログラミングに高速チャネルを提供する可能性があります.ここでmap内部のデータの組織について言えば、map内部には赤と黒の木(厳密な意味ではないバランスの二叉木)が建てられています.この木はデータを自動的にソートする機能を持っているので、map内部のすべてのデータは秩序正しく、後で秩序の良いところを見ることができます.
次に、一対一のデータマッピングとは何かを例示する.例えば、クラスでは、各学生の学号と彼の名前には1つ1つのマッピングの関係があり、このモデルはmapで簡単に記述される可能性があり、明らかに学号はintで記述され、名前は文字列で記述されている(この文章ではchar*で文字列を記述するのではなく、STLでstringで記述されている).以下にmap記述コードを示す.
Map mapStudent;
1. mapの構造関数
mapは6つの構造関数を提供しています.これはメモリディスペンサに関連しています.表を省略して、以下ではmapの構造方法に触れます.ここで、mapを構築するには、通常次の方法を使用します.
2. データの挿入
mapコンテナを構築すると、データを挿入できます.ここでは、データを挿入する方法について3つ説明します.
1つ目:insert関数でpairデータを挿入する
以下の例を挙げて説明します(以下のコードは手書きですが、VCとGCCでコンパイルできるはずです.どのような効果を見るかを実行して、VCの下でこの文を加えて、4786警告#pragma warning(disable:4786)を遮断してください.
2つ目:insert関数でvalue_を挿入するtypeデータ
次に例を挙げて説明する
3つ目:配列でデータを挿入する
次に例を挙げて説明する
以上の3つの用法は、いずれもデータの挿入を実現できるが、それらには違いがある.もちろん、第1種と第2種は効果的に全く同じであり、insert関数でデータを挿入し、データの挿入に集合の一意性という概念にかかわる.すなわちmapにこのキーワードがある場合、insert操作はデータを挿入できない.しかし配列方式では異なり、以前のキーワードに対応する値を上書きし、プログラムで説明することができます.
上記の2つの文が実行された後、mapの1というキーワードに対応する値は「student_one」であり、2番目の文は有効ではありません.では、insert文が正常に挿入されたかどうかをどのように知るかについて、pairで挿入に成功したかどうかを得ることができます.手順は以下の通りです.
私たちはpairの2番目の変数を通じて挿入に成功したかどうかを知っています.その1番目の変数はmapの反復器を返しています.挿入に成功すればInsert_Pair.secondはtrueのはずです.そうでなければfalseです.
次に、挿入に成功したかどうかの問題を示す完了コードを示します.
データオーバーライドに配列で挿入する効果を以下のプログラムで見ることができます.
3. mapのサイズ
mapにデータを挿入して、私達はどのように現在すでにどれだけのデータを挿入したことを知っていて、size関数を使うことができて、使い方は以下の通りです:
4. データの遍歴
ここではmapを巡る3つの方法も提供されています
1つ目は、順方向反復器を適用することです.上の例のプログラムはあちこちにあります.省略しません.
2つ目:反転反復器を適用し、次に例を挙げて説明します.効果を体得するには、自分でプログラムを実行してください.
3つ目:配列方式で、プログラムの説明は以下の通りです.
5. データの検索(このキーワードがmapに現れるかどうかを判定することを含む)
ここでは,mapがデータ挿入時に秩序を保つ利点を体得する.
1つのデータ(キーワード)がmapに現れるかどうかを判定する方法が多い場合、ここではタイトルはデータの検索ですが、ここではmapの基本的な使い方がたくさん挿入されています.
ここでは3つのデータ検索方法を示します.
1つ目は、キーワードが現れるか否かをcount関数で判定する欠点は、データの出現位置を特定できないことであり、mapの特性上、一対一のマッピング関係により、count関数の戻り値が2つしかないか、0か、1か、現れる場合、もちろん1を返すことを決定する
第2種:find関数でデータの出現位置を位置決めして、それは1つの反復器を返して、データが現れた時、それはデータの所在する位置の反復器を返して、mapの中で探すデータがなければ、それが返す反復器はend関数が返す反復器に等しくて、プログラムは明らかにします
第三に、この方法はデータが現れたかどうかを判定するために用いられ、少し不器用に見えるが、ここで説明するつもりだ.
Lower_bound関数は、キーワードを検索する下限(反復器)を返すために使用されます.
Upper_bound関数は、キーワードを検索する上界(反復器)を返すために使用されます.
例:mapに1,2,3,4が挿入されている場合、lower_bound(2)なら、戻る2、upper-bound(2)なら、戻る3
Equal_range関数はpairを返します.pairの最初の変数はLowerです.boundが返す反復器、pairの中の2番目の反復器はUpper_boundが返す反復器、もしこの2つの反復器が等しいならば、mapの中でこのキーワードが現れないことを説明して、プログラムは説明します
6. データのクリアとクリア
クリアmapのデータはclear()関数で、mapにempty()関数を使用できるデータがあるかどうかを判定し、trueを返すと空mapであることを示します.
7. データの削除
ここではerase関数を使用します.3つのリロードされた関数があります.次に、例でそれらの使い方を詳しく説明します.
8. その他の関数の使い方
ここにはswap、key_comp,value_comp,get_Allocatorなどの関数は,これらの関数がプログラミングに多く使われていないと感じ,省略して表に出さず,興味があれば自分で研究することができる.
9. ツールバーの
ここでは、ソートの問題について、STLではデフォルトでは小さい番号でソートされています.以上のコードはソートに問題はありません.上のキーワードはint型なので、それ自体は小さい番号の演算をサポートしています.いくつかの特殊な状況では、キーワードは構造体であり、ソートに関連すると問題が発生します.番号より小さい操作がないため、insertなどの関数はコンパイル時に通れないので、次の2つの方法でこの問題を解決します.
1つ目:号より小さいリロード、プログラムの例
以上のプログラムはコンパイルできません.番号より小さいものをリロードすればOKです.以下のようにします.
2つ目:シミュレーション関数の応用、この時構造体の中で直接的な小さい号の重荷がなくて、プログラムの説明
10. さらに
STLは統一された全体であるため、mapの多くの使い方はSTLの他のものと結びついています.例えば、ソートでは、デフォルトではless<>より小さい番号を使用していますが、大きいものから小さいものまでソートするには、ここでは説明できません.
なお,mapでは内部秩序が保たれているため,多くの関数が実行する時間的複雑度はlog 2 Nであり,map関数で実現できる機能であればSTLでは Algorithmもこの機能を完成させることができ、mapで関数を持参することを提案し、効率が高い.
次に、mapの空間的な特性を説明します.そうしないと、mapの各データは赤と黒の木のノードに対応しているため、このノードはあなたのデータを保存しないとき、
16バイトの
あ、1つの親ノードポインタ、左右の子供ポインタ、もう1つの列挙値(赤と黒を示す、バランスツリーのバランス係数に相当)は、これらの場所はメモリがかかることを知っていると思いますが、言わないでください.
次に、一対一のデータマッピングとは何かを例示する.例えば、クラスでは、各学生の学号と彼の名前には1つ1つのマッピングの関係があり、このモデルはmapで簡単に記述される可能性があり、明らかに学号はintで記述され、名前は文字列で記述されている(この文章ではchar*で文字列を記述するのではなく、STLでstringで記述されている).以下にmap記述コードを示す.
Map
1. mapの構造関数
mapは6つの構造関数を提供しています.これはメモリディスペンサに関連しています.表を省略して、以下ではmapの構造方法に触れます.ここで、mapを構築するには、通常次の方法を使用します.
Map<int, string> mapStudent;
2. データの挿入
mapコンテナを構築すると、データを挿入できます.ここでは、データを挿入する方法について3つ説明します.
1つ目:insert関数でpairデータを挿入する
以下の例を挙げて説明します(以下のコードは手書きですが、VCとGCCでコンパイルできるはずです.どのような効果を見るかを実行して、VCの下でこの文を加えて、4786警告#pragma warning(disable:4786)を遮断してください.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
2つ目:insert関数でvalue_を挿入するtypeデータ
次に例を挙げて説明する
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(map<int, string>::value_type (1, “student_one”));
mapStudent.insert(map<int, string>::value_type (2, “student_two”));
mapStudent.insert(map<int, string>::value_type (3, “student_three”));
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
3つ目:配列でデータを挿入する
次に例を挙げて説明する
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[2] = “student_two”;
mapStudent[3] = “student_three”;
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
以上の3つの用法は、いずれもデータの挿入を実現できるが、それらには違いがある.もちろん、第1種と第2種は効果的に全く同じであり、insert関数でデータを挿入し、データの挿入に集合の一意性という概念にかかわる.すなわちmapにこのキーワードがある場合、insert操作はデータを挿入できない.しかし配列方式では異なり、以前のキーワードに対応する値を上書きし、プログラムで説明することができます.
mapStudent.insert(map<int, string>::value_type (1, “student_one”));
mapStudent.insert(map<int, string>::value_type (1, “student_two”));
上記の2つの文が実行された後、mapの1というキーワードに対応する値は「student_one」であり、2番目の文は有効ではありません.では、insert文が正常に挿入されたかどうかをどのように知るかについて、pairで挿入に成功したかどうかを得ることができます.手順は以下の通りです.
Pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));
私たちはpairの2番目の変数を通じて挿入に成功したかどうかを知っています.その1番目の変数はmapの反復器を返しています.挿入に成功すればInsert_Pair.secondはtrueのはずです.そうでなければfalseです.
次に、挿入に成功したかどうかの問題を示す完了コードを示します.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
Pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_one”));
If(Insert_Pair.second == true)
{
Cout<<”Insert Successfully”<<endl;
}
Else
{
Cout<<”Insert Failure”<<endl;
}
Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_two”));
If(Insert_Pair.second == true)
{
Cout<<”Insert Successfully”<<endl;
}
Else
{
Cout<<”Insert Failure”<<endl;
}
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
データオーバーライドに配列で挿入する効果を以下のプログラムで見ることができます.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[1] = “student_two”;
mapStudent[2] = “student_three”;
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
3. mapのサイズ
mapにデータを挿入して、私達はどのように現在すでにどれだけのデータを挿入したことを知っていて、size関数を使うことができて、使い方は以下の通りです:
Int nSize = mapStudent.size();
4. データの遍歴
ここではmapを巡る3つの方法も提供されています
1つ目は、順方向反復器を適用することです.上の例のプログラムはあちこちにあります.省略しません.
2つ目:反転反復器を適用し、次に例を挙げて説明します.効果を体得するには、自分でプログラムを実行してください.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
{
Cout<<iter->first<<” ”<<iter->second<<end;
}
}
3つ目:配列方式で、プログラムの説明は以下の通りです.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
int nSize = mapStudent.size()
// , for(int nIndex = 1; nIndex <= nSize; nIndex++)
//by rainfish
for(int nIndex = 0; nIndex < nSize; nIndex++)
{
Cout<<mapStudent[nIndex]<<end;
}
}
5. データの検索(このキーワードがmapに現れるかどうかを判定することを含む)
ここでは,mapがデータ挿入時に秩序を保つ利点を体得する.
1つのデータ(キーワード)がmapに現れるかどうかを判定する方法が多い場合、ここではタイトルはデータの検索ですが、ここではmapの基本的な使い方がたくさん挿入されています.
ここでは3つのデータ検索方法を示します.
1つ目は、キーワードが現れるか否かをcount関数で判定する欠点は、データの出現位置を特定できないことであり、mapの特性上、一対一のマッピング関係により、count関数の戻り値が2つしかないか、0か、1か、現れる場合、もちろん1を返すことを決定する
第2種:find関数でデータの出現位置を位置決めして、それは1つの反復器を返して、データが現れた時、それはデータの所在する位置の反復器を返して、mapの中で探すデータがなければ、それが返す反復器はend関数が返す反復器に等しくて、プログラムは明らかにします
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::iterator iter;
iter = mapStudent.find(1);
if(iter != mapStudent.end())
{
Cout<<”Find, the value is ”<<iter->second<<endl;
}
Else
{
Cout<<”Do not Find”<<endl;
}
}
第三に、この方法はデータが現れたかどうかを判定するために用いられ、少し不器用に見えるが、ここで説明するつもりだ.
Lower_bound関数は、キーワードを検索する下限(反復器)を返すために使用されます.
Upper_bound関数は、キーワードを検索する上界(反復器)を返すために使用されます.
例:mapに1,2,3,4が挿入されている場合、lower_bound(2)なら、戻る2、upper-bound(2)なら、戻る3
Equal_range関数はpairを返します.pairの最初の変数はLowerです.boundが返す反復器、pairの中の2番目の反復器はUpper_boundが返す反復器、もしこの2つの反復器が等しいならば、mapの中でこのキーワードが現れないことを説明して、プログラムは説明します
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[3] = “student_three”;
mapStudent[5] = “student_five”;
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(2);
{
// 3
Cout<<iter->second<<endl;
}
iter = mapStudent.lower_bound(3);
{
// 3
Cout<<iter->second<<endl;
}
iter = mapStudent.upper_bound(2);
{
// 3
Cout<<iter->second<<endl;
}
iter = mapStudent.upper_bound(3);
{
// 5
Cout<<iter->second<<endl;
}
Pair<map<int, string>::iterator, map<int, string>::iterator> mapPair;
mapPair = mapStudent.equal_range(2);
if(mapPair.first == mapPair.second)
{
cout<<”Do not Find”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
mapPair = mapStudent.equal_range(3);
if(mapPair.first == mapPair.second)
{
cout<<”Do not Find”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
}
6. データのクリアとクリア
クリアmapのデータはclear()関数で、mapにempty()関数を使用できるデータがあるかどうかを判定し、trueを返すと空mapであることを示します.
7. データの削除
ここではerase関数を使用します.3つのリロードされた関数があります.次に、例でそれらの使い方を詳しく説明します.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
// , ,
// 1,
map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
// 1,
Int n = mapStudent.erase(1);// 1, 0
// ,
// map
mapStudent.erase(mapStudent.begin(), mapStudent.end());
// , STL ,
// ,
}
8. その他の関数の使い方
ここにはswap、key_comp,value_comp,get_Allocatorなどの関数は,これらの関数がプログラミングに多く使われていないと感じ,省略して表に出さず,興味があれば自分で研究することができる.
9. ツールバーの
ここでは、ソートの問題について、STLではデフォルトでは小さい番号でソートされています.以上のコードはソートに問題はありません.上のキーワードはint型なので、それ自体は小さい番号の演算をサポートしています.いくつかの特殊な状況では、キーワードは構造体であり、ソートに関連すると問題が発生します.番号より小さい操作がないため、insertなどの関数はコンパイル時に通れないので、次の2つの方法でこの問題を解決します.
1つ目:号より小さいリロード、プログラムの例
#include <map>
#include <string>
Using namespace std;
Typedef struct tagStudentInfo
{
Int nID;
String strName;
}StudentInfo, *PStudentInfo; //
Int main()
{
int nSize;
//
map<StudentInfo, int>mapStudent;
map<StudentInfo, int>::iterator iter;
StudentInfo studentInfo;
studentInfo.nID = 1;
studentInfo.strName = “student_one”;
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 2;
studentInfo.strName = “student_two”;
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;
}
以上のプログラムはコンパイルできません.番号より小さいものをリロードすればOKです.以下のようにします.
Typedef struct tagStudentInfo
{
Int nID;
String strName;
Bool operator < (tagStudentInfo const& _A) const
{
// , nID , nID , strName
If(nID < _A.nID) return true;
If(nID == _A.nID) return strName.compare(_A.strName) < 0;
Return false;
}
}StudentInfo, *PStudentInfo; //
2つ目:シミュレーション関数の応用、この時構造体の中で直接的な小さい号の重荷がなくて、プログラムの説明
#include <map>
#include <string>
Using namespace std;
Typedef struct tagStudentInfo
{
Int nID;
String strName;
}StudentInfo, *PStudentInfo; //
Classs sort
{
Public:
Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const
{
If(_A.nID < _B.nID) return true;
If(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;
Return false;
}
};
Int main()
{
//
Map<StudentInfo, int, sort>mapStudent;
StudentInfo studentInfo;
studentInfo.nID = 1;
studentInfo.strName = “student_one”;
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 2;
studentInfo.strName = “student_two”;
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
}
10. さらに
STLは統一された全体であるため、mapの多くの使い方はSTLの他のものと結びついています.例えば、ソートでは、デフォルトではless<>より小さい番号を使用していますが、大きいものから小さいものまでソートするには、ここでは説明できません.
なお,mapでは内部秩序が保たれているため,多くの関数が実行する時間的複雑度はlog 2 Nであり,map関数で実現できる機能であればSTLでは Algorithmもこの機能を完成させることができ、mapで関数を持参することを提案し、効率が高い.
次に、mapの空間的な特性を説明します.そうしないと、mapの各データは赤と黒の木のノードに対応しているため、このノードはあなたのデータを保存しないとき、
16バイトの
あ、1つの親ノードポインタ、左右の子供ポインタ、もう1つの列挙値(赤と黒を示す、バランスツリーのバランス係数に相当)は、これらの場所はメモリがかかることを知っていると思いますが、言わないでください.