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。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2