app与网站的关系,做网络调查的网站赚钱,广告传媒公司是做什么的,纷享销客个人主页#xff1a;仍有未知等待探索-CSDN博客 专题分栏#xff1a;C 一、简介
map和set都是关联性容器#xff0c;底层都是用红黑树写的。
特点#xff1a;存的Key值都是唯一的#xff0c;不重复。
map存的是键值对#xff08;Key—Value#xff09;。
set存的是键… 个人主页仍有未知等待探索-CSDN博客 专题分栏C 一、简介
map和set都是关联性容器底层都是用红黑树写的。
特点存的Key值都是唯一的不重复。
map存的是键值对Key—Value。
set存的是键值Key。
二、map/set的模拟实现 map.h
#pragma once#include iostream
#include RBTree.h
using namespace std;templateclass Key, class Value
class map
{struct MapKeyOfT{const Key operator()(const pairKey, Value e){return e.first;}};public:typedef pairKey, Value PKV;typedef _RBTree_iteratorPKV, PKV*, PKV iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pairKey, Value e){return _t.insert(e);}void inorder(){_t.inorder();}
private:RBTreeKey, pairKey, Value, MapKeyOfT _t;
};set.h
#pragma once#include RBTree.htemplateclass Key
class set
{struct SetKeyOfT{const Key operator()(const Key e){return e;}};
public :typedef _RBTree_iteratorKey, Key*, Key iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const Key e){return _t.insert(e);}void inorder(){_t.inorder();}
private:RBTreeKey, Key, SetKeyOfT _t;
};
RBTree.h
#pragma once#includeiostream
using namespace std;enum color
{Red,Black
};
template class ValueTpye
struct RBTreeNode
{RBTreeNode(const ValueTpye e ValueTpye()):_left(nullptr),_right(nullptr),_parent(nullptr),_col(Red),_val(e){}struct RBTreeNodeValueTpye* _left;struct RBTreeNodeValueTpye* _right;struct RBTreeNodeValueTpye* _parent;int _col;ValueTpye _val;
};templateclass ValueType, class Ptr, class Ref
class _RBTree_iterator
{typedef RBTreeNodeValueType node;typedef _RBTree_iteratorValueType, Ptr, Ref iterator;
public:_RBTree_iterator(node* e):_node(e){}Ptr operator-(){return _node-_val;}Ref operator*(){return _node-_val;}bool operator!(iterator it){return _node ! it._node;}iterator operator(){if (_node-_right){node* left _node-_right;while (left-_left){left left-_left;}_node left;}else{node* cur _node;node* p cur-_parent;while (p cur p-_right){cur p;p p-_parent;}_node p;}return *this;}
private:node* _node;
};template class Key, class ValueType, class KeyOfT
class RBTree
{
public:typedef RBTreeNodeValueType node;typedef _RBTree_iteratorValueType, ValueType*, ValueType iterator;KeyOfT kot;RBTree():_root(nullptr){}iterator begin(){node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}node* find(const Key e){node* cur _root;while (cur){if (kot(cur-_val).first e){cur cur-_left;}else if (kot(cur-_val).first e){cur cur-_right;}else{return cur;}}return nullptr;}bool insert(const ValueType e){// 根据二叉搜索树插入的方式进行插入node* cur _root;node* parent cur;while (cur){parent cur;if (kot(cur-_val) kot(e)){cur cur-_left;}else if (kot(cur-_val) kot(e)){cur cur-_right;}else{return false;}}cur new node(e);if (parent nullptr){_root cur;}else{if (kot(parent-_val) kot(cur-_val)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;}// 更新对于不同的情况进行不同的调整// parent 为黑、不存在结束node* p parent;while (p p-_col Red){node* g p-_parent;if (g-_left p){node* u g-_right;// 叔叔存在且为红if (u u-_col Red){p-_col u-_col Black;g-_col Red;// 继续往上处理cur g;p cur-_parent;}// 叔叔不存在且为黑else {// g// p u// cif (cur p-_left){// 右单旋RotateR(g);// 变色g-_col Red;p-_col Black;}// g// p u// celse {// 左右双旋RotateL(p);RotateR(g);// 变色cur-_col Black;g-_col Red;}// 叔叔不存在或者存在且为黑调整完就不需要继续进行调整了break;}}else{node* u g-_left;if (u u-_col Red){p-_col u-_col Black;g-_col Red;// 继续往上处理cur g;p cur-_parent;}else {// g// u p// cif (cur p-_right){// 左单旋RotateL(g);// 变色g-_col Red;p-_col Black;}// g// u p// celse {// 左右双旋RotateR(p);RotateL(g);// 变色cur-_col Black;g-_col Red;}// 叔叔不存在或者存在且为黑调整完就不需要继续进行调整了break;}}}_root-_col Black;return true;}void inorder(){_inorder(_root);}
private:void _inorder(node* root){if (root nullptr) return;_inorder(root-_left);cout kot(root-_val) ;_inorder(root-_right);}void RotateR(node* parent){node* subl parent-_left;node* sublr subl-_right;node* grandfather parent-_parent;parent-_left sublr;if (sublr){sublr-_parent parent;}subl-_right parent;parent-_parent subl;subl -_parent grandfather;if (_root parent){if (grandfather-_left parent){grandfather-_left subl;}else{grandfather-_right subl;}}else{_root subl;}}void RotateL(node* parent){node* subr parent-_right;node* subrl subr-_left;node* grandfather parent-_parent;parent-_right subrl;if (subrl){subrl-_parent parent;}subr-_left parent;parent-_parent subr;subr -_parent grandfather;if (_root ! parent){if (grandfather-_left parent){grandfather-_left subr;}else{grandfather-_right subr;}}else{_root subr;}}private:node* _root;
};
main.cpp测试
#define _CRT_SECURE_NO_WARNINGS 1#include map.h
#include set.h
//#include map
//#include set
#include iostream
using namespace std;void test1()
{int a[] {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};mapint, int m;for (int e : a){m.insert(make_pair(e, e));}m.inorder();
}void test2()
{int a[] {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};setint s;for (int e : a){s.insert(e);}s.inorder();
}void test3()
{int a[] {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};setint s;for (int e : a){s.insert(e);}auto it s.begin();while (it ! s.end()){cout *it endl; it;}
}void test4()
{pairint, int a[] {{5, 5}, {3, 3}, {7, 7}, {3, 3}, {7, 7}, {8, 8}, {4, 4}, {2, 2}, {9, 9}, {10, 10}};setpairint, int s;for (auto e : a){s.insert(e);}auto it s.begin();while (it ! s.end()){cout (*it).first (*it).second endl; it;}
}
int main()
{test1();return 0;
}
