C++ 关联容器

关联容器

关联容器支持高效的关键字查找和访问。
两个主要的关联容器（associative container）类型是 map 和 set。
map 中的元素是一些关键字——值对。
关键字起到索引的作用，值则表示与索引相关联的数据。
set 中的每个元素只包含一个关键字。
set 支持高效的关键字查询操作——检查一个给定关键字是否在 set 中。
标准库提供 8 个关联容器：

容器	功能
map	关联数组：保存关键字——值对
set	关键字即值，即只保存关键字的容器
multimap	关键字可重复出现的map
multiset	关键字可重复出现的set
unordered_map	用哈希函数组织的map
unordered_set	用哈希函数组织的set
unordered_multimap	哈希函数组织的map，关键字可重复出现
unordered_multiset	哈希函数组织的set，关键字可重复出现

允许重复关键字的容器的名字中包含 mutli；不保持关键字按顺序存储的容器的名字都以单词 unordered 开头。
map 和 mutlimap 定义在头文件 map 中；set 和 mutliset 定义在头文件 set 中；无序容器则定义在头文件 unordered_map 和 unordered_set 中。

关联容器概述

定义关联容器

默认初始化

	map <int, string> M1;
	set <char> Set; 

列表初始化

当初始化一个 map 时，必须提供关键字类型和值类型；每一个关键字—值对包围在花括号中‘{ key , value }’来指出它们一起构成了 map 中的一个元素。

	map <int, string> M1 {
		{1,"C++"},{2,"Java"},{5,"Python"}
	};

当初始化一个 set 时，只需提供关键字类型，关键字类型就是元素类型。

	set <char> Set1 { 'A','B','C' };

一个 map 或 set 中的关键字必须是唯一的；容器 mulitmap 和 mulitset 没有这个限制，它们都允许多个元素具有相同的关键字。

	map <int, string> M1{
		{100,"C++"},{2,"Java"},{100,"Python"},{100,"C"}
	};
	cout <<M1.size() << endl;  // 内含 2 个元素
	multimap <int, string> M2{
		{100,"C++"},{2,"Java"},{100,"Python"},{100,"C"}
	};
	cout << M2.size() << endl;	// 内含 4 个元素
	
	set <char> Set1{ 'A','B','C','B','B' };
	cout << Set1.size() << endl; // 内含 3 个元素
	multiset <char> Set2{ 'A','B','C','B','B' };
	cout << Set2.size() << endl; // 内含 5 个元素

将一个新容器创建为另一个容器的拷贝

拷贝整个容器

	map <int, string> M1 {
		{1,"C++"},{2,"Java"},{5,"Python"}
	};
	map <int, string> M2{ M1 };
	set <char> Set1 { 'A','B','C' };
	set <char> Set2 { Set1 };

拷贝迭代器指定范围中的元素

	map <int, string> M1 {
		{1,"C++"},{2,"Java"},{5,"Python"}
	};
	map <int, string> M2{ M1.begin(),M2.end() };
	set <char> Set1 { 'A','B','C' };
	set <char> Set3{ Set1.begin(),Set1.end() };

有序容器的关键字类型的要求

对于有序容器，关键字类型必须定义元素比较的方法。
默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。
向算法提供的自定义比较操作必须在关键字类型上定义一个严格偌序（strict weak ordering）。
自定义的比较操作必须具备如下基本性质：

• 两个关键字不能同时“小于等于”对方；如果 k1 “小于等于” k2，那么 k2 绝不能“小于等于” k1。
• 如果 k1 “小于等于” k2，且 k2 “小于等于” k3，那么 k1 必须“小于等于” k3。
• 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。
• 如果 k1 “等价于” k2，且 k2 “等价于” k3，那么 k1 必须“等价于” k3。

pair 类型

名为 pair 的标准库类型，定义在头文件 utility 中。
pair 是一个用来生成特定类型的模版。
一个 pair 保存两个数据成员。
当创建一个 pair 时，必须提供两个类型名，两个类型不要求一样。

	pair <int, char> p;           //未指定成员的初始值，则进行值初始化
	pair <int, char> p{ 10,'A' }; //指定成员的初始值
	auto p = make_pair(1,'A');    //返回一个指定了成员初始值的 pair

pair 的两个数据成员是 public 的，两个成员分别命名为 first 和 second，使用普通的成员访问符来访问它们。

	pair <int, char> p{ 10,'A' };
	cout << p.first << endl;  //输出 10
	cout << p.second << endl; //输出 A

关联容器迭代器

当解引用一个关联容器迭代器时，会得到一个类型为容器的 value_type 值的引用。
对于 map 而言，value_type 是一个 pair 类型，其 first 成员保存 const 的关键字，second 成员保存值。

	map <int, string> M1{
		{1,"C++"},{2,"Java"},{100,"Python"},{100,"C"}
	};
	auto map_it = M1.begin();       //value_type 值的引用
	cout<< map_it->first <<endl;    //输出 1，关键字值不允许修改
	cout << map_it->second << endl; //输出 C++

对于 set 而言，value_type 与 key_type 相同。

	set <char> Set1 {'A', 'B', 'C'};
	auto set_it = Set1.begin();
	cout << *set_it << endl;   //输出 A，关键字值不允许修改

遍历关联容器

当使用迭代器遍历有序容器时，迭代器按关键字升序遍历元素。
map

	map <int, string> M1{
		{5,"C++"},{2,"Java"},{100,"Python"},{10,"C"}
	};
	auto map_it = M1.cbegin();
	while ( map_it != M1.cend() )
	{
		cout <<'{'<< map_it->first <<
		',' << map_it->second << '}'<<' ';
		map_it++;
	}
	/*输出：{2,"Java"} {5,"C++"} {10,"C"} {100,"Python"}*/

set

	set <char> Set1 {'D', 'B', 'A','C'};
	auto set_it = Set1.cbegin();
	while ( set_it != Set1.cend() )
	{
		cout << *set_it++ << ' ';
	}
	/*输出：A B C D*/

map的下标操作

map 和 unordered_map 容器提供了下标运算符和一个对应的 at 函数。
不能对一个 mutlimap 或 unordered_mutlimap 进行下标操作，因为该容器中可能有多个值与一个关键字相关联。
set 容器不支持下标访问，因为 set 中没有与关键字相关的值。
map 下标运算符接收一个索引（即，关键字）获取与此索引相关联的值。

	map <char, string> M1{
		{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	cout << M1['A'] << endl;    //输出 C++
	cout << M1.at('C') << endl; //输出 Java

如果索引（关键字）并不在 map 中，下标运算符会为它创建一个元素并插入到 map 中，关联值将进行值初始化。

	map <int, char> M1{
		{1,'A'},{3,'B'},{5,'F'}
	};
	cout << (int)M1[2] << endl; //输出 0

如果索引（关键字）并不在 map 中，at 函数会抛出一个 out_of_range 异常。
当对一个 map 进行下标操作时，会获得一个 mapped_type 对象。
下标运算符和 at 函数只适用于非 const 的 map 和 unordered_mutlimap。

关联容器查找

对 map 使用 find 代替下标操作

成员函数 find 返回一个迭代器，指向第一个关键字为 k 的元素，若 k 不在容器中，则返回尾后迭代器

	map <char, string> M1{
		{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	auto map_it = M1.find('C');
	cout << map_it->second << endl; //输出 Java

lower_bound 和 upper_bound

成员函数 lower_bound 和 upper_bound 不适用于无序容器。
成员函数 lower_bound 返回一个迭代器，指向第一个关键字不小于 k 的元素。

	map <char, string> M1{
		{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	auto map_it = M1.lower_bound('C');
	cout << map_it->second << endl; //输出 Java

成员函数 upper_bound 返回一个迭代器，指向第一个关键字大于 k 的元素。

	map <char, string> M1{
		{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	auto map_it = M1.upper_bound('C');
	cout << map_it->second << endl; //输出Python

在 multimap 或 multiset 中查找元素

方法一：
成员函数 count 返回关键字等于 k 的元素的数量；对于不允许重复关键字的容器，返回值永远是 0 或 1.

	multimap <char, string> M1{
		{'A',"C++"},{'B',"Java"},{'B',"Python"},{'B',"C"}
	};
	/*输出所有与关键字'B'相关联的值 */
	auto map_it = M1.find('B');
	for (int i = 0; i < M1.count('B'); ++i)
	{
		cout << map_it->second  << ' ';
		map_it++;
	}

方法二：

	multimap <char, string> M1{
		{'A',"C++"},{'B',"Java"},{'B',"Python"},{'B',"C"}
	};
	/*输出所有与关键字'B'相关联的值 */
	auto map_it = M1.lower_bound('B');
	/*如果 lower_bound 和 upper_bound 返回相同的迭代器，则给定关键字不在容器中*/
	while ( map_it != M1.upper_bound('B') )
	{
		cout << map_it->second << endl;
		map_it++;
	}

方法三：
成员函数 equal_range 返回一个迭代器 pair，表示关键字等于 k 的元素的范围；若 k 不存在，pair 的两个成员均等于尾后迭代器。

	multimap <char, string> M1{
		{'A',"C++"},{'B',"Java"},{'B',"Python"},{'B',"C"}
	};
	/*输出所有与关键字'B'相关联的值 */
	auto p = M1.equal_range('B');
	multimap <char, string>::iterator map_it = p.first;
	while ( map_it != p.second )
	{
		cout << map_it->second << endl;
		map_it++;
	}

向关联容器添加元素

向关联容器中插入一个元素。
map 的元素类型是 pair 类型。

	map <char, string> M1;
	M1.insert( {'A',"C++"} );
	M1.insert( make_pair('B',"Java") );
	M1.insert( pair <char, string> {'C', "Python"} );
	M1.insert( map <char, string>::value_type{ 'D',"C" } );
	set <char> Set;
	Set.insert('B');
	Set.insert('A');

成员函数 insert 的返回值。
对于不包含重复关键字的容器，添加单一元素的 insert 的版本返回一个 pair 对象。
pair 的 first 成员是一个迭代器，指向具有给定关键字的元素；
pair 的 second 成员是一个 bool 值；
如果关键字已存在容器中，则 insert 什么都不做，bool 值为 false。
如果关键字不在容器中，则元素被插入到容器中，bool 值为 true。

	map <char, string> M1;
	M1.insert( {'A',"C++"} );
	M1.insert( make_pair('B',"Java") );

	auto p = M1.insert( { 'A',"C++" } );
	cout << p.first->second << endl; // 输出 C++
	cout << p.second << endl;        // 输出 0

向关联容器中插入一个花括号包围的元素值列表。

	vector <int> V1{ 1,3,5,7,9 };
	set <int> Set;
	Set.insert({ 2,4,6,8,10 });

向关联容器中插入一对迭代器指定范围的所有元素；第一个迭代器指向要插入的第一个元素，第二个迭代器指向要插入的最后一个元素之后的位置。

	vector <int> V1{ 1,3,5,7,9 };
	set <int> Set;
	Set.insert( V1.begin(), V1.end() );

删除元素

成员函数 erase 从容器中删除每个与关键字 k 相关联的元素；返回一个 size_type 值，指出删除的元素的数量。

	map <char, string> M1{
	{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	M1.erase('A'); //删除 {'A',"C++"}
	set <char> Set{ 'B','C','D','E','A' };
	Set.erase('B'); //删除 B

成员函数 erase 从容器中删除迭代器 p 指向的元素；p 必须指向容器中一个真实元素；返回一个指向 p 之后元素的迭代器。

	map <char, string> M1{
	{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	M1.erase( M1.begin(),M1.end() ); //删除所有元素
	set <char> Set{ 'B','C','D','E','A' };
	auto set_its = Set.end();
	--set_its;
	Set.erase( Set.begin(),set_its ); //删除 A B C D
	

成员函数 erase 删除一对迭代器指定范围内的所有元素；返回指向被删除的元素之后位置的迭代器。

	map <char, string> M1{
	{'A',"C++"},{'C',"Java"},{'D',"Python"},{'F',"C"}
	};
	auto map_its = M1.begin();
	++map_its;
	M1.erase(map_its); //删除 {'C',"Java"}
	set <char> Set{ 'B','C','D','E','A' };
	auto set_its = Set.end();
	--set_its;
	Set.erase( set_its ); //删除 E

删除容器内所有的元素

成员函数 clear 删除容器内所有元素。

	set <char> Set{ 'B','C','D','E','A' };
	Set.clear();

无序容器

有序容器使用关键字类型的比较运算符来组织元素。
无序容器使用哈希函数和关键字类型的==运算符来组织元素。

管理桶

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。
无序容器使用一个哈希函数将元素映射到桶。
无序容器将具有一个特定哈希值的所有元素都保存在相同的桶中；如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。
为了访问容器中一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。
无序容器提供了一组管理桶的函数：

桶接口

成员函数	功能
bucket_count ()	正在使用的桶的数目
max_bucket_count ()	容器能容纳的最多的桶的数量
bucket_size (n)	第 n 个桶中有多少个元素
bucket (k)	关键字为 k 的元素在哪个桶中

桶迭代

成员	功能
local_iterrator	可以用来访问桶中元素的迭代器类型
const_local_iterrator	桶迭代器的 const 版本
begin (n)	桶 n 的首元素迭代器
end (n)	桶 n 的尾后迭代器
cbegin (n)	桶 n 的首元素迭代器，返回 const_local_iterrator
cend (n)	桶 n 的尾后迭代器，返回 const_local_iterrator

哈希策略

成员函数	功能
load_factor ()	每个桶的平均元素数量，返回 float 值
max_load_factor ()	容器试图维护的平均桶大小，返回 float 值；容器会在需要时添加新桶，使得 load_factor () <= max_load_factor ()
rehash (n)	重组存储，使得 bucket_count >= n 且 bucket_count >size/max_load_factor ()
reserve (k)	重组存储，使得容器可以保存 n 个元素且不必 rehash

这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。