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

Python爬虫（11）Python数据存储实战：深入解析NoSQL数据库的核心应用与实战

Python爬虫（11）Python数据存储实战：深入解析NoSQL数据库的核心应用与实战

目录 * 引言 * 一、背景：为什么选择NoSQL存储爬虫数据？ * 1.1 爬虫数据的核心挑战 * 1.2 NoSQL数据库的核心优势 * 二、NoSQL数据库在爬虫中的核心应用 * 2.1 MongoDB：文档型数据库的王者 * 2.2 Redis：内存数据库的极致性能 * 三、NoSQL选型与性能优化策略 * 3.1 数据库选型对比 * 3.2 性能优化实战技巧 * 四、总结与未来趋势 * 4.1 核心总结 * Python爬虫相关文章（推荐） 引言 在Python爬虫开发中，数据存储的效率和扩展性直接决定了项目的长期价值。传统关系型数据库（如MySQL）虽然支持事务和复杂查询，但在应对‌动态数据结构‌、‌海量数据存储‌和‌高并发写入‌时往往捉襟见肘。而‌NoSQL数据库‌

By Ne0inhk
标准 Python 项目结构

标准 Python 项目结构

理解 Python 项目的通用结构对于初学者来说非常重要。虽然每个项目可能略有不同，但大多数规范、可维护的 Python 项目都遵循一些常见的组织模式。 常见的项目结构如下： my_project/ # 项目根目录 ├── my_package/ # 主要 Python 包（模块集合） │ ├── __init__.py # 标识这是一个 Python 包 │ ├── core.py # 核心逻辑 │ ├── utils.py # 工具函数 │ └── ... # 其他模块 ├── tests/ # 单元测试目录 │ ├── __init__.py │ ├── test_core.py │ └── test_utils.py ├── docs/ # 文档（可选） ├── examples/ # 使用示例（可选） ├── requirements.txt # 依赖列表 ├── setup.

By Ne0inhk

Python 零基础学习指南

Python 零基础学习指南 🐍 从零开始，轻松掌握Python - 最适合初学者的Python学习路径 📋 目录导航 * 第1章：Python简介与环境搭建 * 第2章：基础语法入门 * 第3章：数据类型详解 * 第4章：控制流程 * 第5章：函数的世界 * 第6章：面向对象编程 * 第7章：模块和包 * 第8章：文件操作 * 第9章：异常处理 * 第10章：进阶特性 * 实战项目 第1章：Python简介与环境搭建 🤔 什么是Python？ 想象一下，如果编程语言是工具，那么Python就像是一把瑞士军刀 - 简单易用，功能强大！ Python的特点： * 🎯 简单易学：语法接近自然语言 * 📖 可读性强：代码像写文章一样清晰 * 🌍 应用广泛：从网站到人工智能都能用 * 🆓 完全免费：开源且免费使用 🛠️ 安装Python Windows用户： 1. 访问

By Ne0inhk

ezdxf库终极指南：Python CAD自动化从入门到精通

ezdxf库终极指南：Python CAD自动化从入门到精通 【免费下载链接】ezdxfPython interface to DXF 项目地址: https://gitcode.com/gh_mirrors/ez/ezdxf 想要用Python操控CAD图纸却不知从何入手？ezdxf库为你打开了通往CAD自动化世界的大门。这个纯Python实现的DXF文件处理工具，让你无需安装任何CAD软件就能轻松读写、编辑和生成图纸文件。无论你是机械工程师、建筑设计师，还是数据可视化开发者，掌握ezdxf都将让你的工作效率倍增。 快速入门：5分钟上手ezdxf 安装与环境配置 安装ezdxf库只需一行命令，简单到让人难以置信： pip install ezdxf 验证安装是否成功： import ezdxf print(f"ezdxf版本: {ezdxf.__version__}") 你的第一个DXF文件 让我们从一个简单的例子开始，感受ezdxf的强大之处： import ezdxf # 创建新图纸 -

By Ne0inhk