map,set的封装

admin管理员组

文章数量:1122906

map,set的封装

相信大家都对map,set不会陌生，这是非常好用的容器，它的底层是红黑树，红黑树在数据结构中，个人感觉是比较难的一种数据结构，尤其是一会染色，一会旋转的，弄来弄去把人给弄晕了。而我想说的是，红黑树不仅实现难，封装起来也不简单，下面是封装的代码：

#pragma once
#include<iostream>
#include<map>
#include<set>
#include<time.h>
#include<string>
using namespace std;
namespace RB
{template<class T, class ref, class ptr>struct Iterator;enum colous{RED,BLACK};template<class T>struct RbTreeNode{T _data;colous _col = RED;RbTreeNode<T>* _left = nullptr;RbTreeNode<T>* _right = nullptr;RbTreeNode<T>* _parent = nullptr;RbTreeNode(const T& x):_data(x){}};template<class K,class T,class KofT>class RbTree{typedef RbTreeNode<T> node;typedef Iterator<T, T&, T*> iterator;public:void reol(node* parent){node* sub = parent->_right;node* subl = sub->_left;if (_root == parent){_root = sub;sub->_parent = nullptr;sub->_left = parent;parent->_parent = sub;parent->_right = subl;if (subl)subl->_parent = parent;return;}node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = sub;elsepparent->_right = sub;sub->_parent = pparent;sub->_left = parent;parent->_parent = sub;parent->_right = subl;if (subl)subl->_parent = parent;}void reor(node* parent){node* sub = parent->_left;node* subr = sub->_right;if (_root == parent){_root = sub;sub->_parent = nullptr;sub->_right = parent;parent->_parent = sub;parent->_left = subr;if (subr)subr->_parent = parent;return;}node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = sub;elsepparent->_right = sub;sub->_parent = pparent;sub->_right = parent;parent->_parent = sub;parent->_left = subr;if (subr)subr->_parent = parent;}pair<iterator,bool> insert(const T& x){if (_root == nullptr){_root = new node(x);_root->_col = BLACK;return make_pair(iterator(_root), true);}node* parent = nullptr;node* cur = _root;while (cur){parent = cur;if (kot(x) < kot(cur->_data))cur = cur->_left;else if (kot(x) > kot(cur->_data))cur = cur->_right;elsereturn make_pair(iterator(cur), false);}cur = new node(x);if (x < parent->_data)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;node* grandfather = parent->_parent;while (parent && parent->_col != BLACK){if (grandfather->_left == parent){node* uncle = grandfather->_right;//染色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;if (grandfather == _root){grandfather->_col = BLACK;break;}}//染色+旋转else if (uncle && uncle->_col == BLACK){//染色+单旋if (parent->_left == cur){reor(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//染色+双旋else{reol(parent);reor(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}//叔叔节点不存在else{//染色+单旋if (parent->_left == cur){reor(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//染色+双旋else{reol(parent);reor(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;if (grandfather == _root){grandfather->_col = BLACK;break;}}else if (uncle && uncle->_col == BLACK){if (parent->_left == cur){reor(parent);reol(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else{reol(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}//叔叔节点不存在else{//染色+单旋if (parent->_left == cur){reor(parent);reol(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//染色+双旋else{reol(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}}cur = grandfather;parent = cur->_parent;grandfather = parent->_parent;}return make_pair(iterator(cur), true);}iterator find(const K& key){if (_root == nullptr)return  iterator(nullptr);node* cur = _root;while (cur){if (key < kot(cur->_data))cur = cur->_left;else if (key > kot(cur->_data))cur = cur->_right;elsereturn iterator(cur);}return iterator(nullptr);}iterator begin(){node* cur = _root;while (cur->_left)cur = cur->_left;return iterator(cur);}iterator end(){return iterator(nullptr);}//下面是测试红黑树是否正确的函数/*void print(node* root,int num){if (root == nullptr){cout << num << endl;return;}if (root->_col == BLACK)num++;print(root->_left, num);print(root->_right, num);}void prin(){int num = 0;print(_root, num);}*/private:node* _root = nullptr;KofT kot;};template<class T,class ref,class ptr>struct Iterator{typedef RbTreeNode<T> node;node* _it;Iterator(node* x):_it(x){}bool operator!=(const Iterator<T,ref,ptr>& x)const{return _it != x._it;}ref operator*()const{return _it->_data;}ptr operator->(){return &_it->_data;}Iterator<T,ref,ptr>& operator++(){//右孩子不为空if (_it->_right){node* cur = _it->_right;while (cur->_left)cur = cur->_left;_it = cur;return *this;}//右孩子为空else{//找父节点不是祖父节点的右孩子的节点node* parent = _it->_parent;if (parent->_left == _it){_it = parent;return *this;}else{node* pparent = parent->_parent;while (pparent){if (pparent->_left == parent){_it = pparent;return *this;}else{parent = pparent;pparent = pparent->_parent;}}_it = nullptr;return *this;					}}}};
}

#pragma once
#include "rbtree.h"
namespace cc
{//可以写成内部类template<class K>struct setfunc{const K& operator()(const K& key){return key;}};template<class K>class set{public:typedef RB::RbTreeNode<K> node;typedef RB::Iterator<K, K&, K*> iterator;pair<iterator,bool> insert(const K& x){return Rbtree.insert(x);}iterator find(const K& key){return Rbtree.find(key);}iterator begin(){return Rbtree.begin();}iterator end(){return Rbtree.end();}private:RB::RbTree<K, K, setfunc<K>> Rbtree;};
}

#pragma once
#include "rbtree.h"
namespace cc
{//可以写成内部类template<class K,class V>struct mapfunc{const K& operator()(const pair<K,V>& key){return key.first;}};template<class K,class V>class map{public:typedef RB::RbTreeNode<pair<K, V>> node;typedef RB::Iterator<pair<K, V>, pair<K, V>&, pair<K, V>*> iterator;pair<iterator,bool> insert(const pair<K, V>& x){return Rbtree.insert(x);}iterator find(const K& key){return Rbtree.find(key);}iterator begin(){return Rbtree.begin();}iterator end(){return Rbtree.end();}V& operator[](const K& x){return Rbtree.insert(make_pair(x, V())).first->second;}private:RB::RbTree<K, pair<K, V>, mapfunc<K,V>> Rbtree;};
}

#include"rbtree.h"
#include "map.hpp"
#include "set.h"
void test1()
{//RB::RbTree<int> rb;//srand(time(0));//for (size_t i = 0; i < 100; i++)//	rb.insert(rand());///*rb.insert(1);//rb.insert(2);//rb.insert(3);//rb.insert(4);//rb.insert(5);//rb.insert(6);//rb.insert(7);//rb.insert(8);//rb.insert(9);//rb.insert(10);*///rb.prin();
}
void test2()
{/*cc::map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(2, 1));m.insert(make_pair(3, 1));m.insert(make_pair(4, 1));m.insert(make_pair(5, 1));m.insert(make_pair(6, 1));m.insert(make_pair(7, 1));m.insert(make_pair(8, 1));m.insert(make_pair(9, 1));m.insert(make_pair(10, 1));m.insert(make_pair(11, 1));m.insert(make_pair(12, 1));m.insert(make_pair(13, 1));m.insert(make_pair(14, 1));m.insert(make_pair(15, 1));m.find(5);cc::map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << endl;++it;}*/cc::map<string, int> m;///*int arr[] = { 1,1,1,1,1,1,1,1 };//for (auto e : arr)//	m[e]++;*/string arr[] = { "苹果","香蕉","梨","苹果","香蕉","香蕉" };for (auto& e : arr)m[e]++;//for (auto& e : m)//cout << e.first << ":" << e.second << endl;auto it = m.begin();for (auto& e : m)cout << e.first << ":" << e.second << endl;}
void test3()
{srand(time(0));cc::map<int, int> m;for (size_t i = 0; i < 1000; i++){static int x = rand() % 1000;m[x++]++;}for (auto& e : m)cout << e.first << ":" << e.second << endl;
}
void test4()
{cc::set<int> s;/*s.insert(1);s.insert(2);s.insert(3);s.insert(5);s.insert(2);s.insert(10);for (auto e : s){cout << e << endl;}*/for (size_t i = 0; i < 1000; i++){s.insert(rand());}for (auto e : s)cout << e << endl;
}
int main()
{//test1();//test2();//test3();test4();return 0;
}

上面是我的封装过程以及代码实现，其实我昨天封装了unordered_map,unordered_set这两个容器，今天封装map,set就感觉简单不少，但是也不是简单。其他的没啥要注意的地方，唯一一个要注意的就是迭代器，迭代器怎么说，还是要动一会脑子的。

首先就是，判断当前节点的右子树是不是空树，如果不是空树的话，那么代表的这个节点以及这个节点的做左子树已经访问完成，而右子树不为空，所还没有访问完这颗树，所以++之后就要找右子树的最左节点。而难得是如果右子树为空的话，那么就代表已经访问完了这课子树的所有节点，所以找他的父节点，而父节点应该已经是被访问了，所以就向上遍历，直到找到父节点不是祖父节点右孩子的节点为止。

这个思想还是有点绕人的，再就是其他的封装，如果看了我上一篇文章内容的伙伴，封装map,set应该还是很简单的。

希望大家支持一下吧！！谢谢！

本文标签： mAPset的封装