【C++】STL之map和set的模拟实现

文章目录

• • 红黑树的改造
  • • 树的结点改造
    • 仿函数的设计
    • 迭代器设计
    • • 正向迭代器
      • • begin()和end()
        • operator++()和operator--()
        • 正向迭代器类代码实现
      • 反向迭代器
      • • rbegin()和rend()
        • operator++()和operator--()
        • 反向迭代器类代码实现
    • 红黑树改造代码实现
  • set的模拟实现
  • map的模拟实现

map和set的 底层数据存储管理都是 红黑树实现的，但是 set是K模型的容器只关注key值，而 map是KV模型的容器， 关注的是KV键值对，那么红黑树的模板参数该如何传入，此时就应该 对红黑树进行改造，让 map和set用同一个红黑树就能进行封装适配

红黑树的改造

以前的红黑树实现的是KV模型，并不适合同时封装map和set

红黑树未改造版(KV模型)

我们要对这个树进行改造

---

树的结点改造

以前实现的红黑树节点是KV模型的，传入的模板参数很明确，第一个值是key，第二个值是value，但是这种模型并不适用于set，这里对节点进行改造，只让传入一个模板参数，map传入键值对，而set只传入key

template 
struct RBTreeNode {
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;

	Colour _Col;
	
    //这里的val
    //set传入key
    //map传入pair
	Value _Val;

	RBTreeNode(const Value& val)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _Col(RED)
		, _Val(val)
	{}
};

---

仿函数的设计

对树的结点进行改造后，看似已经完成了红黑树的改造，但是当使用Find函数查找结点时，就会出现问题

Node* Find(const Key& key);

Find函数查找时传入的参数是key值，而Find函数的内部查找，需要和结点的value值进行比较，对于set来说不影响，而map结点中的value值是一个键值对pair，这时map的查找就要使用key值和pair进行比较，这显然是不行的

使用Insert函数也会遇到比较的问题

pair Insert(const Val& val);

Insert函数传入的是一个Val类型的数据，进行比较时，set也是正常的，map的比较就是两个pair类型的比较，其实pair类型在库中已经重载了比较，但是我们依然让它用pair的第一个K键值进行比较

所以我们让红黑树的模板参数增加一个仿函数，由map和set自己控制比较时的取值，让比较都是使用value值来比较

set仿函数设计

如果是set，就让仿函数返回key值

template
class set {
	//仿函数，传入红黑树，用作泛型的比较
	struct SetKeyOfVal {
		const K& operator()(const K& key) {
			return key;
		}
	};
	public:
	//...
	private:
	RBTree _t;
};

map仿函数设计

如果是map，就让仿函数返回键值对的first，也就是key值

template
class map {
	//仿函数，传入红黑树，用作泛型的比较
	struct MapKeyOfVal {
		const K& operator()(const pair& kv) {
			return kv.first;
		}
	};
public:
//...
private:
	RBTree, MapKeyOfVal> _t;
};

红黑树框架

template 
class RBTree
{
    typedef RBTreeNode Node;
public:
	//...
private:
	Node* _root;
};

---

Find函数的实现

这时Find函数就可以使用仿函数来实现不同的传参对应不同的取值了

Node* Find(const Key& key) {
    //仿函数对象
	KeyOfValue kov;

	if (_root == nullptr)
		return nullptr;

	Node* cur = _root;

	while (cur) {
        //用仿函数控制比较的类型
		if (kov(cur->_Val) > key) {
			cur = cur->_left;
		}
		else if (kov(cur->_Val) < key) {
			cur = cur->_right;
		}
		else {
			//找到了
			return cur;
		}
	}
	//没找到
	return nullptr;
}

---

Insert函数的实现

Insert函数内的比较都成了pair的第一个参数key的比较

pair Insert(const Val& val) {

	KeyOfValue kov;

	//......

	while (cur) {
		if (kov(cur->_Val) > kov(val)) {
			parent = cur;
			cur = cur->_left;
		}
		else if (kov(cur->_Val) < kov(val)) {
			parent = cur;
			cur = cur->_right;
		}
		else {
			//节点已经存在，插入失败
			return make_pair(iterator(cur), false);
		}
	}

	//找到要插入的节点位置
	cur = new Node(val);
	//记录插入节点的位置
	Node* newNode = cur;

	//新节点的链接关系
	if (kov(parent->_Val) > kov(val)) {
		parent->_left = cur;
		cur->_parent = parent;
	}
	else {
		parent->_right = cur;
		cur->_parent = parent;
	}
		
	//......
}

---

总体设计思路

---

迭代器设计

迭代器本质上是指针的一个封装的类，其底层就是指针；好处是可以方便遍历，是数据结构的底层实现与用户透明

正向迭代器 begin()和end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置即nullptr

---

operator++()和operator–()

实现红黑树的正向迭代器时，一个结点的正向迭代器进行++操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点

实现逻辑如下

• 如果当前结点的右子树不为空，则++操作应该走到当前结点右子树中的最左结点
• 如果当前结点的右子树为空，则应该向上找祖先结点中找到不是父亲右结点的祖先结点

Self& operator++() {
	//如果当前节点右子树不为空
	//那么就访问右子树的最左节点
	if (_node->_right) {
		Node* left = _node->_right;

		while (left->_left) {
			left = left->_left;
		}
		_node = left;
	}
	//当前节点的右子树为空
	else {
		Node* cur = _node;
		Node* parent = cur->_parent;

		//当前节点是父亲节点的右节点
		//说明当前节点的父亲节点也已经访问完
		//继续向上迭代
		while (parent && parent->_right == cur) {
			cur = parent;
			parent = parent->_parent;
		}

		//此时说明当前节点是父亲节点的左节点，下一个就该访问父亲节点了
		_node = parent;
	}

	return *this;
}

实现红黑树的正向迭代器时，一个结点的正向迭代器进行--操作后，应该根据红黑树中序遍历的序列找到当前结点的前一个结点

实现逻辑如下

• 如果当前结点的左子树不为空，则++操作应该走到当前结点左子树中的最右结点
• 如果当前结点的左子树为空，则应该向上找祖先结点中找到不是父亲左结点的祖先结点

Self& operator--() {
	if (_node->_left) {
		Node* right = _node->_left;
		while (right->_right) {
			right = right->_right;
		}
		_node = right;
	}
	else {
		Node* cur = _node;
		Node* parent = cur->_parent;

		while (parent && parent->_left == cur) {
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}

	return *this;
}

---

正向迭代器类代码实现

template
struct __TreeIterator {
	typedef Ref reference; //结点指针的引用
	typedef Ptr pointer; //结点指针

	typedef RBTreeNode Node;
	typedef __TreeIterator Self;

	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

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

	Ptr operator->() {
		return &_node->_Val;
	}

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

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

	Self& operator++() {
		//如果当前节点右子树不为空
		//那么就访问右子树的最左节点
		if (_node->_right) {
			Node* left = _node->_right;

			while (left->_left) {
				left = left->_left;
			}

			_node = left;
		}
		//当前节点的右子树为空
		else {
			Node* cur = _node;
			Node* parent = cur->_parent;

			//当前节点是父亲节点的右节点
			//说明当前节点的父亲节点也已经访问完
			//继续向上迭代
			while (parent && parent->_right == cur) {
				cur = parent;
				parent = parent->_parent;
			}

			//此时说明当前节点是父亲节点的左节点，下一个就该访问父亲节点了
			_node = parent;
		}

		return *this;
	}


	Self& operator--() {
		if (_node->_left) {
			Node* right = _node->_left;
			while (right->_right) {
				right = right->_right;
			}

			_node = right;
		}
		else {
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent && parent->_left == cur) {
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

};

---

反向迭代器 rbegin()和rend()

反向迭代器的rbegin()其实就是红黑树的最大结点，rend()放在最小节点(最左侧节点)的下一个位置即nullptr

operator++()和operator–()

反向迭代器的operator++()其实就是正向迭代器的operator--()操作

反向迭代器的operator--()其实就是正向迭代器的operator++()操作

反向迭代器类代码实现

template
struct ReverseIterator {
	typedef ReverseIterator Self;
	typedef typename Iterator::reference Ref;
	typedef typename Iterator::pointer Ptr;

	Iterator _it;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

	Ref operator*() {
		return *_it;
	}

	Ptr operator->() {
		return _it.operator->();
	}

	Self& operator++() {
		--_it;
		return *this;
	}

	Self& operator--() {
		++_it;
		return *this;
	}

	bool operator!=(const Self& s) {
		return _it != s._it;
	}

	bool operator==(const Self& s) {
		return _it == s._it;
	}
};

---

红黑树改造代码实现

完整的红黑树改造和迭代器实现代码

红黑树的改造完整代码

---

set的模拟实现

#pragma once
#include"RBTree.h"
namespace ns_self {
	template
	class set {
		//仿函数，传入红黑树，用作泛型的比较
		struct SetKeyOfVal {
			const K& operator()(const K& key) {
				return key;
			}
		};
	public:

		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();
		}


		pair insert(const K& k) {
			return _t.Insert(k);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}


	private:
		RBTree _t;
	};
}

---

map的模拟实现

#pragma once
#include"RBTree.h"
namespace ns_self{
	template
	class map {
		//仿函数，传入红黑树，用作泛型的比较
		struct MapKeyOfVal {
			const K& operator()(const pair& kv) {
				return kv.first;
			}
		};
	public:
		typedef typename RBTree, MapKeyOfVal>::iterator iterator;//正向迭代器	
		typedef typename RBTree, MapKeyOfVal>::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();
		}


		pair insert(const pair& kv) {
			return _t.Insert(kv);
		}


		iterator find(const K& key)
		{
			return _t.Find(key);
		}

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


	private:
		RBTree, MapKeyOfVal> _t;
	};
}