一、关联式容器与键值对

1.关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身;。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

2.键值对

键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息

我们举一个我们上节在二叉搜索树中提到的例子：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() 
        : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) 
        : first(a), second(b)
	{}
};

我们可以看到，C++中的键值对是 通过一个pair结构体/类来进行表示的，pair类中的first就是键值key，second就是键值key对应的value，那么我们以后再设计KV模型的容器时只需要在容器/容器的每一个节点定义一个pair对象即可；

但是为什么我们不直接在容器中定义key和value这两个成员变量呢，而是将key和value作为一个整体来使用呢？这是因为C++的函数只能有一个返回值，需要多个返回值的时候只能通过输出型参数进行返回，所以如果我们将key和value单独定义在一个容器中作为成员变量，此时我们就无法同时返回key和value，但是如果我们将key和value定义成一个结构体或者一个类中，此时我们就可以直接返回pair，然后再通过pair获得key和value，即first和second；

make_pair函数

由于pair是类模板，所以我们通常是以显式实例化+匿名对象的方式进行使用的，但是由于显式实例化比较的麻烦，比如下面的例子：

int main()
{
	map<string, string> dict;
	dict.insert(pair<string, string>("排序", "sort"));
	dict.insert(pair<string, string>("左边", "left"));
	dict.insert(pair<string, string>("右边", "right"));
	return 0;
}

如上，我们书写就比较的麻烦，所以C++提供了make_pair函数，其定义如下：

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );
}

我们可以看到，make_pair函数返回的是一个pair的匿名对象，匿名对象会自动调用pair的默认构造函数完成初始化，但是由于make_pair是一个函数模板，所以参数的类型可以根据实参来自动推导完成隐式类型转换，这样我们就不需要每次都显式指明参数的类型了；所以我们就可以使用下面的方式了：

int main()
{
	map<string, string> dict;
	dict.insert(make_pair("排序", "sort"));
	dict.insert(make_pair("左边", "left"));
	dict.insert(make_pair("右边", "right"));
	return 0;
}

由于make_pair使用起来比pair方便得多，所以我们一般都是直接使用make_pair，而不使用pair

3.树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面依次介绍每一个容器。

二、set

1.set的介绍

我们和之前学习STL容器一样，使用cpluslpus.com进行辅助学习

set是按照一定次序存储元素的容器，set在底层是用二叉搜索树(红黑树)实现的，由于二叉搜索树的每个节点的值满足左孩子<根<右孩子，并且二叉搜索树中没有重复非节点，所以set可以用来排序，去重和查找，同时，由于这是一棵平衡树，所以set查找的时间复杂度为O(logN)

在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序， set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代

【总结】

1.与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。

2.set中插入元素时，只需要插入value即可，不需要构造键值对。

3.set中的元素不可以重复(因此可以使用set进行去重)。

4.使用set的迭代器遍历set中的元素，可以得到有序序列

5.set中的元素默认按照小于来比较，即set默认使用的仿函数为less

6.set中查找某个元素，时间复杂度为：O(logN)

7.set中的元素不允许修改，因为这可能破坏树的结构

8.set中的底层使用二叉搜索树(红黑树)来实现

2.set的使用

构造

和之前我们所学的STL容器一样，set也支持单个元素构造，迭代器区间构造以及拷贝构造

迭代器

迭代器分为正向迭代器和反向迭代器，正向和反向又分为const迭代器和非const迭代器

容量

修改

insert

insert支持插入一个值，在某个迭代器位置插入一个值，插入一段迭代器区间，我们一般使用第一个即可，其他两个很少使用，插入的过程就是二叉搜索树插入的过程，我们需要注意的是，insert的返回值是pair类型，pair中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功(插入重复节点返回false)

erase也有三种，分别为删除迭代器位置的数据，删除指定键值的数据，删除迭代器区间的数据，其中最常用的是第一种和第二种

其他操作

set还有一些其他相关的操作函数：

这些函数不太常用，其中比较重要的只有find，由于set中不允许出现相等的key，因此在set中count函数的返回值只有1/0，可以说没有太大的价值，set中定义了count由于count在multiset中有作用，这里是为了保持一致，当然，我们也可以充当查找的功能，有返回1，没有返回0，但是意义也不大，因为有find函数就足够了；lower_bound和upper_bound是得到一个左闭右开的迭代器区间，然后我们可以对这段区间中的数据进行某些操作，但是我们在实际中也基本不会使用

find的作用是在二叉搜索树中查找key对应的节点，然后返回该节点的迭代器，如果没有找到，find则返回end()

set的find和算法库里的find对比

set是二叉树搜索树查找的时间复杂度为O(logN),算法库中的find是暴力查找，所以时间复杂度为O(N)

set使用范例

void test_set1()
{
	set<int> s;
	// 插入数据
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(7);
	s.insert(2);
	s.insert(5);
	s.insert(8);
	s.insert(6);

	// 使用迭代遍历set
	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用范围for遍历set
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 查找加删除
	auto pos = s.find(3);                    // O(logN)
	//auto pos = find(s.begin(), s.end(), 3);  //  O(N)
	if (pos != s.end())
	{
		s.erase(pos);
	}
	cout << s.erase(1) << endl;
	cout << s.erase(3) << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 打印key为1的个数
	cout << s.count(1) << endl;
}

三、multiset

multiset文档介绍

【总结】

1.multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

2.在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

3.在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。

4.multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。

5.multiset底层结构为二叉搜索树(红黑树)。

【注意】

1.multiset中再底层中存储的是<value, value>的键值对

2.mtltiset的插入接口中只需要插入即可

3.与set的区别是，multiset中的元素可以重复，set是中value是唯一的

4.使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

5.multiset中的元素不能修改

6.在multiset中找某个元素，时间复杂度为$O(lo{g}_{2}N)$

7.multiset的作用：可以对元素进行排序

multiset是使用和set的使用几乎一模一样，区别在于count和find的函数的差异：

count

由于multiset中允许存在重复key值的节点，所以multiset中count函数就可以用来统计key值为特定值的数量，此时返回值可以是大于等于0的任何数字，而set是不允许重复的key值的，所以count的返回值只能是0/1

find

set中没有重复的节点，所以find的返回值要么是返回该节点的迭代器(找到)，要么是end()(没有找到)，而multiset中允许存在重复的节点，此时如果没有找到就返回end()，当有多个的时候，find返回中序遍历过程中第一个匹配的节点位置的迭代器

erase

multiset允许重复的数据，当我们删除指定的val的时候，erase函数会将所有等于val的节点都删掉

multiset的使用范例

void test_set2()
{
	multiset<int> s;
	// 插入数据
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(7);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(1);

	// 使用迭代遍历multiset
	//multiset<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 使用范围for遍历set
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 查找加删除
	auto pos = s.find(3);                    // O(logN)
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	cout << s.erase(1) << endl;
	cout << s.erase(3) << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << s.count(1) << endl;
}

四、map

1.map的介绍

map的文档简介

【总结】

1.map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。

2.在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;

3.在内部，map中的元素总是按照键值key进行比较排序的。

4.map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

5.map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

6.map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

【注意】

1.map中的的元素是键值对

2.map中的key是唯一的，并且不能修改

3.默认按照小于的方式对key进行比较

4.map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5.map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$

6.支持[]操作符，operator[]中实际进行插入查找。

7.map允许修改key对应的value值，但是不允许修改key，因为这样会破坏二叉搜索树的结构

8.map中的元素是按照键值对key进行比较排序的，而与key对应的value无关，同时，map中也不允许有重复的key值的节点，map也可以用于排序，查找和去重，且map查找的时间复杂度为O(logN)

2.map的使用

构造

迭代器

容量

元素访问

我们可以看到，map重载了[]运算符，其函数原型如下：

//mapped_type: pair中第二个参数，即first
//key_type: pair中第一个参数，即second
mapped_type& operator[] (const key_type& k);

函数定义如下：

mapped_type& operator[] (const key_type& k) 
{
	(*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

我们可以看到，map的operator[]函数的实现看起来非常的复杂，我们可以将其进行分解

V& operator[] (const K& k)
{
	pair<iterator, bool> ret = insert(make_pair(k, V()));
    //return *(ret.first)->second;
	return ret.first->second;
}

我们可以看到，operator[]函数是先向map中插入一个k，其中这里的插入结果有两种情况，一种是map中已经存在与其相等的key，那么就插入失败，返回的pair中存放给节点位置的迭代器和false，如果map中没有与其相等的key值，则插入成功，即在map中插入key值为k的节点，该节点对应的value值为V的默认构造的缺省值。然后，operator[]会取出pair中迭代器(ret.first)，然后对迭代器进行解引用得到一个pair<k,v>对象，最后再返回pair对象中的second的引用，即key对应的value的引用，所以我们可以在函数的外面直接修改key对应的value值

operator[]的原理是：

用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
operator[]函数最后将insert返回值键值对中的value返回

所以，map中的operator[]可以实现插入，查找，修改三个功能，示例如下：

void map_test()
{
	map<string, string> dict;
	dict.insert(pair<string, string>("排序", "sort"));
	dict.insert(pair<string, string>("左边", "left"));
	dict.insert(pair<string, string>("右边", "right"));
	dict.insert(make_pair("字符串", "string"));
	dict["迭代器"] = "iterator"; // 插入+修改
	dict["insert"]; // 插入  key不在就是插入
	dict.insert(pair<string, string>("左边", "xxx")); // 插入失败，搜索树只比较key
	dict["insert"] = "插入"; //修改
	cout << dict["左边"] << endl; // 查找  key在就是查找

	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << (*it).first<<":"<<(*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

注意:在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时,operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常

修改

map和set一样，插入支持插入一个值，在某个迭代器的位置进行插入，插入一段迭代器区间的值，我们最常用的还是第一个，插入的过程就是二叉搜索树插入的过程，需要注意的是，插入的返回值是pair类型，pair的第一个元素代表插入的迭代器的位置，第二个元素代表是否插入成功(重复插入节点会返回false)

erase也是三种方式，分别为删除一个迭代器位置的数据，删除特定key值的数据，删除一段迭代器区间中的数据

其他操作

map的使用范例：

void TestMap()
{
	map<string, string> m;
	// 向map中插入元素的方式：
	// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));
	// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
	m.insert(make_pair("banan", "香蕉"));

	// 借用operator[]向map中插入元素
	/*
	operator[]的原理是：
	 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
	 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
	 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
	 operator[]函数最后将insert返回值键值对中的value返回
	*/
	// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
		m["apple"] = "苹果";
	// key不存在时抛异常
	//m.at("waterme") = "水蜜桃";
	cout << m.size() << endl;
	// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
	for (auto& e : m)
		cout << e.first << "--->" << e.second << endl;
	cout << endl;
	// map中的键值对key一定是唯一的，如果key存在将插入失败
	auto ret = m.insert(make_pair("peach", "桃色"));
	if (ret.second)
		cout << "<peach, 桃色>不在map中, 已经插入" << endl;
	else
		cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
		<< ret.first->second << " 插入失败" << endl;
	// 删除key为"apple"的元素
	m.erase("apple");
	if (1 == m.count("apple"))
		cout << "apple还在" << endl;
	else
		cout << "apple被吃了" << endl;
}

五、multimap

multimap的使用文档

【总结】

1.Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。

2.在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;

3.在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。

4.multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代

器直接遍历multimap中的元素可以得到关于key有序的序列。

5.multimap在底层用二叉搜索树(红黑树)来实现

【注意】

1.multimap中的key是可以重复的。

2.multimap中的元素默认将key按照小于来比较

3.multimap中没有重载operator[]操作

4.使用时与map包含的头文件相同：

multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

multimap和map的使用基本相同，需要注意的是，multimap中find返回的是中序遍历中第一个节点位置的迭代器，count返回和key相等节点的个数，此外，multimap中并没有重载[]运算符，因为multimap中的元素可以是重复的，如果使用[]运算符，会导致多个元素的key值相同，无法确定是访问哪一个的节点