★ C++进阶篇 ★ map和set-二 set系列的使用

2024-10-02 09:32:11

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

码农公寓