C++中map_set的封装实现整体代码

前言以前理解的 set 是 keymap 是 key_value似乎是 2 棵树但其实他俩用同一个类模板一. 源码剖析set123#include stl_tree.h#include stl_set.h#include stl_multiset.hset 和 map 是一层浅浅的封装核心都在树里实现stl_set.h12345678910templateclassKey,classCompare lessKey,classAlloc allocclassset {public:typedefKey key_type;typedefKey value_type;private:typedefrb_treekey_type, value_type,// K, Kidentityvalue_type, key_compare, Alloc rep_type;rep_type t;// red-black tree representing set}stl_map.h12345678910templateclassKey,classT,classCompare lessKey,classAlloc allocclassmap {public:typedefKey key_type;typedefpairconstKey, T value_type;private:typedefrb_treekey_type, value_type,// K, pairK, Vselect1stvalue_type, key_compare, Alloc rep_type;rep_type t;// red-black tree representing map}stl_tree.h123456789101112131415161718192021222324252627282930313233struct__rb_tree_node_base{typedef__rb_tree_color_type color_type;typedef__rb_tree_node_base* base_ptr;color_type color;base_ptr parent;base_ptr left;base_ptr right;};templateclassValuestruct__rb_tree_node :public__rb_tree_node_base{typedef__rb_tree_nodeValue* link_type;Value value_field;};templateclassKey,classValue,classKeyOfValue,classCompare,classAlloc allocclassrb_tree {protected:typedef__rb_tree_nodeValue rb_tree_node;public:typedefKey key_type;typedefValue value_type;typedefrb_tree_node* link_type;protected:size_type node_count;// keeps track of size of treelink_type header;Compare key_compare;}link_type 是节点的指针树的节点里存第二个模板参数 Value 这个不是真 value对 map 而言value_type 传给 Value 的是 pairK, V树的节点存的是 pairK, V对 set 而言value_type 传给 Value 的是 K树的节点存的是 K用Value做 __rb_tree_node 的模板参数决定了树节点 node 里面存什么二. 逐步实现1. 框架MySet.h12345678910#include RBTree.hnamespaceqtw{templateclassKclassset{private:RBTreeK, K _t;};}MyMap.h12345678910#include RBTree.hnamespaceqtw{templateclassK,classVclassmap{private:RBTreeK, pairK, V _t;};}RBTree.h12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455enumColour { RED, BLACK };templateclassTstructRBTreeNode{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;T _data;RBTreeNode(constT data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){ }};templateclassK,classTclassRBTree{typedefRBTreeNodeT Node;public:boolInsert(constT data){if(_root nullptr){_root newNode(data);_root-_col BLACK;returntrue;}Node* cur _root;Node* parent nullptr;while(cur){if(cur-_data data){parent cur;cur cur-_right;}elseif(cur-_data data){parent cur;cur cur-_left;}else{returnfalse;}}// ......}39 44 行不能用 data 直接比较。set 可以map 不期望用 pair期望用 pair.first 比较库里重载了 pair 的比较first 小或 second 小但不符合我们的需求