STL 改造红黑树 模拟封装set和map

改造红黑树

在初次看STL中实现红黑树的源码时有些不理解,然后自己尝试对set以RBTree<K,K>的方式封装红黑树的迭代器;实现过程发现,这样封装复用程度特别低,也特别冗余,因此才能领悟到STL源码实现红黑树复用时的精髓.下文将模拟STL的实现方式改造红黑树和封装map和set.

参考的STL版本为SGI30

适配STL迭代器的红黑树

红黑树数据操作的代码实现是旧版本的,新版本在上一篇博客中有详细分析.

本篇主要特点在迭代器适配上

基本结构

#pragma once

#include<assert.h>
#include<iostream>
using std::cout;
using std::endl;
using std::cin;
using std::pair;
using std::make_pair;
using std::string;


namespace test
{
	enum Colour { RED, BLACK };
	template<class T> struct RBTreeNode;
	template<class T, class Ref, typename Ptr> struct __RBTree_iterator;
	template<class K, class T, class keyOfT> class RBTree;
}

RBTreeNode

	template<class T> // T为key或pair,T是key或者key-value类型
	struct RBTreeNode
	{
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		T _data; //data是key或pair
		Colour _col;

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

__RBTree_iterator

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

		//首先,<class T, class Ref, class Ptr>这种写法能够提高复用性和灵活性(实现不同类型的迭代器)等,,库里迭代器都这么写
		//其次,模板参数中,T用于获取类型,Ref用于返回引用,Ptr用于返回指针

		using Self           = __RBTree_iterator<T,Ref,Ptr>;            //自己--实例化出下面两种迭代器
		using iterator       = __RBTree_iterator<T,T&,T*>;              //普通迭代器
		using const_iterator = __RBTree_iterator<T,const T&,const T*>;  //const迭代器
		__RBTree_iterator(const iterator& it) 
			:_node(it._node)
		{}
		//这个构造函数的作用,
	    //a.当迭代器被实例化成iterator时,他就是拷贝构造函数.      __RBTree_iterator<T,T&,T*>
		//b.当迭代器被实例化成const_iterator时,他是支持隐式类型转换的带参构造函数. __RBTree_iterator<T,const T&,const T*> 

		//这样实现的目的
	    // 能够复用普通迭代器,可以通过类型转换后直接实现出const迭代器


		//Ref为 T& 或 const T&, Ptr为 T* 或 const T*
		//typedef __RBTree_iterator<T, Ref, Ptr> Self;

		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(const Self& x)
		{
			return _node != x._node;
		}
    //前置++
    Self& operator++() {
        //此版本实现迭代器不需要判空,为空说明遍历结束,要么是用户错误使用
        Node* cur = _node;
        //1. 有右子树
        if (cur->_right) {
            //找右子树的最小结点
            Node* rightMin = cur->_right;
            while (rightMin->_left) {
                rightMin = rightMin->_left;
            }
            _node = rightMin;
        }
        //2. 没有右子树
        else {
            ////1.没有父亲,说明是根
            //Node* parent = cur->_parent;
            //if (parent == nullptr) {
            //    _node == nullptr;
            //}
            ////2.且我是父的左子树,说明父亲是下一个正序值
            //else if (parent->_left == cur) {
            //    _node = parent;
            //}
            ////3.或我是父亲的右子树,说明走完了当前最小分支祖先这棵树.迭代往上
            //else if (parent->_right == cur) {
            //    while (parent && cur != parent->_left) {
            //        cur = parent;
            //        parent = parent->_parent;
            //    }
            //    _node = parent;
            //}
            //else {
            //    asssert(false);
            //}

            //上面3种情况可以合并成一种情况:找最近的不是右孩子的祖父
            Node* parent = cur->_parent;
            while (parent && cur != parent->_left) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    //后置++
    Self operator++(int) {
        Self tmp(_node);
        operator++();
        return tmp;
    }


    Self& operator--() {
        //将++反过来就是--
        Node* cur = _node;
        //左子树存在,就找最大
        if (cur->_left) {
            Node* leftMax = cur->_left;
            while (leftMax->_right) {
                leftMax = leftMax->_right;
            }
            _node = leftMax;
        }
        //2. 没有左子树
        else {
            Node* parent = cur->_parent;
            while (parent && cur != parent->_right) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self operator--(int) {
        Self tmp(_node);
        operator--();
        return tmp;
    }
	};

RBTree

	//参数K用在find,erase等,虽然K也可以被T取代了,但没必要,K更快
	template<class K, class T, class keyOfT> //库中还有1个compare,先不写了
	class RBTree
	{
	public:
		typedef RBTreeNode<T> node; //T是key或pair
	public:
		typedef __RBTree_iterator<T, T&, T*> iterator;
		typedef __RBTree_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			node* cur = _root;
			while (cur && cur->_left)//不能走到空
			{
				cur = cur->_left;
			}
			return iterator(cur);//返回中序的第一个结点,最左结点
		}

		iterator end() //end是最一个位置的下一个
		{
			return iterator(nullptr);//暂时可以这么写
		}

		const_iterator begin()const
		{
			node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return iterator(cur);
		}

		const_iterator end() const
		{
			return iterator(nullptr);
		}

	private:
		node* _root = nullptr;
	public:
		node* find(const K& key)
		{
			keyOfT kot;//kot是个仿函数,根据不同参数返回不同的参数对象
			node* cur = _root;
			while (cur)
			{
				if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					cur = cur->_left;
				}
				else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					cur = cur->_right;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		pair<iterator, bool> insert(const T& data)
		{
			if (!_root)
			{
				_root = new node(data);
				_root->_col = BLACK;
				return std::make_pair(iterator(_root), true);
			}
			
			keyOfT kot;

			node* cur = _root;
			node* parent = nullptr;
			while (cur)
			{
				if (kot(cur->_data) < kot(data)  ) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return std::make_pair(iterator(cur), false);
				}
			}
			cur = new node(data);
			if ( kot(parent->_data) < kot(data)) // --------------------------------------------
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//调整/旋转
			node* newnode = cur;//调整过程cur会发生变化,将cur结点记住 -- 记住原来key的位置
			while (parent && parent->_col == RED)
			{
				node* g = parent->_parent;
				if (parent == g->_right)
				{
					node* u = g->_left;
					if (u && u->_col == RED)
					{
						g->_col = RED;
						parent->_col = BLACK;
						u->_col = BLACK;
						cur = g;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_right)
						{
							RotateL(g);
							parent->_col = BLACK;
							g->_col = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(g);
							g->_col = RED;
							cur->_col = BLACK;
						}
						break;
					}

				}
				else
				{
					node* u = g->_right;
					if (u && u->_col == RED)
					{
						g->_col = RED;
						parent->_col = BLACK;
						u->_col = BLACK;
						cur = g;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							RotateR(g);
							parent->_col = BLACK;
							g->_col = RED;
						}
						else
						{
							RotateL(parent);
							RotateR(g);
							g->_col = RED;
							cur->_col = BLACK;
						}
						break;
					}
				}
			}
			_root->_col = BLACK;
			return std::make_pair(iterator(newnode), true);
		}
	public:
		void InOrderTraversal()
		{
			_InOrderTraversal(_root);
		}

		bool isBalanceTree()
		{
			//需要判断3个规则
			//1.根为黑
			if (_root && _root->_col == RED)
			{
				cout << "错误:根是红色" << endl;
				return false;
			}

			//2.不能有连续得红
			//3.黑同
			int benchmark = 0;
			node* cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
				{
					++benchmark;
				}
				cur = cur->_left;
			}
			return _check(_root, 0, benchmark);
		}

		int Height()
		{
			return _Height(_root);
		}
		~RBTree()
		{
			Destroy(_root);
		}

	private:
		void Destroy(node*& root)
		{
			if (!root)
			{
				return;
			}
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

		bool _check(node* root, int blackNum, int benchmark)
		{
			keyOfT kot;
			if (!root) //
			{
				if (blackNum != benchmark)
				{
					cout << "错误:存在不同路径的黑色结点数量不相同" << endl;
					return false;
				}
				return true;
			}

			if (root->_col == BLACK)
			{
				++blackNum;
			}

			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << kot(root->_data) << " 错误,与父节点同时为红色"; // --------------------------------------------
				return false;
			}

			return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
		}

		int _Height(node* root)
		{
			if (!root)
			{
				return 0;
			}
			int leftH = _Height(root->_left);
			int rightH = _Height(root->_right);

			return leftH > rightH ? leftH + 1 : rightH + 1;
		}

		void _InOrderTraversal(node* root)
		{
			keyOfT kot;
			if (root == nullptr)
			{
				return;
			}
			_InOrderTraversal(root->_left);
			cout << kot(root->_data) << " "; // --------------------------------------------
			_InOrderTraversal(root->_right);
		}

		void RotateL(node* parent)
		{
			node* subR = parent->_right;
			node* subRL = subR->_left;

			parent->_right = subRL;
			if (subRL)
			{
				subRL->_parent = parent;
			}

			node* pparent = parent->_parent;

			subR->_left = parent;
			parent->_parent = subR;

			if (!pparent)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
				{
					pparent->_left = subR;
				}
				else
				{
					pparent->_right = subR;
				}
				subR->_parent = pparent;
			}
		}

		void RotateR(node* parent)
		{
			node* subL = parent->_left;
			node* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR)
			{
				subLR->_parent = parent;
			}

			node* pparent = parent->_parent;

			subL->_right = parent;
			parent->_parent = subL;


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

完整代码

#pragma once

#include<assert.h>
#include<iostream>
using std::cout;
using std::endl;
using std::cin;
using std::pair;
using std::make_pair;
using std::string;


namespace test
{

	//与库中的RBT差异
	/**
	 *
	 * 库中还有结点数量 count
	 *
	 * 库中RBT是带头结点哨兵卫的,头结点的左是中序第一个(最小结点),右节点是中序的最后一个(最大结点),
	 * 哨兵卫的parent指向根节点,根节点的parent指向哨兵卫
	 *
	 * 库中的begin直接取head的left -- 函数:leftmost() //最左结点
	 * 库中的end 是head的right -- 不是rightmost,rightmost是最右结点,end是最右结点的下一个
	 * 库中的end 需要判断一下,防止只有左子树的歪脖子树时,end == head->right,死循环
	 *
	 * 和库的区别就是end,库的end能走回到head,我的不能,只能走到空就没了d
	 *
	 */


	enum Colour { RED, BLACK };

	template<class T> //T是什么,为什么只传T? T为key或pair,T是key或者key-value类型
	struct RBTreeNode
	{
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		T _data; //data是key或pair
		Colour _col;

		RBTreeNode(const T& data)
			: _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _col(RED)
		{}
	};
	//const_iterator<T,const T&,const T*>
	//iterator<T, T&, T*>

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

		//首先,<class T, class Ref, class Ptr>这种写法能够提高复用性和灵活性(实现不同类型的迭代器)等,,库里迭代器都这么写
		//其次,模板参数中,T用于获取类型,Ref用于返回引用,Ptr用于返回指针

		using Self           = __RBTree_iterator<T,Ref,Ptr>;            //自己--实例化出下面两种迭代器
		using iterator       = __RBTree_iterator<T,T&,T*>;              //普通迭代器
		using const_iterator = __RBTree_iterator<T,const T&,const T*>;  //const迭代器
		__RBTree_iterator(const iterator& it) 
			:_node(it._node)
		{}
		//这个构造函数的作用,
	    //a.当迭代器被实例化成iterator时,他就是拷贝构造函数.      __RBTree_iterator<T,T&,T*>
		//b.当迭代器被实例化成const_iterator时,他是支持隐式类型转换的带参构造函数. __RBTree_iterator<T,const T&,const T*> 

		//这样实现的目的
	    // 能够复用普通迭代器,可以通过类型转换后直接实现出const迭代器


		//Ref为 T& 或 const T&, Ptr为 T* 或 const T*
		//typedef __RBTree_iterator<T, Ref, Ptr> Self;

		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(const Self& x)
		{
			return _node != x._node;
		}
    //前置++
    Self& operator++() {
        //此版本实现迭代器不需要判空,为空说明遍历结束,要么是用户错误使用
        Node* cur = _node;
        //1. 有右子树
        if (cur->_right) {
            //找右子树的最小结点
            Node* rightMin = cur->_right;
            while (rightMin->_left) {
                rightMin = rightMin->_left;
            }
            _node = rightMin;
        }
        //2. 没有右子树
        else {
            ////1.没有父亲,说明是根
            //Node* parent = cur->_parent;
            //if (parent == nullptr) {
            //    _node == nullptr;
            //}
            ////2.且我是父的左子树,说明父亲是下一个正序值
            //else if (parent->_left == cur) {
            //    _node = parent;
            //}
            ////3.或我是父亲的右子树,说明走完了当前最小分支祖先这棵树.迭代往上
            //else if (parent->_right == cur) {
            //    while (parent && cur != parent->_left) {
            //        cur = parent;
            //        parent = parent->_parent;
            //    }
            //    _node = parent;
            //}
            //else {
            //    asssert(false);
            //}

            //上面3种情况可以合并成一种情况:找最近的不是右孩子的祖父
            Node* parent = cur->_parent;
            while (parent && cur != parent->_left) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    //后置++
    Self operator++(int) {
        Self tmp(_node);
        operator++();
        return tmp;
    }


    Self& operator--() {
        //将++反过来就是--
        Node* cur = _node;
        //左子树存在,就找最大
        if (cur->_left) {
            Node* leftMax = cur->_left;
            while (leftMax->_right) {
                leftMax = leftMax->_right;
            }
            _node = leftMax;
        }
        //2. 没有左子树
        else {
            Node* parent = cur->_parent;
            while (parent && cur != parent->_right) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self operator--(int) {
        Self tmp(_node);
        operator--();
        return tmp;
    }
	};

	//参数K用在find,erase等,虽然K也可以被T取代了,但没必要,K更快
	template<class K, class T, class keyOfT> //库中还有1个compare,先不写了
	class RBTree
	{
	public:
		typedef RBTreeNode<T> node; //T是key或pair
	public:
		typedef __RBTree_iterator<T, T&, T*> iterator;
		typedef __RBTree_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			node* cur = _root;
			while (cur && cur->_left)//不能走到空
			{
				cur = cur->_left;
			}
			return iterator(cur);//返回中序的第一个结点,最左结点
		}

		iterator end() //end是最一个位置的下一个
		{
			return iterator(nullptr);//暂时可以这么写
		}

		const_iterator begin()const
		{
			node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return iterator(cur);
		}

		const_iterator end() const
		{
			return iterator(nullptr);
		}

	private:
		node* _root = nullptr;
	public:
		node* find(const K& key)
		{
			keyOfT kot;//kot是个仿函数,根据不同参数返回不同的参数对象
			node* cur = _root;
			while (cur)
			{
				if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					cur = cur->_left;
				}
				else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					cur = cur->_right;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		pair<iterator, bool> insert(const T& data)
		{
			if (!_root)
			{
				_root = new node(data);
				_root->_col = BLACK;
				return std::make_pair(iterator(_root), true);
			}
			
			keyOfT kot;

			node* cur = _root;
			node* parent = nullptr;
			while (cur)
			{
				if (kot(cur->_data) < kot(data)  ) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return std::make_pair(iterator(cur), false);
				}
			}
			cur = new node(data);
			if ( kot(parent->_data) < kot(data)) // --------------------------------------------
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//调整/旋转
			node* newnode = cur;//调整过程cur会发生变化,将cur结点记住 -- 记住原来key的位置
			while (parent && parent->_col == RED)
			{
				node* g = parent->_parent;
				if (parent == g->_right)
				{
					node* u = g->_left;
					if (u && u->_col == RED)
					{
						g->_col = RED;
						parent->_col = BLACK;
						u->_col = BLACK;
						cur = g;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_right)
						{
							RotateL(g);
							parent->_col = BLACK;
							g->_col = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(g);
							g->_col = RED;
							cur->_col = BLACK;
						}
						break;
					}

				}
				else
				{
					node* u = g->_right;
					if (u && u->_col == RED)
					{
						g->_col = RED;
						parent->_col = BLACK;
						u->_col = BLACK;
						cur = g;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							RotateR(g);
							parent->_col = BLACK;
							g->_col = RED;
						}
						else
						{
							RotateL(parent);
							RotateR(g);
							g->_col = RED;
							cur->_col = BLACK;
						}
						break;
					}
				}
			}
			_root->_col = BLACK;
			return std::make_pair(iterator(newnode), true);
		}
	public:
		void InOrderTraversal()
		{
			_InOrderTraversal(_root);
		}

		bool isBalanceTree()
		{
			//需要判断3个规则
			//1.根为黑
			if (_root && _root->_col == RED)
			{
				cout << "错误:根是红色" << endl;
				return false;
			}

			//2.不能有连续得红
			//3.黑同
			int benchmark = 0;
			node* cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
				{
					++benchmark;
				}
				cur = cur->_left;
			}
			return _check(_root, 0, benchmark);
		}

		int Height()
		{
			return _Height(_root);
		}
		~RBTree()
		{
			Destroy(_root);
		}

	private:
		void Destroy(node*& root)
		{
			if (!root)
			{
				return;
			}
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

		bool _check(node* root, int blackNum, int benchmark)
		{
			keyOfT kot;
			if (!root) //
			{
				if (blackNum != benchmark)
				{
					cout << "错误:存在不同路径的黑色结点数量不相同" << endl;
					return false;
				}
				return true;
			}

			if (root->_col == BLACK)
			{
				++blackNum;
			}

			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << kot(root->_data) << " 错误,与父节点同时为红色"; // --------------------------------------------
				return false;
			}

			return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
		}

		int _Height(node* root)
		{
			if (!root)
			{
				return 0;
			}
			int leftH = _Height(root->_left);
			int rightH = _Height(root->_right);

			return leftH > rightH ? leftH + 1 : rightH + 1;
		}

		void _InOrderTraversal(node* root)
		{
			keyOfT kot;
			if (root == nullptr)
			{
				return;
			}
			_InOrderTraversal(root->_left);
			cout << kot(root->_data) << " "; // --------------------------------------------
			_InOrderTraversal(root->_right);
		}

		void RotateL(node* parent)
		{
			node* subR = parent->_right;
			node* subRL = subR->_left;

			parent->_right = subRL;
			if (subRL)
			{
				subRL->_parent = parent;
			}

			node* pparent = parent->_parent;

			subR->_left = parent;
			parent->_parent = subR;

			if (!pparent)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
				{
					pparent->_left = subR;
				}
				else
				{
					pparent->_right = subR;
				}
				subR->_parent = pparent;
			}
		}

		void RotateR(node* parent)
		{
			node* subL = parent->_left;
			node* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR)
			{
				subLR->_parent = parent;
			}

			node* pparent = parent->_parent;

			subL->_right = parent;
			parent->_parent = subL;


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

封装的set

红黑树改造完成后,封装set和map就比较简单了,基本上都是套用红黑树的功能,特别方便,这也体会到了实现STL的大佬们的厉害.

#pragma once

#include"RBT.hpp"
namespace test
{

	template<class K>
	class set
	{

	private:
		struct setKeyOfT//取出RBT的类型T中的key
		{
			const K& operator()(const K& key) 
			{
				return key; 
			}
		};
	private:
		RBTree< K, K, setKeyOfT>_t;
	public:
		//使用类域的要加typename,以防和静态变量冲突
		typedef typename RBTree<K, K, setKeyOfT>::const_iterator iterator; //普通迭代器
		typedef typename RBTree<K, K, setKeyOfT>::const_iterator const_iterator; //const迭代器

		iterator begin()
		{
			return _t.begin(); //begin是普通迭代器,返回值是const,发生隐式类型转换(单参数)
			//如果有相应的构造函数,则支持隐式类型转换 ,但此时迭代器没有参数为迭代器的构造函数,需要添加
		}
		iterator end()
		{
			return _t.end();
		}

		const_iterator begin()const
		{
			return _t.begin();
		}
		const_iterator end()const
		{
			return _t.end();
		}

		

	public:
		pair<iterator, bool> insert(const K& key)
		{
			return _t.insert(key);
		}


	};

	void test_mySet1()
	{
		test::set<int> s;
		s.insert(2);
		s.insert(1);
		s.insert(3);

		set<int>::iterator it = s.begin();
		//while (it!=s.end())
		//{
		//	cout << *it << " ";
		//	++it;
		//}
		for (auto& e : s)
		{
			cout << e << " ";
		}
		cout << *++it << " ";
		cout << *--it << " ";
		cout << endl;
		//*it = 1;////不允许赋值,表达式必须是可以修改的左值 .不能给常量赋值
		

	}
}

封装的map

#pragma once

#include"RBT.hpp"
namespace test
{
	template<class K,class V>
	class map
	{
	private:
		struct mapKeyOfT
		{ 
			const K& operator()(const pair<const K,V>& kv) 
			{
				return kv.first; 
			}
		};
	private:
		RBTree<K, pair<const K, V>, mapKeyOfT> _t;
	public:
		typedef typename RBTree<K, pair<const K,V>, mapKeyOfT>::iterator iterator; 

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}

	public:
		pair<iterator,bool> insert(const pair<const K, V>& kv)
		{
			return _t.insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator,bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}

	};

	void test_myMap1()
	{
		test::map<int, int> m;
		m.insert(std::make_pair(1, 1));
		m.insert(std::make_pair(3, 3));
		m.insert(std::make_pair(2, 2));
		test::map<int,int>::iterator it = m.begin();
		//while (it != m.end())
		//{
		//	cout << it->first << " ";
		//	++it;
		//}
		for (auto e : m)
		{
			cout << e.first << " ";
		}

		cout << (++it)->first << " ";
		cout << (--it)->first << " ";
		cout << endl;

		//it->second = 1; //可以赋值
		//it->first = 1;//不允许赋值,表达式必须是可以修改的左值 .不能给常量赋值
	}

	void test_myMap2()
	{
		//map的使用
		map<std::string, std::string>  dict;
		dict.insert(std::pair<std::string, std::string>("sort", "排序")); //匿名对象插入
		dict.insert(std::make_pair("string", "字符串"));    //pair封装插入
		dict.insert(std::make_pair("count", "计数"));
		dict.insert(std::make_pair("count", "(计数)")); //插入失败的
		auto it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
	}

	void test_myMap3()
{
	std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	map<std::string, int> countMap;
	/*for (auto e : arr)
	{
		auto ret = countMap.find(x);
		if (ret==countMap.end())
		{
			countMap.insert(std::pair<string, int>(x, 1));
		}
		else
		{
			++ret->second;
		}
	}*/

	for (auto& e : arr)
	{
		++countMap[e];
	}

	for (auto& s : countMap)
	{
		cout <<  s.first << ":" << s.second << endl;
	}
	}
}



未经允许不得转载:大白鲨游戏网 » STL 改造红黑树 模拟封装set和map