map和set的模拟实现｜利用红黑树封装map和set｜STL源码剖析

news/2025/1/12 4:09:31/

前言

那么这里博主先安利一些干货满满的专栏了！

首先是博主的高质量博客的汇总，这个专栏里面的博客，都是博主最最用心写的一部分，干货满满，希望对大家有帮助。

高质量干货博客汇总icon-default.png?t=N6B9https://blog.csdn.net/yu_cblog/category_12379430.html?spm=1001.2014.3001.5482这两个都是博主在学习Linux操作系统过程中的记录，希望对大家的学习有帮助！

操作系统Operating Syshttps://blog.csdn.net/yu_cblog/category_12165502.html?spm=1001.2014.3001.5482Linux Syshttps://blog.csdn.net/yu_cblog/category_11786077.html?spm=1001.2014.3001.5482这两个是博主学习数据结构的同时，手撕模拟STL标准模版库各种容器的专栏。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html

Map和Set的底层是什么

在C++ STL中，map和set底层通常是使用红黑树（Red-Black Tree）来实现的。

红黑树是一种自平衡的二叉搜索树，它通过在每个节点上存储额外的信息（颜色）来维护平衡。这些颜色信息遵循一组特定的规则，以确保树保持平衡状态。红黑树的平衡性质使得插入、删除和查找操作的时间复杂度为对数级别。

在红黑树中，每个节点都有一个键值对，按照键的顺序进行排序。对于map而言，每个节点还有一个相关联的值，而对于set而言，节点的键即是其值。这种有序性质使得map和set非常适合需要按照键进行查找、插入和删除的应用场景。

需要注意的是，虽然红黑树是map和set的常见底层实现，但具体的实现可能因不同的编译器和标准库实现而有所不同。因此，对于特定的编译器和标准库版本，底层实现可能会有所变化。

因此，在学习如何使用红黑树封装STL的map和set的之前，我们需要先学习红黑树的底层原理，可以见博主之前的一篇博客，里面对于红黑树的原理讲的非常的详细。

手撕红黑树 | 变色+旋转你真的明白了吗？【超用心超详细图文解释 | 一篇学会Red_Black_Tree】icon-default.png?t=N6B9https://blog.csdn.net/Yu_Cblog/article/details/128210260

但是，上面这篇博客里面的红黑树，和即将要封装的版本，还是略微有差别的。

因为set只需要key，而map是key-value结构的。

封装版本的红黑树头文件博主放在博客结尾。

封装

Map.h

#pragma once#include"RBTree.h"namespace ns_Map {template<class K, class V>class map {struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}};public://迭代器//取模板的模板的类型 -- 所以要typename -- 告诉编译器是类型typedef typename RBTree <K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin() {return _t.begin();}iterator end() {return _t.end();}public://operator[] -- 只有map才有V& operator[](const K& key) {//如果有 -- 插入成功//如果没有 -- 插入失败pair<iterator, bool>ret = insert(make_pair(key, V()));return ret.first->second;}public:pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.insert(kv);}private:RBTree <K, pair<K, V>, MapKeyOfT>_t;};void test_map() {map<int, int>m;m.insert(make_pair(1, 2));m.insert(make_pair(5, 2));m.insert(make_pair(2, 2));m.insert(make_pair(2, 2));m.insert(make_pair(3, 2));m.insert(make_pair(4, 2));m.insert(make_pair(6, 2));cout << "测试++" << endl;map<int, int>::iterator it = m.begin();while (it != m.end()) {cout << it->first << endl;++it;}cout << "测试--" << endl;//--it;//while (it != m.begin()) {//	cout << it->first << endl;//	--it;//}cout << endl;}void test_map2() {string arr[] = { "苹果","香蕉","苹果","苹果","西瓜","香蕉","苹果","苹果" };map<string, int>hash;for (auto& str : arr) {hash[str]++;}//map<string, int>::iterator it = hash.begin();//while (it != hash.end()) {//	cout << it->first << ":" << it->second << endl;//	++it;//}//范围forfor (auto& e : hash) {cout << e.first << ":" << e.second << endl;}}
}

Set.h

#pragma once#include"RBTree.h"namespace ns_Set{template<class K>class set {struct SetKeyOfT {const K& operator()(const K& key) {return key;}};public://µü´úÆ÷typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin() {return _t.begin();}iterator end() {return _t.end();}public:pair<iterator, bool> insert(const K& key) {return _t.insert(key);}private:RBTree<K, K, SetKeyOfT>_t;};void test_set() {set<int>s;s.insert(3);s.insert(3);s.insert(1);s.insert(2);s.insert(5);s.insert(5);s.insert(7);s.insert(6);set<int>::iterator it = s.begin();while (it != s.end()) {cout << *it << endl;++it;}cout << endl;}
}

RBTree.h

#pragma once
#include<map>
#include<iostream>
#include<assert.h>
using namespace std;
enum Colour {RED,BLACK
};template<class T>
struct __Red_Black_TreeNode {__Red_Black_TreeNode<T>* _left;__Red_Black_TreeNode<T>* _right;__Red_Black_TreeNode<T>* _parent;//pair<K, V>_kv;T _data;Colour _col;__Red_Black_TreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data) {}
};//迭代器
template<class T, class Ref, class Ptr>
struct __redblack_tree_iterator {typedef __Red_Black_TreeNode<T>Node;Node* _node;__redblack_tree_iterator(Node* node):_node(node) {}Ref operator*() {return _node->_data;}Ptr operator->() {return &_node->_data;}bool operator!=(const __redblack_tree_iterator& s) const {return _node != s._node;}bool operator==(const __redblack_tree_iterator& s) const {return _node == s._node;}__redblack_tree_iterator& operator++() {//1.右子树不为空，++就是找右子树的中序第一个//2.如果右子树为空，找孩子不是父亲右边的那个祖先//如果当前节点是父亲的右，说明父亲访问过了if (_node->_right) {//1.Node* left = _node->_right;while (left->_left) {left = left->_left;}_node = left;}else {//2.Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_right) {cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}__redblack_tree_iterator& operator--() {//1.如果左不为空 -- 找左的最右//2.如果左为空 -- 找到孩子不是父亲的左的那个祖先if (_node->_left) {Node* right = _node->_left;while (right->_right) {right = right->_right;}_node = right;}else {Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_left) {cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}	
};//第三个模板参数是一个仿函数
template<class K,class T,class KeyOfT>
struct RBTree {typedef __Red_Black_TreeNode<T>Node;
private:Node* _root = nullptr;
public:typedef __redblack_tree_iterator<T, T&, T*> iterator;iterator begin() {//stl源码里面是有哨兵位的，这里我们没有 -- 所以我们找一下最左节点Node* left = _root;while (left && left->_left) {left = left->_left;}return iterator(left);}iterator end() {return iterator(nullptr);//直接给空就行了}
private://左单旋void rotate_left(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) {subRL->_parent = parent;}Node* ppNode = parent->_parent;//记录一下原先parent的parentsubR->_left = parent;parent->_parent = subR;if (_root == parent) {_root = subR;subR->_parent = nullptr;}else {//如果ppNode==nullpt，是不会进来这里的if (ppNode->_left == parent) {ppNode->_left = subR;}else {ppNode->_right = subR;}subR->_parent = ppNode;}}//右单旋void rotate_right(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) {subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) {_root = subL;subL->_parent = nullptr;}else {if (ppNode->_left == parent) {ppNode->_left = subL;}else {ppNode->_right = subL;}subL->_parent = ppNode;}}
public://前面插入的过程和搜索树一样的pair<iterator, bool> insert(const T& data) {KeyOfT kot;if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* parent = nullptr;Node* cur = _root;while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;}else return make_pair(iterator(cur), false);}cur = new Node(data);Node* newnode = cur;cur->_col = RED;//一开始尽量先变红if (kot(parent->_data) < kot(data)) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED) {Node* grandparent = parent->_parent;assert(grandparent && grandparent->_col == BLACK);//关键看叔叔//判断一下左右if (parent == grandparent->_left) {Node* uncle = grandparent -> _right;//情况1（不看方向）if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上处理cur = grandparent;parent = cur->_parent;}//情况2+3//uncle不存在/存在且为黑else {//情况2//   g//  p  u// c//右单旋+变色if (cur == parent->_left) {rotate_right(grandparent);parent->_col = BLACK;//父亲变黑grandparent->_col = RED;//祖父变红}//情况3//   g//  p  u//   c//左右双旋+变色else {rotate_left(parent);rotate_right(grandparent);//看着图写就行了cur->_col = BLACK;grandparent->_col = RED;}break;}}else {Node* uncle = grandparent->_left;//情况1（不看方向）if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上处理cur = grandparent;parent = cur->_parent;}else {//情况2//   g//  u  p//      c //左单旋+变色if (cur == parent->_right) {rotate_left(grandparent);parent->_col = BLACK;//父亲变黑grandparent->_col = RED;//祖父变红}//情况3//   g//  u  p//    c//右左双旋+变色else {rotate_right(parent);rotate_left(grandparent);//看着图写就行了cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;//最后无论根是红是黑 -- 都处理成黑//这里我们要返回新增的节点 -- 但是刚才插入过程可能不见了，所以前面最好保存一下return make_pair(iterator(newnode), true);}
};

http://www.ppmy.cn/news/904532.html

相关文章

【FPGA】基于C5的第一个SoC工程

【FPGA】基于C5的第一个SoC工程

文章目录 前言SoC的Linux系统搭建 前言 本文是在毕业实习期间学习FPGA的SoC开发板运行全连接神经网络实例手写体的总结。 声明&#xff1a;本文仅作记录和操作指南&#xff0c;涉及到的操作会尽量细致&#xff0c;但是由于文件过大不会分享文件&#xff0c;具体软件可以自行搜…
阅读更多...
喜讯 | 国际智慧城市大会巨杉喜获两项大奖

喜讯 | 国际智慧城市大会巨杉喜获两项大奖

近日&#xff0c;第六届中国(广东)国际智慧城市大会智慧园区和社区高峰论坛暨2018-2019年度智慧城市建设评优活动颁奖盛典在广州圆满举行。SequoiaDB巨杉数据库荣获“2018-2019年度智慧城市大数据十佳技术创新奖”及“2018-2019年度大数据新锐人物奖”两项奖项。 本次论坛由广东…
阅读更多...
香港内推 | 上海千象资产招聘海外CTA量化研究实习生

香港内推 | 上海千象资产招聘海外CTA量化研究实习生

合适的工作难找&#xff1f;最新的招聘信息也不知道&#xff1f; AI 求职为大家精选人工智能领域最新鲜的招聘信息&#xff0c;助你先人一步投递&#xff0c;快人一步入职&#xff01; 上海千象资产 We are Shanghai Qianxiang Asset Management Co., Ltd., a leading China qu…
阅读更多...
新锐办公简介

新锐办公简介

新锐在线办公系统是一个先进的企业信息平台建立及维护软件。它的设计宗旨是功能强大、操作简便、界面友好&#xff0c;软件运行基于Browser/Server模式&#xff0c;符合当今技术发展的趋势&#xff1b;界面如同Windows的资源管理器&#xff0c;用户只要具备支持JavaScript和HTM…
阅读更多...
诚聘技术英才

诚聘技术英才

高级芯片设计工程师 岗位描述&#xff1a; 1.与设计团队一起参与AI并行处理器系统的设计及开发&#xff1b; 2. 根据高标准功耗、面积、性能要求下的架构定义和设计规范进行模块的RTL设计&#xff1b; 3.紧密与架构、验证、后端、软件等多个团队协同工作已解决设计问题。…
阅读更多...
新锐技术探索

新锐技术探索

项目管理&#xff1a; Maven 代码管理&#xff1a; Git 数据服务&#xff1a; Vert.x SpringBoot Node.js 苹果开发&#xff1a; Swift 安卓开发&#xff1a; Kotlin 微服务&#xff1a; SpringCloud DubboZookeeper 容器&#xff1a; Docker 桌面开发&#xff1a; Java…
阅读更多...
万豪国际集团任命新CEO和总裁；智联招聘获春华资本等战略投资 | 美通企业日报...

万豪国际集团任命新CEO和总裁；智联招聘获春华资本等战略投资 | 美通企业日报...

今日看点&#xff1a;万豪国际公布集团高管最新任命。春华资本联合管理层战略投资智联招聘。LINE FRIENDS与腾讯微视达成战略合作。药明奥测完成1.5亿美元B轮融资&#xff0c;依生生物完成1.3亿美元B轮融资。Hopium氢动能车将于2021年6月亮相。阿科玛宣布进一步提升其中国常熟基…
阅读更多...
纽创信安获深圳市“专精特新”企业认定

纽创信安获深圳市“专精特新”企业认定

‍2022年6月15日&#xff0c;深圳市工业和信息化局发布关于2021年度深圳市“专精特新”中小企业名单公示的通知&#xff0c;纽创信安成功获得深圳市“专精特新”企业认定。 “专精特新”最早于2011年由工信部提出&#xff0c;2018年国务院首次提出要开展“专精特新小巨人”培育…
阅读更多...
最新文章

Copyright @ 2022~2023