map和set的使用和底层实现

2024-09-05 06:52
文章标签 实现 使用 set 底层 map

本文主要是介绍map和set的使用和底层实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

嗨喽大家好，时隔许久阿鑫又给大家带来了新的博客，c++进阶——map和set的使用和底层实现，下面让我们开始今天的学习吧！

map和set的使用和底层实现

1.set和multiset的使用

set中的find和algorithm库中find的区别
在这里插入图片描述
在这里插入图片描述
删除一段区间的值，如删除[30,60]之间的值
在这里插入图片描述
在这里插入图片描述
区别：find时，多个x在树中，返回中序的第一个x

2.map和multimap的使用

在这里插入图片描述

2.1 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义。
在这里插入图片描述

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

2.2map中对象的插入

int main()
{//map<string, string> dict;//pair<string, string> kv1("left", "左边");//dict.insert(kv1);//dict.insert(pair<string, string>("right", "右边"));//dict.insert(make_pair("insert", "插入"));pair<string, string> kv2 = {"string","字符串" };//dict.insert({ "string", "字符串" });map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };map<string, string>::iterator it = dict.begin();while (it != dict.end()){//cout << (*it).first <<":"<<(*it).second << endl;//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}
///
int main(){
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.find(str);if (ret == countTree.end()){countTree.insert({ str, 1 });}else{ret->second++;}}for (const auto& e : countTree){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

在这里插入图片描述

it是对象，*it是返回结构体，((it->)->)中的(it->)是返回指向结构体的指针(&it)。

2.3map中的operator[]

分为插入成功和插入失败，调用insert检查key是否存在
插入成功：调用insert，构造出一个节点返回new_iterator和true，返回新迭代器的V&
插入失败：调用insert，返回与当前key值相同的迭代器和false，返回该迭代器的V&

在这里插入图片描述

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// 插入+修改dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key不存在->插入 <"insert", "">dict["insert"];// key存在->查找cout << dict["left"] << endl;return 0;
}
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countTree;for (const auto& str : arr){countTree[str]++;}for (const auto& e : countTree){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

2.4map在oj中的应用

通过一个key去寻找一个value

  1. 随机链表的复制问题在于原节点指针和拷贝节点指针的映射关系
    在这里插入图片描述
class Solution {
public:map<Node*,Node*> p1;//通过map来查找原节点地址和拷贝节点地址的相对映射关系,key是原节点指针Node* copyRandomList(Node* head) {if(head==nullptr)return nullptr;Node* prev = new Node(head->val);//拷贝节点的头节点Node* headCopy = prev;//拷贝节点的头节点p1[head] = headCopy;Node* cur = head->next;while(cur){Node* newnode = new Node(cur->val);p1[cur] = newnode;prev->next = newnode;prev = prev->next;cur = cur->next;}Node* head1 = headCopy;//拷贝节点的头节点while(head){//当前节点的random在拷贝节点中的位置headCopy->random = p1[head->random];headCopy = headCopy->next;head = head->next;}return head1;}
};

3.底层结构

3.1 AVL 树

3.1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右
子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均
搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子(右子树的高度减去左子树的高度))的绝对值不超过1(-1/0/1)
    如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
    O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)
    在这里插入图片描述
    在这里插入图片描述
3.1.2 AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，
使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
下列图为抽象图，可能是一整棵树，也可能是子树
h是>=0的AVL树

  1. 新节点插入较高左子树的左侧—左左：右单旋
    在这里插入图片描述

  2. 新节点插入较高右子树的右侧—右右：左单旋
    在这里插入图片描述

  3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋
    只进行左旋时
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  1. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

若旋转节点的右子树高于左子树，则以右节点为根的子树也必须是右子树高于左子树(因为单纯的左旋或右旋已经无法保持旋转后的二叉搜索树依旧是AVL树了)
否则就需要先以右节点为旋转节点进行右旋，再以根节点为旋转节点进行左旋
右左双旋需要标记三个节点的原因是，先进行旋转的是子树，只要旋转就需要标记两个节点
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.2 红黑树

3.2.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。
在这里插入图片描述

3.2.2 红黑树的性质

在这里插入图片描述

在这里插入图片描述

3.2.3 红黑树的插入

检测新节点插入后，红黑树的性质是否造到破坏，插入的节点颜色都是红色
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

在这里插入图片描述
2.abcde不为空，cur开始是黑色，以cur为根的红黑树满足情况一，cur后来变为红色。
在这里插入图片描述

在这里插入图片描述
1.u不存在，abcde都是空，cur是新增节点
需要注意的是，对于双旋(情况三)，先进行单旋就变成情况二
在这里插入图片描述

2.abcde不为空，cur开始是黑，cur为根的红黑树满足情况一，cur由情况一变为红色
在这里插入图片描述
双旋(情况三)先进行单旋变为情况二
在这里插入图片描述

while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//    g//  p   uif (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// u存在且为红 -》变色再继续往上处理parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// u存在且为黑或不存在 -》旋转+变色if (cur == parent->_left){//    g//  p   u//c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g//  p   u//    c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//    g//  u   pNode* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}				}}_root->_col = BLACK;return true;}
3.2.4计算每条路径上黑色节点的个数

从空节点开始往回推理，每一个节点都可以当作一个子树的根，将一颗二叉树看成有限个子树构成
（完成二叉树相关的题目，需要将一颗二叉树的大问题拆分为有限个子树的小问题）

    //先选取一个参考值，别的路径上的黑色节点的个数都和参考值进行比较bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED){return false;}// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}

3.3通过红黑树实现map和set

利用同一颗红黑树实现map和set(是一种红黑树泛型的实现)
在这里插入图片描述
对于map和set来说，第一个模板参数存在的意义是用来查找Key
在这里插入图片描述

为了同时实现map和set内部数据的比较大小，需要实现一个另类的仿函数

只要记住模板接受不同的类型参数就能实例化出不同的对象

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.3.1 红黑树的迭代器

分为当前节点右子树为空和不为空两种情况
有右子树说明该子树还没遍历完，找右子树最左节点(以右节点为根的最小节点)
无右子树说明该子树已经遍历到根，需要跳转到孩子是父亲左的那个祖先节点
反向迭代器和正向迭代器相反，分为左子树为空和左子树不为空两种情况
在这里插入图片描述
RBTree.h中的成员函数用大写，Map和Set中的成员函数用小写来区分。

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){// 右不为空，右子树最左节点就是中序第一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{// 孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr) // end(){// --end()，特殊处理，走到中序最后一个节点，整棵树的最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 左子树不为空，中序左子树最后一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}bool operator== (const Self& s){return _node == s._node;}
};

在MyMap.h中

namespace bit
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;//typename告知编译器iterator是一个类型名typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}
3.3.2map和set不支持修改key

在map和set中不允许修改key，因为修改了key会破坏红黑树的特性
在这里插入图片描述

3.3.3map中的operator[]

在Insert中，由于Node* cur = new Node(data);
但是cur指针当红黑树需要旋转时会指向另外的节点，所以需要一个newnode来记录下新节点的地址。

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

c++stl中的set中的compare = less<>

在这里插入图片描述

std::set<int, std::greater<int>> mySet;
#include <iostream>  
#include <set>  
#include <functional> // 对于 std::greater，但实际上包含 <set> 就足够了  int main() {  std::set<int, std::greater<int>> mySet;  // 向集合中添加元素  mySet.insert(5);  mySet.insert(1);  mySet.insert(10);  mySet.insert(3);  // 遍历集合并打印元素  for (int elem : mySet) {  std::cout << elem << " ";  }  std::cout << std::endl;  return 0;  
}

在这里插入图片描述

std::set<int, std::greater> 并没有改变二叉树（特别是红黑树）的插入规则本身。红黑树的插入规则是固定的，包括如何旋转节点以保持树的平衡等。然而，它确实改变了元素之间的比较方式，这影响了插入过程中新元素在树中的位置。
当你使用 std::greater 作为 std::set 的比较函数时，你实际上是在告诉集合：“我想要按照从大到小的顺序来存储元素。” 因此，当插入新元素时，集合会使用 std::greater 来比较新元素和树中已存在的元素，以确定新元素应该放在哪里。
这种比较方式的改变并没有修改红黑树的插入算法，而是改变了插入算法中用于比较元素的部分。因此，可以说它改变了元素在集合中的排序方式，而不是改变了二叉树的插入规则。插入规则仍然是红黑树的插入规则，只是比较元素的方式不同。

好啦，今天的内容我们就学习到这里，如果大家觉得阿鑫写的不错的话，记得留下你的一键三连哦，期待我们的下一次相遇！## 好啦，今天的内容我们就学习到这里，如果大家觉得阿鑫写的不错的话，记得留下你的一键三连哦，期待我们的下一次相遇！

这篇关于map和set的使用和底层实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1138255。

相关文章

深入理解Go语言中二维切片的使用

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态
阅读更多...
Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
prometheus如何使用pushgateway监控网路丢包

prometheus如何使用pushgateway监控网路丢包

《prometheus如何使用pushgateway监控网路丢包》：本文主要介绍prometheus如何使用pushgateway监控网路丢包问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录监控网路丢包脚本数据图表总结监控网路丢包脚本[root@gtcq-gt-monitor-prome
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Python通用唯一标识符模块uuid使用案例详解

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
SpringBoot中如何使用Assert进行断言校验

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr
阅读更多...
Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理；Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2