★ C++进阶篇 ★ map和set

Ciallo～(∠・ω< )⌒☆ ~ 今天，我将继续和大家一起学习C++进阶篇第四章----map和set ~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页：椎名澄嵐-CSDN博客

C++基础篇专栏：★ C++基础篇 ★_椎名澄嵐的博客-CSDN博客

C++进阶篇专栏：★ C++进阶篇 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

目录

一  序列式容器和关联式容器

二  set系列的使用

2.1 set类的介绍

2.2 set的构造和迭代器

2.3 set的增删查

2.4 set的使用

2.5 multiset和set的差异

2.6 两道set经典例题

三  map系列的使用

3.1 map类的介绍

3.2 pair类型介绍

3.3 map的构造

3.4 map的增删查

3.5 构造遍历及增删查使用样例

3.6 insert & operator[ ]

3.7 multimap和map的差异

一  序列式容器和关联式容器

序列式容器：有string、vector、list、deque、array、forward_list等。逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器：有map/set系列和unordered_map/unordered_set系列。关联式容器逻辑结构通常是非线性结构， 两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。

本次学习的map和set底层是红黑树，红⿊树是⼀颗平衡二叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。

二  set系列的使用

2.1 set类的介绍

set - C++ Reference (cplusplus.com)

• set的声明如上，T就是set底层关键字的类型
• set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是用红黑树实现，增删查效率是 ，迭代器遍历是走的搜索树的中序，所以是有序的。 O(logN) 。

2.2 set的构造和迭代器

set的各种构造~( 无参默认构造，迭代器区间构造， 拷贝构造，移动构造， initializer列表构造 )

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

2.3 set的增删查

set 不支持修改，主要有以下接口~

Member types
key_type -> T
value_type -> T

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find(const value_type& val);
// 查找val，返回Val的个数
size_type count(const value_type& val) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase(const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等val位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type& val) const;

2.4 set的使用

• 迭代器 & insert

#include<iostream>
#include<set>
using namespace std;
int main()
{
	// 去重+升序排序
	set<int> s1;
	// 去重+降序排序
	set<int, greater<int>> s2;
	s1.insert(5);
	s1.insert(2);
	s1.insert(7);
	s1.insert(5);
	//set<int>::iterator it = s.begin();
	auto it = s1.begin();
	while (it != s1.end())
	{
		// error C3892: “it”: 不能给常量赋值
		// *it = 1;
		cout << *it << " ";
		++it;
	}
	cout << endl; // 2 5 7

	// 插入⼀段initializer_list列表值，已经存在的值插入失败
	s1.insert({ 2,8,3,9 });
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl; // 2 3 5 7 8 9

	set<string> strset = { "sort", "insert", "add" };
	// 遍历string比较ascll码大小顺序遍历的
	for (auto& e : strset)
	{
		cout << e << " ";
	} 
	cout << endl; // add insert sort

	return 0;
}

•  erase & find 

int main()
{
	set<int> s = { 4,2,7,2,8,5,9 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除最小值
	s.erase(s.begin());
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 直接删除x
	int x;
	cin >> x;
	int num = s.erase(x);
	if (num == 0)
	{
		cout << x << "不存在！" << endl;
	}
	for (auto e : s)
	{
		cout << e << "删除成功！" << " ";
	}
	cout << endl;

	// 直接查找在利⽤迭代器删除x
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end())
	{
		// pos在erase后失效
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在！" << endl;
	}
	for (auto e : s)
	{
		cout << e << "删除成功！" << " ";
	}
	cout << endl;

	// 算法库的查找 O(N)
	auto pos1 = find(s.begin(), s.end(), x);
	// set⾃⾝实现的查找 O(logN)
	auto pos2 = s.find(x);

	// 利⽤count间接实现快速查找
	cin >> x;
	if (s.count(x))
	{
		cout << x << "在！" << endl;
	}
	else
	{
		cout << x << "不存在！" << endl;
	}
	return 0;
}

 注意迭代器失效的问题

int main()
{
	std::set<int> myset;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	// 实现查找到的[itlow,itup)包含[30, 60]区间
	// 返回 >= 30
	auto itlow = myset.lower_bound(30);
	// 返回 > 60
	auto itup = myset.upper_bound(60);

	// 实现查找到的[itlow,itup)包含[25, 55]区间
	// 返回 >= 25
	auto itlow = myset.lower_bound(25);
	// 返回 > 55
	auto itup = myset.upper_bound(55);

	// 删除这段区间的值
	myset.erase(itlow, itup);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

2.5 multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset⽀持值冗余，那么 insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下面的样例代码理解。

int main()
{
	// 相比set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 相比set不同的是，x可能会存在多个，find查找中序的第⼀个
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	// 相比set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;

	// 相比set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

2.6 两道set经典例题

1.  两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

首先用两个集合s1和s2来存储nums1和nums2的元素，因为集合会自动去重并且排序~
然后，函数用两个迭代器it1和it2来分别遍历s1和s2。在遍历的过程中，如果it1指向的元素小于it2指向的元素，就让it1向后移动一位；如果it1指向的元素大于it2指向的元素，就让it2向后移动一位；如果它们相等，就把这个元素加入到结果向量ret中，并且让it1和it2都向后移动一位~ 

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遍历是有序的，有序值，依次⽐较
        // ⼩的++，相等的就是交集
        vector<int> ret;
        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
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return ret;
    }
};

2.  环形链表

142. 环形链表 II - 力扣（LeetCode）

把每个节点遍历插入set， 若插入时发现set中已经有此节点，则带环。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while(cur)
        {
            if(s.count(cur))
                return cur;
            else
                s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

三  map系列的使用

3.1 map类的介绍

map的声明如上，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持小于比较，如果不⽀持或者需要的话可以自行实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。

3.2 pair类型介绍

map 的成员中的 value_type 使用了 pair 类型，那什么是 pair 类型呢~

3.3 map的构造

map的构造我们关注以下⼏个接口即可。 map⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

3.4 map的增删查

map增接口，插⼊的pair键值对数据，跟set所有不同，但是查和删的接⼝只⽤关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
// 查找k，返回k的个数
size_type count (const key_type& k) const;

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

3.5 构造遍历及增删查使用样例

int main()
{
	map<string, string> dict;
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1); // 有名对象
	dict.insert(pair<string, string>("second", "第二个")); // 匿名对象
	dict.insert(make_pair("third", "第三个")); // make_pair函数
	dict.insert({ "forth", "第四个" }); // C++11
	// 隐式类型转换构造
	map<string, string> dict2 = { { "left", "左边" }, { "right", "右边" }, { "insert", "插入" }, { "erase", "删除" } };
	
	auto it = dict.begin();
	while (it != dict.end())
	{
		// cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;// 存结构可以用箭头
		// 实际上是cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		++it;
	}
	return 0;
}

3.6 insert & operator[ ]

insert 插⼊⼀个 pair 对象

• 1 、如果 key 已经在 map 中，插⼊失败，则返回⼀个 pair 对象，返回 pair 对象 first 是 key 所在结点的迭代器， second 是 false。
• 2 、如果 key 不在在 map 中，插⼊成功，则返回⼀个 pair 对象，返回 pair 对象 first 是新插⼊ key 所在结点的迭代器， second 是 true。
• ⽆论插⼊成功还是失败，返回 pair 对象的 first 都会指向 key 所在的迭代器。
• 那么也就意味着 insert 插⼊失败时充当了查找的功能，正是因为这⼀点，insert 可以⽤来实现 operator[]。
• 需要注意的是这⾥有两个 pair ，不要混淆了，⼀个是 map 底层红⿊树节点中存的 pair ，另 ⼀个是 insert 返回值 pair。

operator[ ] 有插入，查找，修改，三个功能 ~

// operator的内部实现
mapped_type& operator[] (const key_type& k)
{
	// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，
	// 同时[]返回结点中存储mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能
	// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，
	// 返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能
	pair<iterator, bool> ret = insert({ k, mapped_type() });
	iterator it = ret.first;
	return it->second;
}

operator[ ]的使用：

确定key存在才能使用[ ]查找~要不就变成插入了~

int main()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	// key不存在->插入{ "insert", string() }
	dict["insert"];

	// 插入+修改
	dict["left"] = "左边";

	// 修改
	dict["left"] = "左边、剩余";

	// key存在->查找
	cout << dict["left"] << endl;

	return 0;
}

 使用find统计次数：

int main()
{
	// 利⽤find和iterator修改功能，统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// 先查找水果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
		// 2、在，则查找到的节点中⽔果对应的次数++
		auto ret = countMap.find(str);
		if (ret == countMap.end())
		{
				countMap.insert({ str, 1 });
		}
		else
		{
				ret->second++;
		}
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

使用operator[ ] 统计次数：

int main()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// []先查找水果在不在map中
		// 1、不在，说明水果第⼀次出现，则插⼊{水果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
		// 2、在，则返回水果对应的次数++
		countMap[str]++;
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

3.7 multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[ ]，因为⽀持key冗余，[ ]就只能⽀持插⼊了，不能⽀持修改。