[C++随想录] map和set的封装

编程入门行业动态更新时间:2024-10-19 22:32:38

[C++<a href=https://www.elefans.com/category/jswz/34/1761140.html style= 随想录] map和set的封装"/>

[C++随想录] map和set的封装

map和set的封装

1. 红黑树模版的改变
- 1.1 RBTree类模板头的改变
- 1.2 封装迭代器类
- - 1.2.1 构造 && 拷贝构造
  - 1.2.2. ++
  - 1.2.3. - -
  - 1.2.4. 其他运算符重载
- 1.3 RBTree类实现普通迭代器和const迭代器
2. set的底层逻辑
3. map的底层逻辑
4. 源码
- 4.1 RBTree类
- 4.2 set类
- 4.3 map类

1. 红黑树模版的改变

1.1 RBTree类模板头的改变

原来的红黑树模版是 <class K, class V>
由于 set 的存储数据是K类型, 而map的存储数据是 <K, V>类型
⇒ 红黑树的模版要进行改变

🗨️ set中控制 key不允许修改为什么不用 RBTree<K, const K, SetofT>?

见set中普通迭代器和 const迭代器的实现

1.2 封装迭代器类

1.2.1 构造 && 拷贝构造

构造

_iterator(Node* t):_node(t)
{}

用普通迭代器初始化const迭代器

// 用普通迭代器去初始化const迭代器
_iterator(const Iterator& it):_node(it._node)
{}

🗨️为什么要写 用普通迭代器初始化const迭代器呢 ?

见set的 insert逻辑
按照道理来说, 迭代器是 内置类型 ⇒ 浅拷贝, 是不需要我们亲自写拷贝构造的

1.2.2. ++

++ — — 返回 中序 中的下一个节点
由于中序是 左跟右 ⇒ 当前节点 ++ 主要有两大情况 右子树为空, 右子树不为空

右子树为空, 说明当前根节点的右子树的逻辑并没有结束, 意味着要找到右子树的最小节点
右子树为空, 说明当前根节点的整个逻辑已经结束(左子树向上, 向根节点返回左子树的情况), 意味着要找到最近的孩子是父亲左孩子的父亲节点

self& operator++()
{// 右子树不为空if (_node->_right){Node* rightmin = _node->_right;while (rightmin->_left){rightmin = rightmin->_left;}_node = rightmin;}// 右子树为空// 向上回溯并返回最近的孩子是父亲左孩子的父亲节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

1.2.3. - -

减减 — — 加加反过来, 右跟左
当前节点减减, 主要有两大情况 左子树为空, 左子树不问空

左子树不为空, 说明当前根结点的左子树逻辑并没有结束, 意味着要找到左子树中的最大节点
左子树为空, 说明当前根节点的这个逻辑已经结束(右子树向上, 向根节点返回右子树的情况), 意味着要找到最近的孩子是父亲右孩子的父亲节点

self& operator--()
{// 左子树不为空if (_node->_left){Node* leftmost = _node->_left;while (leftmost->_right){leftmost = leftmost->_right;}_node = leftmost;}// 左子树为空// 找到最近的孩子是父亲右孩子的父亲节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

1.2.4. 其他运算符重载

operator!=

bool operator !=(const self& t)
{return _node != t._node;
}

operator==

bool operator ==(const self& t)
{return _node->_data == t._node;
}

operator*

Ptr operator*()
{return _node->_data;
}

operator->

Ref operator->()
{return &_node->_data;
}

1.3 RBTree类实现普通迭代器和const迭代器

类型

typedef _iterator<T, T&, T*> iterator;
typedef _iterator<T, const T&, const T*> const_iterator;

begin, end

// begin - 最左节点
iterator begin()
{Node* leftmin = _root;while (leftmin && leftmin->_left){leftmin = leftmin->_left;}// return iterator(leftmin);return leftmin;
}iterator end()
{return iterator(nullptr);
}const_iterator begin()const
{Node* leftmin = _root;while (leftmin && leftmin->_left){leftmin = leftmin->_left;}// return const_iterator(leftmin);return leftmin;
}const_iterator end()const
{return const_iterator(nullptr);
}

2. set的底层逻辑

SetofT

底层RBTree类中, 只知道数据类型是 T, 而不知道 set 和 map的具体数据类型 && set的数据类型是 K, 而map的数据类型是pair<K, V>⇒ 这个模版T实现了 泛型编程
但是有一点是相同的, 都需要 数据中的 key 来进行比较逻辑 ⇒ 我们需要一个函数来 提取数据中的key

set中数据类型是K, key的类型也是 K ⇒ 我们 直接返回

struct SetofT
{const K& operator()(const K& data){return data;}
};

迭代器

typedef typename RBTree<K, K, SetofT>::const_iterator iterator;
typedef typename RBTree<K, K, SetofT>::const_iterator const_iterator;

我们发现 : set中迭代器和 const迭代器都是 const迭代器 ⇒ 保证了 key是不能进行修改的
🗨️ set中控制 key不允许修改为什么不用 RBTree<K, const K, SetofT>?

如果数据类型直接传 const类型 ⇒ 常量 ⇒ 常量, 结构是不成立的

begin, end
一个const版本即可

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

find

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

insert

pair<iterator, bool>& insert(const K& data)
{pair<RBTree<K, K, SetofT>::iterator, bool> tem = _t.Insert(data);pair<iterator, bool> res = tem;return res;
}

返回值是 pair结构的原因:
map的 [ ] 的本质是调用 insert, 有如下功能: (以 map[ret] 为例子)
1. ret 在map中存在, 返回value
2. ret 在map中不存在, 则新插入该节点

⇒ 这就要求insert 返回的是一个 pair结构, <节点迭代器, 是否存在> ⇒ pair<iterator, bool>
由于 set 和 map 共用同一个 红黑树 ⇒ set中的 insert的返回值也是一个 pair结构

进行类型转换的原因
注意: set中的iterator是 const_iterat
而RBTree中 Insert的返回值是 pair<iterator, bool> && RBTre类中的 iterator是正常的, 是普通迭代器
⇒ 就会出现 pair<const_iterator, bool> = pair<iterator, bool> 的类型不匹配问题
由于普通迭代器是可以初始化const迭代器的 (在RBTree类中的迭代器类中要多一个用普通迭代器去初始化const迭代器的函数 ) ⇒ 所以, 我们要先接收一下 Insert的返回值, 然后再进行类型转换

3. map的底层逻辑

MapofT

struct MapofT
{const K& operator()(const pair<K, V>& data){return data.first;}
};

迭代器

typedef typename RBTree<K, pair<const K, V>, MapofT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapofT>::const_iterator const_iterator;

begin, end

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

find

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

insert

pair<iterator, bool> insert(const pair<K, V>& data)
{return _t.Insert(data);
}

operator[ ]

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

4. 源码

4.1 RBTree类

#pragma once#include<iostream>
#include<assert.h>using namespace std;// 枚举enum Color{RED,BLACK };template<class T>struct RBTreeNode{public:RBTreeNode(const T& data):_data(data){}public:T _data;Color _color = BLACK;RBTreeNode<T>* _left = nullptr;RBTreeNode<T>* _right = nullptr;RBTreeNode<T>* _parent = nullptr;};template<class T, class Ptr, class Ref>struct _iterator{typedef RBTreeNode<T> Node;typedef _iterator<T, Ptr, Ref> self;typedef _iterator<T, T&, T*> Iterator;public:// 用普通迭代器去初始化const迭代器_iterator(const Iterator& it):_node(it._node){}_iterator(Node* t):_node(t){}bool operator !=(const self& t){return _node != t._node;}bool operator ==(const self& t){return _node->_data == t._node;}Ptr operator*(){return _node->_data;}Ref operator->(){return &_node->_data;}self& operator++(){if (_node->_right){Node* rightmin = _node->_right;while (rightmin->_left){rightmin = rightmin->_left;}_node = rightmin;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}self& operator--(){if (_node->_left){Node* leftmost = _node->_left;while (leftmost->_right){leftmost = leftmost->_right;}_node = leftmost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}public:Node* _node;};template<class K, class T, class KeyofT>struct RBTree{typedef RBTreeNode<T> Node;public:typedef _iterator<T, T&, T*> iterator;typedef _iterator<T, const T&, const T*> const_iterator;public:iterator begin(){Node* leftmin = _root;while (leftmin && leftmin->_left){leftmin = leftmin->_left;}return leftmin;}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* leftmin = _root;while (leftmin && leftmin->_left){leftmin = leftmin->_left;}return leftmin;}const_iterator end()const{return const_iterator(nullptr);}Node* find(const K& key){KeyofT kot;Node* cur = _root;while (cur){if (key > kot(cur->_data)){cur = cur->_right;}else if (key < kot(cur->_data)){cur = cur->_left;}else{return cur;}}return nullptr;}void RotateL(Node* parent){++RotateCount;Node* cur = parent->_right;Node* grandfather = parent->_parent;Node* curleft = cur->_left;// 旋转核心parent->_right = curleft;cur->_left = parent;// 更新父亲// 1. parent && curleftif (curleft){curleft->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}void RotateR(Node* parent){++RotateCount;Node* cur = parent->_left;Node* grandfather = parent->_parent;Node* curright = cur->_right;// 旋转核心parent->_left = curright;cur->_right = parent;// 更新链接关系// 1. parent && currightif (curright){curright->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}pair<iterator, bool> Insert(const T& data){KeyofT kot;if (_root == nullptr){// 根节点是黑色的_root = new Node(data);_root->_color = BLACK;return make_pair(iterator(_root), true);}Node* parent = _root;Node* cur = _root;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}// 新建一个节点, 默认是红色cur = new Node(data);cur->_color = RED;// 链接cur 和 parentif (kot(cur->_data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑红比例while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;parent->_color = uncle->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // u不存在 或 u存在且为黑色{if (cur == parent->_left){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;uncle->_color = parent->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}// u不存在 或 u存在且为黑色else{if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else{assert("黑红比例失控!");}}// 暴力统一处理根节点的颜色_root->_color = BLACK;return make_pair(iterator(cur), true);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_color == BLACK){++blacknum;}if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_color != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int GetRoateCount(){return RotateCount;}private:Node* _root = nullptr;int RotateCount = 0;};

4.2 set类

#pragma once#include"RBTree.h"namespace muyu
{template<class K>class set{struct SetofT{const K& operator()(const K& data){return data;}};public:typedef typename RBTree<K, K, SetofT>::const_iterator iterator;typedef typename RBTree<K, K, SetofT>::const_iterator const_iterator;public:pair<iterator, bool>& insert(const K& data){pair<RBTree<K, K, SetofT>::iterator, bool> tem = _t.Insert(data);pair<iterator, bool> res = tem;return res;}iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}iterator find(const K& key){return _t.find(key);}private:RBTree<K, K, SetofT> _t;};
}

4.3 map类

#pragma once#include"RBTree.h"namespace muyu
{template<class K, class V>class map{struct MapofT{const K& operator()(const pair<K, V>& data){return data.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapofT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapofT>::const_iterator const_iterator;public:pair<iterator, bool> insert(const pair<K, V>& data){return _t.Insert(data);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin()const{return _t.begin();}iterator find(const K& key){return _t.find(key);}const_iterator end()const{return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapofT> _t;};
}