map&set的封装_把stl set再封装一层

前言

在STL中，map和set底层都是用红黑树实现的，在前面一篇博客模拟实现了红黑树后，这篇博客要对map和set进行封装，以了解及熟悉其底层实现。

k模型和kv模型

set只存储key值，将key值作为关键码，作为被搜索的对象，属于k模型；而map存储的是一个键值对，每一个key值对应一个value值，但底层的红黑树是k模型还是kv模型？如果是k模型，模板参数只有一个k，如果是kv模型，模板参数有两个，一个k一个v。参考了STL源码，我发现红黑树将k模型和kv模型抽象出来，即只使用一个模板参数T，set封装时传k，map封装时将k和v打包成pair传给T。

set将key作为第二个参数传给re_tree

map将用key和T打包成的键值对作为第二个参数传给rb_tree

rb_tree的第二个参数作为node的参数
总之，re_tree中存储的数据类型为value。（第一个参数有什么用？第一个参数是key的类型，第一个参数常用在搜索函数，需要用key值搜索，所以第一个参数要作为函数的参数类型存在）

template <class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;

	RBTreeNode(pair<K, V> kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

所以对之前实现的代码进行改造

template <class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;

	RBTreeNode(T data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

节点中存储的数据类型统一成T，那么在比较时有两种情况，一种T是key可以直接进行比较，另一种T是pair，比较时要用pair的first数据进行比较，但看文档之后，pair确实有重载比较，但比较的规则不是我们想要的：没有用first来判断pair的大小
但又不能再重载一次（函数名相同，参数相同，再重载的话跟库中重载的冲突），STL是怎么解决这个问题的？STL使用了仿函数，分别在map和set中定义仿函数，将仿函数作为第三个传给re_tree，通过这个仿函数能取出T中我们需要比较的对象，对于set比较的对象就是key，对于map比较的对象就是pair的first

（KeyOfValue在STL中的一个使用，用KeyOfValue构造匿名对象，由于KeyOfValue重载了()，将v作为参数就能得到要进行比较的对象）

改造后的红黑树

#pragma once
#include <iostream>
using namespace std;
#include <utility>
#include <assert.h>

enum Colour
{
	RED,
	BLACK
};

template <class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;

	RBTreeNode(T data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	bool Insert(const T& data);
	void Inorder() { _Inorder(_root); }
private:
	void RotateL(Node* parent);
	void RotateR(Node* parent);
	void _Inorder(Node* root);
private:
	Node* _root = nullptr;
};

template <class K, class T, class KeyOfT>
bool RBTree<K, T, KeyOfT>::Insert(const T& data)
{
	KeyOfT kot;

	// 以搜索二叉树的规则插入
	if (_root == nullptr)
	{
		_root = new Node(data);
		// 根节点为黑色
		_root->_col = BLACK;
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	// 找合适的插入位置
	while (cur)
	{
		if (kot(data) < kot(cur->_data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kot(data) > kot(cur->_data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(data);
	// 判断该插入parent的哪边
	if (kot(data) < kot(parent->_data))
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	// 插入结束

	// 保持平衡
	while (parent && parent->_col == RED) // 出现连续的红节点
	{
		Node* grandParent = parent->_parent;
		assert(grandParent);

		if (grandParent->_left == parent) // parent在祖父节点左边
		{
			Node* uncle = grandParent->_right;
			// u为红色，一定要提前判断u是否存在
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandParent->_col = RED;
				if (grandParent == _root)
				{
					grandParent->_col = BLACK;
					return true;
				}
				else // grandParent不是根节点，但其父节点为黑色，也插入完成
				{
					if (grandParent->_parent && grandParent->_parent->_col == BLACK)
					{
						return true;
					}
					else // grandParent的父节点为红，出现连续红节点，更新节点，继续调整
					{
						cur = grandParent;
						parent = cur->_parent;
					}
				}
			} // end of if (uncle && uncle->_col == RED)

			else // u不存在或者为黑
			{
				// cur在p的左边
				if (cur == parent->_left)
				{
					RotateR(grandParent);
					grandParent->_col = RED;
					parent->_col = BLACK;
				}
				else // cur在p的右边，需要旋转成左边的情况
				{
					RotateL(parent);
					RotateR(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				return true;
			}
		} // end of - if (grandParent->_left == parent)

		else // p在grandParent的右边
		{
			Node* uncle = grandParent->_left;
			assert(grandParent);
			// u为红色
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandParent->_col = RED;
				if (grandParent == _root)
				{
					_root->_col = BLACK;
					return true;
				}
				else
				{
					if (grandParent->_parent->_col == BLACK)
					{
						return true;
					}
					// 更新继续调整
					else
					{
						cur = grandParent;
						parent = cur->_parent;
					}
				}
			} // end of if (uncle && uncle->_col == RED)

			else // u不存在或者为黑
			{
				// cur在p的右边
				if (cur == parent->_right)
				{
					RotateL(grandParent);
					grandParent->_col = RED;
					parent->_col = BLACK;
				}
				else // cur在p的右边，需要旋转成左边的情况
				{
					RotateR(parent);
					RotateL(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				return true;
			}
		} // end of - else
	}// end if - while
	return true;
}

template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateL(Node* parent)
{
	KeyOfT kot;

	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	subR->_left = parent;
	parent->_right = subRL;

	Node* pparent = parent->_parent;
	parent->_parent = subR;

	if (subRL)
		subRL->_parent = parent;
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else // 该子树是树的一部分
	{
		subR->_parent = pparent;
		if (kot(subR)->_data < kot(pparent->_data))
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
	}
}

template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateR(Node* parent)
{
	KeyOfT kot;

	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	subL->_right = parent;
	parent->_left = subLR;

	Node* pparent = parent->_parent;
	parent->_parent = subL;

	if (subLR)
		subLR->_parent = parent;
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		subL->_parent = pparent;
		if (kot(subL->_data) < kot(pparent->_data))
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
	}
}

template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::_Inorder(Node* root)
{
	KeyOfT kot;

	if (root == nullptr)
		return;

	_Inorder(root->_left);
	cout << root->kot(root->_data) << ' ';
	_Inorder(root->_right);
}
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281

改造部分大多是将比较数据套上仿函数

迭代器的定义

红黑树迭代器的结构和链表的迭代器类似，模板参数都有三个，T为节点中存储数据的类型，Ref为节点数据的引用，Ptr为节点中数据的指针。STL库中的红黑树实现了头节点，头节点的left指向树中最小节点，right指向树中最大节点，但实现头节点要付出较大的代价，在节点有了parent指针后，可以直接模拟中序进行++，–的操作。

++就是找比当前节点大的节点，翻译一下就是当前节点右树的最左节点。如果当前节点无右树，向上找parent，如果当前节点是parent的左孩子，那么parent就是比当前节点大的节点；如果当前节点是parent的右孩子，说明当前节点大于parent，将当前节点更新为parent继续向上找，直到当前节点是parent的左孩子。

–同理

1.左孩子存在，返回左树的最大节点
2.左孩子不存在，如果当前节点是parent的右孩子，返回parent
3.左孩子不存在，当前节点是parent的左孩子，向上更新，直到当前节点是parent的右孩子

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator++()
{
	if (_node->_right) // 右孩子存在
	{
		_node = _node->_right;
		while (_node->_left)
		{
			_node = _node->_left;
		}
	}
	else
	{
		while (_node->_parent && _node == _node->_parent->_right) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新
		{
			_node = _node->parent;
		}
		_node = _node->_parent;
	}
	return *this;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator++(int)
{
	self tmp = *this;
	++(*this);
	return tmp;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator--()
{
	if (_node->_left) // 右孩子存在
	{
		_node = _node->_left;
		while (_node->_right)
		{
			_node = _node->_right;
		}
	}
	else
	{
		while (_node->_parent && _node == _node->_parent->_left) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新
		{
			_node = _node->parent;
		}
		_node = _node->_parent;
	}
	return *this;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator--(int)
{
	self tmp = *this;
	--(*this);
	return tmp;
}
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

红黑树的封装

#pragma once
#include <iostream>
using namespace std;
#include <utility>
#include <assert.h>

enum Colour
{
	RED,
	BLACK
};

template <class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;

	RBTreeNode(T data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> self;
	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*() { return _node->_data; }
	Ptr operator->() { return &(_node->_data); }
	self& operator++();
	self operator++(int);
	self& operator--();
	self operator--(int);
	bool operator!=(self& s) { return s._node != _node; }

	Node* _node;
};

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;
public:
	pair<iterator, bool> Insert(const T& data);
	
	iterator begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end() { return iterator(nullptr); }
	const_iterator begin() const 
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}
	const_iterator end() const { return const_iterator(nullptr); }

	void Inorder() { _Inorder(_root); }
private:
	void RotateL(Node* parent);
	void RotateR(Node* parent);
	void _Inorder(Node* root);
private:
	Node* _root = nullptr;
};

template <class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::iterator, bool> RBTree<K, T, KeyOfT>::Insert(const T& data)
{
	KeyOfT kot;

	// 以搜索二叉树的规则插入
	if (_root == nullptr)
	{
		_root = new Node(data);
		// 根节点为黑色
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}

	Node* cur = _root;
	Node* parent = nullptr;
	// 找合适的插入位置
	while (cur)
	{
		if (kot(data) < kot(cur->_data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kot(data) > kot(cur->_data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return make_pair(iterator(cur), false);
		}
	}
	cur = new Node(data);
	// 判断该插入parent的哪边
	if (kot(data) < kot(parent->_data))
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	// 插入结束

	// 保持平衡
	while (parent && parent->_col == RED) // 出现连续的红节点
	{
		Node* grandParent = parent->_parent;
		assert(grandParent);

		if (grandParent->_left == parent) // parent在祖父节点左边
		{
			Node* uncle = grandParent->_right;
			// u为红色，一定要提前判断u是否存在
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandParent->_col = RED;
				if (grandParent == _root)
				{
					grandParent->_col = BLACK;
					return make_pair(iterator(cur), true);
				}
				else // grandParent不是根节点，但其父节点为黑色，也插入完成
				{
					if (grandParent->_parent && grandParent->_parent->_col == BLACK)
					{
						return make_pair(iterator(cur), true);
					}
					else // grandParent的父节点为红，出现连续红节点，更新节点，继续调整
					{
						cur = grandParent;
						parent = cur->_parent;
					}
				}
			} // end of if (uncle && uncle->_col == RED)

			else // u不存在或者为黑
			{
				pair<iterator, bool> ret = make_pair(iterator(cur), true);
				// cur在p的左边
				if (cur == parent->_left)
				{
					RotateR(grandParent);
					grandParent->_col = RED;
					parent->_col = BLACK;
				}
				else // cur在p的右边，需要旋转成左边的情况
				{
					RotateL(parent);
					RotateR(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				return ret;
			}
		} // end of - if (grandParent->_left == parent)

		else // p在grandParent的右边
		{
			Node* uncle = grandParent->_left;
			assert(grandParent);
			// u为红色
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandParent->_col = RED;
				if (grandParent == _root)
				{
					_root->_col = BLACK;
					return make_pair(iterator(cur), true);
				}
				else
				{
					if (grandParent->_parent->_col == BLACK)
					{
						return make_pair(iterator(cur), true);
					}
					// 更新继续调整
					else
					{
						cur = grandParent;
						parent = cur->_parent;
					}
				}
			} // end of if (uncle && uncle->_col == RED)

			else // u不存在或者为黑
			{
				pair<iterator, bool> ret = make_pair(iterator(cur), true);
				// cur在p的右边
				if (cur == parent->_right)
				{
					RotateL(grandParent);
					grandParent->_col = RED;
					parent->_col = BLACK;
				}
				else // cur在p的右边，需要旋转成左边的情况
				{
					RotateR(parent);
					RotateL(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				return ret;
			}
		} // end of - else
	}// end if - while
	return make_pair(iterator(cur), true);
}

template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateL(Node* parent)
{
	KeyOfT kot;

	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	subR->_left = parent;
	parent->_right = subRL;

	Node* pparent = parent->_parent;
	parent->_parent = subR;

	if (subRL)
		subRL->_parent = parent;
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else // 该子树是树的一部分
	{
		subR->_parent = pparent;
		if (kot(subR->_data) < kot(pparent->_data))
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
	}
}

template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateR(Node* parent)
{
	KeyOfT kot;

	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	subL->_right = parent;
	parent->_left = subLR;

	Node* pparent = parent->_parent;
	parent->_parent = subL;

	if (subLR)
		subLR->_parent = parent;
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		subL->_parent = pparent;
		if (kot(subL->_data) < kot(pparent->_data))
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
	}
}


template <class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::_Inorder(Node* root)
{
	KeyOfT kot;

	if (root == nullptr)
		return;

	_Inorder(root->_left);
	cout << kot(root->_data) << ' ';
	_Inorder(root->_right);
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator++()
{
	if (_node->_right) // 右孩子存在
	{
		_node = _node->_right;
		while (_node->_left)
		{
			_node = _node->_left;
		}
	}
	else
	{
		while (_node->_parent && _node == _node->_parent->_right) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新
		{
			_node = _node->_parent;
		}
		_node = _node->_parent;
	}
	return *this;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator++(int)
{
	self tmp = *this;
	++(*this);
	return tmp;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator--()
{
	if (_node->_left) // 右孩子存在
	{
		_node = _node->_left;
		while (_node->_right)
		{
			_node = _node->_right;
		}
	}
	else
	{
		while (_node->_parent && _node == _node->_parent->_left) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新
		{
			_node = _node->parent;
		}
		_node = _node->_parent;
	}
	return *this;
}

template <class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator--(int)
{
	self tmp = *this;
	--(*this);
	return tmp;
}
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388

set的封装

template <class K>
class Set
{
	struct KeyOfSet
	{
		const K& operator()(const K& data)
		{
			return data;
		}
	};
public:
	typedef RBTreeIterator<K, const K&, const K*> iterator;
	typedef RBTreeIterator<K, const K&, const K*> const_iterator;

	iterator begin() const{ return _t.begin(); }
	iterator end() const{ return _t.end(); }
	pair<iterator, bool> Insert(const K& k)
	{
		pair<RBTreeIterator<K, K&, K*>, bool> p = _t.Insert(k);
		return pair<iterator, bool>(iterator(p.first._node), p.second);
	}
	void Inorder() { _t.Inorder(); }
private:
	typedef RBTree<K, K, KeyOfSet> RBTree;
	RBTree _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

map的封装

template <class K, class V>
class Map
{
	struct KeyOfMap
	{
		const K& operator()(const pair<K, V>& data)
		{
			return data.first;
		}
	};
public:
	typedef RBTreeIterator<pair<K, V>, pair<K, V>&, pair<K, V>*> iterator;
	typedef RBTreeIterator<const pair<K, V>, const pair<K, V>&, const pair<K, V>*> const_iterator;
	iterator begin() { return _t.begin(); }
	iterator end() { return _t.end(); }
	const_iterator begin() const { return _t.begin(); }
	const_iterator end() const { return _t.end(); }
	pair<iterator, bool> Insert(const pair<K, V>& kv) { return _t.Insert(kv); }
	void Inorder() { _t.Inorder(); }
	V& operator[](const K& k)
	{
		pair<K, V> p(k, V());
		pair<iterator, bool> ret = _t.Insert(p);
		return ret.first->second;
	}
private:
	typedef RBTree<K, pair<K, V>, KeyOfMap> RBTree;
	RBTree _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

两者的接口大多是复用红黑树的接口，其中map要实现[]的重载：先根据key值构造一个键值对，该键值对的value值是默认值，然后将键值对插入得到返回的pair，函数最后返回插入得到的pair的first的value引用（pair的first为map的迭代器）