【C++】map和set的介绍及使用

int main()
{
	//去重+升序
	/*set<int> s;*/
	set<int, greater<int>> s;
	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	s.insert(7);
	s.insert(3);

	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		// error C3892: “it”: 不能给常量赋值
		cout << *it << " ";
		++it;
	}
	cout << endl;

	s.insert({ 2,8,3,9,2 });
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// void insert (initializer_list<value_type> il);
	//set<string> strset = { "sort","insert","add" };
	set<string> strset({ "sort","insert","add" });
	
	// 遍历string比较ascll码大小顺序遍历的
	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.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;
	}
	else
	{
		cout << x << "删除成功！" << endl;
	}*/
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end())
	{
		//pos失效
		s.erase(pos);
		//cout<<*pos<<endl;
	}
	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;

	// [30, 50]值
	// [25, 55]值

	返回 >= 30
	//auto itlow = myset.lower_bound(30);
	返回 > 50
	//auto itup = myset.upper_bound(50);

	//返回 >= 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;
}

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;
	去重
	//pos = s.find(x);
	//while (pos != s.end() && *pos == x)
	//{
	//	pos = s.erase(pos);
	//}
	//cout << endl;
	
	// 相⽐set不同的是，erase给值时会删除所有的x
	s.erase(x);//
	it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> set1 (nums1.begin(),nums1.end());
        set<int> set2 (nums2.begin(),nums2.end());
        vector<int> ret;
        auto it1 = set1.begin();
        auto it2 = set2.begin();
        while(it1 != set1.end() && it2 != set2.end())
        {
            if(*it1 > *it2)
            {
                ++it2;
            }
            else if(*it2 > *it1)
            {
                ++it1;
            }
            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))
            {
                return cur;
            }
            else
            {
                s.insert(cur);
            }
             cur = cur->next;
        }
        return nullptr;
        
    }
};

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
	template<class U, class V>
	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
	{}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

#include<iostream>
#include<map>
using namespace std;
int main()
{
	// initializer_list构造及迭代遍历
	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
	{"insert", "插入"},{ "string", "字符串" } };
	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << (*it).first <<":"<<(*it).second << endl;
		// map的迭代基本都使⽤operator->,这⾥省略了⼀个->
		// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据
		
		//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;// insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	dict.insert(pair<string, string>("second", "第二个"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert({ "auto", "自动的" });

	// "left"已经存在，插⼊失败
	dict.insert({ "left", "左边，剩余" });
	// 范围for遍历
	for (const auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
		}
		else
		{
			cout << "无此单词，请重新输入" << endl;
		}
	}
	// erase等接⼝跟set完全类似，这⾥就不演⽰讲解了
	return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
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;

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

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

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*,Node*>nodeMap;
        Node*copyhead=nullptr,*copytaill=nullptr;
        Node*cur = head;
        while(cur)
        {
            if(copytaill == nullptr)
            {
                copyhead = copytaill = new Node(cur->val);
                
            }
            else
            {
                copytaill->next = new Node (cur->val);
                copytaill = copytaill->next;
            }
            // 原节点和拷⻉节点map kv存储
            nodeMap[cur] = copytaill;
            cur = cur->next;
        }
        // 处理random
        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            if(nodeMap[cur->random] == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
			const
		{
			return x.second > y.second;
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		vector<pair<string, int>> v(countMap.begin(), countMap.end());
		// 仿函数控制降序
		stable_sort(v.begin(), v.end(), Compare());
		//sort(v.begin(), v.end(), Compare());
		// 取前k个
		vector<string> strV;
		for (int i = 0; i < k; ++i)
		{
			strV.push_back(v[i].first);
		}
		return strV;
	}
};

class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
			const
		{
			return x.second > y.second || (x.second == y.second && x.first <
				y.first);;
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		vector<pair<string, int>> v(countMap.begin(), countMap.end());
		// 仿函数控制降序,仿函数控制次数相等，字典序⼩的在前⾯
		sort(v.begin(), v.end(), Compare());
		// 取前k个
		vector<string> strV;
		for (int i = 0; i < k; ++i)
		{
			strV.push_back(v[i].first);
		}
		return strV;
	}
};

class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
			const
		{
			// 要注意优先级队列底层是反的，⼤堆要实现⼩于⽐较，所以这⾥次数相等，想要字典
			序⼩的在前⾯要⽐较字典序⼤的为真
				return x.second < y.second || (x.second == y.second && x.first >
					y.first);
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		// 将map中的<单词，次数>放到priority_queue中，仿函数控制⼤堆，次数相同按照字典
		序规则排序
			priority_queue<pair<string, int>, vector<pair<string, int>>, Compare>
			p(countMap.begin(), countMap.end());
		vector<string> strV;
		for (int i = 0; i < k; ++i)
		{
			strV.push_back(p.top().first);
			p.pop();
		}
		return strV;
	}
};