怎么免费做公司网站,文山网站建设哪家好,做网站入什么会计科目,品牌网页设计1.Map和Set的简单介绍 Map和set没有多大区别#xff0c;它俩都是键值对容器#xff0c;即该结构中一般只包含两个成员key#xff0c;value#xff0c;key代表键值#xff0c;value表示与key对应的信息。并且这两个容器为树型结构的关联式容器#xff0c;这两种容器的共同…1.Map和Set的简单介绍 Map和set没有多大区别它俩都是键值对容器即该结构中一般只包含两个成员keyvaluekey代表键值value表示与key对应的信息。并且这两个容器为树型结构的关联式容器这两种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。 Set的介绍 set是按照一定次序存储元素的容器。 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。 注意 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列set中的元素默认按照小于来比较set中查找某个元素时间复杂度为$log_2 n$set中的元素不允许修改set中的底层使用二叉搜索树(红黑树)来实现 Map的介绍 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。 map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 2.Map和Set的实现
由于Map和Set的底层都为红黑树所以Map和Set的实现通过对红黑树的封装来实现Set为一个参数Map为两个参数所以通过改变模板来实现Map和Set的同时封装。
Set的简单封装
namespace sss
{templateclass Kclass Set{struct SetKeyofT{const K operator()(const K date){return date;}}; public:typedef typename RedBlackTreeK, K, SetKeyofT::iterator iterator;iterator begin(){return _S.begin();}iterator end(){return _S.end();}pairiterator, bool Insert(const K date){return _S.insert(date);}private:RedBlackTreeK, K, SetKeyofT _S;};//测试用例/*void text_set(){string str[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };Setstring hash;for (auto sh : str){hash.Insert(sh);}auto it hash.begin();while (it ! hash.end()){cout *it endl;it;}}*/}
Map的简单封装
namespace sss
{templateclass K,class V class Map{public:struct MapKeyofT{const K operator()(const pairK, V date){return date.first;}};typedef typename RedBlackTreeK, pairK, V, MapKeyofT::iterator iterator;//t//ypedef RedBlackTreeK, pairK, V, MapKeyofT RedBlackTree;iterator begin() {return _T.begin();}iterator end(){return _T.end();}pairiterator, bool Insert(const pairK,V date){return _T.insert(date);}V operator[](const K key){pairiterator, bool ret Insert(make_pair(key, V()));return ret.first-second;}private:RedBlackTreeK,pairK,V, MapKeyofT _T;};//测试用例//void text_map()//{// Mapint, int hash1;// hash1.Insert(make_pair(1,1));// couthash1[1];// Mapstring, int hash2;// string str[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };// for (auto sh:str)// {// hash2[sh];// }// Mapstring, int::iterator it hash2.begin();// while (it ! hash2.end())// {// cout it-first : it-second endl;// it;// }// for (auto kv : hash2)// {// cout kv.first : kv.second endl;// }// //hash1 hash2;// //}
}
底层实现
namespace sss
{enum Color{red,black};templateclass Tstruct RedBlackTreeNode{RedBlackTreeNodeT* _left;RedBlackTreeNodeT* _right;RedBlackTreeNodeT* _parent;//pairK, V _date;T _date;Color _col;RedBlackTreeNode(const T dateT()):_left(nullptr),_right(nullptr),_parent(nullptr),_date(date)//, _col(black){}};templateclass T, class Ref, class Ptrstruct __RBTreeIterator{typedef RedBlackTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node-_date;}Ptr operator-(){return _node-_date;}bool operator!(const Self _t){return _node ! _t._node;}bool operator(const Self _t){return _node _t._node;}Self* operator(){if (_node-_right){Node* cur _node;cur cur-_right;while (cur-_left){cur cur-_left;}_nodecur;}else{Node* parent _node-_parent;Node* cur _node;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_nodeparent;}return this;}Self* operator--(){if (_node-_left){Node* cur _node;cur cur-_left;while (cur-_right){cur cur-_right;}_nodecur;}else{Node* parent _node-_parent;Node* cur _node;while (parent cur parent-left){parent parent-_parent;cur parent;}_node parent;}return this;}};templateclass K, class T, class KeyofTclass RedBlackTree{typedef RedBlackTreeNodeT Node;public: typedef __RBTreeIteratorT, T, T* iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}//插入pairiterator,bool insert(const T date){KeyofT _com;if (_root nullptr){_root new Node(date);_root-_col black;return make_pair(iterator(_root), true);}Node* parent nullptr;Node* cur _root;while (cur){if (_com(cur-_date) _com(date)){parent cur;cur cur-_right;}else if (_com(cur-_date) _com(date)){parent cur;cur cur-_left;}else{return make_pair(iterator(cur), false);}}cur new Node(date);cur-_col red;if (_com(parent-_date) _com(date)){parent-_right cur;}else {parent-_left cur;}cur-_parent parent;//Node* uncleparent-_parent-while(parent parent-_col red){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_colblack);if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col black;grandfater-_col red;}break;}}else{Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col black;grandfater-_col red;}break;}}}_root-_col black;return make_pair(iterator(cur), true);}void Inorder(){_Inorder(_root);}private://右旋void RotateR(Node* parent){Node* subl parent-_left;Node* sublr subl-_right;Node* prev parent-_parent;parent-_left sublr;if (sublr)sublr-_parent parent;parent-_parent subl;subl-_right parent;if (_root parent){_root subl;subl-_parent nullptr;}else{if (prev-_left parent){subl-_parent prev;prev-_left subl;}else{subl-_parent prev;prev-_right subl;}}}//左旋void RotateL(Node* parent){Node* subr parent-_right;Node* subrl subr-_left;Node* prev parent-_parent;parent-_right subrl;if (subrl)subrl-_parent parent;subr-_left parent;parent-_parent subr;if (_root parent){_root subr;subr-_parent nullptr;}else{if (prev-_left parent){subr-_parent prev;prev-_left subr;}else{subr-_parent prev;prev-_right subr;}}}//遍历void _Inorder(Node* _root){if (_root nullptr)return;_Inorder(_root-_left);cout _root-_date.first _root-_date.second endl;_Inorder(_root-_right);}private:Node* _root nullptr;};}
完整代码
//在不同平台下需加不同头文件
#pragma once
using namespace std;
#include iostream
#include assert.h
#include RedBlackTree.h
#include stringnamespace sss
{templateclass Kclass Set{struct SetKeyofT{const K operator()(const K date){return date;}}; public:typedef typename RedBlackTreeK, K, SetKeyofT::iterator iterator;iterator begin(){return _S.begin();}iterator end(){return _S.end();}pairiterator, bool Insert(const K date){return _S.insert(date);}private:RedBlackTreeK, K, SetKeyofT _S;};//测试用例/*void text_set(){string str[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };Setstring hash;for (auto sh : str){hash.Insert(sh);}auto it hash.begin();while (it ! hash.end()){cout *it endl;it;}}*/}namespace sss
{templateclass K,class V class Map{public:struct MapKeyofT{const K operator()(const pairK, V date){return date.first;}};typedef typename RedBlackTreeK, pairK, V, MapKeyofT::iterator iterator;//t//ypedef RedBlackTreeK, pairK, V, MapKeyofT RedBlackTree;iterator begin() {return _T.begin();}iterator end(){return _T.end();}pairiterator, bool Insert(const pairK,V date){return _T.insert(date);}V operator[](const K key){pairiterator, bool ret Insert(make_pair(key, V()));return ret.first-second;}private:RedBlackTreeK,pairK,V, MapKeyofT _T;};//测试用例//void text_map()//{// Mapint, int hash1;// hash1.Insert(make_pair(1,1));// couthash1[1];// Mapstring, int hash2;// string str[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };// for (auto sh:str)// {// hash2[sh];// }// Mapstring, int::iterator it hash2.begin();// while (it ! hash2.end())// {// cout it-first : it-second endl;// it;// }// for (auto kv : hash2)// {// cout kv.first : kv.second endl;// }// //hash1 hash2;// //}
}namespace sss
{enum Color{red,black};templateclass Tstruct RedBlackTreeNode{RedBlackTreeNodeT* _left;RedBlackTreeNodeT* _right;RedBlackTreeNodeT* _parent;//pairK, V _date;T _date;Color _col;RedBlackTreeNode(const T dateT()):_left(nullptr),_right(nullptr),_parent(nullptr),_date(date)//, _col(black){}};templateclass T, class Ref, class Ptrstruct __RBTreeIterator{typedef RedBlackTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node-_date;}Ptr operator-(){return _node-_date;}bool operator!(const Self _t){return _node ! _t._node;}bool operator(const Self _t){return _node _t._node;}Self* operator(){if (_node-_right){Node* cur _node;cur cur-_right;while (cur-_left){cur cur-_left;}_nodecur;}else{Node* parent _node-_parent;Node* cur _node;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_nodeparent;}return this;}Self* operator--(){if (_node-_left){Node* cur _node;cur cur-_left;while (cur-_right){cur cur-_right;}_nodecur;}else{Node* parent _node-_parent;Node* cur _node;while (parent cur parent-left){parent parent-_parent;cur parent;}_node parent;}return this;}};templateclass K, class T, class KeyofTclass RedBlackTree{typedef RedBlackTreeNodeT Node;public: typedef __RBTreeIteratorT, T, T* iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}//插入pairiterator,bool insert(const T date){KeyofT _com;if (_root nullptr){_root new Node(date);_root-_col black;return make_pair(iterator(_root), true);}Node* parent nullptr;Node* cur _root;while (cur){if (_com(cur-_date) _com(date)){parent cur;cur cur-_right;}else if (_com(cur-_date) _com(date)){parent cur;cur cur-_left;}else{return make_pair(iterator(cur), false);}}cur new Node(date);cur-_col red;if (_com(parent-_date) _com(date)){parent-_right cur;}else {parent-_left cur;}cur-_parent parent;//Node* uncleparent-_parent-while(parent parent-_col red){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_colblack);if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col black;grandfater-_col red;}break;}}else{Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col black;grandfater-_col red;}break;}}}_root-_col black;return make_pair(iterator(cur), true);}void Inorder(){_Inorder(_root);}private://右旋void RotateR(Node* parent){Node* subl parent-_left;Node* sublr subl-_right;Node* prev parent-_parent;parent-_left sublr;if (sublr)sublr-_parent parent;parent-_parent subl;subl-_right parent;if (_root parent){_root subl;subl-_parent nullptr;}else{if (prev-_left parent){subl-_parent prev;prev-_left subl;}else{subl-_parent prev;prev-_right subl;}}}//左旋void RotateL(Node* parent){Node* subr parent-_right;Node* subrl subr-_left;Node* prev parent-_parent;parent-_right subrl;if (subrl)subrl-_parent parent;subr-_left parent;parent-_parent subr;if (_root parent){_root subr;subr-_parent nullptr;}else{if (prev-_left parent){subr-_parent prev;prev-_left subr;}else{subr-_parent prev;prev-_right subr;}}}//遍历void _Inorder(Node* _root){if (_root nullptr)return;_Inorder(_root-_left);cout _root-_date.first _root-_date.second endl;_Inorder(_root-_right);}private:Node* _root nullptr;};}
