map与set的封装实现-红黑树_map封装数据

---

map与set的封装实现-红黑树

---

再谈：

• 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($lo{g}_{2}N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
• 而map与set底层结构就是红黑树。
• 关于红黑树，可参考之前文章：https://blog.csdn.net/m0_69597277/article/details/129897990
  

---

前言

编译环境：VS2013

---

一、关联式容器与键值对

1.关联式容器

1.序列式容器：STL中的部分容器，比如：string、vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
2.关联式容器：也是用来存储数据的，与序列式容器不同的是，其里面存储的是<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)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、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. 默认按照小于(less)的方式对key进行比较，即升序。
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列。
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

2.红黑树模拟实现map

为实现map与set，我们需改造红黑树，在红黑树基础上，增加迭代器，在涉及到元素的比较上，由于存储元素的不同，如map中为键值对中k来进行比较，而set中是直接k值来进行比较，所以红黑树中原来直接将存储元素取出来进行比较的方法便行不通。故：我们在红黑树的类中增加一模板参数KOFT，表示从存储元素中将要进行比较的k值提取出来。
（1）红黑树的迭代器
增加迭代器便于元素的遍历。

迭代器begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列。
故：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，那问题是最大节点的下一个位置在哪里呢？能否给成nullptr呢？
答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，因此最好的方式是将end()放在头结点的位置。
这也解释了我们一开始在构造红黑树时增加一个头结点的原因。

封装类如下：

//封装红黑树迭代器的类
template<class T,class Ref,class Ptr>
class RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
public:
	RBTreeIterator(Node* pNode = nullptr)
		:_pNode(pNode)
	{}
	//迭代器需有指针类似的操作
	//解引用* 和指向->
	Ref operator*()
	{
		return _pNode->_data;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	//迭代器可比较
	bool operator==(const Self& s)const
	{
		return _pNode == s._pNode;
	}
	bool operator!=(const Self& s)const
	{
		return _pNode != s._pNode;
	}
	//迭代器可移动
	//++a
	Self& operator++()
	{
		Increment();
		return *this;
	}
	//a++
	Self operator++(int)
	{
		Self temp(*this);
		Increment();
		return temp;
	}
	Self& operator--()
	{
		Decrement();
		return *this;
	}
	Self operator--(int)
	{
		Self temp(*this);
		Decrement();
		return temp;
	}

private:
	Node* _pNode;
};
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

（2）红黑树迭代器的移动operator++()与operator–()
迭代器的移动，依次找红黑树中的节点即可。

//迭代器移动
void Increment()
	{
		//迭代器往后移动
		//要么根节点，要么右子树最左侧的节点（右子树最小节点）
		if (_pNode->_right)
		{
			//_pNode右子树存在，到右子树中找最左侧的节点
			_pNode = _pNode->_right;
			while (_pNode->_left)
			{
				_pNode = _pNode->_left;
			}
		}
		else //若右子树存在，再往双亲里去找
		{
			Node* parent = _pNode->_parent;
			while (parent->_right == _pNode)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}
			//特殊：根节点没有右子树，迭代器恰好在根的位置
			//_pNode->_parent=头节点，而_pNode的右指针域是指向自己的
			if (_pNode->_right != parent)
			{
				_pNode = parent;
			}
		}
	}
	void Decrement()
	{
		//迭代器往前移动
		//要么根节点，要么左子树最右侧的节点（左子树最大的节点）
		//当迭代器在end的位置
		if (_pNode->_parent->_parent = _pNode && _pNode->_color == RED)
		{
			_pNode = _pNode->_right;
		}
		else if (_pNode->_left)
		{
			//_pNode左子树存在，在左子树中找最大的（最右侧节点）
			_pNode = _pNode->_left;
			while (_pNode->_right)
			{
				_pNode = _pNode->_right;
			}
		}
		else
		{
			//左子树存在的情况下再往双亲里面去找
			Node* parent = _pNode->_parent;
			while (_pNode = parent->_left)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}
			_pNode = parent;
		}
	}
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

（3）红黑树构造
红黑树中增加迭代器和KOFT，在元素有进行比较的地方，便不是直接将存储元素取出来进行比较，而是将从存储元素将比较值k提取出来进行比较。
类中其余方法同红黑树。

//规定：树中元素唯一
//红黑树封装map 和 set
//T表示往红黑树当中存储的元素类型，map中T为键值对，set中T为k值
//参数模板中加一参数KOFT：从T中将比较值K值提取出来
template<class T,class KOFT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;

public:
	RBTree()
	{
		_head = new Node();
		_head->_parent = nullptr;
		_head->_left = _head;
		_head->_right = _head;
		_size = 0;
	}
	~RBTree()
	{
		Destroy(_head->_parent);
	}
	
	iterator Begin()
	{
		return iterator(_head->_left);
	}
	iterator End()
	{
		return iterator(_head);
	}
	bool Empty()const
	{
		return _head->_parent == nullptr;
	}
	size_t Size()const
	{
		return _size;
	}

	//红黑树中节点的插入
	pair<iterator,bool> Insert(const T& data)
	{
		Node* newNode = nullptr;
		//1.按照二叉搜索树的方式进行节点的插入
		Node*& root = _head->_parent;
		//树为空，插入节点为树的根
		if (root == nullptr)
		{
			newNode = root = new Node(data, BLACK);
			root->_parent = _head;
		}
		else
		{
			//树非空，查找插入节点元素是否存在
			Node* cur = root;
			Node* parent = _head;
			KOFT koft;
			while (cur)
			{
				parent = cur;
				if (koft(cur->_data) <koft(data))
				{
					cur = cur->_right;
				}
				else if (koft(cur->_data)>koft(data))
				{
					cur = cur->_left;
				}
				else
				{
					return make_pair(iterator(cur),false);
				}
			}
			//进行节点的插入
			newNode = cur = new Node(data);
			if (koft(parent->_data) > koft(data))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

			//2.验证红黑树的性质若遭到破坏则对树进行调整
			//节点插入成功可能会违反不能有连在一起的红色节点
			//即新节点颜色为红色，parent颜色也为红
			while (parent != _head && parent->_color == RED)
			{
				Node* pParent = parent->_parent;

				//parent可能为pParent的左孩子或是右孩子
				if (parent == pParent->_left)
				{
					//情况一：cur为红，parent为红，pParent为黑，uncle存在且为红
					//处理：将parent和uncle颜色改为黑，将pParent颜色改为红,继续往上调整
					Node* uncle = pParent->_right;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = BLACK;
						uncle->_color = BLACK;
						pParent->_color = RED;
						cur = pParent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔节点不存在 || 树树节点存在且颜色为黑
						if (parent->_right == cur)
						{
							//情况三: cur为红，parent为红，pParent为黑，uncle不存在或uncle存在且为黑
							//处理：若parent为pParent的左孩子，cur为parent的右孩子，则针对parent做左单旋转
							//若parent为g的右孩子，cur为parent的左孩子，则针对parent做右单旋转，转化为情况二
							RotateLeft(parent);
							swap(parent, cur);
						}
						parent->_color = BLACK;
						pParent->_color = RED;
						RotateRight(pParent);
					}
				}
				else
				{
					Node* uncle = pParent->_left;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = BLACK;
						uncle->_color = BLACK;
						pParent->_color = RED;
						cur = pParent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔节点不存在 || 树树节点存在且颜色为黑
						if (parent->_left == cur)
						{
							RotateRight(parent);
							swap(cur, parent);
						}
						parent->_color = BLACK;
						pParent->_color = RED;
						RotateLeft(pParent);
					}
				}

			}
		}
		_head->_left = MostLeftNode();    //树的左子树最左侧的节点
		_head->_right = MostRightNode();  //树的右子树最右侧的节点

		//根节点必须为黑
		_head->_parent->_color = BLACK;
		++_size;
		return make_pair(iterator(newNode), true);
	}
	//查找元素
	iterator Find(const T& data)
	{
		Node* cur = _head->_parent;
		KOFT koft;
		while (cur)
		{
			if (koft(data) == koft(cur->_data))
			{
				return iterator(cur);
			}
			else if (koft(data) < koft(cur->_data))
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
		return End();
	}
	//清空元素
	void Clear()
	{
		Destroy(_head->_parent);
		_head->_left = _head;
		_head->_right = _head;
		_size = 0;
	}
	//节点交换
	void Swap(RBTree<T,KOFT>& t)
	{
		std::swap(_head->_parent, t._head->_parent);
	}
private:
	Node* _head;  //定义一个头结点
	size_t _size;
};
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

（4）map实现

#pragma once 
#include"RBTree.hpp"
namespace ma
{
	template<class K,class V>
	class map
	{
		typedef pair<K, V> KV;
		struct KOFKV
		{
			const K& operator()(const KV& data)const
			{
				return data.first;
			}
		};
		typedef RBTree<KV, KOFKV> RBT;
	public:
		//此处需加上typename
		//因为静态成员变量是通过 类名::静态成员方式来访问，故编译器不确定iterator是否是RBT中的类型
		//而typename明确地告诉编译器iterator是RBT中的一个类型，而不是静态成员变量
		typename typedef  RBT::iterator iterator;
	public:
		map()
			:_t()
		{}
		//Iterator
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		//Capacity
		bool empty()const
		{
			return _t.Empty();
		}
		size_t size()const
		{
			return _t.Size();
		}
		//Element access
		V& operator[](const K& x)
		{
			//make_pair(x,V()) 构造默认的键值对
			return (*(insert(make_pair(x, V())).first)).second;
		}

		pair<iterator, bool> insert(const KV& data)
		{
			return _t.Insert(data);
		}
		iterator find(const K& data)
		{
			return _t.Find(KV(data, V()));
		}
		void swap(map<K, V>& m)
		{
			_t.Swap(m._t);
		}
		void clear()
		{
			_t.Clear();
		}
	private:
		RBT _t;
	};
}
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

三、set

1.set容器说明

set文档查看

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

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。key唯一。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列(其底层实现为红黑树，而红黑树为二叉搜索树)
5. set中的元素默认按照小于(less)来比较，即升序。
6. set中查找某个元素，时间复杂度为：$lo{g}_{2}N$

2.红黑树模拟实现set

set大体同map。

#pragma once 
#include"RBTree.hpp"
namespace se
{
	template<class K>
	class set
	{
		struct KOFK
		{
			const K& operator()(const K& data)const
			{
				return data;
			}
		};
		typedef RBTree<K, KOFK> RBT;
	public:
		//此处需加上typename
		//因为静态成员变量是通过 类名::静态成员方式来访问，故编译器不确定iterator是否是RBT中的类型
		//而typename明确地告诉编译器iterator是RBT中的一个类型，而不是静态成员变量
		typename typedef  RBT::iterator iterator;
	public:
		set()
			:_t()
		{}
		//Iterator
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		//Capacity
		bool empty()const
		{
			return _t.Empty();
		}
		size_t size()const
		{
			return _t.Size();
		}
		//Element access
		pair<iterator, bool> insert(const K& data)
		{
			return _t.Insert(data);
		}
		iterator find(const K& data)
		{
			return _t.Find(data);
		}
		void swap(set<K>& s)
		{
			_t.Swap(s._t);
		}
		void clear()
		{
			_t.Clear();
		}
	private:
		RBT _t;
	};
}
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

四、实现测试与结果

测试：

//RBTree测试函数
void TestRBTree()
{
	struct KOFInt
	{
		int operator()(const int data)const
		{
			return data;
		}
	};
	RBTree<int, KOFInt> t;
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.Inorder();

	auto it = t.Begin();
	while (it !=t.End())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	if (t.IsValidRBTree())
	{
		cout << "t is valid tree" << endl;
	}
	else
	{
		cout << "t is invalid tree" << endl;
	}

	cout << t.Size() << endl;
	if (t.Find(18) != t.End())
	{
		cout << "18 is in the RBTree." << endl;
	}
	else
	{
		cout << "18 is not in the RBTree." << endl;
	}
	if (!t.Empty())
	{
		t.Clear();
	}
	cout << t.Size() << 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
39
40
41
42
43
44
45
46
47
48
49
50

//map测试函数
void TestMap()
{
	ma::map<string, string> m;
	m.insert(make_pair("apple", "苹果"));
	m.insert(make_pair("orange", "橙子"));
	m.insert(make_pair("pear", "鸭梨"));
	m.insert(make_pair("watermelon", "西瓜"));

	cout << m.size() << endl;
	cout << m["orange"] << endl;
	auto it = m.begin();
	while (it != m.end())
	{
		cout << it->first << "---->" << it->second << endl;
		++it;
	}
	cout << endl;

	if (m.find("orange") != m.end())
	{
		cout << "orange is in map." << endl;
	}
	else
	{
		cout << "orange is not in map." << 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

//set测试函数
void TestSet()
{
	se::set<string> s;
	s.insert("apple");
	s.insert("orange");
	s.insert("pear");
	s.insert("watermelon");

	cout << s.size() << endl;
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	if (s.find("orange") != s.end())
	{
		cout << "orange is in map." << endl;
	}
	else
	{
		cout << "orange is not in map." << 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

结果：

---

五、总结

map的底层结构就是红黑树，故在进行map的封装实现时，实质其实也就是将红黑树中的相应接口包装一下，当然，set同理。
完整代码可点击进入仓库查看：
https://gitee.com/confused-cat/code_-connection_point/tree/master/Map-and-Set