深度解析C++中的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();

int main()
{
	//这个是降序的，给一个大于的仿函数
	//set<int,greater<int>>s;
	
	//升序排列+去重
	//set<int>s;
	set<int>s = {10,6,8,9};


	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	s.insert({ 1,2,3 });
	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	set<string> strset = { "sort","insert","add" };//string是按照ASCII进行比较大小的
	for (auto& e : strset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

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

	//s.erase(s.end()--);//因为迭代器是左闭右开的，end要进行减减操作的


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

	int x;
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end())//end是一个非法的位置，是最后一个数据的下一个位置
	{
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在" << endl;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;


	//算法库的find，时间复杂度O（N）
	auto pos1 = find(s.begin(), s.end(), x);

	//set自身实现的查找O(logN)
	auto pos2 = s.find(x);

	return 0;
}

	//算法库的find，时间复杂度O（N）
	auto pos1 = find(s.begin(), s.end(), x);

	//set自身实现的查找O(logN)
	auto pos2 = s.find(x);

int main()
{
	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)这段区间并且进行删除操作
	auto itlow = myset.lower_bound(30);//返回大于30的第一个值

	//返回>60的值
	auto itup = myset.upper_bound(60);

	//我们可以通过这种方法找到这个区间中包含我们想找的区间
	//通过这个方法可以给我们一个比我们想要找的区间大一些的空间，刚好包含我们想找的区间
	//然后我们就可以进行删除操作了

	myset.erase(itlow, itup);//通过这两个迭代区间进行删除操作
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

#include<iostream>
using namespace std;                                 
#include<set>
int main()
{
	//与set不同的是，multiset是排序，但是不进行去重操作的
	multiset<int>s = { 4,5,6,11,4,5,1,1, };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	//find进行数据的寻找，如果有多个会返回第一个
	//因为我们的multiset会将数组进行排序的操作，默认从小到大的排序
	//那么我们这里利用find找到了第一个4，然后如果有相同的4的话那么都是跟在第一个4的后面的
	cout << endl;
	//相比set不同的是，count回返回x的实际个数
	cout << s.count(x) << endl;
	//conut如果这个数字有多个的话那么就会返回这个数字的个数的
	
	//相比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)
    {
        //依次进行比较
        //1.小的++
        //2.相等的就是交集，同时++，其中一个结束就是结束了

        //排序+去重
        set<int> s1(nums1.begin(),nums1.end());//set是可以利用迭代器区间进行初始化操作的
        set<int> s2(nums2.begin(),nums2.end());

        vector<int> ret;
        auto it1=s1.begin();
        auto it2=s2.begin();
        while(it1!=s1.end()&&it2!=s2.end())
        {
            //谁小谁就++
            if(*it1<*it2)
            {
                it1++;
            }
            else if(*it2<*it1)
            {
                it2++;
            }
            //相等的就是交集，然后我们同时++
            else
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return ret;


    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        set<ListNode*>s;
        ListNode*cur=head;

        while(cur)
        {
            if(s.count(cur))//如果这个节点在的话，就是说这个节点在set中已经存在了，那么这个count就会返回一个1
            {
                return cur;//我们直接把这个节点返回了，这个就是把环形链表的入环的第一个节点
            }
            else//如果不存在的话那么我们就进行插入的操作
            {
                s.insert(cur);
            }
            cur=cur->next;
        }
        return nullptr;//如果出了循环的话还没有结果的话那么就是不带环的，那么我们直接返回空就行了



    }
};