template <class T1, class T2>
struct pair {
    T1 first;
    T2 second;
};

void test_pair()
{
		// 1. 默認構造 - 成員使用默認值
		std::pair<int, std::string> p1;

		// 2. 直接值構造
		std::pair<int, std::string> p2(42, "hello");
		std::cout <<  p2.first << ", \"" << p2.second << "\")" << std::endl;

		// 3. 拷貝構造
		std::pair<int, std::string> p3(p2);
		std::cout << p3.first << ", \"" << p3.second << "\")" << std::endl;

		// 4. 使用 make_pair (自動類型推導)
		auto p6 = std::make_pair(123, "auto deduction");
		std::cout << p6.first << ", \"" << p6.second << "\")" << std::endl;

		// 5. 統一初始化 (C++11)
		std::pair<int, std::string> p7{ 999, "uniform init" };
		std::cout << p7.first << ", \"" << p7.second << "\")" << std::endl;

		// 6. 賦值初始化
		std::pair<int, std::string> p8 = { 888, "assignment init" };
		std::cout << p8.first << ", \"" << p8.second << "\")" << std::endl;
}

struct PairCompare {
    // 先比較 first，如果 first 相等再比較 second
    template <typename T1, typename T2>
    bool operator()(const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs) const {
        if (lhs.first != rhs.first) {
            return lhs.first < rhs.first;  // 先按 first 升序
        }
        return lhs.second > rhs.second;    // first 相等時按 second 降序
    }
};

void test1()
{
	// 1. 默認構造：創建一個空的set
	std::set<int> s1;

	// 2. 迭代器範圍構造：用 [first, last) 區間內的元素構造
	std::vector<int> v = { 5, 2, 3, 2, 5 };
	std::set<int> s2(v.begin(), v.end()); // s2: {2, 3, 5} (自動去重排序)

	// 3. 拷貝構造：用一個set初始化另一個
	std::set<int> s3(s2); 

	// 4. 初始化列表構造 (C++11)
	std::set<int> s4 = { 1, 4, 2, 1, 3 }; // s4: {1, 2, 3, 4}

	// 正向迭代器 (順序為排序後的順序：1, 2, 3, 4)
	for (auto it = s4.begin(); it != s4.end(); ++it) {
		std::cout << *it << " "; // 可以讀 *it
		// *it = 10; // 錯誤！不能修改
	}

	for (const auto& val : s4) {
		std::cout << val << " ";
	}

	// 反向迭代器 (順序為 4, 3, 2, 1)
	for (auto rit = s4.rbegin(); rit != s4.rend(); ++rit) {
		std::cout << *rit << " ";
	}
}

void test2()
{
	set<int> s;

	// 1. 插入單個值，返回 pair<iterator, bool>
	auto ret = s.insert(5);

	// 2. 插入一個迭代器範圍
	std::vector<int> v = { 2, 7, 2, 3 };
	s.insert(v.begin(), v.end());

	// 3. 使用初始化列表插入 
	s.insert({ 8, 1, 6 });

	for (const auto& val : s) {
		cout << val << " ";
	}

	auto it = s.find(3);
	// 1. 通過迭代器位置刪除
	if (it != s.end()) 
		s.erase(it); // 刪除元素 3

	// 2. 通過值刪除，返回刪除的元素個數 (對於set，只能是0或1)
	size_t count = s.erase(2); 

	// 3. 刪除一個迭代器範圍 [first, last)
	s.erase(s.begin(), ++s.begin()); // 刪除前兩個元素

	for (const auto& val : s) {
		cout << val << " ";
	}
}

/*
1 2 3 5 6 7 8
7
5 6 7 8
1
*/

void test3()
{
	set<int> s = { 10, 20, 30, 40 };
	auto it_low = s.lower_bound(30);  //30
	auto it_up = s.upper_bound(25);   //30
	auto it_up2 = s.upper_bound(30);  //40
	if (s.count(20) == 1) {
		cout << "Element 220 exists." << endl;
	}
}

std::multiset<int> ms;
auto ret = ms.insert(5); // 返回 iterator (不是pair!)
// 總是插入成功，返回指向新插入元素的迭代器
ms.insert(5); // 可以重複插入相同的值
ms.insert(5); // 再插入一個5
// ms 現在包含: 5, 5, 5

std::multiset<int> ms = {1, 2, 2, 3, 3, 3}; 
// 存儲: 1, 2, 2, 3, 3, 3
auto it = ms.find(2); // 返回指向"第一個"2的迭代器
// 如果有多個相同元素，find返回中序遍歷遇到的第一個

std::multiset<int> ms = {1, 2, 2, 2, 3};
size_t n = ms.erase(2); // 刪除所有值為2的元素
// n = 3 (刪除了3個元素)
// ms 變為 {1, 3}

std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
size_t c = ms.count(2); // 返回元素的實際個數
// c = 2 (有兩個2)
size_t c2 = ms.count(3); // c2 = 3 (有三個3)

std::multiset<int> ms = {1, 2, 3, 3, 3, 4, 5};

auto low = ms.lower_bound(3); // 指向第一個 >=3 的元素 (第一個3)
auto up = ms.upper_bound(3);  // 指向第一個 >3 的元素 (4)

// 可以用它們來遍歷所有3
for (auto it = low; it != up; ++it) {
    std::cout << *it << " "; // 輸出: 3 3 3
}

std::set<int> s = {1, 2, 3, 4, 5};
auto range = s.equal_range(3);
// range.first 指向3
// range.second 指向4
// 範圍最多包含一個元素

std::multiset<int> ms = {1, 2, 3, 3, 3, 4, 5};
auto range = ms.equal_range(3);
// range.first 指向第一個3
// range.second 指向4
// [range.first, range.second) 包含所有3個"3"
for (auto it = range.first; it != range.second; ++it)
    std::cout << *it << " "; // 輸出: 3 3 3

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        for(auto e:s1)
        {
            if(s2.find(e)!=s2.end())  ret.push_back(e);
        }
        return ret;
    }
};
//也能用雙指針

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode *cur=head;
        set<ListNode *> s;
        while(cur)
        {
            auto p = s.insert(cur);
            if(!p.second) return cur;
            cur=cur->next;
        }
        return cur;
    }
};

void test4()
{
	// 1. 默認構造
	std::map<std::string, int> m1;

	// 2. 迭代器範圍構造 (迭代器必須指向pair對象)
	std::vector<pair<string, int>> v = { {"apple", 1}, {"banana", 2} };
	std::map<string, int> m2(v.begin(), v.end());

	// 3. 拷貝構造
	std::map<string, int> m3(m2);

	// 4. 初始化列表構造 (C++11)
	std::map<string, int> m4{ { "apple", 1 }, { "banana", 2 }, { "cherry", 3 } };
	//千萬不能寫成 ({},{},..)
	//std::map<std::string, int> m4 = { {"apple", 1}, {"banana", 2}, {"cherry", 3} };

	std::map<std::string, int> m = { {"apple", 1}, {"banana", 2}, {"cherry", 3} };

	// 正向迭代器 (按鍵排序: apple, banana, cherry)
	for (auto it = m.begin(); it != m.end(); ++it) {
		std::cout << it->first << ": " << it->second << std::endl;
		// it->first 是 const，不能修改
		// it->second 可以修改
	}

	for (const auto& kv : m) {
		std::cout << kv.first << ": " << kv.second << std::endl;
	}

	// 反向迭代器 (cherry, banana, apple)
	for (auto rit = m.rbegin(); rit != m.rend(); ++rit) {
		std::cout << rit->first << ": " << rit->second << std::endl;
	}
}

void test5()
{
	map<string, int> m;

	// 1. 插入單個pair，返回 pair<iterator, bool>
	auto ret = m.insert({ "apple", 1 });
	// ret.second 為true表示插入成功，false表示key已存在

	// 2. 插入迭代器範圍
	vector<pair<std::string, int>> v = { {"date", 4}, {"elderberry", 5} };
	m.insert(v.begin(), v.end());

	// 3. 使用初始化列表
	m.insert({ {"fig", 6}, {"grape", 7} });

	auto it = m.find("b");
	// 1. 通過迭代器位置刪除
	if (it != m.end()) 
		m.erase(it); // 刪除 "b"

	// 2. 通過key刪除，返回刪除的元素個數 (0或1)
	size_t count = m.erase("c"); 

	// 3. 刪除迭代器範圍
	m.erase(m.begin(), m.begin()++); // 刪除前兩個元素

	cout << m.size();
	m.clear();
	cout << endl << m.empty() << endl;
}

mapped_type& operator[] (const key_type& k)
{
	pair<iterator, bool> ret = insert({ k, mapped_type() });
	iterator it = ret.first;
	return it->second;
}

void test6()
{
	map<string, int> m;
	// 1. 插入新元素 (key不存在時)
	m["apple"] = 5; // 插入 {"apple", 5}
	// 2. 修改現有元素 (key存在時)
	m["apple"] = 10; // 修改為 {"apple", 10}
	// 3. 查找/訪問元素
	std::cout << m["apple"] << std::endl; // 輸出: 10
	// 4. 注意：如果key不存在，operator[]會插入該key，並用默認值初始化value
	std::cout << m["banana"] << std::endl; // 自動插入 {"banana", 0}
}

void test7()
{
	map<string, int> m1 = { {"apple", 1} };
	if (m1.count("apple") == 1) 
		cout << "Key exists" << endl;
	map<string, int> m2 = { {"apple", 1}, {"banana", 2}, {"cherry", 3} };
	auto it1 = m2.lower_bound("b");
	// it1 指向 "banana" (第一個 >= "b" 的元素)
	map<string, int> m3 = { {"apple", 1}, {"banana", 2}, {"cherry", 3} };
	auto it2 = m3.upper_bound("b");
	// it2 指向 "cherry" (第一個 > "b" 的元素)
}

std::map<std::string, int> m = {{"apple", 1}, {"banana", 2}};
auto range = m.equal_range("apple");
// range包含最多一個元素

std::multimap<std::string, int> mm = {
    {"apple", 1}, {"apple", 2}, {"apple", 3}, {"banana", 4}
};

auto range = mm.equal_range("apple");
// range.first 指向第一個apple
// range.second 指向banana (第一個不是apple的元素)

// 遍歷所有"apple"
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}
// 輸出:
// apple: 1
// apple: 2  
// apple: 3

Node* copyRandomList1(Node* head)
{
    map<Node*, Node*> m1;
    Node* cur = head;
    while (cur)
    {
        Node* copy = new Node(cur->val);
        m1.insert({ cur,copy });
        cur = cur->next;
    }

    cur = head;
    while (cur)
    {
        m1[cur]->next = m1[cur->next];
        m1[cur]->random = m1[cur->random];
        cur = cur->next;
    }

    return m1[head];
}

// 使用鏈表交錯方法的深拷貝
Node* copyRandomList2(Node* head) 
{
    if (!head) return nullptr;

    // 第一步：在每個原節點後面插入對應的拷貝節點
    // 創建交錯鏈表：原節點1 -> 拷貝節點1 -> 原節點2 -> 拷貝節點2 -> ...
    Node* cur = head;
    while (cur)
    {
        // 創建當前節點的拷貝節點
        Node* copy = new Node(cur->val);
        // 將拷貝節點插入到原節點後面
        copy->next = cur->next;
        cur->next = copy;
        // 移動到下一個原節點（跳過剛插入的拷貝節點）
        cur = cur->next->next;
    }

    // 第二步：設置拷貝節點的random指針
    // 利用交錯結構：拷貝節點的random = 原節點random的next
    cur = head;
    while (cur)
    {
        // 如果原節點有random指針，設置對應拷貝節點的random指針
        if (cur->random)
            // cur->random->next 指向對應的拷貝節點
            cur->next->random = cur->random->next;
        // 移動到下一個原節點（跳過拷貝節點）
        cur = cur->next->next;
    }

    // 第三步：分離原鏈表和拷貝鏈表
    Node* ret = head->next;  // 拷貝鏈表的頭節點
    Node* newcur = ret;      // 拷貝鏈表的當前節點
    cur = head;              // 原鏈表的當前節點

    while (cur)
    {
        // 恢復原鏈表的next指針：跳過拷貝節點，指向下一個原節點
        cur->next = cur->next->next;

        // 連接拷貝鏈表的next指針：指向下一個拷貝節點
        if (newcur->next) 
            newcur->next = newcur->next->next;

        // 移動到下一組節點
        cur = cur->next;        // 移動到原鏈表的下一個原節點
        newcur = newcur->next;  // 移動到拷貝鏈表的下一個拷貝節點
    }
    
    return ret;
}

void test8()
{
	unordered_set<int> us = { 1, 2, 3, 4, 5, 10, 15 };
	//bucket_count() - 返回桶的數量
	cout << "桶的數量: " << us.bucket_count() << endl;

	// bucket_size(n) - 返回指定桶中的元素數量
	for (size_t i = 0; i < us.bucket_count(); ++i) 
		cout << "桶 " << i << " 有 " << us.bucket_size(i) << " 個元素" << endl;

	//bucket - 查找元素所在的桶索引
	for (int value : us) 
	{
		size_t bucket_idx = us.bucket(value);
		cout << "元素 " << value << " 在桶 " << bucket_idx << endl;
	}

	//load_factor - 返回負載因子    負載因子 = 元素數量 / 桶數量
	cout << "負載因子: " << us.load_factor() << endl;

	//rehash - 直接設置桶的數量
	us.rehash(20);
	cout << us.bucket_count() << endl;  

	//reserve - 預留容量（一般用這個）
	us.reserve(1000);  // 預期要插入1000個元素，提前預留空間
	std::cout << "預留後桶數量: " << us.bucket_count() << endl;

	//它們都會略大於給的數據
}

//沒用Top-K
struct Comp1
{
    bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)
    {
        if (p1.second != p2.second) return p1.second < p2.second;
        else  return p1.first > p2.first;
    }
};
class Solution {
public:
    vector<string> topKFrequent1(vector<string>& words, int k)
    {
        unordered_map<string, int> m;
        for (auto e : words)
        {
            m[e]++;
        }
        vector<string> strV;
        priority_queue<pair<string, int>, vector<pair<string, int>>, Comp1> pq;
        for (auto it = m.begin(); it != m.end(); it++)
        {
            pq.push({ it->first,it->second });
        }

        for (int i = 0; i < k; ++i)
        {
            strV.push_back(pq.top().first);
            pq.pop();
        }
        return strV;
    }
};

struct Comp2
{
    bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)
    {
        if (p1.second != p2.second) return p1.second > p2.second;
        else  return p1.first < p2.first;
    }
};

vector<string> topKFrequent2(vector<string>& words, int k)
{
    unordered_map<string, int> m;
    for (auto e : words)
    {
        m[e]++;
    }
    vector<string> strV;
    vector<pair<string, int>> v(m.begin(), m.end());
    // 仿函數控制降序,仿函數控制次數相等，字典序小的在前面 
    sort(v.begin(), v.end(), Comp2());

    // 取前k個 
    for (int i = 0; i < k; ++i)
    {
        strV.push_back(v[i].first);
    }
    return strV;
}

struct Comp3
{
    bool operator()(const pair<string, int>& x, const pair<string, int>& y) const
    {
        return x.second > y.second;
    }
};

vector<string> topKFrequent3(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(), Comp3());
    // 取前k個 
    vector<string> strV;
    for (int i = 0; i < k; ++i)
    {
        strV.push_back(v[i].first);
    }
    return strV;
}

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;

	Colour _col;     //節點顏色

	RBTreeNode(const T& data)
		:_data(data),
		_parent(nullptr),
		_left(nullptr),
		_right(nullptr)
	{ }
};

template<class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;
};


template<class K>
class set
{
	struct SetOfK
	{
		const K& operator()(const K& date)
		{
			return date;
		}
	};
		
    RBTree<K, const K, SetOfK> _t;
};


template<class K, class V>
class map
{
	struct MapOfK
	{
		const K& operator()(const pair<K, V>& date)
		{
			return date.first;
		}
	};
private:
	RBTree<K, pair<const K, V>, MapOfK> _t;
};

Self& operator++()
{
	assert(_node != nullptr);
	if (_node->_right)
	{
		_node = _node->_right;
		while (_node->_left)
		{
			_node = _node->_left;
		}
	}
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && parent->_right == cur)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

Self& operator--()
{
	if (_node->_left)
	{
		_node = _node->_left;
		while (_node->_right)
		{
			_node = _node->_right;
		}
	}

	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && parent->_left == cur)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

if (_node == nullptr)  // --end()
{
	// --end()，特殊處理，走到中序最後一個結點，整棵樹的最右結點
	Node* rightMost = _root;
	while (rightMost && rightMost->_right)
	{
		rightMost = rightMost->_right;
	}
	_node = rightMost;
}

pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Iterator it = Find(kot(data));
	if (it != End())
		return { it, false };

	if (load_factor() > 0.98)
	{
		vector<Node*> newtables;
		newtables.resize(__stl_next_prime(_tables.size() + 1));
		Hash hash;
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hash(kot(cur->_data)) % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				cur = next;
			}
		}
		_tables.swap(newtables);
	}
	Hash hash;
	size_t hashi = hash(kot(data)) % _tables.size();
	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	_n++;

	return { Iterator(newnode, this), true };
}

//RBTree.h
#pragma once
#include<iostream>
#include <utility>
#include<math.h>
#include<assert.h>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;

	Colour _col;     //節點顏色

	RBTreeNode(const T& data)
		:_data(data),
		_parent(nullptr),
		_left(nullptr),
		_right(nullptr)
	{ }
};

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	Node* _root;

	RBTreeIterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(_node->_data);
	}

	Self& operator++()
	{
		assert(_node != nullptr);
		if (_node->_right)
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node == nullptr)  // --end()
		{
			// --end()，特殊處理，走到中序最後一個結點，整棵樹的最右結點
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}

		else if (_node->_left)
		{
			_node = _node->_left;
			while (_node->_right)
			{
				_node = _node->_right;
			}
		}

		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!= (const Self& s) const
	{
		return _node != s._node;
	}

	bool operator== (const Self& s) const
	{
		return _node == s._node;
	}
};


template<class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

	Iterator Begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur, _root);
	}

	Iterator End()
	{
		return Iterator(nullptr, _root);
	}

	ConstIterator CBegin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur, _root);
	}

	ConstIterator CEnd() const
	{
		return Iterator(nullptr, _root);
	}

	pair<Iterator, bool> insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return { Iterator(_root, _root), true };
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return { Iterator(cur, _root), false };
		}

		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = newnode;
		}
		else
		{
			parent->_left = newnode;
		}

		newnode->_parent = parent;
		newnode->_col = RED;

		while (parent && cur->_col == RED)
		{
			if (cur->_parent && cur->_parent->_col == BLACK)  break;
			Node* grandparent = parent->_parent;
			//parent不為根節點，grandparent一定存在
			if (grandparent->_left == parent)
			{
				Node* uncle = grandparent->_right;
				{
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;

						cur = grandparent;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RotateR(grandparent);
							grandparent->_col = RED;
							parent->_col = BLACK;
							cur = parent;
						}
						else
						{
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
					}
				}
			}
			//    g
			//  u   p
			else if (grandparent->_right == parent)
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
						cur = parent;
						parent = cur->_parent;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
						parent = cur->_parent;
					}
				}
			}
			else  assert(false);
		}

		_root->_col = BLACK;
		return { Iterator(newnode, _root), true };
	}

	Iterator Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur, _root);
			}
		}
		return Iterator(nullptr, _root);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

private:
	Node* _root = nullptr;
	//右單旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandparent = parent->_parent;

		parent->_parent = subL;
		parent->_left = subLR;
		if (subLR)  subLR->_parent = parent;

		subL->_right = parent;
		if (grandparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == grandparent->_left)
				grandparent->_left = subL;
			else  grandparent->_right = subL;

			subL->_parent = grandparent;
		}

	}

	//左單旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandparent = parent->_parent;

		parent->_parent = subR;
		parent->_right = subRL;
		if (subRL)  subRL->_parent = parent;

		subR->_left = parent;
		if (grandparent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == grandparent->_left)
				grandparent->_left = subR;
			else  grandparent->_right = subR;
			subR->_parent = grandparent;
		}

	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		int a = _Size(root->_left);
		int b = _Size(root->_right);
		return a + b + 1;
	}

};


//set.h
#pragma once
#include"RBTree.h"

namespace DaYuanTongXue
{
	template<class K>
	class set
	{
		struct SetOfK
		{
			const K& operator()(const K& date)
			{
				return date;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetOfK>::Iterator iterator;
		typedef typename RBTree<K, const K, SetOfK>::ConstIterator const_iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator cbegin() const
		{
			return _t.CBegin();
		}
		const_iterator cend() const
		{
			return _t.CEnd();
		}
		pair<iterator, bool> insert(const K& date)
		{
			return _t.insert(date);
		}
		iterator find(const K& date)
		{
			return _t.Find(date);
		}
	private:
		RBTree<K, const K, SetOfK> _t;
	};
}


//map.h
#pragma once
#include"RBTree.h"

namespace DaYuanTongXue
{
	template<class K, class V>
	class map
	{
		struct MapOfK
		{
			const K& operator()(const pair<K, V>& date)
			{
				return date.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapOfK>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapOfK>::ConstIterator const_iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator cbegin() const
		{
			return _t.CBegin();
		}
		const_iterator cend() const
		{
			return _t.CEnd();
		}

		pair<iterator, bool> insert(const pair<K, V>& date)
		{
			return _t.insert(date);
		}

		iterator find(const K& date)
		{
			return _t.Find(date);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.insert({ key, V() });
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, MapOfK> _t;
	};
}

typedef HSIterator<K, T, Ref, Ptr, KeyOfT, Hash, Pred> Self;

Self& operator++()
{
	if (_node->_next)
	{
		_node = _node->_next;
	}
	else
	{
		KeyOfT kot;
		Hash hash;
		size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
		hashi++;
		while (hashi < _ht->_tables.size())
		{
			if (_ht->_tables[hashi])
			{
				_node = _ht->_tables[hashi];
				break;
			}
			else hashi++;
		}
		if (hashi == _ht->_tables.size())
			_node = nullptr;

		return *this;
	}
}

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash, class Pred>
struct HSIterator
{
	typedef HashNode<T> Node;
	typedef Hashtable<K, T, KeyOfT, Hash, Pred> HT;
	typedef HSIterator<K, T, Ref, Ptr, KeyOfT, Hash, Pred> Self;

	Node* _node;
	const HT* _ht;

	HSIterator(Node* node, const HT* ht)
		:_node(node)
		,_ht(ht)
	{}
}；

template<class K, class T, class KeyOfT, class Hash, class Pred> class Hashtable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash, class Pred>
struct HSIterator
{
	typedef HashNode<T> Node;
	typedef Hashtable<K, T, KeyOfT, Hash, Pred> HT;
	typedef HSIterator<K, T, Ref, Ptr, KeyOfT, Hash, Pred> Self;
    //......
}；

template<class K, class T, class KeyOfT, class Hash, class Pred>
class Hashtable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash, class Pred>
	friend struct HSIterator;
public:
	typedef HashNode<T> Node;
	typedef HSIterator<K, T, T&, T*, KeyOfT, Hash, Pred> Iterator;
	typedef HSIterator<K, T, const T&, const T*, KeyOfT, Hash, Pred> ConstIterator;
    //......
};

//HSTable.h
#pragma once
#include<string>
#include<vector>
using namespace std;

template<class K>
struct myhash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct myhash<std::string>
{
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

template<class K>
struct myequal_to
{
	bool operator()(const K& lhs, const K& rhs) const
	{
		return lhs == rhs;
	}
};


template<class T>
struct HashNode
{
	T _data;
	HashNode* _next;

	HashNode(const T& data)
		:_data(data),
		_next(nullptr)
	{ }
};


template<class K, class T, class KeyOfT, class Hash, class Pred>
class Hashtable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash, class Pred>
struct HSIterator
{
	typedef HashNode<T> Node;
	typedef Hashtable<K, T, KeyOfT, Hash, Pred> HT;
	typedef HSIterator<K, T, Ref, Ptr, KeyOfT, Hash, Pred> Self;

	Node* _node;
	const HT* _ht;

	HSIterator(Node* node, const HT* ht)
		:_node(node)
		,_ht(ht)
	{}
	
	Ptr operator->()
	{
		return &(_node->_data);
	}

	Ref operator*()
	{
		return _node->_data;
	}

	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}

	bool operator==(const Self& it)
	{
		return _node == it._node;
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			hashi++;
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				else hashi++;
			}
			if (hashi == _ht->_tables.size())
				_node = nullptr;

			return *this;
		}
	}
};

template<class K, class T, class KeyOfT, class Hash, class Pred>
class Hashtable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash, class Pred>
	friend struct HSIterator;
public:
	typedef HashNode<T> Node;
	typedef HSIterator<K, T, T&, T*, KeyOfT, Hash, Pred> Iterator;
	typedef HSIterator<K, T, const T&, const T*, KeyOfT, Hash, Pred> ConstIterator;

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] = {
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	Hashtable()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}

	~Hashtable()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}

	Iterator Begin()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]) return Iterator(_tables[i], this);
		}
		return End();
	}

	Iterator End()
	{
		return Iterator(nullptr, this);
	}

	ConstIterator cEnd() const
	{
		return ConstIterator(nullptr, this);
	}

	ConstIterator cBegin() const
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			if (_tables[i])  return ConstIterator(_tables[i], this);
		}
		return cEnd();
	}

	float load_factor() const
	{
		return (float)_n / (float)(_tables.size());
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		Iterator it = Find(kot(data));
		if (it != End())
			return { it, false };

		if (load_factor() > 0.98)
		{
			vector<Node*> newtables;
			newtables.resize(__stl_next_prime(_tables.size() + 1));
			Hash hash;
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = hash(kot(cur->_data)) % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;
					cur = next;
				}
			}
			_tables.swap(newtables);
		}
		Hash hash;
		size_t hashi = hash(kot(data)) % _tables.size();
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;

		return { Iterator(newnode, this), true };
	}

	Iterator Find(const K& key)
	{
		KeyOfT kot;
		Hash hash;
		Pred equal;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (equal(kot(cur->_data), key))
				return Iterator(cur, this);
			else cur = cur->_next;
		}
		return End();
	}

	bool Erase(const K& key)
	{
		KeyOfT kot;
		Hash hash;
		Pred equal;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (equal(kot(cur->_data), key))
			{
				if (prev == nullptr)
					_tables[hashi] = cur->_next;
				else
					prev->_next = cur->_next;

				delete cur;
				_n--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}

private:
	std::vector<Node*> _tables;
	size_t _n;
};


//unordered_set.h
#pragma once
#include"HSTable.h"
using namespace std;

template<class K, class Hash = myhash<K>, class Pred = myequal_to<K>>
class myunordered_set
{
public:
	struct SetOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	typedef typename Hashtable<K, const K, SetOfT, Hash, Pred>::Iterator iterator;
	typedef typename Hashtable<K, const K, SetOfT, Hash, Pred>::ConstIterator const_iterator;

	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}

	const_iterator cbegin() const
	{
		return _ht.cBegin();
	}

	const_iterator cend() const
	{
		return _ht.cEnd();
	}

	pair<iterator, bool> insert(const K& key)
	{
		return _ht.Insert(key);
	}

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}
private:
	Hashtable<K, const K, SetOfT, Hash, Pred> _ht;
};


//unordered_map.h
#pragma once
#include"HSTable.h"
using namespace std;

template<class K, class V, class Hash = myhash<K>, class Pred = myequal_to<K>>
class myunordered_map
{
public:
	struct MapOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename Hashtable<K, pair<const K, V>, MapOfT, Hash, Pred>::Iterator iterator;
	typedef typename Hashtable<K, pair<const K, V>, MapOfT, Hash, Pred>::ConstIterator const_iterator;

	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}

	const_iterator cbegin() const
	{
		return _ht.cBegin();
	}
	const_iterator cend() const
	{
		return _ht.cEnd();
	}

	pair<iterator, bool> insert(const pair<const K, V>& kv)
	{
		return _ht.Insert(kv);
	}

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert({ key, V() });
		return ret.first->second;
	}

private:
	Hashtable<K, pair<const K, V>, MapOfT, Hash, Pred> _ht;
};