深入剖析C++ STL中的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;

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

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (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;

#include<iostream>
#include<set>
using namespace std;
int main()
{
	// 去重+升序排序
	set<int> s;
	// 去重+降序排序（给⼀个⼤于的仿函数）
	//set<int, greater<int>> s;
	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		// error C3892: “it”: 不能给常量赋值
		// *it = 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败
	s.insert({ 2,8,3,9 });
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	set<string> strset = { "sort", "insert", "add" };
	// 遍历string⽐较ascll码⼤⼩顺序遍历的
	for (auto& e : strset)
	{
		cout << e << " ";
	}
	cout << endl;
}

#include<iostream>
#include<set>
using namespace std;
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;
}

class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        // 将 nums1 的元素存入一个 set，自动去重并排序
        set<int> s1(nums1.begin(), nums1.end());
        // 将 nums2 的元素存入另一个 set，自动去重并排序
        set<int> s2(nums2.begin(), nums2.end());

        // 用于存储交集结果的 vector
        vector<int> ret;
        
        // 定义两个迭代器分别指向 s1 和 s2 的起始位置
        auto it1 = s1.begin();
        auto it2 = s2.begin();

        // 使用双指针遍历两个有序集合，寻找交集
        while(it1 != s1.end() && it2 != s2.end())
        {
            // 如果当前 s1 的元素小于 s2 的元素，则移动 s1 的迭代器
            if(*it1 < *it2)
            {
                it1++;
            }
            // 如果当前 s2 的元素小于 s1 的元素，则移动 s2 的迭代器
            else if(*it2 < *it1)
            {
                it2++;
            }
            // 如果 s1 和 s2 的当前元素相等，将其加入结果并同时移动两个迭代器
            else
            {
                ret.push_back(*it1); // 将交集元素加入结果
                it1++;
                it2++;
            }
        }

        // 返回交集结果
        return ret;
    }
};

class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 使用 set 存储已经访问过的节点
        set<ListNode*> s;
        // 定义一个指针从链表头部开始遍历
        ListNode* cur = head;

        // 遍历链表
        while (cur)
        {
            // 尝试将当前节点插入 set 中
            auto ret = s.insert(cur);
            // 如果插入失败，说明当前节点已经存在于 set 中，检测到环
            if (ret.second == false)
                return cur; // 返回环的起始节点
            // 向下移动指针
            cur = cur->next;
        }

        // 如果遍历结束仍未检测到环，则返回 nullptr 表示无环
        return nullptr;
    }
};