c++关联容器，哈希学习笔记。_用哈希函数组织的关联容器是

9.4 关联容器

1. 常用的两个关联容器set与map （关联容器 associative-container）
   map中是 key-value 键值对。
   Set 每个元素只包含一个关键字

2.Map 关联数组，保存 键值对
例如：

#include<vector>
#include<iostream>
#include<string>
#include<map>
using namespace std;

int main()
{
	map<string, size_t>m;
	string word;
	while (true)
	{
		cin >> word;
		if (word == "0")
		{
			break;
		}
	    m[word]++;

}
	for (const auto &x : m)
	{
		cout << x.first <<"  "<<x.second<< endl;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

（ 其中关键字是string 而 值是size_t类型
Word 未在容器中，则会创建一个关键字，其值为0；
不管元素是不是新创建都为其加一。）

3.Set 关键字即值，只保存关键字的容器 按关键字有序保存元素

4.Multimap 关键字可重复的map
5.Multiset 关键字可重复的set

6.Unordered_map 用哈希函数组织的map
7.Unorderde_set 用哈希函数组织的set
(6,7 无序集合，按照特定的哈希函数来排)

9.set高速度查找

set<string> s;   
s.find(something)==s.end();
1
2

这是没有查找到；

10.关联容器不支持顺序容器的位置相关的操作，例如push_front , push_back;
原因是关联容器中元素是根据关键字存储的，这些操作就没啥意义。
且关联容器不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
11.Map和set 中关键字是唯一的；
Set对应的便有去重操作：

#include<vector>
#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;

int main()
{
	vector<int>temp;
	for (int i = 0;i < 9;i++)
	{
		temp.push_back(i);
		temp.push_back(i);
	}
	set<int>res(temp.begin(), temp.end());
	multiset<int>ress(temp.begin(), temp.end());
	for (auto& x : res)
	{
		cout << x << " ";
	}
	cout << endl;
	for (auto& x : ress)
	{
		cout << x << " ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

12.pair类型（定义在头文件utility中）
pair<类型1，类型2> p
pair<类型3，vector> p；
pair是默认构造函数对数据成员进行值初始化；
类型1，2，3为空，size_t值为0
pair数据成员是public的，为first 和 second
make_pair(v1,v2) 返回一个v1和v2初始化的pair。

13.key_type----- 键类型。
mapped_type ------- 值类型
value_type 元素pair<>; 我们可以改变pair的值，但是不能改变它的键
例如：

14.Set的迭代器是const的，

15.添加元素方面；
关联容器的insert 成员向容器中添加一个元素或一个元素范围，
向set中只能插入不重复的元素
向map进行insert操作时，元素类型必须是pair:
{元素，元素}
或者make_pair(元素，元素)
或者pair<键，值>（元素，元素），
或者map<键类型，值类型>：：value_type(元素，元素)

16.删除元素。

17.map下标操作
M[k] 返回关键字为k的元素，没有则创建

M.at[k]访问关键字为k的元素，带参数检查，k不在则抛出异常，out_of_range;

18.map访问
查找一个指定的元素，不允许重复的可能find最优选择，count还会统计有多少个元素有相同的关键字。

19.无序容器。不是用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。