【C++】容器篇（五）—— map和set的基本介绍

news/2024/11/16 21:02:59/

序言：

在之前，我们已经对STL中的 序列式容器 进行了相关的学习。本期，我将给大家介绍的则是另外一类容器 —— 关联式容器 ！！！

目录

（一）容器回顾

💨【顺序容器】

💨【关联式容器】

💨【容器适配器】

（二）键值对

（三）树形结构的关联式容器

1、set

 1️⃣基本介绍

2️⃣set的使用

2、multiset

 1️⃣ 基本介绍

2️⃣ multiset的使用

3、map

 1️⃣基本介绍

2️⃣ map的使用

4、multimap

1️⃣基本介绍

2️⃣ multimap的使用

（四）在OJ中的使用

 1、前k个高频单词

2、两个数组的交集

总结

（一）容器回顾


在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
 

接下来，我先带大家回顾一下有关容器的一些基本知识，帮助大家唤醒一些“远古”的记忆！

容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类：分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：
 

💨【顺序容器】


容器并非排序的，元素的插入位置同元素的值无关。包含 vector、deque、list，具体实现原理如下：

（1）vector 头文件

  • 动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。

（2）deque 头文件

  • 双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）

（3）list 头文件

  • 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

💨【关联式容器】

而本期将要介绍的 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；
通常以平衡二叉树的方式实现。包含set、multiset、map、multimap，具体实现原理如下：
（1）set/multiset 头文件

  1. set 即集合。set中不允许相同元素，multiset中允许存在相同元素。

（2）map/multimap 头文件

  1. map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second；
  2. map根据first值对元素从小到大排序，并可快速地根据first来检索元素。

💨【容器适配器】


封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功
能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue，具体实现原
理如下：
（1）stack 头文件

  • 栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的
  • 项）；
  • 后进先出

（2）queue 头文件

  • 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行；
  • 先进先出

（3）priority_queue 头文件

  • 优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列

（二）键值对

在C++中，键值对是一种常见的数据结构，它将一个唯一的键与一个值相关联。提供了一种高效的方式来存储和检索数据。该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
 

【场景】

比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义.
 

键值对的定义可以采用不同的数据结构或语法表示，具体取决于所使用的编程语言或数据格式。

以下是一些常见的定义方式：

  • C++关联容器示例：
std::map<std::string, int> myMap;
myMap["apple"] = 10;
myMap["banana"] = 5;
  • JSON格式示例：
{"name": "John","age": 30,"city": "New York"
}
  • Python字典示例：
my_dict = {"key1": "value1", "key2": "value2", "key3": "value3"}
  • JavaScript对象示例：
var myObject = { key1: "value1", key2: "value2", key3: "value3" };

【说明】

  1. 在以上示例中，“key1”、“key2"等都是键，对应的"value1”、"value2"等是对应的值；
  2. 你可以使用键值对来存储、访问和处理各种数据，根据具体编程语言和数据结构的不同，提供了丰富的函数和操作来操作和处理键值对。

而在SGI-STL中关于键值对的定义如下：

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){}};


（三）树形结构的关联式容器

  1. 根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构；
  2. 树型结构的关联式容器主要有四种：map、set、multimap、multiset；
  3. 这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

下面一依次介绍每一个容器：
 

1、set

 1️⃣基本介绍

  • 官方链接如下：set文档介绍

简单点来说 set是按照一定次序存储元素的容器，且set中的元素不可以重复。具体的大家可以参照文档进行相应的学习。
 

2️⃣set的使用

set的模板参数列表：

 

【说明】

  1. T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
  2. Compare：set中元素默认按照小于来比较
  3. Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
     

接下来，我们简单的来使用下 set：


void test_set1()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(2);s1.insert(1);s1.insert(2);set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;
}

输出展示：

 

 

【说明】

  1. 首先，我们可以使用迭代器对其进行操作；
  2. 其次，我们验证了上述所说的  set中的元素不可以重复，可以发现结果自动进行了去重的操作

紧接着，此时我们就会想，既然可以使用迭代器，那么我们就可以知道 范围for 也可以使用：

 

有的小伙伴可能不知道迭代器和范围for的联系，接下来我简单的描述一下：

迭代器 和 范围for循环 都是在 C++ 中用于遍历容器（如数组、向量、映射等）中的元素的工具。它们之间存在联系和互补关系。

  1. 迭代器：迭代器是一个对象，用于遍历容器中的元素序列。通过迭代器，可以逐个访问容器中的元素，并进行增加、删除、修改等操作。C++ 标准库提供了多种类型的迭代器，如 begin() 和 end() 返回的迭代器可以表示容器的起始和结束位置。迭代器可以使用 * 运算符来访问当前位置的值，也可以使用 ++ 运算符来移动到下一个位置。

  2. 范围for循环：范围for循环是一种简洁的语法形式，用于遍历容器中的元素。它可以自动处理迭代器的创建和递增，并以一种更直观的方式对容器中的元素进行访问。范围for循环的语法是 for (element : container)，其中 element 是用于存储当前元素的变量，container 是要遍历的容器。在每次循环迭代中，element 会被赋值为容器中的下一个元素，直到遍历完所有元素。

迭代器和范围for循环的联系在于，范围for循环在内部使用迭代器来实现对容器的遍历。范围for循环抽象了迭代器的创建和递增过程，使得代码更加简洁和易读。范围for循环适用于大多数情况下对容器进行遍历，并且不需要修改容器中的元素。而当需要更精细的控制和操作时，迭代器提供了更灵活的功能。

紧接着，在文档中介绍了 set中的元素不能在容器中修改。举例来验证一下：

【说明】

  1. 从上述图片中不难发现在C++的set容器中，元素不允许直接修改；
  2. set是一个有序的集合容器，它通常基于红黑树实现。红黑树是一种平衡二叉搜索树，用于维护元素的有序性。为了保持树的平衡和有序，set 中的元素在插入时按照特定规则被插入到合适的位置，并且不允许直接修改。
  3. 具体而言，当你在set 中插入一个元素时，该元素会被自动插入到正确的位置，以保持集合的有序性。红黑树的平衡性是通过左旋、右旋以及颜色调整等操作来维护的。直接修改元素的值可能导致元素位置不再准确，破坏了红黑树的性质，进而影响整个集合的有序性。
  4. 因此，在set 中，如果你需要修改一个元素，你需要先将该元素从集合中删除，然后再重新插入修改后的值。

【注意】

  • 如果你需要对集合中的元素进行频繁的修改操作，可能 set 并不是最适合的容器选择；
  • 相应地，可以考虑使用 unordered_set容器，它基于哈希表实现，并提供了快速的查找和修改元素的能力；
  • 在 unordered_set中，元素的位置是根据哈希函数计算得到的，而不是通过有序性进行维护，因此允许直接修改元素的值。

接下来，再给大家介绍一下关于 查找元素是否存在的操作。

举例：

void test_set2()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(2);s1.insert(1);s1.insert(2);int x;while (cin >> x){auto ret = s1.find(x);if (ret != s1.end()){cout << "在" << endl;}else{cout << "不在" << endl;}}}

输出显示：

 

  • 除了上述方法，我们还可以使用 count函数来进行操作。具体如下：
if (s1.count(x))
{cout << "在" << endl;
}
else
{cout << "不在" << endl;
}

输出显示：

 

2、multiset

  • 链接如下：Multiple的文档介绍

 1️⃣ 基本介绍

multiset 对比 set，multiset是按照特定顺序存储元素的容器，其中元素是可以重复的

2️⃣ multiset的使用

void test_set3()
{multiset<int> s1;s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(2);s1.insert(1);s1.insert(2);multiset<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;
}

输出显示：

 

此时，对于在 set中进行的查找操作，在multiset中该如何表现呢？（因此存在重复的情况）

void test_set3()
{multiset<int> s1;s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(1);s1.insert(2);s1.insert(1);s1.insert(2);s1.insert(1);multiset<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;// 多个key，find中序的第一个keyauto ret = s1.find(1);while (ret != s1.end() && *ret == 1){cout << *ret << " ";++ret;}cout << endl;}

输出显示：

 

【说明】

需要注意的是，multiset 中的元素是按键的自然顺序存储的。当存在多个相同的键时，它们按照插入的顺序存储在容器中。使用 find 方法仅返回指向中序遍历的第一个key，而不能一次性找到所有具有相同键的元素。

其次，除了上述的操作之外，multiset 还可以使用 count函数来统计元素出现的次数：

 

对于其他的操作，在这里就不做过多的介绍。大家结合文档我相信各位都可以看懂的！！！

 

3、map

 1️⃣基本介绍

  • 链接如下：map的使用

 

【说明】 

  1.  在正式的学习之前，先要了解在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容；
  2. 键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:

2️⃣ map的使用

【说明】

  1. key: 键值对中key的类型
  2. T： 键值对中value的类型
  3. Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
  4. Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
  5. 注意：在使用map时，需要包含头文件

接下来，我们简单的来使用下 map：

void test_map1()
{map<string, string> dict;dict.insert(make_pair("insert", "排序"));dict.insert(make_pair("count", "计数"));dict.insert(make_pair("find", "查找"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("swap", "交换"));map<string, string>::iterator dt1 = dict.begin();while (dt1 != dict.end()){cout << (*dt1).first << " ";++dt1;}cout << endl;
}

输出显示：

 【说明】

请注意，指针形式的输出在实际编码中可能不常见。通常，可以直接访问 std::pair 对象的成员变量，并以合适的方式打印出所需的内容。例如，cout << dt1->first << " "; 与 cout << (*dt1).first << " "; 是等效的。

  •  具体如下：

 

 

接下来，带大家看个例子，让大家更加深入的理解：

 【说明】

  • 在 C++ 的map容器中，每个键（key）都是唯一的。当你尝试插入一个已经存在的键时，插入操作会失败；
  • map是一个关联容器，它按照键的顺序对元素进行排序，并且保持唯一键的特性。当你插入一个新的键值对时，map会自动根据键的顺序将其插入到合适的位置，如果已经存在相同的键，则插入失败。

接下来，我给大家讲一下 operator[] 。首先我先用一下这个，让大家直观的感受：

void test_map2()
{string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

输出结果：

 

接下来，带大家详解这个operator[] ：

 

 【解释】

在给定的代码中，this 是一个指向当前对象的指针（或引用），make_pair(k, mapped_type()) 创建一个键为 k，值为默认构造的 mapped_type 类型对象的 std::pair 对象。接下来，通过调用 insert 方法将这个 std::pair 对象插入到容器中，并获取插入结果的迭代器。

然后，通过解引用和成员访问操作符 .second，(*((this->insert(make_pair(k, mapped_type ()))).first)).second 表达式从插入结果的迭代器中获取对应元素的值。

其实文档给的有一点太复杂了，在这里我给出简化的版本，供大家参考：

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

接下来，有了上述operator[] 这样的功能，我们就可以使用其进行插入操作了。具体如下:

当我们有这样的代码时： 

dict["left"];			// 插入
dict["right"] = "右边"; // 插入+修改
dict["string"] = "(字符串)"; // 修改
cout << dict["string"] << endl; // 查找
cout << dict["string"] << endl; // 查找

输出展示：

 接下来，我们通过调试看看：

 

【总结】

  • 1. map中的的元素是键值对
  • 2. map中的key是唯一的，并且不能修改
  • 3. 默认按照小于的方式对key进行比较
  • 4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
  • 5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(log_2 N)$
  • 6. 支持[]操作符，operator[]中实际进行插入查找
     

4、multimap

1️⃣基本介绍

  • 链接如下：multimap的使用

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
重复的
 

2️⃣ multimap的使用

multimap中的接口可以参考map，功能都是类似的。

【注意】

  • 1. multimap中的key是可以重复的。
  • 2. multimap中的元素默认将key按照小于来比较
  • 3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。
  • 4. 使用时与map包含的头文件相同：
     

 

（四）在OJ中的使用
 

 1、前k个高频单词

692. 前K个高频单词

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> num;for(auto e : words)num[e]++;//按照单词出现次数的逆序存储单词及其对应的出现次数multimap<int, string, greater<int>> arry;for(auto e : num){arry.insert(make_pair(e.second, e.first));}vector<string> res;auto it = arry.begin();for(int i = 0; i < k; i++){res.push_back(it->second);it++;}return res;}
};

输出结果：

 

2、两个数组的交集

349. 两个数组的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1(nums1.begin(), nums1.end());unordered_set<int> set2(nums2.begin(), nums2.end());vector<int> intersection;for (auto num : set1) {if (set2.find(num) != set2.end()) {intersection.push_back(num);}}return intersection;}
};

输出结果：

总结

 以上便是关于 map和set 的全部知识。感谢大家的观看与支持！！！

 


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

相关文章

LeetCode-Java(06)

LeetCode-Java(06)

24. 两两交换链表中的节点 非递归解法 class Solution {public ListNode swapPairs(ListNode head) {ListNode pre new ListNode(0);pre.next head;ListNode temp pre;while(temp.next ! null && temp.next.next ! null) {ListNode start temp.next;ListNode end …
阅读更多...
数据库报错1045-Access denied for user ‘root‘@‘localhost‘ (using password: YES)解决方式

数据库报错1045-Access denied for user ‘root‘@‘localhost‘ (using password: YES)解决方式

文章目录 前言一、原因&#xff1a;1.数据库密码被篡改了&#xff01;2.数据库权限变更了&#xff01; 二、解决方法1.方法&#xff1a;编辑mysql配置文件my.ini2.步骤如下&#xff1a; 三、总结&#xff1a;mysql8.0版本下命令行mysqld -skip-grant-tables 失效 无法登陆问题的…
阅读更多...
【链表OJ 1】移除链表元素val

【链表OJ 1】移除链表元素val

大家好&#xff0c;欢迎来到我的博客&#xff0c;此题是关于链表oj的第一题&#xff0c;此后还会陆续更新博客&#xff0c;如有错误&#xff0c;欢迎大家指正。 来源:https://leetcode.cn/problems/remove-linked-list-elements/description/ 题目: 方法一:定义prev和cur指针…
阅读更多...
C++/Qt读写ini文件

C++/Qt读写ini文件

今天介绍C/Qt读写ini文件&#xff0c;ini文件一般是作为配置文件来使用&#xff0c;比如一些程序的一些默认参数会写在一个ini文件中&#xff0c;程序运行时会进行对应的参数读取&#xff0c;详细可以查看百度ini文件的介绍。https://baike.baidu.com/item/ini%E6%96%87%E4%BB%…
阅读更多...
Apache RocketMQ 命令注入

Apache RocketMQ 命令注入

漏洞简介 RocketMQ 5.1.0及以下版本&#xff0c;在一定条件下&#xff0c;存在远程命令执行风险。RocketMQ的NameServer、Broker、Controller等多个组件外网泄露&#xff0c;缺乏权限验证&#xff0c;攻击者可以利用该漏洞利用更新配置功能以RocketMQ运行的系统用户身份执行命令…
阅读更多...
【新人指南】给新人软件开发工程师的干货建议

【新人指南】给新人软件开发工程师的干货建议

在我是新人时&#xff0c;如果有前辈能够指导方向一下&#xff0c;分享一些踩坑经历&#xff0c;或许会让我少走很多弯路&#xff0c;节省更多的学习的成本。 这篇文章根据我多年的工作经验&#xff0c;给新人总结了一些建议&#xff0c;希望对你会有所帮助。 写好注释 没有注…
阅读更多...
Cocos Creator的rigidBody.applyForce变成了滚动

Cocos Creator的rigidBody.applyForce变成了滚动

序: 1、原因是因为没有调整摩擦系数physics-material 2、摩擦系数调整你要在你的节点 一个物理材料才会有的&#xff0c;教程没跳过去了所以没有 3、扩展阅读第一话&#xff1a;入行程序员的一波三折 最终效果&#xff1a; git录屏会卡&#xff0c;其实过程很平滑 正…
阅读更多...
计算机毕设 深度学习猫狗分类 - python opencv cnn

计算机毕设 深度学习猫狗分类 - python opencv cnn

文章目录 0 前言1 课题背景2 使用CNN进行猫狗分类3 数据集处理4 神经网络的编写5 Tensorflow计算图的构建6 模型的训练和测试7 预测效果8 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往…
阅读更多...
最新文章

Copyright @ 2022~2023