系列文章目录

C++入门

C++类和对象（上）

C++类和对象（中）

C++类和对象（下）

C/C++内存管理

C++string类

C++vector类

C++list类

C++stack和queue

C++双端队列

C++模板进阶

C++IO流

C++中的继承

C++中的多态

---

---

前言

序列式容器

在之前我们见到的都是序列式容器，比如：vector,list,deque,forward_list等，因为其底层为线性序列的数据结构，容器中存储的是元素本身。

关联式容器

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

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

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。 比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

---

一、set

1、set介绍

1. set是按照一定次序存储元素的容器，set中的元素不可以重复
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

2、set的使用

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

void test6()
{
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;

	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	// set中值为3的元素出现了几次
	cout << s.count(3) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

结果如下：

set插入元素时遇到重复元素将不会插入，若想插入重复元素，可以用multiset。

二、map

1、map介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair value_type
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

2、map的使用

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

map的构造：

void test2()
{
	map<int, double> m;
	//调用pari构造函数，构造一个匿名对象插入
	m.insert(pair<int, double>(1, 1.1));
	m.insert(pair<int, double>(2, 2.2));
	
	//调用函数模板构造对象
	m.insert(make_pair(3, 3.3));

	map<int, double>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << " " << it->second << endl;
		++it;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

map插入方式：

void test4()
{
	string arr[] = { "苹果","橙子", "芒果", "西瓜", "西瓜", "芒果", "芒果", "苹果", "苹果", "芒果", "苹果", "苹果" };
	map<string, int> fruitMap;
	//插入方式1
	//for (string& s : arr)
	//{
	//	map<string, int>::iterator pos = fruitMap.find(s);
	//	if (pos != fruitMap.end())
	//	{
	//		++pos->second;
	//	}
	//	else
	//	{
	//		fruitMap.insert(make_pair(s, 1));
	//	}
	//}
	
	//插入方式2
	//for (string& s : arr)
	//{
	//	pair<map<string, int>::iterator, bool> temp = fruitMap.insert(make_pair(s, 1));
	//	if (temp.second == false)
	//	{
	//		++temp.first->second;
	//	}
	//}
	
	//插入方式3
	for (string& s : arr)
	{
		++fruitMap[s];
	}
	for (auto& e : fruitMap)
	{
		cout << e.first << " " << e.second << endl;
	}
}
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
29
30
31
32
33
34
35
36
37
38

operator[]的原理是：

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

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

同样的map也无法插入关键字(key)相同的元素，如果需要，可以使用multimap

三、底层结构

这几个容器有个共同点是：
其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

3.1 AVL树

1.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一颗AVL树具有以下性质：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 ，搜索时
间复杂度O( )。

2.AVL树节点定义

template<class T>
struct AVLTreeNode
 {
    AVLTreeNode(const T& data)
    : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
    , _data(data), _bf(0)
    {}
    AVLTreeNode<T>* _pLeft; // 该节点的左孩子
    AVLTreeNode<T>* _pRight; // 该节点的右孩子
    AVLTreeNode<T>* _pParent; // 该节点的双亲
    T _data;
    int _bf; // 该节点的平衡因子
 };
1
2
3
4
5
6
7
8
9
10
11
12
13

3.AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

我们假设新插入节点为cur，其双亲节点为parent。在cur插入之前，parent的平衡因子可能为0，1，-1三种情况。根据cur插入方向的不同，可分为：

1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

此时，parent的平衡因子可能有三种情况，0，±1，±2，我们进行逐个分析：

1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此
   时满足 AVL树的性质，插入成功。
2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负
   1，此 时以parent为根的树的高度增加，需要继续向上更新。
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转
   处理。

pair<Node*, bool> insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return make_pair(_root, true);
		}
		Node* parent = _root, * cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, true);
			}
		}

		cur = new Node(kv);
		Node* newnode = cur;
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		cur->_bf = 0;
		//更新父节点到根结点的平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				--parent->_bf;
			}
			else
			{
				++parent->_bf;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//不平衡，需要旋转
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						rotateR(parent);
					}
					else
					{
						rotateLR(parent);
					}
				}
				else
				{
					if (cur->_bf == 1)
					{
						rotateL(parent);
					}
					else
					{
						rotateRL(parent);
					}
				}
				break;
			}
			else
			{
				//平衡因子大于2，插入之前就不平衡了，可能其他地方出错了
				assert(false);
			}

		}
		return make_pair(newnode, true);
	}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

4.AVL树的旋转

根据节点插入位置的不同，AVL树的旋转分为四种：

新节点插入较高左子树的左侧—左左：右单旋

	//右单旋
	void rotateR(Node* root)
	{
		//根结点左孩子和根结点左孩子的右孩子
		Node* rootL = root->_left;
		Node* rootLR = rootL->_right;
		Node* grandParent = root->_parent;
		//右旋
		root->_left = rootLR;
		if (rootLR)
		{
			rootLR->_parent = root;
		}
		rootL->_right = root;
		root->_parent = rootL;

		if (grandParent == nullptr)
		{
			_root = rootL;
			rootL->_parent = nullptr;
		}
		else
		{
			if (grandParent->_left == root)
			{
				grandParent->_left = rootL;
			}
			else
			{
				grandParent->_right = rootL;
			}
			rootL->_parent = grandParent;
		}

		root->_bf = 0;
		rootL->_bf = 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
29
30
31
32
33
34
35
36
37

新节点插入较高右子树的右侧—右右：左单旋

//左单旋
	void rotateL(Node* root)
	{
		Node* rootR = root->_right;
		Node* rootRL = root->_right->_left;
		Node* grandParent = root->_parent;

		rootR->_left = root;
		root->_parent = rootR;
		root->_right = rootRL;
		if (rootRL)
		{
			rootRL->_parent = root;
		}

		if (grandParent == nullptr)
		{
			_root = rootR;
		}
		else
		{
			if (grandParent->_left == root)
			{
				grandParent->_left = rootR;
			}
			else
			{
				grandParent->_right = rootR;
			}
		}
		rootR->_parent = grandParent;

		root->_bf = 0;
		rootR->_bf = 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
29
30
31
32
33
34
35

新节点插入较高左子树的右侧—左右：先左单旋再右单旋

//左右双旋
	void rotateLR(Node* root)
	{
		Node* rootL = root->_left;
		Node* rootLR = rootL->_right;
		int bf = rootLR->_bf;
		rotateL(rootL);
		rotateR(root);

		if (bf == -1)
		{
			rootLR->_bf = 0;
			rootL->_bf = 0;
			root->_bf = 1;
		}
		else if (bf == 1)
		{
			rootLR->_bf = 0;
			rootL->_bf = -1;
			root->_bf = 0;
		}
		else if (bf == 0)
		{
			rootLR->_bf = 0;
			rootL->_bf = 0;
			root->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
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
29
30
31
32

新节点插入较高右子树的左侧—右左：先右单旋再左单旋

	//右左双旋
	void rotateRL(Node* root)
	{
		Node* rootR = root->_right;
		Node* rootRL = rootR->_left;
		int bf = rootRL->_bf;

		rotateR(rootR);
		rotateL(root);

		//
		if (bf == -1)
		{
			root->_bf = 0;
			rootR->_bf = 1;
			rootRL->_bf = 0;
		}
		else if (bf == 1)
		{
			root->_bf = -1;
			rootR->_bf = 0;
			rootRL->_bf = 0;
		}
		else if (bf == 0)
		{
			root->_bf = 0;
			rootR->_bf = 0;
			rootRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
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
29
30
31
32
33
34

总的来说，假设以parent为根的子树不平衡，平衡因子为2或-2：

当平衡因子为2时：说明右子树高，根据parent右子树的平衡因子的的不同，进行旋转：
右子树平衡因子为1，说明新增节点在右子树的右子树上，进行左单旋
右子树平衡因子为-1，说明新增节点在右子树的左子树上，进行左右双旋

当平衡因子为-2时：说明左子树高，根据parent左子树的平衡因子的的不同，进行旋转：
左子树平衡因子为-1，说明新增节点在左子树的左子树上，进行右单旋
左子树平衡因子为1，说明新增节点在左子树的右子树上，进行右左双旋

5.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

3.2 红黑树

1. 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

2. 红黑树的性质

1. 每个结点不是黑色就是红色。
2. 根结点为黑色。
3. 如果一个结点为红色，则其两个孩子都是黑色的。
4. 每个叶结点（指的是空结点）都是黑色的。
5. 对于每个结点，从该结点到其所有后代的叶结点的简单路径上，均包含相同数目的黑色结点。

3. 红黑树的插入

首先，按照二叉搜索树的规则插入新结点。
插入新结点后，判断红黑树的性质是否被破坏，大致分为以下情形：
首先假设当前结点为N，父结点为P，祖父结点为GP，叔叔结点U。

情形1： 若N为根结点，直接涂黑。
情形2： 父结点为黑色，直接插入即可。
情形3： P和U都为红，将P和U都涂黑，同时向上递归：

情形4： P为红，U为黑
情形4.1： P和N在同一边（都为父结点的左子树或右子树）

都为左子树时：
此时以祖父节点(GP)为支点进行右旋；然后将P涂黑，将GP涂红。

旋转后，P涂黑是因为要涂为原GP的黑色（往上兼容GP的父节点）；而GP涂红则是因为右旋后，经过U的路径的黑色节点数量+1，涂红进行数量平衡。

都为右子树时：
此时以祖父节点(GP)为支点进行左旋；将P涂黑，将GP涂红。

情形4.2： P和N不在同一边
当P左N右时（P为左子树，N为右子树）：
此时，以父节点§进行左旋，旋转后，以P作为新的平衡节点N，转至 [情形4.1.1 父N同左] 处理。

当P右N左时：
此时，以父节点§进行右旋，旋转后，以P作为新的平衡节点，此时再进行【情形4.1.2 父N同右】处理。

3.3 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

---