用红黑树封装map、set

• 1. 红黑树
• • 1.1 模板参数的控制
  • • 1.1.1 Value
    • 1.1.2 KeyOfValue
  • 1.2 正向迭代器
  • • 1.2.1 构造函数
    • 1.2.2 begin()+end()
    • 1.2.3 operator++()
    • 1.2.4 operator--()
    • 1.2.5 operator*()
    • 1.2.6 operator->()
    • 1.2.7 operator==()
    • 1.2.8 operator!=()
    • 1.2.9 总代码
  • 1.3 反向迭代器
  • • 1.3.1 rbegin()+rend()
    • 1.3.2 总代码
  • 1.4 find()
  • 1.5 insert()
• 2. Map
• • 2.1 operator[]
• 3. typename作用
• 4. 完整代码
• • 4.1 Map.h
  • 4.2 Set.h
  • 4.3 RBTree.h

1. 红黑树

• set是K模型，map是KV模型，二者底层都是使用红黑树来实现的，所以我们可以将红黑树设置为模板，即：set、map复用同一个类模板的红黑树。

1.1 模板参数的控制

1.1.1 Value

• Value决定你是k模型的set、还是KV模型的map。

enum Color {  //枚举，一一列举出事物具有的所有可能 	Red,  //枚举常量，给枚举变量进行赋值 	Black, };  template//红黑树的节点 struct RBTreeNode { 	typedef RBTreeNode Node;  	//三叉链-》优点：便于查找孩子、父亲节点 	Node* _left;      //该节点的左孩子 	Node* _right;    //该节点的右孩子 	Node* _parent;  //该节点的父亲，便于向上更新 	T _data; 	Color _col;  	RBTreeNode(const T& data, Color col = Red)  //构造函数 		:_data(data) 		, _left(nullptr) 		, _right(nullptr) 		, _parent(nullptr) 		, _col(col)  //默认新插入节点的颜色为红色 	{ } };  

//Value决定你是k模型的set、还是KV模型的map template  class RBTree {   public: 	typedef RBTreeNode Node; }; 

template class set{   //K模型 public:            private:  //set中的key不允许被修改 		RBTree _t;  //红黑树对象 	}; } 

template class map {   //KV模型   public:  private:   //map中的key不允许被修改 		RBTree, MapKeyOfT> _t;  //红黑树对象 	};  }; 

1.1.2 KeyOfValue

• KeyOfT : 取出Value对象中的key。

// KeyOfT : 取出Value对象中的key template  class RBTree {  }; 

struct SetKeyOfT{    	const K& operator()(const K& key) 	{ 		return key;  //key 	} }; 

struct MapKeyOfT { 	const K& operator()(const pair& kv) 	{ 		return kv.first;  //pair中的key 	} }; 

1.2 正向迭代器

1.2.1 构造函数

💡RBTreeIterator(Node* node) ；

RBTreeIterator(Node* node) //构造函数，单参数构造函数支持隐式类型转化 		:_node(node) 	{ } 

• Tips : 单参数构造函数支持隐式类型转换 Node*->iterator 。

1.2.2 begin()+end()

💡iterator begin( ) ；

• 功能：返回红黑树中最左节点(左孩子必为空)的迭代器。
• Tips：set、map对象为非const对象，就调用begin()、end()。

iterator begin()  //红黑树最左节点 {  	Node* subLeft = _root;    	while (subLeft && subLeft->_left) 		subLeft = subLeft->_left;  	return iterator(subLeft); }	 

💡iterator end( ) ；

• 功能：返回最后一个元素的下一个的迭代器(空指针)。

iterator end()  //空指针 左闭右开[begin,end) { 	return iterator(nullptr); } 

1.2.3 operator++()

/*1.右不为空，下一个为该节点右子树的最左节点 ; 	* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/ Self& operator++()  //中序 左、根、右 { 	if (_node->_right)  //1 	{ 		Node* subLeft = _node->_right; 		while (subLeft->_left) 			subLeft = subLeft->_left;  		_node = subLeft; 	} 	else  //2 	{ 		Node* cur = _node; 		Node* parent = cur->_parent; 		while (parent && parent->_left != cur) 		{ 			cur = parent; 			parent = cur->_parent; 		} 		_node = parent; 	} 	return *this; } 

• 中序遍历，左、根、右。
  情况一：右不为空，下一个为该节点右子树的最左节点 ;
  情况二：右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找，直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左。

1.2.4 operator–()

/*1.左不为空，下一个为该节点左子树的最右节点 ; 	* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/ Self& operator--() //中序 左、根、右  --与++逻辑相反 { 	if (_node->_left)  //1 	{ 		Node* subRight = _node->_left; 		while (subRight->_right) 			subRight = subRight->_right;  		_node = subRight; 	} 	else  //2 	{ 		Node* cur = _node; 		Node* parent = cur->_parent; 		while (parent && parent->_right != cur) 		{ 			cur = parent; 			parent = cur->_parent; 		} 		_node = parent; 	} 	return *this; } 

1.2.5 operator*()

Ref operator*() { 	return _node->_data; } 

1.2.6 operator->()

Ptr operator->() //结构体指针，data为结构体 { 	return &_node->_data; } 

1.2.7 operator==()

bool operator==(const Self& rb) { 	return _node == rb._node; } 

1.2.8 operator!=()

bool operator!=(const Self& rb) { 	return _node != rb._node; } 

1.2.9 总代码

template  struct RBTreeIterator   //红黑树的正向迭代器 { 	typedef RBTreeNode Node; 	typedef RBTreeIterator Self;  	Node* _node;  	RBTreeIterator(Node* node) //构造函数，单参数构造函数支持隐式类型转化 		:_node(node) 	{ }  	Ref operator*() 	{ 		return _node->_data; 	}  	Ptr operator->() //结构体指针，data为结构体 	{ 		return &_node->_data; 	}  	/*1.右不为空，下一个为该节点右子树的最左节点 ; 	* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/ 	Self& operator++()  //中序 左、根、右 	{ 		if (_node->_right)  //1 		{ 			Node* subLeft = _node->_right; 			while (subLeft->_left) 				subLeft = subLeft->_left;  			_node = subLeft; 		} 		else  //2 		{ 			Node* cur = _node; 			Node* parent = cur->_parent; 			while (parent && parent->_left != cur) 			{ 				cur = parent; 				parent = cur->_parent; 			} 			_node = parent; 		} 		return *this; 	}  	/*1.左不为空，下一个为该节点左子树的最右节点 ; 	* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/ 	Self& operator--() //中序 左、根、右  --与++逻辑相反 	{ 		if (_node->_left)  //1 		{ 			Node* subRight = _node->_left; 			while (subRight->_right) 				subRight = subRight->_right;  			_node = subRight; 		} 		else  //2 		{ 			Node* cur = _node; 			Node* parent = cur->_parent; 			while (parent && parent->_right != cur) 			{ 				cur = parent; 				parent = cur->_parent; 			} 			_node = parent; 		} 		return *this; 	}  	bool operator!=(const Self& rb) 	{ 		return _node != rb._node; 	}  	bool operator==(const Self& rb) 	{ 		return _node == rb._node; 	} }; 

1.3 反向迭代器

1.3.1 rbegin()+rend()

💡reverse_iterator rbegin( ) ；

• 功能：返回红黑树中最右节点(右孩子必为空)的迭代器。

reverse_iterator rbegin()  //红黑树最右节点，因为此处反向迭代器*，是直接调用正向迭代器* [rbegin,erend) { 	Node* subRight = _root; 	while (subRight && subRight->_right) 		subRight = subRight->_right;  	return reverse_iterator(subRight); } 

💡reverse_iterator rend( ) ；

• 功能：返回第一个元素的前一个的迭代器(空指针)。

reverse_iterator rend()   { 	return reverse_iterator(nullptr); } 

1.3.2 总代码

template struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin { 	typedef ReverseIterator Self;   	iterator _it;   //适配器  	ReverseIterator(iterator it) 		:_it(it) 	{ }  	Ref operator*() 	{ 		return *_it; 	}  	Ptr operator->() 	{ 		return &(operator*());  // 	}  	Self& operator++() 	{ 		--_it; 		return *this; 	}  	Self& operator--() 	{ 		++_it; 		return *this; 	}  	bool operator==(const Self& rb) 	{ 		return _it == rb._it; 	}  	bool operator!=(const Self& rb) 	{ 		return _it != rb._it; 	} }; 

1.4 find()

💡iterator find(const K& key) ;

• 功能：查找。
• 若key在红黑树中，则返回树中与key值相等元素的迭代器，否则，就返回end( )。

iterator find(const K& key)  //查找  模板参数K的作用 { 	KeyOfT kot;  	Node* cur = _root; 	while (cur)  //先按照二叉搜索树的方式插入 	{ 		if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key 			cur = cur->_right; 		else if (kot(cur->_data) > key) 			cur = cur->_left; 		else 			return iterator(cur);  //找到了 	} 	return end();  //找不到 } 

1.5 insert()

💡pair insert(const T& data) ;

• 功能：向红黑树中插入data。

• insert返回值为pair,若key(set的key、map的pair的first)在树中存在，因为搜索树中不能出现重复的键值key，所以pair::first指向在树中与key值相等的迭代器，pair::second为false。若key在树中不存在，pair::first指向在树中新插入元素的迭代器，pair::second为true。insert相当于查找。

pair insert(const T& data)  //插入   {   //不能使用引用放回，因为返回值作用域为栈区，传值返回 	KeyOfT kot;  //仿函数类创建的对象，对象去调用operator()  	Node* parent = nullptr; 	Node* cur = _root; 	while (cur)  //先按照二叉搜索树的方式插入     {     	if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值     	{     		parent = cur;     		cur = cur->_right;     	}     	else if (kot(cur->_data) > kot(data))     	{     		parent = cur;     		cur = cur->_left;     	}     	else     	{     		return make_pair(iterator(cur), false);  //插入节点已存在，插入失败，返回在树中与该节点值相同的迭代器     	}     }      cur = new Node(data);  //注意 insert 		 	Node* newnode = cur;  //非空树，插入成功，因为要做旋转处理，会导致cur值发生改变，需提前将新节点的位置存储起来  	if (parent == nullptr) //空树 	{ 		_root = cur; 		_root->_col = Black;  //跟节点为黑 		return make_pair(iterator(_root), true);  //空树，插入成功，返回新插入节点在树中的迭代器 	}  	if (kot(parent->_data) < kot(cur->_data)) 	{ 		parent->_right = cur; 	} 	else 	{ 		parent->_left = cur; 	} 	cur->_parent = parent;  //记录当前节点的父亲  	//更新颜色 	//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色 	while (parent && parent->_col == Red) 	{ //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点 		Node* grandfather = parent->_parent; 		if (parent == grandfather->_left)  //旋转需要确定方向 		{ 			Node* uncle = grandfather->_right; 			if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边) 			{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红 				parent->_col = uncle->_col = Black; //p、u变为黑，g变为红 				grandfather->_col = Red;  				//g可能为根节点(更新结束)，也可能为子树(继续向上更新) 				cur = grandfather; 				parent = cur->_parent; 			} 			else  //情况二：叔叔不存在 或者 叔叔存在且为黑 			{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红 				if (parent->_left == cur)  //左左——右单旋 				{ 					RotateR(grandfather); 					parent->_col = Black; //p变为黑，g变为红 					grandfather->_col = Red; 				} 				else    //左右——左右单旋  				{ 					RotateL(parent); 					RotateR(grandfather); 					cur->_col = Black;  //c变黑，g变红 					grandfather->_col = Red; 				} 				break;  //更新结束：3.旋转+颜色处理后就是红黑树了 			} 		} 		else 		{ 			Node* uncle = grandfather->_left; 			if (uncle && uncle->_col == Red) 			{ 				parent->_col = uncle->_col = Black; 				grandfather->_col = Red;  				cur = grandfather; 				parent = cur->_parent; 			} 			else 			{ 				if (parent->_right == cur)  //右右——左单旋 				{ 					RotateL(grandfather); 					parent->_col = Black; 					grandfather->_col = Red; 				} 				else   //右左——右左单旋 				{ 					RotateR(parent); 					RotateL(grandfather); 					cur->_col = Black; 					grandfather->_col = Red; 				} 				break; 			} 		} 	} 	_root->_col = Black;  //g为根，颜色变为黑，更新结束 	return make_pair(iterator(newnode), true);  //情况一，插入节点的父亲为黑，插入结束 } 

2. Map

2.1 operator[]

💡V& operator[ ](const K& key) ;

• 功能：访问与key相对应的value值。即可读又可写。
• 原理：operator[ ]底层是通过调用insert( )将键值队插入到map中。如果key存在，插入失败，insert返回与map中key值相同元素的迭代器。如果key不存在，插入成功，insert返回在map中新插入元素的迭代器。operator[ ]最后返回与key值相对应的value值的引用。
• operator[ ] 具有插入、查找、插入+修改、查找+修改功能。

V& operator[](const K& key) //功能:查找+修改、插入+修改 { 	pair ret = _t.insert(make_pair(key, V())); 	return ret.first->second; } 

3. typename作用

1. 使用域作用限定符(: : )的两种情况：静态变量、类中typedef的类型。
2. 使用typename表示: :后面为类型，不是静态成员

//使用::两种情况：静态变量、类中typedef的类型  typename表示::前面为类型，不是静态成员 typedef typename RBTree, MapKeyOfT>::iterator iterator;  

4. 完整代码

4.1 Map.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1  #include"RBTree.h" #include  namespace zzx { 	template 	class map {   //KV模型   	public:  		struct MapKeyOfT { 			const K& operator()(const pair& kv) 			{ 				return kv.first;  //pair中的key 			} 		};  		//使用::两种情况：静态变量、类中typedef的类型  typename表示::前面为类型，不是静态成员 		typedef typename RBTree, MapKeyOfT>::iterator iterator;   //正向迭代器 		typedef typename RBTree, MapKeyOfT>::reverse_iterator reverse_iterator;  //反向迭代器  		iterator begin()   		{ 			return _t.begin(); 		}  		iterator end()   		{ 			return _t.end(); 		}  		reverse_iterator rbegin() 		{ 			return _t.rbegin(); 		}  		reverse_iterator rend() 		{ 			return _t.rend(); 		}  		iterator find(const K& key)  //查找 		{ 			return _t.find(key); 		}  		pair insert(pair& kv)  //插入 		{ 			return _t.insert(kv); 		}  		V& operator[](const K& key) //功能:查找+修改、插入+修改 		{ 			pair ret = _t.insert(make_pair(key, V())); 			return ret.first->second; 		}  	private:   //map中的key不允许被修改 		RBTree, MapKeyOfT> _t;  //红黑树对象 	};  }; 

4.2 Set.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1  #include"RBTree.h"  namespace zzx{ 	template 	class set{   //K模型 	public:   //仿函数类:比较对象大小，获取对象中的元素—自己手动传递比较逻辑 		struct SetKeyOfT{    			const K& operator()(const K& key) 			{ 				return key;  //key 			} 		};  		//使用::两种情况：静态变量、类中typedef的类型  typename表示::后面为类型，不是静态成员 		typedef typename RBTree::iterator iterator;   //正向迭代器 		typedef typename RBTree::reverse_iterator reverse_iterator;  //反向迭代器  		iterator begin() 		{ 			return _t.begin(); 		}  		iterator end() 		{ 			return _t.end(); 		}  		reverse_iterator rbegin() 		{ 			return _t.rbegin(); 		}  		reverse_iterator rend() 		{ 			return _t.rend(); 		}  		iterator find(const K& key)  //查找 		{ 			return _t.find(key); 		}  		pair insert(const K& key)  //插入 		{ 			return _t.insert(key); 		}  	private:  //set中的key不允许被修改 		RBTree _t;  //红黑树对象 	}; } 

4.3 RBTree.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include  using namespace std;  enum Color {  //枚举，一一列举出事物具有的所有可能 	Red,  //枚举常量，给枚举变量进行赋值 	Black, };  template//红黑树的节点 struct RBTreeNode { 	typedef RBTreeNode Node;  	//三叉链-》优点：便于查找孩子、父亲节点 	Node* _left;      //该节点的左孩子 	Node* _right;    //该节点的右孩子 	Node* _parent;  //该节点的父亲，便于向上更新 	T _data; 	Color _col;  	RBTreeNode(const T& data, Color col = Red)  //构造函数 		:_data(data) 		, _left(nullptr) 		, _right(nullptr) 		, _parent(nullptr) 		, _col(col)  //默认新插入节点的颜色为红色 	{ } };  template  struct RBTreeIterator   //红黑树的正向迭代器 { 	typedef RBTreeNode Node; 	typedef RBTreeIterator Self;  	Node* _node;  	RBTreeIterator(Node* node) //构造函数，单参数构造函数支持隐式类型转化 		:_node(node) 	{ }  	Ref operator*() 	{ 		return _node->_data; 	}  	Ptr operator->() //结构体指针，data为结构体 	{ 		return &_node->_data; 	}  	/*1.右不为空，下一个为该节点右子树的最左节点 ; 	* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/ 	Self& operator++()  //中序 左、根、右 	{ 		if (_node->_right)  //1 		{ 			Node* subLeft = _node->_right; 			while (subLeft->_left) 				subLeft = subLeft->_left;  			_node = subLeft; 		} 		else  //2 		{ 			Node* cur = _node; 			Node* parent = cur->_parent; 			while (parent && parent->_left != cur) 			{ 				cur = parent; 				parent = cur->_parent; 			} 			_node = parent; 		} 		return *this; 	}  	/*1.左不为空，下一个为该节点左子树的最右节点 ; 	* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找， 	* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/ 	Self& operator--() //中序 左、根、右  --与++逻辑相反 	{ 		if (_node->_left)  //1 		{ 			Node* subRight = _node->_left; 			while (subRight->_right) 				subRight = subRight->_right;  			_node = subRight; 		} 		else  //2 		{ 			Node* cur = _node; 			Node* parent = cur->_parent; 			while (parent && parent->_right != cur) 			{ 				cur = parent; 				parent = cur->_parent; 			} 			_node = parent; 		} 		return *this; 	}  	bool operator!=(const Self& rb) 	{ 		return _node != rb._node; 	}  	bool operator==(const Self& rb) 	{ 		return _node == rb._node; 	} };  template struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin { 	typedef ReverseIterator Self;   	iterator _it;   //适配器  	ReverseIterator(iterator it) 		:_it(it) 	{ }  	Ref operator*() 	{ 		return *_it; 	}  	Ptr operator->() 	{ 		return &(operator*());  // 	}  	Self& operator++() 	{ 		--_it; 		return *this; 	}  	Self& operator--() 	{ 		++_it; 		return *this; 	}  	bool operator==(const Self& rb) 	{ 		return _it == rb._it; 	}  	bool operator!=(const Self& rb) 	{ 		return _it != rb._it; 	} };  //红黑树的模板参数:T决定你是k模型的set、还是KV模型的map ; KeyOfT:取出T对象中的key ; pair比较:先比较first,在比较second template  class RBTree {   public: 	typedef RBTreeNode Node;  	//正向迭代器 	typedef RBTreeIterator iterator;  //普通迭代器 	typedef RBTreeIterator const_iterator; //const迭代器  	//反向迭代器 	typedef ReverseIterator reverse_iterator; 	typedef ReverseIterator const_reverse_iterator;  	iterator begin()  //红黑树最左节点 	{  		Node* subLeft = _root;    		while (subLeft && subLeft->_left) 			subLeft = subLeft->_left;  		return iterator(subLeft); 	}  	iterator end()  //空指针 左闭右开[begin,end) 	{ 		return iterator(nullptr); 	}  	const_iterator begin()const   	{ 		Node* subLeft = _root; 		while (subLeft && subLeft->_left) 			subLeft = subLeft->_left;  		return const_iterator(subLeft); 	}  	const_iterator end()const 	{ 		return const_iterator(nullptr); 	}  	reverse_iterator rbegin()  //红黑树最右节点，因为此处反向迭代器*，是直接调用正向迭代器* [rbegin,erend) 	{ 		Node* subRight = _root; 		while (subRight && subRight->_right) 			subRight = subRight->_right;  		return reverse_iterator(subRight); 	}  	reverse_iterator rend()   	{ 		return reverse_iterator(nullptr); 	}  	const_reverse_iterator rbegin()const 	{ 		Node* subRight = _root; 		while (subRight && subRight->_right) 			subRight = subRight->_right;  		return const_reverse_iterator(subRight); 	}  	const_reverse_iterator rend()const 	{ 		return const_reverse_iterator(nullptr); 	}  	iterator find(const K& key)  //查找  模板参数K的作用 	{ 		KeyOfT kot;  		Node* cur = _root; 		while (cur)  //先按照二叉搜索树的方式插入 		{ 			if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key 				cur = cur->_right; 			else if (kot(cur->_data) > key) 				cur = cur->_left; 			else 				return iterator(cur);  //找到了 		}  		return end();  //找不到 	}  	void RotateL(Node* parent)  //右右—左单旋 	{ 		Node* subR = parent->_right; 		Node* subRL = subR->_left;  		Node* pphead = parent->_parent;  		parent->_right = subRL; 		if (subRL) 			subRL->_parent = parent; 		subR->_left = parent; 		parent->_parent = subR;   		if (parent == _root) 		{ 			_root = subR; 			subR->_parent = nullptr; 		} 		else 		{ 			if (pphead->_left == parent) 				pphead->_left = subR; 			else 				pphead->_right = subR;  			subR->_parent = pphead; 		} 	}  	void RotateR(Node* parent)  //左左—右单旋 	{ 		Node* subL = parent->_left; 		Node* subLR = subL->_right;  		Node* pphead = parent->_parent;  		parent->_left = subLR; 		if (subLR) 			subLR->_parent = parent; 		subL->_right = parent; 		parent->_parent = subL;  		if (parent == _root) 		{ 			_root = subL; 			subL->_parent = nullptr; 		} 		else 		{ 			if (pphead->_left == parent) 				pphead->_left = subL; 			else 				pphead->_right = subL;  			subL->_parent = pphead; 		} 	}  	void RotateRL(Node* parent)  //右左—先右旋再左旋 	{ 		Node* subR = parent->_right; 		Node* subRL = subR->_left;  		RotateR(subR); 		RotateL(parent); 	}  	void RotateLR(Node* parent)  //左右—先左旋再右旋 	{ 		Node* subL = parent->_left; 		Node* subLR = subL->_right;  		RotateL(subL); 		RotateR(parent); 	}  	pair insert(const T& data)  //插入   	{   //不能使用引用放回，因为返回值作用域为栈区，传值返回 		KeyOfT kot;  //仿函数类创建的对象，对象去调用operator()  		Node* parent = nullptr; 		Node* cur = _root; 		while (cur)  //先按照二叉搜索树的方式插入 		{ 			if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值 			{ 				parent = cur; 				cur = cur->_right; 			} 			else if (kot(cur->_data) > kot(data)) 			{ 				parent = cur; 				cur = cur->_left; 			} 			else 			{ 				return make_pair(iterator(cur), false);  //插入节点已存在，插入失败，返回在树中与该节点值相同的迭代器 			} 		}  		cur = new Node(data);  //注意 insert 		 		Node* newnode = cur;  //非空树，插入成功，因为要做旋转处理，会导致cur值发生改变，需提前将新节点的位置存储起来  		if (parent == nullptr) //空树 		{ 			_root = cur; 			_root->_col = Black;  //跟节点为黑 			return make_pair(iterator(_root), true);  //空树，插入成功，返回新插入节点在树中的迭代器 		}  		if (kot(parent->_data) < kot(cur->_data)) 		{ 			parent->_right = cur; 		} 		else 		{ 			parent->_left = cur; 		} 		cur->_parent = parent;  //记录当前节点的父亲  		//更新颜色 		//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色 		while (parent && parent->_col == Red) 		{ //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点 			Node* grandfather = parent->_parent; 			if (parent == grandfather->_left)  //旋转需要确定方向 			{ 				Node* uncle = grandfather->_right; 				if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边) 				{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红 					parent->_col = uncle->_col = Black; //p、u变为黑，g变为红 					grandfather->_col = Red;  					//g可能为根节点(更新结束)，也可能为子树(继续向上更新) 					cur = grandfather; 					parent = cur->_parent; 				} 				else  //情况二：叔叔不存在 或者 叔叔存在且为黑 				{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红 					if (parent->_left == cur)  //左左——右单旋 					{ 						RotateR(grandfather); 						parent->_col = Black; //p变为黑，g变为红 						grandfather->_col = Red; 					} 					else    //左右——左右单旋  					{ 						RotateL(parent); 						RotateR(grandfather); 						cur->_col = Black;  //c变黑，g变红 						grandfather->_col = Red; 					} 					break;  //更新结束：3.旋转+颜色处理后就是红黑树了 				} 			} 			else 			{ 				Node* uncle = grandfather->_left; 				if (uncle && uncle->_col == Red) 				{ 					parent->_col = uncle->_col = Black; 					grandfather->_col = Red;  					cur = grandfather; 					parent = cur->_parent; 				} 				else 				{ 					if (parent->_right == cur)  //右右——左单旋 					{ 						RotateL(grandfather); 						parent->_col = Black; 						grandfather->_col = Red; 					} 					else   //右左——右左单旋 					{ 						RotateR(parent); 						RotateL(grandfather); 						cur->_col = Black; 						grandfather->_col = Red; 					} 					break; 				} 			} 		} 		_root->_col = Black;  //g为根，颜色变为黑，更新结束 		return make_pair(iterator(newnode), true);  //情况一，插入节点的父亲为黑，插入结束 	}  private: 	Node* _root = nullptr; };