网站导航
> 文章列表 > C++STL——map与set的模拟实现

C++STL——map与set的模拟实现

网友: 文章列表 2024-03-22 05:35:35

C++STL——map与set的模拟实现

map与set的模拟实现

  • map与set的部分源码参考
  • 改造红黑树
  • 红黑树的迭代器
  • 补全set与map的实现
  • 完整代码

map与set的部分源码参考

map和set的底层都是由红黑树实现的。
所以这里将上次实现的红黑树插入拿来用。
首先想一想，搜索二叉树不能修改值，因为会破坏整棵树的平衡。
set与map的部分源码：

class set {
public:// typedefs:typedef Key key_type;typedef Key value_type;typedef Compare key_compare;typedef Compare value_compare;
private:typedef rb_tree<key_type, value_type, //set这里传了一个K，一个Videntity<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing set

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>class map {
public:// typedefs:typedef Key key_type;typedef T data_type;typedef T mapped_type;typedef pair<const Key, T> value_type;
private:typedef rb_tree<key_type, value_type, //map这里传了一个K，一个Vselect1st<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing map

这个是红黑树的部分源码：

template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;
public:typedef rb_tree_node* link_type;
protected:size_type node_count; // keeps track of size of treelink_type header;  Compare key_compare;

set要传入到红黑树的Value的值是K,map要传入的值是pair<const K,V>
那么，这里完全可以区分传入的是set还是map，为什么要给红黑树传入第一个模板参数呢？
第一个模板参数是用来查找的，因为无论是set还是map都是用kay去查找的。

改造红黑树

这是红黑树的结点：

enum Color//利用枚举来给红黑树配色
{RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data)//让红黑树的结点变成一个模板就行了，因为有可能是set有可能是map:_data(data), _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦, _left(nullptr), _right(nullptr), _parent(nullptr){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Color _color;//结点的配色
};

namespace baiye
{template<class K>class set{public:private:RBTree<K, K> _t;//K模型};
}

namespace baiye
{template<class K, class V>class map{public:private:RBTree<K, pair<const K, V>> _p;//KV模型};
}

然后我们发现，后面的插入这里调用出现了问题：
C++STL——map与set的模拟实现
原来写的是VK模型，但是现在set是K模型，要兼容两个模型。
让我们来看看源码是怎么做的：
C++STL——map与set的模拟实现
源码这里多了一个模板参数，意思是将key取出来比较大小。
这里可以写两个仿函数用：

namespace baiye
{template<class K>class set{struct setKeyOFV{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, setKeyOFV> _t;};
}

namespace baiye
{template<class K, class V>class map{struct mapKeyOFV{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:bool insert(const pair<const K, V>& kv){return _p.Insert(kv);}private:RBTree<K, pair<const K, V>, mapKeyOFV> _p;};
}

红黑树的迭代器

先来实现*与->：

template<class T>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;Node* _node;RBTreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}
};

迭代器难的是++和- -操作：
原来stl中的红黑树其实有一个哨兵位的头结点：
C++STL——map与set的模拟实现
哨兵位中还有两个指针分别指向红黑树中的最小值和最大值，但是这里我并没有去实现这个哨兵位，所以就用另一种方法。
首先先给红黑树加begin和end函数：

	iterator begin(){Node* cur = _root;while (cur && cur->left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}

然后是++，++是要走中序遍历的，我们要采用迭代的方式，以前要借助一个队列来进行中序遍历的方法进行++。
C++STL——map与set的模拟实现
假设我们传入的迭代器的结点是8结点，那么下一个结点就是10号结点，也就是8号结点的右子树最小结点。
那么如果右为空呢？
右子树为空就说明不需要去右子树找了，需要向上找节点，假设是这样子的：
C++STL——map与set的模拟实现
it指向5结点，发现右为空，那就向上走，走到6结点发现右不为空然后走到7结点，7结点右为空就要继续往上走，这个时候不应该走到6结点的位置，应该是8结点的位置。
C++STL——map与set的模拟实现
C++STL——map与set的模拟实现
假设这里再多出一个结点：
C++STL——map与set的模拟实现
那么他的右为空也不能再走到7结点的位置了。
C++STL——map与set的模拟实现
所以我们能总结出来一个规律。

右不为空就去找右子树的最小节点。
右为空就去找祖先（孩子为父节点的左的那个祖先）

如果是it在15结点这个位置，往上走没有遇到符合祖先的位置，并且已经走到空了，那就代表已经结束了。

	Self& operator++(){if (_node->_right)//右子树不为空{Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else//左子树为空{Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

然后来实现- -逻辑：

	Self& operator--(){if (_node->_left)//左子树不为空{Node* cur = _node->_left;while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur != parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

补全set与map的实现

set当中的值是不允许被修改的。
这里我们就要实现const版本的迭代器：

template<class T,class Ref, class Ptr>
struct RBTreeIterator//红黑树的迭代器
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}

先将这两个函数变成能兼容const和非const版本。
看一下set源码是怎么定义迭代器的：
C++STL——map与set的模拟实现

那么set当中就算是非const版本的迭代器也不能修改值：

	template<class K>class set{struct setKeyOFV{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, setKeyOFV> _t;};

但是我们的begin函数和end函数的返回值和重命名的迭代器类型已经不相同了。
所以看看set源码是如何做到的：
C++STL——map与set的模拟实现
后面加了一个const就解决了问题，因为权限可以缩小，传入的就算是非const版本也可以。
在set的begin与end中加了个const就说明要去调用const版本的begin与end，所以在树那里也要实现const版本的begin与end。

template<class K, class T, class KeyOFV>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> 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);}

然后来实现map的const版本的迭代器：
先看看源码：
C++STL——map与set的模拟实现
C++STL——map与set的模拟实现

	template<class K, class V>class map{struct mapKeyOFV{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator;iterator begin(){return _p.begin();}iterator end(){return _p.end();}const_iterator begin()const{return _p.begin();}const_iterator end()const{return _p.end();}bool insert(const pair<const K, V>& kv){return _p.Insert(kv);}private:RBTree<K, pair<const K, V>, mapKeyOFV> _p;};

然后就是[]重载了：
这里首先要改插入的返回值和返回类型。

	pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_color = BLACK;return make_pair(iterator(_root), true);}Node* cur = _root;Node* parent = nullptr;KeyOFV kot;//仿函数对象while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);//这里默认是红色结点Node* newnode = cur;//因为cur会变位置，所以储存一下新节点if (kot(parent->_data) > kot(data)){cur->_parent = parent;parent->_left = cur;}else if (kot(parent->_data) < kot(data)){cur->_parent = parent;parent->_right = cur;}//如果父节点为空就代表cur是根节点，没必要调整了//还要判断cur结点是否与父节点的颜色均为红色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;//祖父结点if (parent == grandfather->_left)//新增结点在祖父左{Node* uncle = grandfather->_right;//情况一if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在{parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;//最后让cur等于祖父结点的位置parent = cur->_parent;}else{if (parent->_left == cur)//情况二{RotateR(grandfather);//右单旋grandfather->_color = RED;parent->_color = BLACK;}else if (parent->_right == cur)//情况三{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur->_color = BLACK;grandfather->_color = RED;}break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环}}else//新增结点在祖父右{Node* uncle = grandfather->_left;if (uncle && uncle->_color == RED)//情况一{uncle->_color = BLACK;parent->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else {if (cur == parent->_right)//情况二{RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else if (cur == parent->_left)//情况三{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}}_root->_color = BLACK;return make_pair(iterator(newnode), true);}

[]在map中重载即可：

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

因为树种插入的函数改变了返回值，所以set与map的插入调用函数也要改变返回值，但是set当中插入的返回值是非const类型：
C++STL——map与set的模拟实现
这里看看源码是如何解决的：
C++STL——map与set的模拟实现
这里使用了rep_type类型去接收，然后再用p去重新构造一个pair<iterator, bool>类型。
C++STL——map与set的模拟实现
这是构造，为了解决非const的迭代器不能拷贝给const迭代器的问题。
C++STL——map与set的模拟实现
C++STL——map与set的模拟实现

完整代码

RBTree.h

#include<iostream>
#include<cassert>
using namespace std;
enum Color//利用枚举来给红黑树配色
{RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦, _left(nullptr), _right(nullptr), _parent(nullptr){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Color _color;//结点的配色
};
template<class T,class Ref, class Ptr>
struct RBTreeIterator//红黑树的迭代器
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;typedef RBTreeIterator<T, T&, T*> iterator;Node* _node;RBTreeIterator(Node* node):_node(node){}//普通迭代器传给普通迭代器用的是默认生成的拷贝构造//当迭代器是const的时候用的就是普通迭代器构造的const迭代器RBTreeIterator(const iterator& s):_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right)//右子树不为空{Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else//左子树为空{Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left)//左子树不为空{Node* cur = _node->_left;while (cur && cur->_right){cur = cur->_right;}_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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};template<class K, class T, class KeyOFV>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> 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<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_color = BLACK;return make_pair(iterator(_root), true);}Node* cur = _root;Node* parent = nullptr;KeyOFV kot;//仿函数对象while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);//这里默认是红色结点Node* newnode = cur;//因为cur会变位置，所以储存一下新节点if (kot(parent->_data) > kot(data)){cur->_parent = parent;parent->_left = cur;}else if (kot(parent->_data) < kot(data)){cur->_parent = parent;parent->_right = cur;}//如果父节点为空就代表cur是根节点，没必要调整了//还要判断cur结点是否与父节点的颜色均为红色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;//祖父结点if (parent == grandfather->_left)//新增结点在祖父左{Node* uncle = grandfather->_right;//情况一if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在{parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;//最后让cur等于祖父结点的位置parent = cur->_parent;}else{if (parent->_left == cur)//情况二{RotateR(grandfather);//右单旋grandfather->_color = RED;parent->_color = BLACK;}else if (parent->_right == cur)//情况三{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur->_color = BLACK;grandfather->_color = RED;}break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环}}else//新增结点在祖父右{Node* uncle = grandfather->_left;if (uncle && uncle->_color == RED)//情况一{uncle->_color = BLACK;parent->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else {if (cur == parent->_right)//情况二{RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else if (cur == parent->_left)//情况三{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}}_root->_color = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent)//左单旋{Node* pparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (pparent){if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;}else{_root = subR;}subR->_parent = pparent;}void RotateR(Node* parent)//右单旋{Node* pparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (pparent){if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;}else{_root = subL;}subL->_parent = pparent;}void Inorder(){_Inorder(_root);}bool IsBalanceTree(){if (_root == nullptr)return true;if (_root->_color != BLACK){cout << "根不为黑色" << endl;return false;}int count = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)count++;cur = cur->_left;//找一条路径上的黑节点}_IsBalanceTree(_root, 0, count);}
private:bool _IsBalanceTree(Node* root, int k, int sum)//验证{if (root == nullptr){if (k == sum)//这里代表当前路径点和最左边的路径点相同return true;else{cout << "每条路径上黑色结点数量不同" << endl;}return false;}if (root->_color == BLACK)k++;if (root->_parent && root->_parent->_color == RED && root->_color == RED){cout << root->_parent->_data.first << endl;return false;}return _IsBalanceTree(root->_left, k, sum) && _IsBalanceTree(root->_right, k, sum);}void _Inorder(Node* _root){if (_root == nullptr)return;_Inorder(_root->_left);cout << _root->_data.first << ":" << _root->_data.second << endl;_Inorder(_root->_right);}Node* _root = nullptr;
};

set.h

#include"RBTree.h"namespace baiye
{template<class K>class set{struct setKeyOFV{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator;iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}pair<iterator, bool> insert(const K& key){pair<typename RBTree<K, K, setKeyOFV>::iterator, bool> it = _t.Insert(key);//这里接收的是普通迭代器return pair<iterator, bool>(it.first, it.second);//这里用普通迭代器构造const迭代器}private:RBTree<K, K, setKeyOFV> _t;};void settest(){int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };set<int>s;for (auto& e : arr){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
}

map.h

#include"RBTree.h"namespace baiye
{template<class K, class V>class map{struct mapKeyOFV{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator;iterator begin(){return _p.begin();}iterator end(){return _p.end();}const_iterator begin()const{return _p.begin();}const_iterator end()const{return _p.end();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _p.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> it = insert(make_pair(key, V()));return it.first->second;}private:RBTree<K, pair<const K, V>, mapKeyOFV> _p;};void maptest(){int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };map<int, int> m;for (auto& e : arr){m.insert(make_pair(e, e));}map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << " ";++it;}cout << endl;}
}

国学经典

相关问题