C++:関連コンテナ(set,multiset,map,multimap)

関連容器(associative container)は容器概念の改善である.
ワイヤコンテナは、値をキーに関連付け、キーを使用して値を検索します.
例:値は、名前、電話番号、住所、性別、健康計画などの従業員情報を表す構造体であってもよく、キーは一意の従業員番号であってもよい.従業員情報を取得するために、プログラムはキーを使用して従業員構造を検索する.
関連コンテナの利点:
エレメントへの迅速なアクセスが可能になり、新しいエレメントの挿入も可能になりますが、エレメントの挿入位置を指定することはできません(関連コンテナは通常、データの配置位置を決定するアルゴリズムで使用され、情報を迅速に取得できるためです).
関連コンテナは、通常、あるツリーを使用して実装されます.ツリーは、ルートノードが1つまたは2つのノードにリンクされ、これらのノードが1つまたは2つのノードにリンクされ、ブランチ構造を形成するデータ構造です.
チェーンテーブルのように、ノードはデータの追加や削除を簡単にしますが、チェーンテーブルの場合、ツリーの検索速度が速くなります.
STLには4種類の関連コンテナが用意されています.
set :
Multiset:この2つのヘッダファイルはsetです
map :
Multimap:この2つのヘッダファイルはmapです
set:最も簡単な関連コンテナで、値のタイプはキーと同じで、キーは一意です.これは、セットに同じキーが複数存在しないことを意味します.setの場合、その値はキーです
Multiset:setに似ていますが、複数の値のキーが同じである可能性があります.
map:その値はキーのタイプとは異なり、キーは一意であり、各キーは1つの値にのみ対応します.
Multimap:mapと同様に、1つのキーが複数の値に関連付けられるだけです.
1)setの例:
set A;//2番目のパラメータ(オプション)を持つことができます.デフォルトではテンプレートless<>を使用します.
set > A;//older implementation

#include 
#include 
#include 

int main()
{
	using namespace std;
	const int N = 6;
	string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};//          for
	set A(s1, s1 + N);//set    ，      
	ostream_iterator out(cout, " ");
	copy(A.begin(), A.end(), out);//buffoon can for heavy thinkers 
	cout << endl;
	return 0;
}

数学はsetのためにいくつかの標準的な操作を定義しました.
≪パラレル・セット|Parallel Sets|emdw≫:2つのセットがマージされたコンテンツが含まれます.2つのセットに同じ値が含まれている場合、setのキーが一意であるため、この値はパラレルセットに1回しか現れません.
    set_union()関数は5つの反復器パラメータを受け入れ,最初の2つの反復器は最初の集合の区間を定義し,後の2つの反復器は2番目の集合の区間を定義し,最後の反復器は出力反復器であり,結果集合をどの位置に複素化するかを指摘する.
    set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator(cout, ""));//表示
       set_union(A.begin(), A.end(), B.begin(), B.end(), C.begin());//Cコレクションに入れるのは間違っています
理由は2つあります.
1)まず,関連集合は鍵を定数と見なすので,C.begin()が返す反復器は定数反復器であり,出力反復器としては利用できない.
2)次に、copy()に似て、set_Union()は、コンテナ内の既存のデータを上書きし、新しい情報を格納するのに十分なスペースが必要です.Cは空で、このような要求を満たすことができません.
テンプレートinsert_iteratorは、レプリケーションを挿入に変換できる2つの問題を解決します.また、出力反復器をシミュレートし、コンテナに情報を書き込むことができます.
匿名のinsert_を作成できますiteratorは、次のような情報をCにコピーします.
    set_union(A.begin(), A.end(), B.begin(), B.end(), insert_iterator >(C, C.begin()));
≪交差｜Intersection｜oem_src≫:2つのセットにある要素が含まれます.
            set_intersection()、使い方とset_union類似
≪差セット|Difference Set|emdw≫:2つのセットの差は、最初のセットから2つのセットにある要素を減算します.
            set_difference()、使い方とset_union類似
STLは、これらの動作をサポートするアルゴリズムを提供する.これらは汎用関数であり、setオブジェクトのみに使用されるわけではありません.
したがってsetオブジェクトは、コンテナがソートされているというアルゴリズムの前提条件を自動的に満たす.
2つの有用なsetメソッド:
lower_bound():キーをパラメータとして反復器に返します.この反復器は、セット内の最初のキーパラメータ以上のメンバーを指します.
upper_bound():キーをパラメータとして反復器に返します.この反復器は、セット内のキーパラメータよりも大きい最初のメンバーを指します.
≪アクション|Actions|emdw≫:集約を含む区間を取得できます.
setでは自動的にソートされるので、挿入する情報を指定するだけで、挿入位置を指定する必要はありません.
上記の例の適用について:

#include 
#include        // set
#include     // string
#include  //set_union
#include 
int main()
{
	using namespace std;
	const int N = 6;
	string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};//          for
	string s2[N] = {"metal", "any", "food", "elegant", "deliver", "for"};

	set A(s1, s1 + N);//set    ，      
	set B(s2, s2 + N);
	ostream_iterator out(cout, " ");
	
	cout << "Set A:
";
	copy(A.begin(), A.end(), out);//buffoon can for heavy thinkers 
	cout << endl;

	cout << "Set B:
";
	copy(B.begin(), B.end(), out);//any deliver elegant food for metal
	cout << endl;

	cout << "Union of A and B:
";
	set_union(A.begin(), A.end(), B.begin(), B.end(), out);
	//any buffoon can deliver elegant food for heavy metal thinkers
	cout << endl;

	cout << "Intersection of A and B:
";
	set_intersection(A.begin(), A.end(), B.begin(), B.end(), out); //for
	cout << endl;

	cout << "Difference of A and B:
";
	set_difference(A.begin(), A.end(), B.begin(), B.end(), out);//buffoon can heavy thinkers
	cout << endl;

	set C;
	cout << "Set C:
";
	set_union(A.begin(), A.end(), B.begin(), B.end(),
		insert_iterator >(C, C.begin()));// A B     C   
	copy(C.begin(), C.end(), out); 
	//any buffoon can deliver elegant food for heavy metal thinkers
	cout << endl;

	string s3("grungy");
	C.insert(s3);
	cout << "Set C After insert s3:
";
	copy(C.begin(), C.end(), out);
	//any buffoon can deliver elegant food for grungy heavy metal thinkers
	cout << endl;

	cout << "Showing a range:
";
	copy(C.lower_bound("ghost"), C.upper_bound("spook"), out);
	//grungy heavy metal
	cout << endl;
	return 0;
}

Multimapの例:

multimap codes; //#1

3番目のパラメータはオプションで、キーをソートする比較関数またはオブジェクトを指定します.デフォルトでは、テンプレートless()を使用して、キータイプをテンプレートパラメータタイプとして使用します.
実際の値はキータイプとデータ型をペアに結合し、pair、
keytypeがキータイプ、datatypeが格納されているデータ型の場合、値タイプは1のようにpairであり、codesのオブジェクトの値のタイプはpairである.
ブロック番号をキーとして都市名を記憶するとすると、

pair item(213, "Los Angeles"); //    
codes.insert(item); //  

匿名オブジェクトを作成して書くこともできます.

codes.insert(pair (213, "Los Angeles"));

データ項目はキーで並べ替えられているので、挿入位置を指摘する必要はありません.
アクセス内容:

cout << item.first << " " << item.second << endl;

firstはキー値を表し、secondはデータ情報を表す.
equal_range()はキーをパラメータとして使用し、2つの反復器を返し、そのキーに一致する区間を返します.この2つの値を返すには、pairの2つのテンプレートパラメータが反復器であるpairオブジェクトにカプセル化されます.
codesオブジェクトの718のすべての都市を印刷するとします.

pair::iterator, multimap::iterator> range = codes.equal_range(718);
std::multimap::iterator it;
for (it = range.first; it != range.second; ++it)
	cout << (*it).second << endl;

C++11の自動推定機能を使用すると、

auto range =  = codes.equal_range(718);
for (auto it = range.first; it != range.second; ++it)
	cout << (*it).second << endl;

typedefを使用してコードを簡略化することもできます.

#include 
#include 
#include 

無秩序関連コンテナ(C++11)
無秩序関連容器も容器概念のもう一つの改善である.関連コンテナと同じです.
下位レベルの違い:関連コンテナはツリー構造であり、無秩序関連コンテナはデータ構造ハッシュテーブルに基づいており、要素の追加と削除の速度を向上させ、検索アルゴリズムの効率を向上させることを目的としています.
無秩序関連ウィンドウは4種類あります.
1)unordered_set
2)unordered_multiset
3)unordered_map
4)unordered_multimap