当前位置： 首页 > article >正文

【C++进阶】set和map的基本使用（灰常详细）

article 2024/11/17 1:35:57

在这里插入图片描述

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：C++航路
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨

目录

  • 一、关联式容器
  • 二、键值对
  • 三、set容器
      • 3.1 概念
      • 3.2 set的使用
        • 3.2.1 构造
        • 3.2.2 insert + 迭代器
        • 3.2.3 find
        • 3.2.4 erase
        • 3.2.5 count
  • 四、multiset容器
  • 五、map容器
      • 5.1 概念
      • 5.2 insert
      • 5.3 访问容器数据 - 迭代器
      • 5.4 operator[]
  • 六、multimap
  • 七、交集与差集
      • 7.1 如何查找交集
      • 7.2 如何查找差集
  • 八、map和set的总结

一、关联式容器

来自【STL源码剖析】

  • 我们已经接触过STL中的部分容器，例如：vector、list、deque等，这些容器统称为序列式容器(其底层为线性序列的数据结构)

那关联式容器与序列式容器有什么区别？

  • 所谓关联式容器，就是每个元素都有一个键值(key）和一个实值(value)。当元素被插入到关联式容器中时，容器内部结构(可能是红黑树，也可能是哈希表)便依照其键值大小，以某种特点规则将这个元素放在一个合适的位置(类似于二叉树搜索树)。注意：关联式容器没有所谓头尾（只有最大元素和最小元素），所以不会有所谓push_back、push_front、pop_back、pop_front这样的操作行为

一般而言，关联式容器的内部结构是一个平衡二叉树，以便获得良好的搜索效率

二、键值对

在以上我们提到了键值，那么键值是什么呢？

  • 键值对是 一种用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量：key和value。其中，key表示键值，value表示与key对应的信息

关联式容器的实现离不开键值对，因此在标准库中，专门提供了这种pair。

pair就不在这里细说了，可以参考往期博客：点击跳转

三、set容器

3.1 概念

【文档介绍】

在这里插入图片描述

  • set其实就是之前在二叉搜索树说的key的模型。但是注意，set并不是完全是二叉搜索树，它的底层其实是一颗红黑树(一颗搜索树)
    *set不像map那样可以同时拥有实值(value)和键值(key)，set元素的键值就是实值，实值就是键值。
  • set不允许有两个元素有相同的键值。

3.2 set的使用

3.2.1 构造

在这里插入图片描述

  1. 默认构造
  2. 迭代区间构造
  3. 拷贝构造

和以往学习的STL容器类似，就不一一演示了

3.2.2 insert + 迭代器

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

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int a[] = { 2,1,5,6,3,4,8,10,7 };
	set<int> s;
	for (auto x : a)
	{
		s.insert(x);
	}

	set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;

	return 0;
}

【程序结果】

在这里插入图片描述

以上代码的逻辑是将数组a中元素全部插入到set容器中，可是有一个问题：为什么迭代器遍历出来的结果为升序呢？我们可以联想【二叉搜索树】，它的中序遍历是一个升序。因此，set容器底层迭代器的实现方式就是中序。

那如果我在set容器中插入重复元素，结果又会是如何呢？

在这里插入图片描述

我们发现：当插入的数出现冗余，它就有去重的效果。其实它的底层其实是：遇到键值冗余的数据就不插入。

那么接下来又牵扯到一个知识点：如果一个容器支持迭代器，那么它必定支持范围for，因为其底层就是靠迭代器实现的

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int a[] = { 2,1,5,6,3,4,8,10,7 };
	set<int> s;
	for (auto x : a)
	{
		s.insert(x);
	}

	for (auto x : s)
	{
		cout << x << " ";
	}
	cout << endl;

	return 0;
}

【程序结果】

在这里插入图片描述

3.2.3 find

在这里插入图片描述

在这里插入图片描述

#include <set>
#include <iostream>
using namespace std;

int main()
{
	set<int> s1;
	s1.insert(2);
	s1.insert(5);
	s1.insert(1);
	s1.insert(4);
	s1.insert(3);
	
	// 查找3
	set<int>::iterator pos = s1.find(3);
	if (pos != s1.end())
		cout << "找到了3" << endl;
	else
		cout << "没找到3" << endl;

	return 0;
}

【输出结果】

在这里插入图片描述

  • 问题1：似乎算法库algorithm中也有一个find函数，那么为什么set容器还要再设计find函数呢？

它们除了功能是相同的以为，在效率方面不是一样，set实现的find函数查找的时间复杂度是O(logN)，大的往右子树查找，小的往左子树查找，因此只需要查找高度次；而算法库中的find是利用迭代器来遍历整颗树（暴力查找），时间复杂度为O(N)。因此，实际中有运用到find函数，建议使用内置的。

  • 问题2：我们可以通过set的迭代器改变set的元素值吗？
#include <set>
#include <iostream>
using namespace std;

int main()
{
	set<int> s1;
	s1.insert(2);
	s1.insert(5);
	s1.insert(1);
	s1.insert(4);
	s1.insert(3);

	// 查找4,找到了修改成100
	set<int>::iterator pos = s1.find(4);
	if (pos != s1.end())
	{
		*pos = 100;
	}
	else
	{
		cout << "没找到3" << endl;
	}

	return 0;
}

【程序结果】

在这里插入图片描述

答案已经很明显了！不能修改！因为set元素值就是其键值，修改了会关系到set元素的排列规则。如果任意改变set元素值，会严重破坏set组织。通过查阅文档，我们发现普通迭代器被定义为const迭代器

在这里插入图片描述

3.2.4 erase

在这里插入图片描述

大家看上图，迭代器方式删除和给值删除方式有没有什么差异? 第给值删除不是更加方便吗？直接给个值删除就行，为什么要提供第一种?

大家可以认为第二种就是依靠第一种实现的。这是因为在大多情况，还是要依靠查找来删除值。

除此之外，给值删除方式有个特点：删除除容器以外的值不会报错

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int a[] = { 2,1,5,6,3,4,8,10,7 };
	set<int> s;
	for (auto x : a)
	{
		s.insert(x);
	}

	// 删除100
	s.erase(100);

	for (auto x : s)
	{
		cout << x << " ";
	}
	cout << endl;

	return 0;
}

【程序结果】

在这里插入图片描述

如果使用迭代删除方式，没有对find的返回值进行特判，就会发生断言错误

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int a[] = { 2,1,5,6,3,4,8,10,7 };
	set<int> s;
	for (auto x : a)
	{
		s.insert(x);
	}

	// 删除100
	set<int>::iterator sit = s.find(100);
	s.erase(sit);

	for (auto x : s)
	{
		cout << x << " ";
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

3.2.5 count

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

除了find可以查找，count也可以。count作用是：传一个值，就会返回这个值出现了几次。因此，它也可以用来查找。

在这里插入图片描述

但是有了find函数，再设计count函数是不是有点冗余。其实count在后面另有用处…

四、multiset容器

在这里插入图片描述

set 还有一个亲兄弟：multiset，它和set容器最大的区别是：允许出现数据冗余，即插入冗余的数据一定是成功的。

除此之外，multiset和set的操作没什么区别，都是一模一样。大家可以通过文档自行查阅：点击跳转

这里单独演示一下允许数据冗余的效果

在这里插入图片描述

所以，multiset 才是真正的排序，可以出现数据冗余的情况，set则是去重 + 排序

除此之外，刚刚说的 count函数其实就是为multiset准备的

在这里插入图片描述

在这里插入图片描述

那么问题来了，如果我想查找的数据恰好出现冗余的情况，请问返回的数据是第几次出现的数据呢？

可以打印出它们的地址来看

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> v = { 1,3,5,7,5,9,2,3,3,3 };
	multiset<int> ms1(v.begin(), v.end());

	auto pos = ms1.begin();
	while (pos != ms1.end())
	{
		cout << *pos << "：" << &(*(pos)) << endl;
		pos++;
	}
	cout << endl;

	// 查找5
	cout << "5：" << &(*(ms1.find(5))) << endl;

	return 0;
}

【输出结果】

在这里插入图片描述

在实际中，multiset用的比较少，重点掌握set即可

五、map容器

5.1 概念

在这里插入图片描述

  • map是二叉搜索树改造后的key/value模型，是一个真正意义上的 键值对
  • map的特性是：所有元素都会根据元素的键值自动被排序。map的所有元素都是用pair结构存储的，同时拥有实值(value)和键值(key)。pair的第一个元素(first)被视为键值，第二个元素(second)被视为实值。
  • 注意：map不允许两个元素拥有相同的键值

5.2 insert

在这里插入图片描述

我们首先可以看看插入接口，注意看其参数类型：value_type，它是key的类型还是value的类型呢？可以查阅文档：

在这里插入图片描述

value_type是一个pair结构，并且key_type（也就是键值key）是由const修饰的，表明不能被修改！

想补充pair知识可以参考往期博客：点击跳转

接下来举一个代码样例：字典

在这里插入图片描述

插入的方式不能向上面这样写，这是很多初学者犯的错误。刚刚说过，键值和实值需要用pair结构来存

int main()
{
    map<string, string> dict;
    // 写法一:创建pair的结构对象
    pair<string, string> p("插入", "insert");
    dict.insert(p);

    // 写法二：pair的匿名对象
    dict.insert(pair<string, string>("插入", "insert"));

    // 写法三：以上的写法非常繁琐，如果没有展开命名空间的话
    // 因此可以使用make_pair简化代码
    dict.insert(make_pair("删除", "erase"));

    // 写法四：用花括号括起来
    // 这种方式非常简洁，但是有一个限制
    // 编译器必须支持C++11:多参数构造函数支持隐式类型转化
    // C++98:单参数构造函数支持隐式类型转换
    dict.insert({"查找", "find"});

    return 0;
}

5.3 访问容器数据 - 迭代器

  • map同样支持迭代器

在这里插入图片描述

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

int main()
{
    map<string, string> dict;
    pair<string, string> p("插入", "insert");
    dict.insert(p);
    dict.insert(pair<string, string>("插入", "insert"));
    dict.insert(make_pair("删除", "erase"));
    dict.insert({ "查找", "find" });

    // 迭代器遍历
    map<string, string>::iterator mit = dict.begin();
    while (mit != dict.end())
    {
        cout << *mit << " ";
        ++mit;
    }
    cout << endl;

    return 0;
}

在这里插入图片描述

很多初学者大概率会写出以上代码，但是编译不通过！从提示可以看出：pair不支持流插入<<

再回过头来分析：数据是存在pair结构里的，那么像访问结构体内的元素，是不是可以用->或者*操作符来访问数据。并且在【map概念部分】说过了：pair的第一个元素(first)被视为键值，第二个元素(second)被视为实值

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

int main()
{
    map<string, string> dict;
    pair<string, string> p("插入", "insert");
    dict.insert(p);
    dict.insert(pair<string, string>("插入", "insert"));
    dict.insert(make_pair("删除", "erase"));
    dict.insert({ "查找", "find" });

    // 迭代器遍历
    // ->访问方式
    map<string, string>::iterator mit = dict.begin();
    while (mit != dict.end())
    {
        cout << mit->first << "：" << mit->second << endl;
        ++mit;
    }
    cout << endl;

    // *访问方式
    mit = dict.begin();
    while (mit != dict.end())
    {
        cout << (*mit).first << "：" << (*mit).second << endl;
        ++mit;
    }
    cout << endl;

    return 0;
}

【运行结果】

在这里插入图片描述

同理地，既然map也支持迭代器，那么就必定支持范围for

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

int main()
{
    map<string, string> dict;
    pair<string, string> p("插入", "insert");
    dict.insert(p);
    dict.insert(pair<string, string>("插入", "insert"));
    dict.insert(make_pair("删除", "erase"));
    dict.insert({"查找", "find"});

    // 访问for
    for (const auto &x : dict)
    {
        cout << x.first << ":" << x.second << endl;
    }
    return 0;
}

【运行结果】

在这里插入图片描述

  • 那么现在就有一个问题：可以通过map的迭代器改变map的元素内容吗？

如果是想修改键值(key)是不行的。还是和set一样的原因：map元素的键值关系到map元素的排列规则。任意改变map元素的key将会严重破坏map组织。
但如果想要修改元素的实值(value)，那么是可以的。因为map元素的实值并不影响map的排列规则

在这里插入图片描述

官方文档同样也给出了答案：键值key被const修饰，表示不能被修改。

5.4 operator[]

大家可能会感到奇怪，map底层是一个树形结构，按理来说是不支持随机访问的，可是为什么map支持operator[]呢？

map常见的使用场景是：统计出现过的次数

假设我要写一个统计水果出现的次数，大部分人都可以写出以下代码

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

// ### 5.3 operator[]
// 大家可能会感到奇怪，map底层是一个树形结构，按理来说是不支持随机访问的，可是为什么map支持`operator[]`呢？

int main()
{
    string s[] = {"西瓜", "西瓜", "香蕉", "苹果", "桃子", "香蕉", "香蕉", "香蕉"};
    map<string, int> dict;
    // 将数组内的元素放进map中来统计次数
    for (auto x : s)
    {
        // 如果水果刚刚出现第一次出现，就将记为1
        map<string, int>::iterator pos = dict.find(x);
        if (pos == dict.end())
        {
            dict.insert(make_pair(x, 1));
        }
        // 否则就是出现过两次以上
        else
        {
            pos->second++;
        }
    }

    for (const auto &x : dict)
    {
        cout << x.first << ":" << x.second << endl;
    }
    return 0;
}

【运行结果】

在这里插入图片描述

但是以上代码还可以优化：使用operator[]

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

// ### 5.3 operator[]
// 大家可能会感到奇怪，map底层是一个树形结构，按理来说是不支持随机访问的，可是为什么map支持`operator[]`呢？

int main()
{
    string s[] = { "西瓜", "西瓜", "香蕉", "苹果", "桃子", "香蕉", "香蕉", "香蕉" };
    map<string, int> dict;
    // 将数组内的元素放进map中来统计次数
    for (auto x : s)
    {
        dict[x]++;
    }

    for (const auto& x : dict)
    {
        cout << x.first << ":" << x.second << endl;
    }
    return 0;
}

【运行结果】

在这里插入图片描述

代码改进后结果也是正确的，并且比第一种简洁多了！那么，operator[]到底是何方神圣呢？我们一起来研究一下

我们可以通过文档来分析

在这里插入图片描述

在这里插入图片描述

注意看它的参数和返回类型，这里的operator[]并不是以往我们所认识的下标访问。它是通过键值key来返回实值value的引用！

那么这里有个问题，它是如何找到实值，然后进行修改的呢？

文档同样给出了答案，operator[]等价于调用以下这么个长东西

在这里插入图片描述

面对这么长的代码一定要耐下心来从内向外剖析

在这里插入图片描述

因此，就要研究insert的返回值

在这里插入图片描述

简单翻译一下：

insert会返回一个pair结构，其中这个pair的first被设置成了一个迭代器，而迭代器的指向分两种情况：

  1. 键值key已经在树里，那么就返回树里面key所在结点的迭代器
  2. 键值key不在树里，那么就返回新插入key所在结点的迭代器

在这里插入图片描述

以上的长代码可以分解如下：

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

通过以上解释，会发现operator[]有插入、修改、插入+修改、查找

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

// ### 5.3 operator[]
// 大家可能会感到奇怪，map底层是一个树形结构，按理来说是不支持随机访问的，可是为什么map支持`operator[]`呢？

int main()
{
    // 有插入、修改、插入+修改、查找
    map<string, string> m1;
    
    // 插入
    m1["hello"] = "你好";
    m1["sort"] = "插入";

    for (const auto& x : m1)
    {
        cout << x.first << ":" << x.second << endl;
    }

    // 修改
    m1["sort"] = "排序";

    for (const auto& x : m1)
    {
        cout << x.first << ":" << x.second << endl;
    }
    return 0;
}

【运行结果】

在这里插入图片描述

六、multimap

在这里插入图片描述

multimap中允许出现多个重复的键值。因此，operator[]就无法确认调用者的意图，也就是不知道要返回哪个 键值对应的结点。所以multimap中没有提供operator[]，当然其他操作都是和map相同

还有的是：查找find时，返回的是中序遍历中第一次出现元素的迭代器；另外计数count返回的则是当前键值的数量

七、交集与差集

7.1 如何查找交集

交集，指两个数组中相同的元素所构成的集合

求交集的步骤如下：

  1. 先将两个数组 排序 + 去重
  2. 遍历两个数组
  3. 如果不相等，小的 ++
  4. 相等就是交集，记录下来
  5. 其中一方走完，所有交集就查找完了

排序 + 去重，就可以使用set

相关题目：点击跳转

//349. 两个数组的交集
//https://leetcode.cn/problems/intersection-of-two-arrays/description/

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //排序 + 去重
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());

        //查找交集
        vector<int> v;
        auto it1 = s1.begin();
        auto it2 = s2.begin();

        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 < *it2)
                ++it1;
            else if(*it1 > *it2)
                ++it2;
            else
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
        }

        return v;
    }
};

7.2 如何查找差集

至于差集的查找，思路和交集差不多

求差集的步骤如下：

  1. 先将两个数组 排序 + 去重
  2. 遍历两个数组
  3. 如果相等，同时 ++
  4. 不相等，小的一方记录后，再 ++
  5. 其中一方走完，再遍历另一方，此时其中的所有元素都是差集

八、map和set的总结

  • set
  1. 只有键值，其键值就是实值，所以传递参数时，只需要传递实值
  2. 自带去重机制，不允许出现数据冗余
  3. 使用迭代器遍历容器时，结果为有序，并且默认为升序
  4. 即使是普通迭代器，也不运行修改键值
  • map
  1. 既包含键值，也包含实值。插入时，需要传pair对象
  2. 自带去重机制，不允许出现数据冗余
  3. 使用迭代器遍历容器时，结果为有序，并且默认为升序。是靠键值进行排序的
  4. 普通迭代器不运行修改键值，但运行修改实值

http://www.kler.cn/a/106616.html

相关文章：

  • 跨域请求解决的核心
  • 二五、pxe自动装机
  • 坚果云·无法连接服务器（无法同步）
  • Linux之vim全选，全部复制，全部删除
  • 微搭低代码入门05循环
  • HarmonyOS ArkTs 解决流式传输编码问题
  • Chapter1：C++概述
  • 三代自动驾驶系统及主流科技公司自动驾驶技术方案简介
  • 在Mac上安装MongoDB 5.0
  • 如何构造强一致性系统？理解数据一致性里的2PC和TCC模式原理，以及如何做（有图）
  • LeetCode 面试题 16.03. 交点
  • clang-前端插件-给各种无花括号的“块”加花括号-基于llvm15--clang-plugin-add-brace
  • STM32：TTL串口调试
  • 计算机操作系统重点概念整理-第二章 进程管理【期末复习|考研复习】
  • 【ModbusTCP协议】
  • Spring Authorization Server 1.1 扩展实现 OAuth2 密码模式与 Spring Cloud 的整合实战
  • C++数据结构X篇_21_插入排序（稳定的排序）
  • FPGA与人工智能泛谈-01
  • 第五天：前端页面展示不出来
  • 分布式消息队列:Rabbitmq(2)
  • Ant Design Pro【面包屑导航】二级路由和三级路由都有component的情况，三级不显示component的页面，怎么解决？
  • matlab simulink 四旋翼跟拍无人机仿真
  • Non-constant range: argument must be an integer literal
  • vue3中刷新当前页面的三种方法
  • 简述一下伪共享的概念以及如何避免
  • 记录：获取windows当前登录的用户信息