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

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

---

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

  

Map 和Set

• 🌈欢迎来到C++专栏~~Map 和Set
• • 一. 关联式容器
  • 二. 键值对
  • 三. C++中的Set
  • • 1️⃣Set的介绍
    • 2️⃣Set的使用（参照文档）
    • • 🌈set的模板参数列表
      • 🌈set的构造
      • 🌈set的迭代器
      • 🌈set的常见修改操作
    • 3️⃣Multiset的用法
  • 四. C++中的Map
  • • ⚡Map的介绍
    • ⚡Map的用法
    • • 💦Map的模板参数
      • 💦Map的迭代器
      • 💦Map的构造
      • 💦Map的常见修改操作
      • 💦Map的[ ]的使用（重头戏）
    • ⚡统计次数的两种方法
    • ⚡multimap的用法
  • 五. 来两道题目练练手
  • • 1️⃣前K个高频单词
    • 2️⃣两个数组的交集
• 📢写在最后

一. 关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、

forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

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

二. 键值对

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

举例子：

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

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

template 
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的模板参数列表

三个模板参数：

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

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

🌈set的构造

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

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

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

	//拷贝构造
	set set3(set2);

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

🌈set的迭代器

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

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

	set s = { 1, 2, 1, 6, 3, 8, 5 };
	//排序 + 去重
	set::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> s(a, a + sizeof(a) / sizeof(int));

🌈set的常见修改操作

🥑find & erase

普通的寻找和删除当然没有什么问题！

但是特殊的呢？

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

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

	set::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 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 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 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::iterator it = dict.begin();
	auto it = dict.begin();

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

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

💦Map的构造

void testmap1()
{
	map 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 map2(map1.begin(),map1.end());//迭代区间构造
	map map3(map2);//拷贝构造
	for (auto& e : map3)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

💦Map的常见修改操作

🌏Insert

find插入的是pair的结构体，此版本是不支持冗余的，插入只看key值，有相等的就不需要了

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

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

	//宏替换
	typedef pair 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 dict;
	dict.insert(make_pair("sort", "排序"));
	dict["insert"];                       //插入
	dict["insert"] = "插入";              //插入 + 修改value返回值
	dict["left"] = "左边";                //插入 + 修改    

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

• key已经在map中，返回pair（key_iterator，false）
• key不在map中，返回pair（new_key_iterator，true）

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

• ✨返回值是一个pair结构pair；第一个值是迭代器，第二个值是bool；第二个bool是用来反应是否插入成功，如果成功，则 第一个值迭代器就是指向插入的pair数据
• 第二个是kv的pair,是插入的pair数据

V& operator[](const K& key)
{
	pair 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 countMap;
	for (auto& str : arr)
	{
		map::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::iterator it = countMap.begin();
	while(it != countMap.end())
	{
		cout <first << ":" <second << endl;
		++it;
	}
	cout << endl;
}

第二种方法：[]

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

⚡multimap的用法

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

	multimap 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 topKFrequent(vector& words, int k) {
        map countMap;
        //统计次数   此时是i在上面，love在下面
        for(auto& str : words)
        {
            countMap[str]++;   
        }

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

        vector v;
        multimap<int, string, greater> :: 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 intersection(vector& nums1, vector& nums2) {
        set s1 (nums1.begin(), nums1.end());
        set s2 (nums2.begin(), nums2.end());

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

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

那如果是求差集呢？

📢写在最后