【高阶数据结构】Map 和 Set（详解）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

🌈欢迎来到C++专栏~~Map 和Set

  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
  • 目前状态大三非科班啃C++中
  • 🌍博客主页张小姐的猫~江湖背景
  • 快上车🚘握好方向盘跟我有一起打天下嘞
  • 送给自己的一句鸡汤🤔
  • 🔥真正的大师永远怀着一颗学徒的心
  • 作者水平很有限如果发现错误可在评论区指正感谢🙏
  • 🎉🎉欢迎持续关注
    在这里插入图片描述

请添加图片描述

Map 和Set

请添加图片描述

一. 关联式容器

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

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

关联式容器容器结构底层实现
set、map、multiset、multimap树型结构平衡搜索树红黑树
unordered_set、unordered_map、unordered_multiset、unordered_multimap哈希结构哈希表哈希桶

二. 键值对

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

举例子

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

SGI-STL中关于键值对pair的定义

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

三. C++中的Set

1️⃣Set的介绍

Set本质就是Key的模型就是确认该值在不在

2️⃣Set的使用参照文档

Set支持的操作是增删查不能改因为底层是一颗搜索树改了就乱了

🌈set的模板参数列表

在这里插入图片描述

三个模板参数

  • Tset中存放元素的类型实际在底层存储<value, value>的键值对
  • Compare仿函数set中元素默认按照小于来比较如果比较的方式不满意可以自己去控制比较规则自己写仿函数
  • Allocset中元素空间的管理方式使用STL提供的空间配置器 内存池

注意在使用set时需要包含头文件set

🌈set的构造

在这里插入图片描述

拷贝都是深拷贝要拷贝一棵树代价很大

void testset2()
{
	set<int> set1;//空构造
	int num[] = { 1, 2, 3, 7, 9, 3, 10, 1 };

	//区间构造
	set<int> set2(num, num + sizeof(num) / sizeof(num[0]));

	//拷贝构造
	set<int> set3(set2);

	for (auto& e : set3) //打印结果看出set可以去重
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

🌈set的迭代器

此处和之前的容器差不多所以就省略过直接看图

函数说明功能介绍
begin + end重点获取第一个数据位置的 获取最后一个数据的下一个位置的
cbegin() const 和 cendconst无非就是针对const的版本不可写
rbegin + rend获取最后一个数据位置获取第一个数据前一个位置
反向迭代器同理

在这里插入图片描述

void test_set()
{
	//set<int> s;
	//s.insert(1);
	//s.insert(2);
	//s.insert(3);

	set<int> s = { 1, 2, 1, 6, 3, 8, 5 };
	//排序 + 去重
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//支持迭代器也就支持范围for了
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

如果我要整成降序的呢

  1. 反向迭代器
  2. 仿函数 less—>greater
	int a[] = { 1, 2, 1, 6, 3, 8, 5 };
	set<int, greater<int>> s(a, a + sizeof(a) / sizeof(int));

🌈set的常见修改操作

🥑find & erase

在这里插入图片描述

普通的寻找和删除当然没有什么问题
但是特殊的呢

  • 我删除一个不存在的值呢会怎么样

所以写完find要判断一下是否真正的找到了在才删除

	set<int>::iterator pos = s.find(20);
	if (pos != s.end())
	{
		s.erase(pos);
	}

🥑count

在这里插入图片描述

在这里插入图片描述

但是count不是为此设计的是为了和multiset保持接口的一致性所以都设计了

提一嘴
🥑lower_bound 和 upper_bound

我想把某个范围的值都找到

  • lower_bound 下限的意思返回 >= val的值
  • upper_bound上限的意思返回 > val的值
	itlow = myset.lower_bound(35);//返回大于等于35的值   
	itup = myset.upper_bound(60);//返回大于60的值

在这里插入图片描述

3️⃣Multiset的用法

multiset容器与set容器实现和接口基本一致唯一区别就是multiset 允许键值冗余即multiset容器当中存储的元素是可以重复的

代码展示

void testset4()
{
	int a[] = { 1, 2, 1, 6, 3, 8, 5 };
	//允许键值冗余
	multiset<int> s(a, a + sizeof(a) / sizeof(int));
	
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果展示

在这里插入图片描述

键值冗余之后我们的find该怎么样找数据呢

  1. find时如果有多个值返回中序的第一个
void testset4()
{
	int a[] = { 1, 2, 1, 6, 3, 8, 5, 3};
	//允许键值冗余
	multiset<int> s(a, a + sizeof(a) / sizeof(int));
	
	//find时如果有多个值返回中序的第一个
	auto pos = s.find(3);
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;//这里的++ 就是加到下一个的3的位置
	}
	cout << endl;
}

在这里插入图片描述

当然如果是要删除erase3的时候肯定是删除所有的3

四. C++中的Map

⚡Map的介绍

  1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair: typedef pair<const key, T> value_type;
  3. 在内部map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。
  5. map支持下标访问符即在[]中放入key就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。

⚡Map的用法

💦Map的模板参数

在这里插入图片描述

参数说明

  1. key: 键值对中key的类型

  2. T 键值对中value的类型

  3. Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

  4. Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器

使用map要包含map的头文件哦

💦Map的迭代器

	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();

	while (it != dict.end())
	{
		//pair没有重载流插入
		//cout << (*it).first << (*it).second << endl;
		//cout << it->->first << it->->second << endl; 
		//operator重载
		cout << it->first << it->second << endl;

		++it;
	}
	
	for (const auto& kv : dict)//给const & 引用
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

💦Map的构造

在这里插入图片描述

void testmap1()
{
	map<int, int> map1;//空构造
	int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 };
	for (auto e : num)
	{
		map1.insert(make_pair(e,e));
	}
	map<int, int> map2(map1.begin(),map1.end());//迭代区间构造
	map<int, int> map3(map2);//拷贝构造
	for (auto& e : map3)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

💦Map的常见修改操作

🌏Insert

在这里插入图片描述
find插入的是pair的结构体此版本是不支持冗余的插入只看key值有相等的就不需要了

void test_map1()
{
	map<string, string> dict;
	//pair<string, string> kv1("sort", "排序");
	//dict.insert(kv1);

	//匿名对象
	dict.insert(pair<string, string>("sort", "排序"));
	dict.insert(pair<string, string>("test", "测试"));
	dict.insert(pair<string, string>("string", "字符串"));

	//宏替换
	typedef pair<string, string> Dictkv;
	dict.insert(Dictkv("string", "字符串"));
}

还有一个很便捷的操作make_pair构造匿名的pair返回

	dict.insert(make_pair("string", "字符串"));//很常用

在这里插入图片描述

💦Map的[ ]的使用重头戏

在这里插入图片描述

[]:的功能查找 + 修改

  • map中有这个key就返回value的引用查找 + 修改
  • map中没有这个key会插入一个pair(key, K())会插入这个key值value就要去调用默认构造最后还是返回value的引用 插入+ 修改

如果是int就是0是指针就默认空指针

	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict["insert"];                       //插入
	dict["insert"] = "插入";              //插入 + 修改value返回值
	dict["left"] = "左边";                //插入 + 修改

在这里插入图片描述

可以看见Insert的返回值和实现

在这里插入图片描述

  • key已经在map中返回pairkey_iteratorfalse
  • key不在map中返回pairnew_key_iteratortrue

[]其底层实现有两个pair结构

  • ✨返回值是一个pair结构pair<iterator, bool>第一个值是迭代器第二个值是bool第二个bool是用来反应是否插入成功如果成功则 第一个值迭代器就是指向插入的pair数据
  • 第二个是kv的pair,是插入的pair数据
V& operator[](const K& key)
{
	pair<iterator, bool> ret = insert(make_pair(key, V());
	//返回key节点的迭代器迭代器是map的再调用->就是pair*,取second
	return ret.first->second;
}

⚡统计次数的两种方法

  1. 第一次找不到的时候make_pair使得count = 1
  2. 后面每遍历一次就++一次
//统计次数
void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			/*(*it).second++;*/
			//it->->second++;  第一个箭头是调用operator->返回的是pair*再->指向成员
			it->second++;
		}
		else
		{
			//找不到
			countMap.insert(make_pair(str, 1));
		}
	}

	//遍历
	map<string, int>::iterator it = countMap.begin();
	while(it != countMap.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

在这里插入图片描述

第二种方法[]

	map<string, int> countMap;
	for (auto& str : arr)
	{
		//1、str不在countMap中插入pair(str, int()),然后对返回次数++
		//2、str在的话就返回value的引用次数++
		countMap[str]++;
	}

在这里插入图片描述

⚡multimap的用法

multimap容器与map容器的底层实现以及成员函数的接口都是基本一致区别是multimap 允许键值冗余即multimap容器当中存储的元素是可以重复的

	multimap<string, string> mdict;
	mdict.insert(make_pair("sort", "排序"));
	mdict.insert(make_pair("left", "左边"));
	mdict.insert(make_pair("left", "左边"));
	mdict.insert(make_pair("left", "你猜"));

在这里插入图片描述

五. 来两道题目练练手

1️⃣前K个高频单词

题目地址传送

在这里插入图片描述

要注意要按出现次数按大到小的来如果出现次数相等要按字母顺序排序比如i和love都出现了两次那么 按字母顺序i要在love之前

思路

  1. 使用一个countMap统计各种单词的出现的次数统计次数 此时是i在上面love在下面
  2. 再写一个sortMap按照字符出现的次数进行降序排列
  3. 不同的单词出现相同的次数会按字典序排列

在这里插入图片描述
注意不能用反向迭代来进行不然同样的次数love会在前面i在后就违背了题意

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        //统计次数   此时是i在上面love在下面
        for(auto& str : words)
        {
            countMap[str]++;   
        }

        // apple 3  \  i  2  \  love  2 \ j  5
        multimap<int, string, greater<int>> sortMap;//排降序
        for(auto& kv : countMap)
        {
            sortMap.insert(make_pair(kv.second, kv.first)); 
        }

        vector<string> v;
        multimap<int, string, greater<int>> :: iterator it = sortMap.begin();

        for(size_t i = 0; i < k; i++)
        {
            v.push_back(it->second);
            it++;
        }
        return v;
    }
};

2️⃣两个数组的交集

题目地址传送

在这里插入图片描述

思路
请添加图片描述

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());

        set<int> :: iterator it1 = s1.begin();
        auto it2 = s2.begin();

        vector<int> v;
        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;
    }
};

那如果是求差集呢

在这里插入图片描述

📢写在最后

在这里插入图片描述

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【有营养的算法笔记】基础算法 —— 高精度算法(加减乘除)

下一篇：【算法】静态单链表、双链表、单调栈与单调队列

“【高阶数据结构】Map 和 Set（详解）” 的相关文章

初始化一个GCP项目并用gcloud访问操作1年前 (2023-02-02)
前端开发：如何正确地跨端1年前 (2023-02-02)
HMS Core 6.8.0版本发布公告1年前 (2023-02-02)
centos7.6在防火墙放开端口1年前 (2023-02-02)
低代码江湖，如何区分“孙悟空”和“六耳猕猴”？1年前 (2023-02-02)
【数据库课程设计】SQLServer数据库课程设计（学生宿舍管理），课设报告+源码+数据库关系图1年前 (2023-02-02)
c++深搜与宽搜的解题思路1年前 (2023-02-02)
三十一岁只是一种新的二十一岁1年前 (2023-02-02)
vue+vite+pinia+axios使用1年前 (2023-02-02)
2023年华为HCIA-Datacom最新题库H12-811，亲测高分PASS_华为hcia最新题库1年前 (2023-02-02)

阿里云国际版