# 关联容器

• set : 唯一键 的集合，按照键排序
• map : 键值队的集合，按照键排序， 键是唯一 的
• multiset : 键的集合，按照键排序
• multimap : 键值对的集合，按照键排序

# set

set 是关联容器，含有 key 类型对象的已排序集，用比较函数 ( compare ) 进行排序。搜索，移除和插入拥有对数复杂度，set 通常以红黑树实现

# 迭代器

• begin/cbegin : 返回指向起始的迭代器
• end/cend : 返回指向末位的迭代器
• rbegin/crbegin ：返回指向起始的逆向迭代器
• rend/crend : 返回指向末尾的逆向迭代器

# 容器

• empty : 检查容器是否为空
• size : 返回容纳的元素数
• max_size ：返回可容纳的最大元素数

#include <iostream>

#include <set>

#include <algorithm>

using namespace std;

int main(void)

{

	// 创建关联容器 set

	set<int> s{ 1,2,3,4,5,6 };

	// 使用 set 的迭代器，循环遍历

	for_each(s.cbegin(), s.cend(), [](int x) { cout << x << " "; });

	cout << endl;

	// 让 bool 显示未 true 或 false

	cout << boolalpha;

	s.empty();

	cout << "s是否为空:" << s.empty() << endl;

	cout << "s的元素个数:" << s.size() << endl;

	cout << "s可理论容纳的最大数量:" << s.max_size() << endl;

	cout << endl;

	// 清除 s 内容

	s.clear();

	cout << "清除后s是否为空:" << s.empty() << endl;

	// 插入元素

	s.insert(s.begin(), 99);

	for_each(s.cbegin(), s.cend(), [](int x) { cout << x << " "; });

	cout << endl;

	return 0;

}

/*

1 2 3 4 5 6

s 是否为空:false

s 的元素个数：6

s 可理论容纳的最大数量：576460752303423487

清除后 s 是否为空:true

99

*/

# 修改器

• clear : 清除内容
• insert ：插入元素或 结点C++17
• emplace : 原位构造元素
• emplace_hint : 使用提示原位构造元素
• erase : 擦除元素
  • 参数:
  • pos : 指向要移除的元素的迭代器
  • first,last ：要移除的元素范围
  • key ：要移除的元素键值
  • x : 任何能与键通透比较的类型的值，自带要移除的元素

#include <iostream>

#include <set>

using namespace std;

int main(void)

{

	set<int> c = { 1,2,3,4,1,2,3,4 };

	auto print = [&c]

	{

		cout << "c={";

		for (int n : c)

		{

			cout << n << " ";

		}

		cout <<"}"<< endl;

	};

	print();

	cout << "移除所有奇数：" << endl;

	for (auto it = c.begin(); it != c.end();)

	{

		if (*it % 2 != 0)

		{

			// 擦除首元素

			it = c.erase(it);

		}

		else

		{

			++it;

		}

	}

	print();

	cout << "移除1，移除个数" << c.erase(1) << endl;

	cout << "移除2，移除个数" << c.erase(2) << endl;

	cout << "移除2，移除个数" << c.erase(2) << endl;

	print();

	return 0;

}

/*

c={1 2 3 4}

移除所有奇数：

c={2 4 }

移除 1，移除个数 0

移除 2，移除个数 1

移除 2，移除个数 0

c={4 }

*/

• swap : 交换内容
• extract : 从另一个容器释出结点 C++17

解链含 position 所指向的结点并返回占有它的结点柄
若容器拥有元素而其关键等于 x，则从容器解链该元素并返回占有它的结点柄，否则返回空结点柄
参数:
* position: 指向此容器中的合法迭代器
* k: 鉴别要被释放出的结点的键
* x: 任何能与键通透比较的类型的值，鉴别要释放的结点
extract 是 set 带走仅移动对象的唯一方式

#include <iostream>

#include <algorithm>

#include <set>

using namespace std;

int main(void)

{

	set<int> cont{ 1,2,3 };

	auto print = [](const int& n) { cout << " " << n; };

	for_each(cont.begin(), cont.end(), print);

	cout << endl;

	//C++17. 解链含 position 所指向元素的结点柄返回占有它的结点柄

	auto nh = cont.extract(1);

	// 对结点柄重新赋值

	nh.value() = 4;

	for_each(cont.begin(), cont.end(), print);

	cout << endl;

	// 将 nh 结点柄插入尾部

	cont.insert(move(nh));

	for_each(cont.begin(), cont.end(), print);

	cout << endl;

}

/*

 1 2 3

 2 3

 2 3 4

*/

• merge : 从另一个容器接合结点 C++17

#include <iostream>

#include <set>

using namespace std;

template <class Os,class K>

Os& operator<<(Os& os, const std::set<K>& v)

{

	// 求出 set 的大小

	os << '[' << v.size() << "] {";

	bool o{};

	for (const auto& e : v)

	{

		// 判断是否为空决定是，还是空

		os << (o ? ", " : (o = 1, " ")) << e;

	}

	return os << " }\n";

}

int main(void)

{

	set<char> 

		p{'C','B','B','A' },

		q{ 'E','D','E','C' };

	cout << "p: " << p << "q: " << q;

	// 对 set 进行合并

	p.merge(q);

	// 合并自动去重

	//q 留下重复的部分

	cout << "p.merge(q):" << p << "q: " << q;

}

/*

p: [3] { A, B, C }

q: [3] { C, D, E }

p.merge(q):[5] { A, B, C, D, E }

q: [1] { C }

*/

# 查找

• count : 返回匹配特定键的元素数量
• find : 遵照带有特定键的元素
• contains ：检查容器是否含有带特定键的元素
• equal_range : 返回匹配特定键的元素范围
• lower_bound : 返回指向首个不小于给定键的元素迭代器
• upper_bound : 返回指向首个大于给定键的元素的迭代器

# 观察器

• key_comp : 返回用于比较键的函数
• value_comp ：返回用于在 value_type 类型的对象中比较键的函数

# multiset

multiset 是含有 key 类型对象有序集的容器，与 set 不同，它允许 多个key 拥有等价的值，用关键比较函数 Compare 进行排序，搜索，插入和移除操作拥有对数复杂度
其用法与set相同

# map

有序键值队容器，它的元素的键是惟一的。

# 元素访问

• at: 访问指定的元素，同时进行越界检查
• operator []: 访问或插入指定的元素

#include <iostream>

#include <map>

#include <string>

using namespace std;

// 输出键值队 map

auto print = [](auto const comment, auto const& map)

{

	cout << comment << "{";

	for (const auto& pair : map)

	{

		cout << "{" << pair.first << ":" << pair.second << "}";

	}

	cout << endl;

};

int main()

{

	map<char,int> letter_counts { {'a',27},{'b',3},{'c',1} };

	print("letter_counts初始状态下包含:", letter_counts);

	letter_counts['b'] = 42;

	letter_counts['x'] = 9;

	print("修改后的值", letter_counts);

	// 统计每个单词出现的次数

	map<string, int> word_map;

	for (const auto& w : { "this","sentence","is","not","a","sentence","this","sentence","is","a","hoax" })

	{

		++word_map[w];

	}

	word_map["that"]; // 插入对 {"that",0}

	print("输出map:",word_map);

}

# 迭代器

• begin/cbegin：返回指向起始的迭代器
• end/cend: 返回指向末尾的迭代器
• rbegin/crbegin: 返回指向起始的逆向迭代器
• rend/crend: 返回指向末尾的逆向迭代器

# 容器

• empty: 检查容器是否为空
• size: 返回容器的元素数
• max_size: 返回可容纳的最大元素数

# 修改器

• clear: 清楚内容
• insert: 插入元素或结点
• insert_or_assign: 插入元素，或若键已存在赋值给当前元素
• emplace: 原位构造元素
• emplace_hint：使用提示原位构造元素
• try_emplace: 若键不存在则原位插入，若键存在则不做任何事情
• erase: 擦除元素
• swap: 交换内容
• extract：从另一个容器释出结点
• merge: 从另一容器接合结点

# 查找

• count: 返回匹配特定键的元素数量
• find: 寻找带有特定键的元素
• contains: 检查容器是否含有带特定键的元素
• equal_range: 返回匹配特定键的元素范围
• lower_bound: 返回指向首个不小于给定键的元素的迭代器
• upper_bound: 返回指向首个大小给定键的元素的迭代器

# 观察器

• key_comp: 返回用于比较键的函数
• value_comp: 返回用于在 value_type 类型的对象中比较键的函数

#include <iostream>

#include <map>

#include <string>

using namespace std;

// 输出键值队 map

auto print_map = [](auto const comment, map<string,int>&map)

{

	cout << comment ;

	//C++11 方案

	for (const auto& pair : map)

	{

		cout << "{" << pair.first << ":" << pair.second << "}";

	}

	cout << endl;

};

int main()

{

	map<string, int> m{ {"cpu",10},{"GPU",15},{"RAM",20} };

	print_map("初始map:", m);

	// 以不存在的键执行插入操作

	m["SSD"] = 30;

	print_map("插入不存在的：", m);

	// 移除 GPU

	m.erase("GPU");

	print_map("移除后：", m);

	// 条件移除

	erase_if(m, [](const auto& pair) { return pair.second > 25; });

	print_map("条件移除后：", m);

	cout << m.size() << endl;

	m.clear();

	cout << boolalpha << "m是否为空:" << m.empty() << endl;

	return 0;

}

/*

初始 map:{GPU:15}{RAM:20}{cpu:10}

插入不存在的：{GPU:15}{RAM:20}{SSD:30}{cpu:10}

移除后：{RAM:20}{SSD:30}{cpu:10}

条件移除后：{RAM:20}{cpu:10}

2

m 是否为空:true

*/

# multimap

含有键值队的已排序列表，同时容纳许多个元素拥有同一键。与 map 用法相同

# 无序关联容器

在内部，元素不以任何特别顺序排序，而是组织进桶中。元素被放进哪个桶完全依赖其值的哈希，这允许对单独元素的快速访问，因为哈希一旦确定，就准确自带元素被放入的桶。 不可修改容器元素 (即使通过非 cons 迭代器), 因为修改更改元素的哈希，并破坏容器

• unordered_set : 唯一键的集合，按照键生成散列
• unordered_map : 键值对的集合，按照键生成散列， 键 是唯一的
• unordered_multiset : 键的集合，按照键生成散列
• unordered_multimap ：键值队的集合，按照键 生成散列

# unordered_set

含有 key 类型的唯一对象集合关联容器

# 迭代器

• begin/cbegin : 返回指向起始的迭代器
• end/cend : 返回指向末尾的迭代器

# 容器

• empty ：检查容器是否为空
• size ：返回容纳的元素数
• max_size ：返回可容纳的 最大 元素数

# 修改器

• clear : 清除内容
• insert : 插入元素 或结点C++17
• emplace : 原位构造元素
• emplace_hint : 使用提示原位构造元素
• erase : 擦除元素
• swap ：交换内容
• extract ：从另一容器释出结点
• merge : 从另一个容器接合结点

# 查找

• count ：返回匹配特定键的元素数量
• find ：寻找带有特定键的元素
• contains : 检查容器是否含有带有特定键的元素
• equal_range ：返回匹配 特定键 的元素范围

# 桶接口

• begin(size_type)/cbegin(size_type) ：返回一个迭代器，指向指定的桶的开始：返回指向下标为 n 的桶首元素的迭代器
• end(size_type)/cend(size_type) : 返回一个迭代器，。返回后随下标为 n 的桶的最后元素的元素的迭代器，此元素表现为占位符，试图访问它会导致未定义行为
• bucket_count : 返回容器中的桶数
• max_bucket_count : 返回容器由于系统或库实现限制的能保有最大桶数
• bucket_size ：返回在特定的桶中的元素数量
• bucket : 返回带有特定键的容，key: 要检验的关键值

# 哈希策略

• load_factor ：返回每个容的平均元素数量
• max_load_factor ：管理每个容的平均数量的最大值
• rehash ：为至少为指定数量的桶预留存储空间并重新生成散列表
• reserve : 为至少为指定数量的元素预留存储空间并重新生成哈希表

# 观察器

• hash_function : 返回用于对键散列的函数
• key_eq : 返回用于比较键的相等性的函数

# unordered_multiset

含有可能非唯一 key 类型对象的集合

# unordered_map

含有唯一键 - 值 pair

# 迭代器

• begin/cbegin : 返回指向起始的迭代器
• end/cend : 返回指向末尾的迭代器

# 容器

• empty ：检查容器是否为空
• size ：返回容纳的元素数
• max_size ：返回可容纳的最大元素数

# 修改器

• clear : 清除内容
• insert : 插入元素 或结点C++17
• emplace : 原位构造元素
• emplace_hint : 使用提示原位构造元素
• erase : 擦除元素
• swap ：交换内容
• extract ：从另一容器释出结点
• merge : 从另一个容器接合结点

# 查找

• at ：访问指定的元素，同时进行 越界 检查
• operator[] : 访问或插入指定的元素
• count ：返回匹配特定键的元素数量
• find ：寻找带有特定键的元素
• contains``C++20 : 检查容器是否含有带有特定键的元素
• equal_range ：返回匹配特定键的元素范围

# 桶接口

• begin(size_type)/cbegin(size_type) ：返回一个迭代器，指向指定的桶的开始：返回指向下标为 n 的桶首元素的迭代器
• end(size_type)/cend(size_type) : 返回一个迭代器，。返回后随下标为 n 的桶的最后元素的元素的迭代器，此元素表现为占位符，试图访问它会导致未定义行为
• bucket_count : 返回容器中的桶数
• max_bucket_count : 返回容器由于系统或库实现限制的能保有最大桶数
• bucket_size ：返回在特定的桶中的元素数量
• bucket : 返回带有特定键的容，key: 要检验的关键值

# 哈希策略

• load_factor ：返回每个容的平均元素数量
• max_load_factor ：管理每个容的平均数量的最大值
• rehash ：为至少为指定数量的桶预留存储空间并重新生成散列表
• reserve : 为至少为指定数量的元素预留存储空间并重新生成哈希表

# 观察器

• hash_function : 返回用于对 键散列 的函数
• key_eq : 返回用于比较键的相等性的函数

# unordered_multimap

支持等价的键 (一个 unordered_multimap 可含有每个键值的多个副本) 和将键与另一个类型的值关联

# 迭代器

• begin/cbegin : 返回指向起始的迭代器
• end/cend : 返回指向末尾的迭代器

# 容器

• empty ：检查容器是否为空
• size ：返回容纳的元素数
• max_size ：返回可容纳的最大元素数

# 修改器

• clear : 清除内容
• insert : 插入元素 或结点C++17
• emplace : 原位构造元素
• emplace_hint : 使用提示原位构造元素
• erase : 擦除元素
• swap ：交换内容
• extract ：从另一容器释出结点
• merge : 从另一个容器接合结点

# 查找

• count ：返回匹配特定键的元素数量
• find ：寻找带有特定键的元素
• contains``C++20 : 检查容器是否含有带有特定键的元素
• equal_range ：返回匹配特定键的元素范围

# 桶接口

• begin(size_type)/cbegin(size_type) ：返回一个迭代器，指向指定的桶的开始：返回指向下标为 n 的桶首元素的迭代器
• end(size_type)/cend(size_type) : 返回一个迭代器，。返回后随下标为 n 的桶的最后元素的元素的迭代器，此元素表现为占位符，试图访问它会导致未定义行为
• bucket_count : 返回容器中的桶数
• max_bucket_count : 返回容器由于系统或库实现限制的能保有 最大桶数
• bucket_size ：返回在特定的桶中的元素数量
• bucket : 返回带有特定键的容， key : 要 检验 的 关 键值

# 哈希策略

• load_factor ：返回每个容的平均元素数量
• max_load_factor ：管理每个容的平均数量的最大值
• rehash ：为至少为指定数量的桶预留存储空间并重新生成散列表
• reserve : 为至少为指定数量的元素预留存储空间并重新生成哈希表

# 观察器

• hash_function : 返回用于对键散列的函数
• key_eq : 返回用于比较键的相等性的函数