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) 無參默認(rèn)構(gòu)造
explicit set(const key_compare& comp = key_compare(),
	 const allocator_type& alloc = allocator_type());
// range (2) 迭代器區(qū)間構(gòu)造 
template <class InputIterator>
set(InputIterator first, InputIterator last,
	const key_compare& comp = key_compare(),
	const allocator_type & = allocator_type());
// copy (3) 拷?構(gòu)造 
set (const set& x);
// initializer list (5) initializer 列表構(gòu)造 
set (initializer_list<value_type> il,
 const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

// 迭代器是?個(gè)雙向迭代器 
iterator -> a bidirectional iterator to const value_type
// 正向迭代器 
iterator begin();
iterator end();
// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

#include <iostream>
#include <set>
using namespace std;
int main()
{
	//去重+升序排序
	set<int> s;
	//去重+降序排序，給一個(gè)大于的仿函數(shù)
	//set<int, greater<int>> s;
	//set<int, greater<int>> s = {1,2,7,4,9,6,}; initializer_list初始化
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(6);
	//set<int> iterator it =  s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		//*it = 1;不能修改里面的值
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//插入一段initilizer_list的值,已經(jīng)存在則插入失敗
	s.insert({1,5,3,2,7,9});
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//插入string類對(duì)象，string類對(duì)象比較是按照ascll碼來比較大小的
	set<string> strset = {"sort","add","insert"};
	for (auto &e : strset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

int main()
{
	set<int> s = {2,7,4,3,1,9,5,0};
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//刪除最小值
	s.erase(s.begin());
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//刪除輸入的值，這個(gè)值有可能在，也有可能不在
	int x;
	cin >> x;
	int num = s.erase(x);
	if (num == 0)
	{
		cout << x  << "不存在!" << endl;
	}
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//直接查找，再利用迭代器刪除
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end())
	{
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在" << endl;
	}
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//算法庫(kù)中的查找O（n） 不會(huì)這樣使用
	auto pos1 = find(s.begin(), s.end(), x);
	//set自己實(shí)現(xiàn)的查找O（logn）
	auto pos2 = s.find(x);
	//利用cout快速實(shí)現(xiàn)間接查找
	cin >> x;
	if (s.count(x))
	{
		cout << x << "在!" << endl;
	}
	else
	{
		cout << x << "不存在!" << endl;
	}
	return 0;
}

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;
	//實(shí)現(xiàn)查找到的[itlow,itup]包含[30,60]區(qū)間
	//返回>=30
	auto itlow = myset.lower_bound(30);
	//返回>60
	auto itup = myset.upper_bound(60);
	//刪除這段區(qū)間的值
	myset.erase(itlow,itup);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

int main()
{
	multiset<int> s = {4,6,4,3,6,7,8,9,2,5,3,7,8,9};
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//相比較set不同的是，x可能會(huì)存在多個(gè)，find查找的是中序的第一個(gè)
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	//相比set不同的是count會(huì)返回x的實(shí)際個(gè)數(shù)
	cout << s.count(x) << endl;
	//相比set不同的是erase會(huì)刪掉里面的所有的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) {
        //這里用set實(shí)現(xiàn)了對(duì)數(shù)組的排序+去重
        set<int> s1(nums1.begin(),nums1.end());//用一段迭代器區(qū)間初始化
        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 (*it1 > *it2) it2++;
            else 
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while(cur)
        {
            if(s.count(cur))
                return cur;//等于1即為入口點(diǎn)
            else
                s.insert(cur);
            cur = cur -> next;
        }
        return nullptr;
    }
};

template < class Key, // map::key_type
 class T, // map::mapped_type
 class Compare = less<Key>, // map::key_compare
 class Alloc = allocator<pair<const Key,T> > // 
map::allocator_type
 > class map

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

// empty (1) ?參默認(rèn)構(gòu)造 
explicit map (const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());
// range (2) 迭代器區(qū)間構(gòu)造 
template <class InputIterator>
 map (InputIterator first, InputIterator last,
 const key_compare& comp = key_compare(),
 const allocator_type& = allocator_type());
// copy (3) 拷?構(gòu)造 
map (const map& x);
// initializer list (5) initializer 列表構(gòu)造 
map (initializer_list<value_type> il,
 const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());
// 迭代器是?個(gè)雙向迭代器 
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(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 單個(gè)數(shù)據(jù)插?，如果已經(jīng)key存在則插?失敗,key存在相等value不相等也會(huì)插?失敗 
pair<iterator, bool> insert(const value_type& val);
// 列表插?，已經(jīng)在容器中存在的值不會(huì)插? 
void insert(initializer_list<value_type> il);
// 迭代器區(qū)間插?，已經(jīng)在容器中存在的值不會(huì)插? 
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，沒有找到返回end() 
iterator find(const key_type& k);
// 查找k，返回k的個(gè)數(shù) 
size_type count(const key_type& k) const;
// 刪除?個(gè)迭代器位置的值 
iterator erase(const_iterator position);
// 刪除k，k存在返回0，存在返回1 
size_type erase(const key_type& k);
// 刪除?段迭代器區(qū)間的值 
iterator erase(const_iterator first, const_iterator last);
// 返回?于等k位置的迭代器 
iterator lower_bound(const key_type& k);
// 返回?于k位置的迭代器 
const_iterator lower_bound(const key_type& k) const;

Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 查找k，返回k所在的迭代器，沒有找到返回end()，如果找到了通過iterator可以修改key對(duì)應(yīng)的mapped_type值
iterator find(const key_type& k);
// ?檔中對(duì)insert返回值的說明 
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to theelement with an equivalent key in the map.The pair::second element in the pairis set to true if a new element was inserted or false if an equivalent keyalready existed.
// insert插??個(gè)pair<key, T>對(duì)象 
// 1、如果key已經(jīng)在map中，插?失敗，則返回?個(gè)pair<iterator,bool>對(duì)象，返回pair對(duì)象first是key所在結(jié)點(diǎn)的迭代器，second是false
// 2、如果key不在map中，插?成功，則返回?個(gè)pair<iterator,bool>對(duì)象，返回pair對(duì)象first是新插?key所在結(jié)點(diǎn)的迭代器，second是true
// 也就是說?論插?成功還是失敗，返回pair<iterator,bool>對(duì)象的first都會(huì)指向key所在的迭代器
// 那么也就意味著insert插?失敗時(shí)充當(dāng)了查找的功能，正是因?yàn)檫@?點(diǎn)，insert可以?來實(shí)現(xiàn)
operator[]
// 需要注意的是這?有兩個(gè)pair，不要混淆了，?個(gè)是map底層紅?樹節(jié)點(diǎn)中存的pair<key, T>，另?個(gè)是insert返回值pair<iterator, bool>
pair<iterator, bool> insert(const value_type & val);
mapped_type& operator[] (const key_type& k);
// operator的內(nèi)部實(shí)現(xiàn) 
mapped_type& operator[] (const key_type& k)
{
	// 1、如果k不在map中，insert會(huì)插?k和mapped_type默認(rèn)值（默認(rèn)值是用默認(rèn)構(gòu)造構(gòu)造的），同時(shí)[]返回結(jié)點(diǎn)中存儲(chǔ)mapped_type值的引?，那么我們可以通過引?修改返映射值。所以[]具備了插? + 修改功能
		// 2、如果k在map中，insert會(huì)插?失敗，但是insert返回pair對(duì)象的first是指向key結(jié)點(diǎn)的迭代器，返回值同時(shí)[]返回結(jié)點(diǎn)中存儲(chǔ)mapped_type值的引?，所以[]具備了查找 + 修改的功能
		pair<iterator, bool> ret = insert({ k, mapped_type() });
	iterator it = ret.first;
	return it->second;
}

#include <map>
int main()
{
	pair<string, string> kv1 = {"left","左邊"};
	//initializer_list構(gòu)造以及迭代遍歷
	map<string, string> dict = { {"left","左邊"},{"right","右邊"},{"insert","插入"},{"erase","刪除"}};
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << " "; //pair不支持流提取和流插入，是一個(gè)結(jié)構(gòu)體
		//cout << (*it).first << ":" << (*it).second << endl;;
		cout << it->first << ":" << it->second << endl;
		//cout << it.operator->()->first << ":" << it.operator->()->second << endl;//原生寫法
		++it;
	}
	//map的插入
	//insert插入pair的四種方式，對(duì)比之下最后一種最方便
	pair<string, string> kv2("first","第一個(gè)");
	dict.insert(kv2);
	//匿名對(duì)象
	dict.insert(pair<string, string>("second", "第二個(gè)"));
	//make_pair
	dict.insert(make_pair("sort","排序"));//make_pair是一個(gè)函數(shù)模板，不用聲明模板參數(shù)，自己推導(dǎo)，在底層構(gòu)造一個(gè)pair對(duì)象再返回
	//最后一種最好用
	dict.insert({"auto","自動(dòng)的"});//支持隱式類型轉(zhuǎn)換
	//支持范圍for遍歷
	for (auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	//結(jié)構(gòu)化綁定 C++17
	//for (const auto& [k,v] : dict)
	//{
	//	cout << k << ":" << v << endl;
	//}
	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
		}
		else
		{
			cout << "無此單詞，請(qǐng)重新輸入" << endl;
		}
	}
	//first是不能被修改的，但是second可以被修改
	return 0;
}

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
	//統(tǒng)計(jì)水果出現(xiàn)的次數(shù)
	string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜","蘋果", "香蕉", "蘋果", "香蕉" };
	map<string, int> countMap;
	//先查找水果在不在map中
	//1.不在，說明水果第一次出現(xiàn)，則插入水果{水果，1}
	//2.在，則查找到的水果對(duì)應(yīng)的次數(shù)+1
	for (const auto& str : arr)
	{
		auto ret = countMap.find(str);
		if (ret == countMap.end())//則證明在
		{
			countMap.insert({str,1});
		}
		//否則，在
		else
		{
			ret->second++;
		}
	}
	//countMap[str]++; 第二種寫法
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*,Node*> nodeMap;
        Node* copyhead = nullptr,*copytail = nullptr;//定義一個(gè)頭一個(gè)尾
        Node* cur = head;
        while(cur)
        {
            //如果為空
            if(copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            //如果不為空
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            //讓原節(jié)點(diǎn)和拷貝節(jié)點(diǎn)建立map
            nodeMap[cur] = copytail;
            cur = cur->next;
        }
        //處理random
        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            //原鏈表的random為空，則拷貝鏈表的random也為空
            if(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>& kv1,const pair<string,int>& kv2)
        {
            return kv1.second > kv2.second;
        }
    }; 
    vector<string> topKFrequent(vector<string>& words, int k) {
        //統(tǒng)計(jì)次數(shù)
        map<string,int> countMap;
        for(auto &str : words)
        {
            countMap[str]++;
        }
        vector<pair<string,int>> v(countMap.begin(),countMap.end());//迭代器區(qū)間初始化
        stable_sort(v.begin(),v.end(),Compare());
        vector<string> retv;
        for(size_t i = 0; i < k ; ++i)
        {
            retv.push_back(v[i].first);//取的是每個(gè)pair對(duì)象中的單詞
        }
        return retv;
    }
};

class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
		{
			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());
		// 仿函數(shù)控制降序,仿函數(shù)控制次數(shù)相等，字典序?的在前? 
		sort(v.begin(), v.end(), Compare());
		// 取前k個(gè) 
		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
		{
			// 要注意優(yōu)先級(jí)隊(duì)列底層是反的，?堆要實(shí)現(xiàn)?于?較，所以這?次數(shù)相等，想要字典序?的在前?要?較字典序?的為真
				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中的<單詞，次數(shù)>放到priority_queue中，仿函數(shù)控制?堆，次數(shù)相同按照字典序規(guī)則排序
			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;
	}