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。

相关文章

Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
使用Python快速实现链接转word文档

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import
阅读更多...
oracle DBMS_SQL.PARSE的使用方法和示例

oracle DBMS_SQL.PARSE的使用方法和示例

《oracleDBMS_SQL.PARSE的使用方法和示例》DBMS_SQL是Oracle数据库中的一个强大包,用于动态构建和执行SQL语句,DBMS_SQL.PARSE过程解析SQL语句或PL/S... 目录语法示例注意事项DBMS_SQL 是 oracle 数据库中的一个强大包，它允许动态地构建和执行
阅读更多...
前端原生js实现拖拽排课效果实例

前端原生js实现拖拽排课效果实例

《前端原生js实现拖拽排课效果实例》：本文主要介绍如何实现一个简单的课程表拖拽功能,通过HTML、CSS和JavaScript的配合,我们实现了课程项的拖拽、放置和显示功能,文中通过实例代码介绍的... 目录1. 效果展示2. 效果分析2.1 关键点2.2 实现方法3. 代码实现3.1 html部分3.2
阅读更多...
SpringBoot中使用 ThreadLocal 进行多线程上下文管理及注意事项小结

SpringBoot中使用 ThreadLocal 进行多线程上下文管理及注意事项小结

《SpringBoot中使用ThreadLocal进行多线程上下文管理及注意事项小结》本文详细介绍了ThreadLocal的原理、使用场景和示例代码,并在SpringBoot中使用ThreadLo... 目录前言技术积累1.什么是 ThreadLocal2. ThreadLocal 的原理2.1 线程隔离2
阅读更多...
Python itertools中accumulate函数用法及使用运用详细讲解

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》：本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言：1.2定义：1.3衍生用法：1.3Leetcode的实际运用:总结 1.1前言：本文将详
阅读更多...
Java深度学习库DJL实现Python的NumPy方式

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操
阅读更多...
最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
浅析如何使用Swagger生成带权限控制的API文档

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里，API
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2