-
【C++】map与set的封装
前言
在学习了红黑树之后，我们便可以尝试初步的在红黑树的基础上封装出map与set，好了，话不多说，进入今天的学习吧！
所需知识：
- 模板,主要为typename的特殊用法，模板参数，类模板。
- 迭代器与const迭代器
- 仿函数、反向迭代器
- 红黑树
正文
1. 类型的泛化
我们先分析map与set以及红黑树的模板参数。
- map 存的是key——val，键值对。
- set 存的是key。
- 红黑树存的是 key——val。
因此，为了适配set，红黑树里面存的是key，为了适配map红黑树存的是key——val, 如何实现呢？
那不如，设红黑树的存放的val是T类型，可以是key，也可以是key——val。
- 既然这样，我们就将原先的结点改为T类型的。
template<class T> struct RBTreeNode { typedef RBTreeNode<T> Node; RBTreeNode(const T& data) :_data(data) ,_right(nullptr) ,_left(nullptr) ,_parent(nullptr) ,_col(RED) {} Node* _right; Node* _left; Node* _parent; T _data; Color _col; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
那既然这样，又会引出两个问题：
- 模板参数的Key还有用吗？
- 插入的数据类型也要变为T，如何进行比较？
先来解决第一个问题，Key有用吗？首先要明白Key是一个类型，在定义变量或者作为函数参数时要使用，很显然红黑树的查找的函数的参数类型是Key，因此有用，且不能舍弃。
2.仿函数
接着解决第二个问题，插入时既然T可以是key，也可以是pair
- T是key时，结点中存的是key可以直接进行比较。
- T是pair
库里的实现涉及到第二参数，因此无法准确的得出正确结果，因此需要我们自己写一个仿函数，那因为map需要写，set也要适配红黑树，因此也需要写一个仿函数，返回key即可。
set实现：
template<class K> struct SetOfT { K operator()(const K& val) { return val; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
map实现:
template<class K, class V> struct MapOfT { const K operator()(const pair<const K, V>& val) { return val.first; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
3.迭代器
3.1正向迭代器
根据之前的内容的学习，我们是封装出来一个通用的正向迭代器，通过模板参数控制其为const还是非const迭代器。
基本框架：
template<class T,class Ref,class Ptr> struct __TreeIterator { typedef __TreeIterator<T, T&, T*> iterator; typedef RBTreeNode<T> Node; typedef __TreeIterator<T,Ref,Ptr> self; __TreeIterator(Node* val) :_node(val) {} //此构造用于将非const迭代器转换为const迭代器，从而实现类型转换的功能。 __TreeIterator(const iterator& val) :_node(val._node) {} //前置++ self& operator++(); //后置++ self operator++(int); //后置-- self operator--(int); //解引用 Ref operator*(); //箭头 Ptr operator->(); //不等于 bool operator!=(const __TreeIterator& it); Node* _node; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
3.1.1 ++
由于三叉链的结构，父节点是很容易找到的，因此可以直接用循环写一个。
原理： 中序遍历
- 开始节点树的最小节点。
- 根据中序遍历的过程遍历整棵树。
图解：
self& operator++() { Node* cur = _node; assert(cur); if (cur->_right) { //如果右子树不为空，访问其右子树的最左结点。 Node* MostLeft = cur->_right; while (MostLeft && MostLeft->_left) { MostLeft = MostLeft->_left; } _node = MostLeft; } else { //右子树为空，访问其祖先 Node* parent = cur->_parent; //结点为其父节点的左边，访问父节点即可 if (parent && parent->_left == cur) { _node = parent; } //结点为其父节点的右边，访问父亲的父亲 else { while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } } return *this; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
3.1.2 - -
- 与 ++同思路。
图解：
注意：当为空时，–我在这实现的是不可以的，但是库里面的是可以的，因为库里的结构是这样的。
库里的判断条件是这样的：当node为header时，node就转换其右边结点，也就是右树的最大结点。
说明一下：这样实现可能会导致增加了维护最大和最小节点的成本，每次插入和删除都得判断一下，不过也还好。因此：这里我们只是实现正向的迭代器，反向的迭代器我们没有写，如果不采用库里的结构，我们也可以用友元+指针+前置类型声明的方式进行实现。
self& operator--() { Node* cur = _node; if (cur->_left) { //访问最右结点 Node* most_right = cur->_left; while (most_right && most_right->_right) { most_right = most_right->_right; } _node = most_right; } else { Node* parent = cur->_parent; if (parent->_right == cur) { //父节点右为cur，该访问父节点了。 _node = parent; } else { //找到父亲作为cur的结点。 while (parent && parent->_left == cur) { cur = parent; parent = parent->_parent; } _node = parent; } } return *this; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
3.1.3 *
Ref operator*() { return _node->_data; }- 1
- 2
- 3
- 4
3.1.4 ->
Ptr operator->() { return &(_node->_data); }- 1
- 2
- 3
- 4
3.1.5 !=
bool operator!=(const __TreeIterator& it) { return _node != it._node; }- 1
- 2
- 3
- 4
完整版代码
template<class T,class Ref,class Ptr> struct __TreeIterator { typedef __TreeIterator<T, T&, T*> iterator; typedef RBTreeNode<T> Node; typedef __TreeIterator<T,Ref,Ptr> self; __TreeIterator(Node* val) :_node(val) {} __TreeIterator(const iterator& val) :_node(val._node) {} //前置++ self& operator++() { Node* cur = _node; assert(cur); if (cur->_right) { //如果右子树不为空，访问其右子树的最左结点。 Node* MostLeft = cur->_right; while (MostLeft && MostLeft->_left) { MostLeft = MostLeft->_left; } _node = MostLeft; } else { //右子树为空，访问其祖先 Node* parent = cur->_parent; //结点为其父节点的左边，访问父节点即可 if (parent && parent->_left == cur) { _node = parent; } //结点为其父节点的右边，访问父亲的父亲 else { while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } } return *this; } self operator++(int) { self tmp(_node); ++(*this); return tmp; } self& operator--() { Node* cur = _node; if (cur->_left) { //访问最右结点 Node* most_right = cur->_left; while (most_right && most_right->_right) { most_right = most_right->_right; } _node = most_right; } else { Node* parent = cur->_parent; if (parent->_right == cur) { //父节点右为cur，该访问父节点了。 _node = parent; } else { //找到父亲作为cur的结点。 while (parent && parent->_left == cur) { cur = parent; parent = parent->_parent; } _node = parent; } } return *this; } self operator--(int) { self tmp(_node); (*this)++; return tmp; } Ref operator*() { return _node->_data; } Ptr operator->() { return &(_node->_data); } bool operator!=(const __TreeIterator& it) { return _node != it._node; } Node* _node; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
4.[]（map）
我们要实现的insert接口为：
因此我们实现的红黑树的接口为：
pair<iterator,bool> insert(const T& val) { //第一步：插入操作 //如果根节点为空 if (_root == nullptr) { _root = new Node(val); _root->_col = BLACK; return make_pair(iterator(_root), true); } else { KeyOfT sel;//select里面的key Node* cur = _root, *parent = _root; while (cur) { if (sel(cur->_data) > sel(val)) { parent = cur; cur = cur->_left; } else if (sel(cur->_data) < sel(val)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(val); if (sel(parent->_data) > sel(val)) { parent->_left = cur; } else { parent->_right = cur; } //变色逻辑略，重点在框架。 return make_pair(iterator(newnode), true); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
map接口的实现为：
pair<iterator,bool> insert(const pair<K,V>& data) { return _tree.insert(data); } mapped_type& operator[](const key_type& data) { pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type())); return x.first->second; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
set的接口为：
pair<iterator,bool> insert(const K& data) { pair<typename rb_type::iterator, bool> k = _tree.insert(data); return pair<iterator,bool>(k.first,k.second); }- 1
- 2
- 3
- 4
- 5
补充小知识：迭代器转const迭代器
先强调：
- const迭代器与非const迭代器是两种完全不同的自定义类型。
- 内置类型默认支持隐式类型转换，自定义类型需要有合适的构造函数才可实现隐式类型的转换，且explict可阻止隐式类型转换的发生。
因此：我们需要在模板内部写一个合适的构造函数，且其成员是公有的，才可实现自定义类型的转换。
框架
1.红黑树
运用封装知识的框架：
template<class Key,class T,class KeyOfT> class RBTree { public: typedef RBTreeNode<T> Node; typedef __TreeIterator<T,T&,T*> iterator; typedef __TreeIterator<T, const T&, const T*> const_iterator; const_iterator begin()const { Node* mostleft = _root; while (mostleft && mostleft->_left) { mostleft = mostleft->_left; } return mostleft; } iterator begin() { Node* mostleft = _root; while (mostleft && mostleft->_left) { mostleft = mostleft->_left; } return mostleft; } const_iterator end()const { return nullptr; } iterator end() { return nullptr; } Node* find(const Key& key) { KeyOfT sel; Node* cur = _root; while (cur) { if (sel(cur->_data) > key) { cur = cur->_right; } else if (sel(cur->_data) < key) { cur = cur->_left; } else { return cur; } } return nullptr; } pair<iterator,bool> insert(const T& val) { //第一步：插入操作 //如果根节点为空 if (_root == nullptr) { _root = new Node(val); _root->_col = BLACK; return make_pair(iterator(_root), true); } else { KeyOfT sel; Node* cur = _root, * parent = _root; while (cur) { if (sel(cur->_data) > sel(val)) { parent = cur; cur = cur->_left; } else if (sel(cur->_data) < sel(val)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(val); if (sel(parent->_data) > sel(val)) { parent->_left = cur; } else { parent->_right = cur; } //根节点可能为红色,不管红色还是黑色都弄成黑色 _root->_col = BLACK; return make_pair(iterator(newnode), true); } } private: Node* _root = nullptr; }; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
2.set
template<class K> class set { template<class K> struct SetOfT { K operator()(const K& val) { return val; } }; //typedef //类型 typedef K key_type; typedef K val_type; typedef SetOfT<K> set_of_key; typedef RBTree<key_type, val_type, set_of_key> rb_type; typedef K key_type; typedef K val_type; typedef SetOfT<K> set_of_key; typedef RBTree<key_type, val_type, set_of_key> rb_type; //typename的作用：声明其为类型。 typedef typename rb_type::Node Node; public: //迭代器 typedef typename rb_type::const_iterator const_iterator; //不管是普通还是const迭代器set的key值都不可被修改。 typedef const_iterator iterator; const_iterator begin() const { return _tree.begin(); } const_iterator end() const { return _tree.end(); } public: Node* find(const K& key) { return _tree.find(key); } pair<iterator,bool> insert(const K& data) { pair<typename rb_type::iterator, bool> k = _tree.insert(data); //这里涉及到普通迭代器转换成const迭代器。 return pair<iterator,bool>(k.first,k.second); } private: rb_type _tree; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
3.map
template<class K,class V> class map { //类型 typedef K key_type; typedef pair<const K, V> val_type; template<class K, class V> struct MapOfT { const K operator()(const pair<const K, V>& val) { return val.first; } }; typedef MapOfT<K, V> map_of_key; typedef RBTree<key_type, val_type, map_of_key> rb_type; public: typedef typename rb_type::Node Node; //迭代器 typedef typename rb_type::iterator iterator; typedef typename rb_type::const_iterator const_iterator; typedef V mapped_type; iterator begin() { return _tree.begin(); } const_iterator begin()const { return _tree.begin(); } iterator end() { return _tree.end(); } const_iterator end()const { return _tree.end(); } bool find(const K& key) { return _tree.find(key); } pair<iterator,bool> insert(const pair<K,V>& data) { return _tree.insert(data); } mapped_type& operator[](const key_type& data) { pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type())); return x.first->second; } private: rb_type _tree; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
总结
模板，迭代器，仿函数，分开起来，或许不难，但是合起来，还是有点难度的，毕竟封装也是套娃，也挺麻烦的，尤其是模板的一大缺陷，增加了编译器识别问题的难度。
如果有所帮助，不妨点个赞鼓励一下吧！ -
相关阅读:
OpenShift 4 - 在 Windows 上安装 OpenShift 单机开发环境
什么是正负样本
为了摆脱 Android ，亚马逊开发基于Linux的操作系统
oracle导出问题：ORA-00904: “POLTYP“: 标识符无效
css实现六边形
ARM CoreLink CCN 互连总线介绍
独立游戏开发的 6 个步骤
M. My University Is Better Than Yours(思维)
A First Programming Exercise For PLSQL code
【Vue】Vue项目需求--实现搜索框输入防抖处理
- 原文地址：https://blog.csdn.net/Shun_Hua/article/details/132879264
