【C++标准模版库】map和set的介绍及使用

2024-09-29 10:10:56

map和set

一.序列式容器和关联式容器
二.set系列的使用
- 1.set和multiset参考文档
- 2.set类的介绍
- 3.set的构造和迭代器
- 4.set的增删查
- 5.insert和迭代器遍历使用
- 6.find和erase的使用
- 7.erase迭代器失效问题
- 8.lower_bound与upper_bound
- 9.multiset和set的差异
- 10.set解决：leetcode例题
- - 1.两个数组的交集
  - 2.交集与差集的应用：数据同步
  - 3.环型链表||
三.map系列的使用
- 1.set和multiset参考文档
- 2.map类的介绍
- 3.pair类型介绍
- 4.map的构造和迭代器
- 5.map的增删查
- 6.map构造遍历及增删查的使用
- 7.map的数据修改：重载operator[]
- 8.map的迭代器和[]功能样例
- 9.multimap和map的差异
- 10.map解决：leetcode例题
- - 1.随机链表的复制
  - 2.前K个高频单词

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

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红黑树，红黑树是一颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。而unordered_map和unordered_set的低层是哈希表。

二.set系列的使用

1.set和multiset参考文档

参考文档

2.set类的介绍

template < class T,                    // set::key_type/value_type
	       class Compare = less<T>,    // set::key_compare/value_compare
	       class Alloc = allocator<T>  // set::allocator_type 空间配置器
           > class set;

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

3.set的构造和迭代器

set的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历（双向迭代器：支持++/–，但是不支持+/-），遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

//empty (1) ⽆参默认构造 
explicit set(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

//range (2) 迭代器区间构造 
template <class InputIterator>
set(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& = allocator_type());
 
//copy (3) 拷⻉构造 
set(const set& x);

//initializer list (4) C++11支持: initializer 列表构造 
set(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

//迭代器是一个双向迭代器 
iterator -> a bidirectional iterator to const value_type

//正向迭代器 
iterator begin();
iterator end();

//反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

int main()
{
	vector<int> v = { 1,5,4,2,3,6,7,8,9 };

	set<int> s1; //无参默认构造
	set<int> s2(v.begin(), v.end()); //迭代器区间构造
	set<int> s3(s2); //拷贝构造
	set<int> s4 = { 1,5,4,2,3,6,7,8,9 }; //列表初始化构造

	//1.正向迭代器
	auto it = s2.begin();
	while (it != s2.end())
	{
		cout << *it << " "; //输出：1 2 3 4 5 6 7 8 9
		++it;
	}
	cout << endl;

	//2.set是双向迭代器迭代器支持++/--，但是不是随机迭代器不支持+/-
	it = --s2.end(); auto end = --s2.begin();
	while (it != end)
	{
		cout << *it << " "; //输出：9 8 7 6 5 4 3 2 1
		--it;
	}
	cout << endl;

	//3.反向迭代器
	set<int>::reverse_iterator rit = s4.rbegin();
	while (rit != s4.rend())
	{
		cout << *rit << " "; //输出 9 8 7 6 5 4 3 2 1
		++rit;
	}
	cout << endl;

	return 0;
}

4.set的增删查

set支持增删查，但是set不支持修改，因为修改之后就会可能失去红黑树的性质。

set的增删查关注以下几个接口即可：

template < class T,                    // set::key_type/value_type
	       class Compare = less<T>,    // set::key_compare/value_compare
	       class Alloc = allocator<T>  // set::allocator_type 空间配置器
           > class set;
           
//1.单个数据插入，如果已经存在则插入失败 
pair<iterator, bool> insert(const value_type& val);

//2.列表插入，已经在容器中存在的值不会插入 
void insert(initializer_list<value_type> il);

//3.迭代器区间插入，已经在容器中存在的值不会插入 
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;

//1.删除一个迭代器位置的值 
iterator erase(const_iterator position);

//2.删除val，val不存在返回0，存在返回1 
size_type erase(const value_type& val);

//3.删除一段迭代器区间的值 
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;

Member types 
key_type   -> The first template parameter (T)
value_type -> The first template parameter (T)

注意：

set是key结构, map才是key/value结构, 这里的key_type和value_type是为了保持与map一致，所以才有了value_type，在set中其实就是key，当然key_type也是key。
set不支持插入相同的数据，multiset支持插入相同的数据。

5.insert和迭代器遍历使用

int main()
{
	vector<int> v{ 8,7,9 };

	set<int> s1;
	s1.insert(1); 
	s1.insert(2);
	s1.insert(2); //1.单个数据插入，如果已经存在则插入失败 
	s1.insert(3); 

	s1.insert({ 4,5,6,5 }); //2.插入列表，同理如果已经存在则该数据插入失败

	s1.insert(v.begin(), v.end()); //3.插入迭代器区间

	//排序+去重
	//升序<：set<int, less<int>> s;
	//降序>：set<int, greater<int>> s;

	set<int> s; //默认传入了仿函数less<int>
	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	s.insert(8);
	s.insert(1);

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 10; 不支持修改
		cout << *it << " "; //输出：1 2 5 7 8
		++it;
	}

	//set(initializer_list<value_type> il);

	//单参数支持隐式类型转换：构造tmp+用tmp拷贝构造strset1——>优化为直接构造strset1
	set<string> strset1 = { "sort", "insert", "add" }; 

	//调用默认构造
	set<string> strset2({ "sort", "insert", "add" });

	//遍历strset1比较ascll码大小顺序遍历的：set的范围for本质就是迭代器的中序遍历
	for (auto& e : strset1)
	{
		cout << e << " "; //输出：add insert sort
	}
	cout << endl;

	return 0;
}

6.find和erase的使用

算法库的遍历查找，适用于各种容器： O(N) auto pos1 = find(s.begin(), s.end(), x);
set自身实现的查找，利用二叉搜索树进行查找： O(logN) auto pos2 = s.find(x);

//1.删除一个迭代器位置的值 
iterator erase (const_iterator position);

//2.删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);

//3.删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);


//查找val，返回val所在的迭代器，没有找到返回end() 
iterator find (const value_type& val);

//查找val，返回Val的个数 
size_type count (const value_type& val) const;

注意：删除具体的值返回size_type而不是bool是为了与multiset保持一致，multiset含有重复数据（例如：multiset中有3个5，若要删除5，则返回值就是3）

int main()
{
	set<int> s = { 4,6,5,8,9,7,2,3,1 };

	//1.迭代器删除最小值
	s.erase(s.begin());

	//2.删除具体的值val：低层就是find+迭代器删除
	int x;
	cin >> x;
	int num = s.erase(x);
	if (num == 0)
		cout << x << "不存在！" << endl;
	else
		cout << x << "删除成功！" << endl;

	//3.删除一段迭代器区间的值
	auto first = s.find(4);
	auto last = s.find(6);
	s.erase(first, last); //删除的值位于迭代器区间[first,last)中
	for (auto e : s)
		cout << e << " ";

	//find+迭代器删除：与上面等价
	int y;
	cin >> y;
	auto pos = s.find(y); //找到返回该值的迭代器，找不到返回s.end()
	if (pos != s.end())
		s.erase(pos);
	else
		cout << y << "不存在！" << endl;

	//利用count间接实现快速查找
	int z;
	cin >> z;
	if (s.count(z))
		cout << z << "在！" << endl;
	else
		cout << z << "不存在！" << endl;

	return 0;
}

7.erase迭代器失效问题

int main()
{
	set<int> s = { 1,5,6,3,2,4 };
	auto pos = s.find(3);
	s.erase(pos); //pos位置的迭代器失效
	cout << *pos << endl; //强行访问导致程序崩溃

	pos = s.erase(pos); //解决办法
	cout << *pos << endl; //输出：3的中序的下一个迭代器4

	//但是若查找的是6的话，那么删除6后迭代器pos就变成了s.end()，此时访问程序崩溃

	return 0;
}

8.lower_bound与upper_bound

//返回大于等于val位置的迭代器：按照搜索树的规则找
iterator lower_bound(const value_type& val) const;

//返回大于val位置的迭代器：按照搜索树的规则找
iterator upper_bound(const value_type& val) const;

int main()
{
	set<int> s1;
	for (int i = 1; i < 10; i++)
	{
		s1.insert(i * 10); //10 20 30 40 50 60 70 80 90
	}
	set<int> s2(s1);
	cout << endl;

	//要求：删除[30, 50]区间的值

	//1.erase的迭代器区间删除左闭右开：[)
	
	auto first = s1.find(30);
	auto last = s1.find(70);
	s1.erase(first, last);
	for (auto e : s1)
	{
		cout << e << " "; //10 20 70 80 90
	}
	cout << endl;

	//要求：删除[25, 55]区间的值：则上面的方法无效，因为find查找不到，返回的是s.end()迭代器

	//此时需要用到lower_bound和upper_bound
	
	auto itlow = s2.lower_bound(25); //返回 >= 25的迭代器：就是30位置的迭代器
	auto itup = s2.upper_bound(55);  //返回 > 55的迭代器：就是60位置的迭代器
	s2.erase(itlow, itup);
	for (auto e : s2)
	{
		cout << e << " "; //10 20 60 70 80 90
	}
	cout << endl;

	return 0;
}

9.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 << " "; //输出：2 2 4 4 4 4 5 7 8 9
		++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;
}

注意：查找3时，返回的是中序的第一个3的迭代器。好处：若后面还有3，则迭代器不断++就可以找到后面的所有3。

10.set解决：leetcode例题

1.两个数组的交集

两个数组的交集

解法：set+双指针

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        //1.将nums1和nums2放入set中：去重+迭代器遍历时是有序的
        set<int> s1(nums1.begin(), nums1.end()); 
        set<int> s2(nums2.begin(), nums2.end());
        vector<int> ret;

        //2.双指针
        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中
            {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return ret;
    }
};

已知：集合A = {1, 2, 3, 4, 5}，集合B = {4, 5, 6, 7, 8}，求A与B的差集和B与A的差集？

A - B = A - AB = {1, 2, 3}；
B - A = B - AB = {6, 7, 8}；

思考：如何找差集？

小的就是差集。
相等就同时++。
若其中一个走完了另一个没走完的值也是属于差集。

2.交集与差集的应用：数据同步

云相册是一种将照片和视频等多媒体内容存储在云端（即互联网上的服务器）的相册服务。具体来说，云相册具备以下几个核心特点和优势：

用户可以将手机、相机等设备中的照片和视频上传到云端，通过云相册提供的平台，随时随地查看、编辑和分享这些照片和视频。
支持多设备同步，用户可以在任何设备上查看和编辑自己的照片和视频，无需担心数据丢失或无法访问的问题。
解决存储问题：传统存储方式存在容量有限、携带不便等问题，云相册的出现极大地缓解了这些问题，用户可以无限量地存储照片和视频。
跨平台使用：无论是iOS、Android还是Windows等操作系统，用户都可以通过相应的应用程序或网页版云相册来访问和管理自己的照片和视频。
节省设备空间：存储在云端的照片和视频不会占用设备的存储空间，用户可以释放设备空间以存储更多其他类型的文件。

3.环型链表||

环型链表||

码农公寓