C进阶红黑树封装map/set 哈希表unordered系列容器详解本文基于SGI-STL源码思想完整实现红黑树封装map/set并对比讲解unordered_map/unordered_set使用与底层差异代码可直接编译运行适合C后端/STL源码学习。文章目录C进阶红黑树封装map/set 哈希表unordered系列容器详解一、前言STL关联式容器底层二、红黑树封装 map / set 核心思想2.1 关键设计点三、完整代码实现可直接运行3.1 红黑树结点与颜色定义3.2 红黑树迭代器实现3.3 红黑树主体插入旋转平衡3.4 封装 set3.5 封装 map含 operator[]3.6 测试代码四、unordered_map / unordered_set 使用与对比4.1 底层结构4.2 与红黑树容器核心差异4.3 使用示例五、总结一、前言STL关联式容器底层C STL 关联式容器分为两大派系红黑树派系map/set/multimap/multiset——有序、去重、O(logN)哈希表派系unordered_map/unordered_set——无序、去重、平均O(1)本文先从红黑树封装map/set讲起再对比哈希表unordered系列带你吃透底层设计。二、红黑树封装 map / set 核心思想SGI-STL 中map/set 底层共用一棵红黑树通过泛型仿函数解耦实现一套红黑树支撑两种容器set只存 key → 红黑树结点存Keymap存 key-value → 红黑树结点存pairconst Key, Value比较时只比 key通过仿函数从结点数据中提取 key2.1 关键设计点红黑树模板参数templateclassK,classT,classKeyOfTclassRBTree;K查找用的 key 类型T结点实际存储数据setKmappairconst K,VKeyOfT仿函数从 T 中提取 key 用于比较set 封装提取自身作为 keymap 封装提取 pair.first 作为 key迭代器中序遍历模拟指针行为map operator[]插入返回 value 引用三、完整代码实现可直接运行3.1 红黑树结点与颜色定义#pragmaonce#includeiostream#includeutilityusingnamespacestd;enumColour{RED,BLACK};// 红黑树结点templateclassTstructRBTreeNode{T _data;RBTreeNodeT*_left;RBTreeNodeT*_right;RBTreeNodeT*_parent;Colour _col;RBTreeNode(constTdata):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)// 新结点默认红色{}};3.2 红黑树迭代器实现// 红黑树迭代器templateclassT,classRef,classPtrstructRBTreeIterator{typedefRBTreeNodeTNode;typedefRBTreeIteratorT,Ref,PtrSelf;Node*_node;Node*_root;RBTreeIterator(Node*node,Node*root):_node(node),_root(root){}// 中序下一个Selfoperator(){if(_node-_right){// 右子树最左结点Node*leftMost_node-_right;while(leftMost-_left)leftMostleftMost-_left;_nodeleftMost;}else{// 向上找孩子是父亲左的祖先Node*cur_node;Node*parentcur-_parent;while(parentcurparent-_right){curparent;parentcur-_parent;}_nodeparent;}return*this;}// --中序上一个Selfoperator--(){if(_nodenullptr)// --end(){Node*rightMost_root;while(rightMostrightMost-_right)rightMostrightMost-_right;_noderightMost;}elseif(_node-_left){// 左子树最右结点Node*rightMost_node-_left;while(rightMost-_right)rightMostrightMost-_right;_noderightMost;}else{// 向上找孩子是父亲右的祖先Node*cur_node;Node*parentcur-_parent;while(parentcurparent-_left){curparent;parentcur-_parent;}_nodeparent;}return*this;}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}};3.3 红黑树主体插入旋转平衡templateclassK,classT,classKeyOfTclassRBTree{typedefRBTreeNodeTNode;public:typedefRBTreeIteratorT,T,T*Iterator;typedefRBTreeIteratorT,constT,constT*ConstIterator;IteratorBegin(){Node*leftMost_root;while(leftMostleftMost-_left)leftMostleftMost-_left;returnIterator(leftMost,_root);}IteratorEnd(){returnIterator(nullptr,_root);}ConstIteratorBegin()const{Node*leftMost_root;while(leftMostleftMost-_left)leftMostleftMost-_left;returnConstIterator(leftMost,_root);}ConstIteratorEnd()const{returnConstIterator(nullptr,_root);}// 插入返回迭代器, 是否插入成功pairIterator,boolInsert(constTdata){if(_rootnullptr){_rootnewNode(data);_root-_colBLACK;returnmake_pair(Iterator(_root,_root),true);}KeyOfT kot;Node*parentnullptr;Node*cur_root;// 1. 搜索插入位置while(cur){if(kot(cur-_data)kot(data)){parentcur;curcur-_right;}elseif(kot(cur-_data)kot(data)){parentcur;curcur-_left;}else// 已存在returnmake_pair(Iterator(cur,_root),false);}// 2. 插入新结点curnewNode(data);Node*newNodecur;cur-_colRED;if(kot(parent-_data)kot(data))parent-_rightcur;elseparent-_leftcur;cur-_parentparent;// 3. 平衡调整while(parentparent-_colRED){Node*grandfatherparent-_parent;if(parentgrandfather-_left){Node*unclegrandfather-_right;// 情况1叔叔存在且为红 → 变色if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else// 情况2/3叔叔黑或不存在 → 旋转{if(curparent-_left){RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else// 对称parent在右{Node*unclegrandfather-_left;if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;returnmake_pair(Iterator(newNode,_root),true);}// 查找IteratorFind(constKkey){Node*cur_root;KeyOfT kot;while(cur){if(kot(cur-_data)key)curcur-_right;elseif(kot(cur-_data)key)curcur-_left;elsereturnIterator(cur,_root);}returnEnd();}private:// 左单旋voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*ppparent-_parent;subR-_leftparent;parent-_parentsubR;if(ppnullptr){_rootsubR;subR-_parentnullptr;}else{if(pp-_leftparent)pp-_leftsubR;elsepp-_rightsubR;subR-_parentpp;}}// 右单旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR)subLR-_parentparent;Node*ppparent-_parent;subL-_rightparent;parent-_parentsubL;if(ppnullptr){_rootsubL;subL-_parentnullptr;}else{if(pp-_leftparent)pp-_leftsubL;elsepp-_rightsubL;subL-_parentpp;}}voidDestroy(Node*root){if(rootnullptr)return;Destroy(root-_left);Destroy(root-_right);deleteroot;}private:Node*_rootnullptr;};3.4 封装 set#pragmaonce#includeRBTree.hnamespacebit{templateclassKclassset{// 仿函数从key提取keystructSetKeyOfT{constKoperator()(constKkey){returnkey;}};public:typedeftypenameRBTreeK,constK,SetKeyOfT::Iterator iterator;typedeftypenameRBTreeK,constK,SetKeyOfT::ConstIterator const_iterator;iteratorbegin(){return_t.Begin();}iteratorend(){return_t.End();}const_iteratorbegin()const{return_t.Begin();}const_iteratorend()const{return_t.End();}pairiterator,boolinsert(constKkey){return_t.Insert(key);}iteratorfind(constKkey){return_t.Find(key);}private:RBTreeK,constK,SetKeyOfT_t;};}3.5 封装 map含 operator[]#pragmaonce#includeRBTree.hnamespacebit{templateclassK,classVclassmap{// 仿函数从pair提取keystructMapKeyOfT{constKoperator()(constpairK,Vkv){returnkv.first;}};public:typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::Iterator iterator;typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::ConstIterator const_iterator;iteratorbegin(){return_t.Begin();}iteratorend(){return_t.End();}const_iteratorbegin()const{return_t.Begin();}const_iteratorend()const{return_t.End();}pairiterator,boolinsert(constpairK,Vkv){return_t.Insert(kv);}iteratorfind(constKkey){return_t.Find(key);}// map核心operator[]Voperator[](sslocal://flow/file_open?urlconstK%26keyflow_extraeyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0){pairiterator,boolretinsert(make_pair(key,V()));returnret.first-second;}private:RBTreeK,pairconstK,V,MapKeyOfT_t;};}3.6 测试代码#includeMySet.h#includeMyMap.hvoidtest_set(){bit::setints;intarr[]{4,2,6,1,3,5,15,7,16,14};for(autoe:arr)s.insert(e);// 遍历有序for(autoe:s)coute ;coutendl;}voidtest_map(){bit::mapstring,stringdict;dict.insert({sort,排序});dict.insert({left,左边});dict[right]右边;dict[insert]插入;for(autokv:dict)coutkv.first : kv.secondendl;}intmain(){test_set();test_map();return0;}四、unordered_map / unordered_set 使用与对比4.1 底层结构unordered_map/unordered_set哈希桶拉链法平均O(1)最坏O(N)哈希冲突严重遍历无序4.2 与红黑树容器核心差异特性map/setunordered_map/unordered_set底层红黑树哈希表拉链法顺序有序中序无序查找效率O(logN)平均O(1)key要求支持 比较支持哈希、 比较迭代器类型双向迭代器单向迭代器内存占用较低较高哈希桶空间4.3 使用示例#includeunordered_map#includeunordered_set#includeiostreamusingnamespacestd;voidtest_unordered(){unordered_setintus;us.insert(1);us.insert(3);us.insert(2);for(autoe:us)coute ;// 无序unordered_mapstring,intum;um[a]1;um[b]2;coutum[a]endl;}五、总结map/set 复用红黑树通过泛型仿函数提取 key一套代码支撑两种容器。迭代器本质中序遍历模拟指针/-- 严格遵循中序规则。map operator[]insert 返回 value 引用是日常高频用法。unordered 系列哈希表实现无序、更快适合纯查找场景。