C++map和set(个人笔记)，C++中的map和set详解（个人笔记）

温馨提示：这篇文章已超过441天没有更新，请注意相关的内容是否还可用！

摘要：本笔记简要介绍了C++中的map和set容器。map是一种关联容器，存储的是键值对，允许通过键快速访问对应的值。set则是一种不包含重复元素的集合容器，元素在插入时自动排序。两者都提供了高效的插入、删除和查找操作。理解map和set的工作原理和用法对于C++程序员来说非常重要，有助于解决各种数据结构和算法问题。

C++map和set

1.set

1.1set的使用

1.1.1 set的模板参数列表
1.1.2set的构造
1.1.3set的迭代器
1.1.4 set的容量
1.1.5 set修改操作
1.1.6 set的具体使用例子
2.map

2.1map的使用

2.1.1map的模板参数列表
2.1.2map的构造
2.1.3map的迭代器
2.1.4 map的容量与元素访问
2.1.5 map中元素的修改
2.1.6map的具体使用例子
3.multiset

3.1 multiset的具体使用
4.multimap
5.笔试题
6.AVL树

6.1AVL树的实现

6.1.1AVL树节点的定义
6.1.2AVL树的插入
6.1.4AVL树的旋转
6.1.5AVL树的验证
7.红黑树

7.1红黑树的性质
7.2红黑树的实现

7.2.1红黑树节点的定义
7.2.2红黑树的插入操作
7.2.3红黑树的验证
8.红黑树与AVL树的比较
9.map和set模拟实现

9.1改造红黑树
9.2map模拟实现

9.3set的模拟实现

1.set

C++set官方文档

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

注意：

与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
set中插入元素时，只需要插入value即可，不需要构造键值对。
set中的元素不可以重复(因此可以使用set进行去重)。
使用set的迭代器遍历set中的元素，可以得到有序序列
set中的元素默认按照小于来比较
set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2n
set中的元素不允许修改
set中的底层使用二叉搜索树(红黑树)来实现。

1.1set的使用

1.1.1 set的模板参数列表

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第1张

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

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

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

1.1.2set的构造

函数声明	功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );	构造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)区间中的元素构造set
set ( const set& x);	set的拷贝构造

1.1.3set的迭代器

函数声明	功能介绍
iterator begin()	返回set中起始位置元素的迭代器
iterator end()	返回set中最后一个元素后面的迭代器
const_iterator cbegin() const	返回set中起始位置元素的const迭代器
const_iterator cend() const	返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin()	返回set第一个元素的反向迭代器，即end
reverse_iterator rend()	返回set最后一个元素下一个位置的反向迭代器，即begin
const_reverse_iterator crbegin() const	返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器，即cbegin

1.1.4 set的容量

函数声明	功能介绍
bool empty ( ) const	检测set是否为空，空返回true，否则返回false
size_type size() const	返回set中有效元素的个数

1.1.5 set修改操作

函数声明	功能介绍
pair insert ( const value_type& x )	在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回,如果插入失败，说明x在set中已经存在，返回
void erase ( iterator position )	删除set中position位置上的元素
size_type erase ( const key_type& x )	删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
void swap ( set& st );	交换set中的元素
void clear ( )	将set中的元素清空
iterator find ( const key_type& x ) const	返回set中值为x的元素的位置
size_type count ( const key_type& x ) const	返回set中值为x的元素的个数

1.1.6 set的具体使用例子

#include
#include
using namespace std;
void TestSet()
{
	//用数组arr中的元素构造set
	int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set s(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout 
		cout 
		cout 
	map
		cout 
		cout 
		cout 
		cout 
		cout 
	int arr[]= { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
	//注意multiset在底层实际储存的是
		cout 
public:
    struct kvCom
    {
        bool operator()(const pair
            return kv1.second  kv2.second || (kv1.first _bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			break;
		}
		else
		{
			assert(false);
		}
	}
	return true;
}

6.1.4AVL树的旋转

左单旋：

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第2张

void RotateL(Node* parent)
{
	++_rotateCount;
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}
	cur->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = cur;
	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
		cur->_parent = ppnode;
	}
	parent->_bf = cur->_bf = 0;
}

右单旋：

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第3张

void RotateR(Node* parent)
{
	++_rotateCount;
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	parent->_left = curright;
	if (curright)
		curright->_parent = parent;
	Node* ppnode = parent->_parent;
	cur->_right = parent;
	parent->_parent = cur;
	if (ppnode == nullptr)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
		cur->_parent = ppnode;
	}
	parent->_bf = cur->_bf = 0;
}

右左单旋：

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第4张

void RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	int bf = curleft->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	if (bf == 0)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		cur->_bf = 1;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

左右单旋：

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第5张

void RotateLR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	int bf = curright->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	if (bf == 0)
	{
		parent->_bf = 0;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		cur->_bf = -1;
		curright->_bf = 0;
	}
}

6.1.5AVL树的验证

验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InOrder(root->_left);
	cout _kv.first _right);
}

验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确

int _Height(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight _left);
	int rightHeight = _Height(root->_right);
	if (rightHeight - leftHeight != root->_bf)
	{
		cout _kv.first _right);
}

7.红黑树

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

7.1红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的（就是不能有连续的红色节点）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

7.2红黑树的实现

7.2.1红黑树节点的定义

enum Colour
{
	RED,
	BLACK
};
template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;
	Colour _col;
	RBTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

7.2.2红黑树的插入操作

新增：插入红色节点

1.插入节点的父亲是黑色节点，那么直接就结束了，没有违反任何规则

2.插入节点的父亲是红色节点，那么存在连续的红色节点，违反规则三，需要处理

情况一：cur为红，p为红，g为黑，u存在且为红

解决方案：将p，u改为黑，g改为红，然后把g赋值给cur，继续向上调整

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第6张

情况二：

1.cur为红，p为红，g为黑，u不存在

解决方案：p为g的左孩子，cur为p的左孩子，则进行右单旋，相反，p为g的右孩子，cur为p的右孩子，则进行左单旋，p变黑，g变红

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第7张

2.cur为红，p为红，g为黑，u存在且为黑（中间态是由下层变上来的）

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第8张

情况三：cur为红，p为红，g为黑，u不存在或者存在且为黑（其实就是g，p，c是折线，经过一次旋转后变成情况二）

C++map和set(个人笔记)，C++中的map和set详解（个人笔记）第9张

bool Insert(const pair& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first _right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	// 新增节点给红色
	cur = new Node(kv);
	cur->_col = RED;
	if (parent->_kv.first _right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			//     g
			//   p   u
			// c
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				// 继续往上更新处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					// 单旋
					//     g
					//   p
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					// 双旋
					//     g
					//   p
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		else  // parent == grandfather->_right
		{
			//     g
			//   u   p 
			//          c
			//
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//        g
				//           p
				//              c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//     g
					//   u   p 
					//     c
					//
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	subR->_left = parent;
	Node* parentParent = parent->_parent;
	parent->_parent = subR;
	if (subRL)
		subRL->_parent = parent;
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}
}
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	Node* parentParent = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}
		subL->_parent = parentParent;
	}
}

7.2.3红黑树的验证

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

void InOrder()
{
	_InOrder(_root);
	cout 
	if (root == nullptr)
		return;
	_InOrder(root-_left);
	cout _kv.first _right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
	if (root == nullptr)
	{
		//cout 
			cout 
		cout 
		++blacknum;
	}
	return Check(root-_left, blacknum, refVal)
		&& Check(root-_right, blacknum, refVal);
}
bool IsBalance()
{
	if (_root == nullptr)
		return true;
	if (_root->_col == RED)
		return false;
	//参考值
	int refVal = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refVal;
		}
		cur = cur->_left;
	}
	int blacknum = 0;
	return Check(_root, blacknum, refVal);
}

8.红黑树与AVL树的比较

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

9.map和set模拟实现

9.1改造红黑树

#pragma once
// set ->key
// map ->key/value
enum Colour
{
	RED,
	BLACK
};
template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};
template
struct __TreeIterator
{
	typedef RBTreeNode Node;
	typedef __TreeIterator Self;
	Node* _node;
	__TreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	Self& operator--();
	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			// 左子树 根 右子树
			// 右为空，找孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};
// set->RBTree _t;
// map->RBTree _t;
template
class RBTree
{
	typedef RBTreeNode Node;
public:
	typedef __TreeIterator iterator;
	typedef __TreeIterator const_iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}
	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
	//pair Insert(const T& data)
	pair Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) _right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
		// 新增节点给红色
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;
		if (kot(parent->_data) _right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				//     g
				//   p   u
				// c
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					// 继续往上更新处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						// 单旋
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// 双旋
						//     g
						//   p
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else  // parent == grandfather->_right
			{
				//     g
				//   u   p 
				//          c
				//
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(newnode, true);
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		subR->_left = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}
	void InOrder()
	{
		_InOrder(_root);
		cout 
		if (root == nullptr)
			return;
		_InOrder(root-_left);
		cout _kv.first _right);
	}
	// 根节点->当前节点这条路径的黑色节点的数量
	bool Check(Node* root, int blacknum, const int refVal)
	{
		if (root == nullptr)
		{
			//cout 
				cout 
			cout 
			++blacknum;
		}
		return Check(root-_left, blacknum, refVal)
			&& Check(root-_right, blacknum, refVal);
	}
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		//参考值
		int refVal = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refVal;
			}
			cur = cur->_left;
		}
		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}
	int Height()
	{
		return _Height(_root);
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	size_t Size()
	{
		return _Size(_root);
	}
	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;
		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first _right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}
private:
	Node* _root = nullptr;
};

9.2map模拟实现

底层红黑树，结合改造红黑树的代码

#pragma once
#include"RBTree.h"
namespace ljh
{
	template
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
		// 对类模板取内嵌类型，加typename告诉编译器这里是类型
		typedef typename RBTree::iterator iterator;
		typedef typename RBTree::const_iterator const_iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		V& operator[](const K& key)
		{
			pair ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
		pair insert(const pair& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree _t;
	};
}

9.3set的模拟实现

底层红黑树，结合改造红黑树的代码

#pragma once
#include"RBTree.h"
namespace ljh
{
	template
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree::const_iterator iterator;
		typedef typename RBTree::const_iterator const_iterator;
		iterator begin() const
		{
			return _t.begin();
		}
		iterator end() const
		{
			return _t.end();
		}
		pair insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree _t;
	};
}