当前位置：首页 > news >正文

map和set封装

news 来源：原创 2024/5/13 1:08:38

背景

简化源码

仿函数

编辑

迭代器

set的实现

map的实现

红黑树的代码

完整代码

Myset.h

Mymap.h

RBTree.h

test.c

背景

map和set封装的底层是红黑树，set的参数只有key，但是map除了key还有value，我们还是需要kv模型的红黑树（红黑树链接：http://t.csdnimg.cn/fSeCF）

简化源码

查看RBTree，map，set的底层源码我们可以发现RBTree是通过传入的第二个模板参数value来判断类型，从而实例化不同的map和set

为了红黑树能识别set和map我们增加一个模板参数T

对于模板T既有可能是键值key，也有可能是键值对pair<key,value>

如果是set容器，那么他传入红黑树底层的模板参数就是key和key

如果是set容器，那么他传入红黑树底层的模板参数就是key和pair<key,value>

通过上面，我们可以知道，对于set和map的区别：我们只要通过第二个模板参数就能进行区分，那是不是第一个模板参数就没有意义了呢？

对于insert(const Value&v)来说，需要放入存入的值，确实是这个样子的，插入的值是value，对于set就是key，对于map就是pair。但是对于find(const Key&key)来说，查找的参数不是value，找的不是pair而是Key，对于map容器来说就不行了。

红黑树的结点

对于map和set的区分是通过第二个模板参数T来决定的，所以node结点我们只需要设置一个T就足够了

仿函数

这里存在一个问题，插入时data的大小是如何比较的，如果是set，类型是key，那么可以正常比较，如果是map，那么类型是pair的比较，我们只需要比较key，而pair的比较如果key相等还会继续比较value来比较大小，就不可以了

这里我们可以用一个仿函数来取出set和map的key值来进行比较

仿函数也是一个类，是一个类对象，仿函数要重载operator( )

map:

set:

RBTree:

关系图

查找过程我们就可以套上仿函数来进行数据的比较了

迭代器

接下来我们要封装迭代器，红黑树的正向迭代器是对结点指针进行封装，所以这里只有一个成员变量

了解：set和map，set的值不可以修改，set的底层是将const迭代器定义成普通迭代器和const迭代器，而mapkey值不可以修改，而value值可以修改，map底层是用const来修饰map'的key值

* 解引用操作，返回对应结点的引用

->成员访问符，返回节点数据的引用

!= ==判断

++迭代器

--迭代器

set的实现

注意：typename：没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型

map的实现

map比set多了一个[ ]的实现

红黑树的代码

值得注意的是

这里返回的Node*创建的键值对

通过pair构造，如果first类型一样就是拷贝，如果不一样就是构造

完整代码

Myset.h

#pragma once#include "RBTree.h"namespace www
{template<class K>class set{public:struct SetKeyofT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyofT>::const_iterator const_iterator;iterator begin()const{return _it.begin();}iterator end()const{return _it.end();}pair<iterator, bool> insert(const K& key){return _it.Insert(key);}private:RBTree<K, K,SetKeyofT> _it;};
}

Mymap.h

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

RBTree.h

#pragma once
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode                       //三叉链结构
{RBTreeNode<T>* _left;RBTreeNode<T>* _parent;RBTreeNode<T>* _right;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _parent(nullptr), _right(nullptr), _data(data), _col(RED){  }
};//迭代器封装
template<class T,class Ref,class Ptr>
struct _RBTreeiterator
{typedef _RBTreeiterator<T, Ref, Ptr> Self;typedef RBTreeNode<T> Node;Node* _node;_RBTreeiterator(Node* node):_node(node){ }Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){	//右子树不为空//++下一个结点就是右子树的最左节点if (_node->_right){Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}//右子树为空//++下一个几点就是沿着根路径孩子是父亲左的那个祖先else{Node* cur = _node;Node* parent = _node->_parent;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->_right){cur = cur->_right;}_node = cur;}//左子树为空//--下一个结点就是沿着根路径孩子是父亲右的那个祖先else{Node* cur = _node;Node* parent = _node->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};template<class K, class T,class KeyofT>
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<Node*,bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root,true);}KeyofT kot;    //定义仿函数对象Node* cur = _root;Node* parent = nullptr;//寻找插入位置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(cur, false);}}//插入cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//调整//1.父亲为黑不需要调整//2.父亲为红需要调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//新增结点在左子树//      g//   p     u//   cif (parent == grandfather->_left){//1.uncle存在且为红色Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//2.uncle不存在或uncle存在且为黑色//             g//         p//      celse{if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//旋转RotateL(parent);RotateR(grandfather);//变色grandfather->_col = RED;cur->_col = BLACK;}break;}}else{//1.uncle存在且为红色Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//uncle不存在或者存在且为黑else{//插入在parent的右边if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;Node* parentparent = parent->_parent;if (subLR)subLR->_parent = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentparent->_left == parent){parentparent->_left = subL;}else{parentparent->_right = subL;}subL->_parent = parentparent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentparent = parent->_parent;if (subRL)subRL->_parent = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentparent->_left == parent){parentparent->_left = subR;}else{parentparent->_right = subR;}subR->_parent = parentparent;}}bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root == nullptr){return true;}if (root->_col != BLACK){return false;}Node* cur = _root;int benmark = 0;while (cur){if (cur->_col == BLACK){++benmark;}cur = cur->_left;}return _IsValidRBTRee(_root, 0, benmark);}bool _IsValidRBTRee(Node* root, int blacknum, int benmark){if (root == nullptr){if (blacknum != benmark){return false;}return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent->_col == RED){cout << "连续红结点" << endl;return false;}return _IsValidRBTRee(root->_left, blacknum, benmark)&& _IsValidRBTRee(root->_right, blacknum, benmark);}int Size(){return _Size(_root);}int _Size(Node* root){if (root == nullptr){return 0;}return _Size(root->_left) + _Size(root->_right) + 1;}void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ' ';_Inorder(root->_right);}private:Node* _root = nullptr;
};

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;#include "Mymap.h"
#include "Myset.h"
#include "RBTree.h"void test_map()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };www::map<int, int> m;for (auto e : a){m.insert(make_pair(e, e));}www::map<int, int>::iterator it = m.begin();/*while (it != m.end()){it->second++;cout << it->first << ":" << it->second << endl;++it;}*/cout << endl;www::map<string, int> countMap;string arr[] = { "苹果","西瓜","香蕉","苹果" };for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}void test_set()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };www::set<int> s;for (auto e : a){s.insert(e);}www::set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << *it;cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{//test_map();test_set();return 0;
}