C++效率掌握之STL库：map && set底层剖析及迭代器万字详解

Ne0inhk

— 16 min read
C++效率掌握之STL库：map && set底层剖析及迭代器万字详解

文章目录

map、set 的封装可以说是很天才的底层结构了，本篇将对其结构进行详细的解析，虽然会很复杂且难以理解，但是学完成就感满满，而且对底层理解和面试很有帮助

1.map、set的基本结构

在这里插入图片描述

通过查看官方文档，截取部分关键代码，我们可以发现 set 虽然事 k-k 类型，map 是 k-v 类型，但是实际上这两个类共用一个红黑树，准确来说是共用同一个模板类型，set 是 <K，K>，map 是 <K，pair<K，V>>，下面会进行详细解析

  • size_type node_count：用于记录红黑树节点数量，跟踪树的大小
  • link_type header：是指向红黑树头节点的指针
  • Value value_field：存储节点的值

那么下面我们将自己实现简单的 set 和 map 类：

2.map、set模拟实现

2.1 初步定义

template<classK>classset{private: RBTree<K, K> _t;};template<classK,classV>classmap{private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

平常我们认为键值对指的就是 K 和 V，但是在库里不是这样的，库里的 K 表示键值对的类型，V 表示插入红黑树的键值对，只不过对于 set 来说，K 和 V 是一样的

在这里插入图片描述

在红黑树中，定义的模板参数 T，而不是原先的 pair，这里的 T 表示插入的数据 _data 的类型，这种定义方法能够共同使用同一参数模板，避免额外的代码编写

2.2 仿函数实现

template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};private: RBTree<K, K, SetKeyOfT> _t;};template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

我们知道 set 和 map 是通过比较 key，在红黑树中来插入的，但是由于上述的定义，如果每次对于 map 都频繁取出 first 就太麻烦了，因此就定义了仿函数

🚩为什么使用仿函数而不是普通函数呢？

红黑树中只要涉及到数据 _data 的地方，就需要使用到仿函数提取 key，使用普通函数消耗太大，而仿函数带有 inline 的性质，降低消耗。同时官方文档中还对比较进行了实现，即 Compare，模板要求参数必须是一个类型，而普通函数无法作为类型传递

🚩为什么要自己定义仿函数，pair自带的仿函数不行吗？

在这里插入图片描述


虽然 pair 确实有自己的仿函数比较，但是他是比较完 first 后不行，会接着比较 second，这不符合我们的设计思路

在这里插入图片描述

截取了部分 insert 中的代码，利用仿函数确实是能够简单的实现键值 first 的提取，我们再对整体的调用思路进行整理

在这里插入图片描述

其实仿函数主要是为了 map 而设计的，为的就是提取 first，set 为了保持设计模式的一致，因而也设计了相同的仿函数，这样就不用关心是否需要调用这一点了，保持一致性

这里我们不对 Compare 进行实现，有兴趣的可以自己去看底层代码

🔥值得注意的是： 仿函数内不实现比较功能是因为，比较功能是一个外层调用功能，如果放在内部就不能操作者自行去调用了，况且 Compare 也是以仿函数的形式实现的，两个仿函数嵌套过于复杂，不好使用

2.3 Find功能实现

Node*Find(const K& key){ Node* cur = _root; KeyOfT kot;while(cur){if(kot(cur->_data)< key){ cur = cur->_right;}elseif(kot(cur->_data)> key){ cur = cur->_left;}else{return cur;}}returnnullptr;}

2.4 迭代器初步功能实现

在这里插入图片描述

类似的迭代器分析我们在 list 部分有做过解析，确实大体上是相像的，但是结构并不一样，这里的树形结构需要以中序遍历：左-根-右的方式遍历

template<classT>struct__TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self; Node* _node;__TreeIterator(Node* node):_node(node){}};

库里的迭代器模式并不能满足我们的设计需要，所以这里自己构建一个 __TreeIterator 类

2.4.1 ++运算符重载

Self&operator++(){if(_node->_right){// 右树的最左节点(最小节点) Node* subLeft = _node->_right;while(subLeft->_left){ subLeft = subLeft->_left;} _node = subLeft;}else{ Node* cur = _node; Node* parent = cur->_parent;// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点while(parent){if(cur == parent->_left){break;}else{ cur = cur->_parent; parent = parent->_parent;}} _node = parent;}return*this;}

中序遍历的方式是 左-根-右，因此可以总结为两种情况来遍历：

  • 当前节点有右子树

处理方式： 找到右子树的最左节点（即右子树中的最小值）

原因： 在中序遍历中，当前节点的下一个节点是其右子树的最左节点

  • 当前节点没有右子树

处理方式： 向上回溯，直到找到某个祖先节点，使得当前节点位于该祖先的左子树中

原因： 在中序遍历中，若无右子树，则下一个节点是第一个满足 “当前节点是其左子节点” 的祖先

🔥值得注意的是： 当前节点没有右子树的情况，是 左-根-右 的最后一步，无论是在根的左边还是右边，最终都会回到根节点，所以直接 _node = parent 即可

2.4.2 --运算符重载

Self&operator--(){if(_node->_left){ Node* subRight = _node->_left;while(subRight->_right){ subRight = subRight->_right;} _node = subRight;}else{// 孩子是父亲的右的那个节点 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;}

operator-- 的思路和 operator++ 是一样的，反过来遍历就行了

2.4.3 *运算符重载

T&operator*(){return _node->_data;}

2.4.4 ->运算符重载

T*operator->(){return&_node->_data;}

这里再提醒一下重载 -> 是因为用 * 的代码不够简洁，具体分析参考 list 部分的解析

传送门：C++效率掌握之STL库：list底层剖析及迭代器万字详解

2.4.5 !=运算符重载

booloperator!=(const Self& s)const{return _node != s._node;}

_node：当前迭代器指向的节点
s._node：另一个迭代器（作为参数传入）指向的节点

2.4.6 begin()

//RBTree.h iterator begin(){ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returniterator(leftMin);}//Set.h Map.h iterator begin(){return _t.begin();}

2.4.7 end()

//RBTree.h iterator end(){returniterator(nullptr);}//Set.h Map.h iterator end(){return _t.end();}

现在已经可以基本实现遍历的功能了

2.5 迭代器进阶功能实现

2.5.1 set：const迭代器及insert的实现

typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();}

由于 set 规定 key 是不可以被修改的，因此 iterator 和 const_iterator 本质上其实都是const_iterator

🔥值得注意的是：begin() 和 end() 的 const 迭代器函数被 const 修饰是为了满足常量容器对象或非常量容器对象都能调用

insert 的错误代码：

pair<iterator,bool>insert(const K& key){return _t.Insert(key);}

这里是返回红黑树的插入，红黑树的插入详见下面的代码展示

从之前的学习我们知道 insert 返回的是 pair<iterator, bool>，那么是不是直接返回insert的结果就好了呢？看似确实是没问题，但是这里理了个巨大的坑，我们实际分析一波：

  • _t.Insert(key) 返回的是 RBTree::iterator，是一个普通迭代器
  • pair<iterator, bool> insert(const K& key) 返回的是 set::iterator，是一个 const 迭代器

insert 的正确代码：

// iterator RBTree::const_iterator pair<iterator,bool>insert(const K& key){// pair<RBTree::iterator, bool> pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);return pair<iterator,bool>(ret.first, ret.second);}

正确的做法是先将 insert 返回的普通迭代器由变量 ret 存储，然后再用一个匿名对象进行构造，将 ret 的普通迭代器构造成 const 迭代器返回即可，下面将进行详细的构造原理解释：

在这里插入图片描述

回看官方文档发现 iterator 和 const_iterator 都是被单独拿出来实例化的，并没有受到 Ref 和 Ptr 的影响，那么此时就分为两种情况：

  • 普通迭代器的拷贝构造

当 __rb_tree_iterator 是普通迭代器时，iterator 就是自身类型，此时构造函数等价于：

__rb_tree_iterator(const __rb_tree_iterator<Value, Value&, Value*>& it):node(it.node){}

这是一个标准的拷贝构造函数，用于创建一个新的普通迭代器，指向相同的节点

  • const迭代器的构造

当 __rb_tree_iterator 是 const 迭代器时， iterator 指的是普通迭代器类型，此时构造函数等价于：

__rb_tree_iterator(const __rb_tree_iterator<Value, Value&, Value*>& it):node(it.node){}

这变成了一个构造函数，允许从普通迭代器创建 const 迭代器

所以可以理解为单独拿出来实例化是为了不让 Ref 和 Ptr 影响参数，而外面的类型就会受 Ref 和 Ptr 影响，这样就能保证外面的类型是 const 迭代器，里面的参数是普通迭代器，成功构造出一个支持普通迭代器构造 const 迭代器的构造函数

在这里插入图片描述

那再转到实际代码上，ret.first 的类型是 typename RBTree<K, K, SetKeyOfT>::iterator ，返回值 pair 的第一个元素类型是 set 类中定义的 iterator，实际上是 typename RBTree<K, K, SetKeyOfT>::const_iterator

ret.first 会调用自定义的迭代器类型的构造函数 __TreeIterator(const Iterator& it) 进行单参数转换，变成 const_iterator

2.5.2 map：const迭代器及insert、[ ]运算符重载的实现

typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();}

对于 map 来说，key 是不允许改变的，value 是可以改变的，但是如果像 set 那样写的话 key 和 value 都不能修改了，所以直接在 pair 的 key 加 const ，控制 value 即可

–
insert 代码：

pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);}

map 就没有像 set 那么麻烦了，红黑树和 `map 的迭代器是一致的

[ ]运算符重载 代码：

V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;}

之前详细解释过，可以看之前的博客

传送门：C++漫溯键值的长河：map && set

3.代码展示

🚩MySet.h

#pragmaonce#include"RBTree.h"namespace bit {template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();}// iterator RBTree::const_iterator pair<iterator,bool>insert(const K& key){// pair<RBTree::iterator, bool> pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);return pair<iterator,bool>(ret.first, ret.second);}private: RBTree<K, K, SetKeyOfT> _t;};}

🚩MyMap.h

#pragmaonce#include"RBTree.h"namespace bit {template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;} pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}

🚩RBTree.h

#pragmaonce#include<iostream>usingnamespace std;enumColour{ RED, BLACK };template<classT>structRBTreeNode{ RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}};template<classT,classPtr,classRef>struct__TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;__TreeIterator(const Iterator& it):_node(it._node){} Node* _node;__TreeIterator(Node* node):_node(node){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node != s._node;} Self&operator--(){if(_node->_left){ Node* subRight = _node->_left;while(subRight->_right){ subRight = subRight->_right;} _node = subRight;}else{// 孩子是父亲的右的那个节点 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;} Self&operator++(){if(_node->_right){// 右树的最左节点(最小节点) Node* subLeft = _node->_right;while(subLeft->_left){ subLeft = subLeft->_left;} _node = subLeft;}else{ Node* cur = _node; Node* parent = cur->_parent;// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点while(parent && cur == parent->_right){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;}};// set->RBTree<K, K, SetKeyOfT> _t;// map->RBTree<K, pair<K, V>, MapKeyOfT> _t;template<classK,classT,classKeyOfT>structRBTree{typedef RBTreeNode<T> Node;public:// 同一个类模板，传的不同的参数实例化出的不同类型typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T,const T*,const T&> const_iterator; iterator begin(){ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returniterator(leftMin);} iterator end(){returniterator(nullptr);} const_iterator begin()const{ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returnconst_iterator(leftMin);} const_iterator end()const{returnconst_iterator(nullptr);} Node*Find(const K& key){ Node* cur = _root; KeyOfT kot;while(cur){if(kot(cur->_data)< key){ cur = cur->_right;}elseif(kot(cur->_data)> key){ cur = cur->_left;}else{return cur;}}returnnullptr;} pair<iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returnmake_pair(iterator(_root),true);} Node* parent =nullptr; Node* cur = _root; KeyOfT kot;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnmake_pair(iterator(cur),false);}} cur =newNode(data); cur->_col = RED; Node* newnode = cur;if(kot(parent->_data)<kot(data)){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;// u存在且为红if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else// u不存在 或 存在且为黑{if(cur == parent->_left){// g// p// cRotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// p// cRotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else// parent == grandfather->_right{ Node* uncle = grandfather->_left;// u存在且为红if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_right){// g// p// cRotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returnmake_pair(iterator(newnode),true);}voidRotateL(Node* parent){++_rotateCount; Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft;if(curleft){ curleft->_parent = parent;} cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(parent == _root){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}voidRotateR(Node* parent){++_rotateCount; Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright) curright->_parent = parent; Node* ppnode = parent->_parent; cur->_right = parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 17:20继续boolCheckColour(Node* root,int blacknum,int benchmark){if(root ==nullptr){if(blacknum != benchmark)returnfalse;returntrue;}if(root->_col == BLACK){++blacknum;}if(root->_col == RED && root->_parent && root->_parent->_col == RED){ cout << root->_kv.first <<"出现连续红色节点"<< endl;returnfalse;}returnCheckColour(root->_left, blacknum, benchmark)&&CheckColour(root->_right, blacknum, benchmark);}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node* root){if(root ==nullptr)returntrue;if(root->_col != BLACK){returnfalse;}// 基准值int benchmark =0; Node* cur = _root;while(cur){if(cur->_col == BLACK)++benchmark; cur = cur->_left;}returnCheckColour(root,0, benchmark);}intHeight(){returnHeight(_root);}intHeight(Node* root){if(root ==nullptr)return0;int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}private: Node* _root =nullptr;public:int _rotateCount =0;};

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述

Read more

CPP-Summit-2022 学习:Modern C++基于性能的重构优化

C++软件性能现状与优化挑战 一、软件性能优化本质 性能优化的核心目标： 减少指令数，提高每秒可执行浮点操作数（GFLOPS），充分利用硬件特性。 通过表格可以看出，不同语言/优化策略的性能提升非常悬殊： 二、性能优化的数学本质 1. 运行时间与指令数关系 运行时间 T T T 与总指令数 I I I 和每秒执行速率 R R R 的关系为： T = I R T = \frac{I}{R} T=RI * I I I：总指令数（越少越快） * R R R：硬件执行速率（可受矢量化、并行化影响） 2.

By Ne0inhk
【C++】多态

【C++】多态

多态 ✨前言：在 C++ 的世界里，“多态（polymorphism）” 是面向对象编程的灵魂之一。 它让同一个接口在不同对象上表现出不同的行为，从而大大提升了代码的复用性、扩展性与灵活性。 本文将带你深入理解多态的核心原理，从概念、实现条件、虚函数、重写规则，到虚函数表与动态绑定机制，逐步揭开多态背后的运行逻辑。 📖专栏：【C++成长之旅】 目录 * 多态 * 一、多态的概念 * 二、多态的定义及实现 * 2.1 多态的构成条件 * 2.1.1 实现多态还有两个必须重要条件： * 2.1.2 虚函数 * 2.1.3 虚函数的重写/覆盖 * 2.1.4 多态场景的⼀个选择题 * 2.1.

By Ne0inhk
【c++】模板进阶，模板的分离编译重点讲解

【c++】模板进阶，模板的分离编译重点讲解

小编个人主页详情<—请点击 小编个人gitee代码仓库<—请点击 c++系列专栏<—请点击 倘若命中无此运，孤身亦可登昆仑，送给屏幕面前的读者朋友们和小编自己! 目录 * 前言 * 一、class和typename作为模板参数的关键字的区别 * 二、非类型模板参数 * 介绍 * 使用 * array容器的使用 * array容器与c语言数组的对比 * 三、模板的特化 * 概念引入 * 四、函数模板特化 * 五、类模板特化 * 全特化 * 偏特化 * 部分特化 * 参数更进一步限制 * 测试 * 类模板特化的应用举例 * 六、模板的分离编译 * 什么是分离编译 * 通常来讲模板为什么不能声明和定义分离 * 怎么样模板才能进行分离编译（只能缓解分离编译，本质上模板不能进行分离编译） * 模板不分离编译做法 * 七、模板的总结 * 总结 前言 【c++】STL容器-list和vector的反向迭代器的模拟实现—

By Ne0inhk