个人主页：仍有未知等待探索-CSDN博客

专题分栏：C++

一、简介

map和set都是关联性容器，底层都是用红黑树写的。

特点：存的Key值都是唯一的，不重复。

map存的是键值对（Key—Value）。

set存的是键值（Key）。

二、map/set的模拟实现

map.h

#pragma once   #include  #include "RBTree.h" using namespace std;  template class map { 	struct MapKeyOfT 	{ 		const Key& operator()(const pair& e) 		{ 			return e.first; 		} 	};  public: 	typedef pair PKV; 	typedef _RBTree_iterator iterator;  	iterator begin() 	{ 		return _t.begin(); 	} 	iterator end() 	{ 		return _t.end(); 	} 	bool insert(const pair& e) 	{ 		return _t.insert(e); 	} 	void inorder() 	{ 		_t.inorder(); 	} private: 	RBTree, MapKeyOfT> _t; }; 

set.h

#pragma once   #include "RBTree.h"  template class set { 	struct SetKeyOfT 	{ 		const Key& operator()(const Key& e) 		{ 			return e; 		} 	}; public : 	typedef _RBTree_iterator iterator;  	iterator begin() 	{ 		return _t.begin(); 	} 	iterator end() 	{ 		return _t.end(); 	} 	bool insert(const Key& e) 	{ 		return _t.insert(e); 	} 	void inorder() 	{ 		_t.inorder(); 	} private: 	RBTree _t; };

RBTree.h

#pragma once  #include using namespace std;   enum color { 	Red, 	Black }; template  struct RBTreeNode { 	RBTreeNode(const ValueTpye& e = ValueTpye()) 		:_left(nullptr) 		,_right(nullptr) 		,_parent(nullptr) 		,_col(Red) 		,_val(e) 	{}  	struct RBTreeNode* _left; 	struct RBTreeNode* _right; 	struct RBTreeNode* _parent; 	int _col; 	ValueTpye _val; };  template class _RBTree_iterator { 	typedef RBTreeNode node; 	typedef _RBTree_iterator iterator; public: 	_RBTree_iterator(node* e) 		:_node(e) 	{} 	Ptr operator->() 	{ 		return &_node->_val; 	} 	Ref operator*() 	{ 		return _node->_val; 	} 	bool operator!=(iterator it) 	{ 		return _node != it._node; 	} 	iterator& operator++() 	{ 		if (_node->_right) 		{ 			node* left = _node->_right; 			while (left->_left) 			{ 				left = left->_left; 			} 			_node = left; 		} 		else 		{ 			node* cur = _node; 			node* p = cur->_parent; 			while (p && cur == p->_right) 			{ 				cur = p; 				p = p->_parent; 			} 			_node = p; 		} 		return *this; 	} private: 	node* _node; };  template  class RBTree { public: 	typedef RBTreeNode node; 	typedef _RBTree_iterator iterator; 	KeyOfT kot;  	RBTree() 		:_root(nullptr) 	{}  	iterator begin() 	{ 		node* cur = _root; 		while (cur && cur->_left) 		{ 			cur = cur->_left; 		} 		return iterator(cur); 	} 	iterator end() 	{ 		return iterator(nullptr); 	}  	node* find(const Key& e) 	{ 		node* cur = _root;  		while (cur) 		{ 			if (kot(cur->_val).first > e) 			{ 				cur = cur->_left; 			} 			else if (kot(cur->_val).first < e) 			{ 				cur = cur->_right; 			} 			else 			{ 				return cur; 			} 		} 		return nullptr; 	}  	bool insert(const ValueType& e) 	{ 		// 根据二叉搜索树插入的方式进行插入 		node* cur = _root; 		node* parent = cur;  		while (cur) 		{ 			parent = cur; 			if (kot(cur->_val) > kot(e)) 			{ 				cur = cur->_left; 			} 			else if (kot(cur->_val) < kot(e)) 			{ 				cur = cur->_right; 			} 			else 			{ 				return false; 			} 		} 		cur = new node(e); 		if (parent == nullptr) 		{ 			_root = cur; 		} 		else 		{ 			if (kot(parent->_val) > kot(cur->_val)) 			{ 				parent->_left = cur; 			} 			else 			{ 				parent->_right = cur; 			} 			cur->_parent = parent; 		}  		// 更新，对于不同的情况，进行不同的调整 		// parent 为黑、不存在，结束 		node* p = parent; 		while (p && p->_col == Red) 		{ 			node* g = p->_parent;  			if (g->_left == p) 			{ 				node* u = g->_right; 				// 叔叔存在且为红 				if (u && u->_col == Red) 				{ 					p->_col = u->_col = Black; 					g->_col = Red;  					// 继续往上处理 					cur = g; 					p = cur->_parent; 				} 				// 叔叔不存在且为黑 				else  				{ 					//    g 					//  p   u 					// c 					if (cur == p->_left) 					{ 						// 右单旋 						RotateR(g);  						// 变色 						g->_col = Red; 						p->_col = Black;  					} 					//    g 					//  p   u 					//    c 					else  					{ 						// 左右双旋 						RotateL(p); 						RotateR(g);  						// 变色 						cur->_col = Black; 						g->_col = Red; 					} 					// 叔叔不存在或者存在且为黑调整完，就不需要继续进行调整了 					break; 				} 			} 			else 			{ 				node* u = g->_left;  				if (u && u->_col == Red) 				{ 					p->_col = u->_col = Black; 					g->_col = Red;  					// 继续往上处理 					cur = g; 					p = cur->_parent; 				} 				else  				{ 					//    g 					//  u   p 					//        c 					if (cur == p->_right) 					{ 						// 左单旋 						RotateL(g);  						// 变色 						g->_col = Red; 						p->_col = Black;  					} 					//    g 					//  u   p 					//    c 					else  					{ 						// 左右双旋 						RotateR(p); 						RotateL(g);  						// 变色 						cur->_col = Black; 						g->_col = Red; 					} 					// 叔叔不存在或者存在且为黑调整完，就不需要继续进行调整了 					break; 				} 			}  		}  		_root->_col = Black;  		return true; 	}   	void inorder() 	{ 		_inorder(_root); 	} private: 	void _inorder(node* root) 	{ 		if (root == nullptr) return;  		_inorder(root->_left); 		cout << kot(root->_val) << " "; 		_inorder(root->_right); 	} 	void RotateR(node* parent) 	{ 		node* subl = parent->_left; 		node* sublr = subl->_right;  		node* grandfather = parent->_parent;  		parent->_left = sublr; 		if (sublr) 		{ 			sublr->_parent = parent; 		}  		subl->_right = parent; 		parent->_parent = subl;  		subl ->_parent = grandfather;  		if (_root == parent) 		{ 			if (grandfather->_left == parent) 			{ 				grandfather->_left = subl; 			} 			else 			{ 				grandfather->_right = subl; 			} 		} 		else 		{ 			_root = subl; 		} 	} 	void RotateL(node* parent) 	{ 		node* subr = parent->_right; 		node* subrl = subr->_left;  		node* grandfather = parent->_parent;  		parent->_right = subrl; 		if (subrl) 		{ 			subrl->_parent = parent; 		}  		subr->_left = parent; 		parent->_parent = subr;  		subr ->_parent = grandfather;  		if (_root != parent) 		{ 			if (grandfather->_left == parent) 			{ 				grandfather->_left = subr; 			} 			else 			{ 				grandfather->_right = subr; 			} 		} 		else 		{ 			_root = subr; 		} 	}  private: 	node* _root; };

main.cpp（测试）

#define _CRT_SECURE_NO_WARNINGS 1  #include "map.h" #include "set.h" //#include