// unordered_set模板聲明：一個(gè)不保證元素順序的集合容器
template < 
    class Key,     // 鍵與值的類型(因?yàn)槭羌?，鍵就是值)
                   // 例如：unordered_set<int>, unordered_set<string>
    
    class Hash = hash<Key>,    // 哈希函數(shù)對象類型,用于計(jì)算元素的哈希值
                              // 默認(rèn)使用標(biāo)準(zhǔn)庫的hash
    
    class Pred = equal_to<Key>,    // 判斷兩個(gè)鍵是否相等的函數(shù)對象類型
                                   // 默認(rèn)使用標(biāo)準(zhǔn)庫的equal_to
    
    class Alloc = allocator<Key>   // 內(nèi)存分配器類型
                                   // 默認(rèn)使用標(biāo)準(zhǔn)分配器allocator
> 
class unordered_set;

// 插入函數(shù)：插入元素到容器
// 參數(shù)：待插入的值
// 返回：pair<迭代器,bool>
//      迭代器指向插入位置或已存在元素位置
//      bool為true表示插入成功,false表示已存在
pair<iterator,bool> insert(const value_type& val);

// 刪除函數(shù)：刪除指定key的元素
// 參數(shù)：要?jiǎng)h除的key
// 返回：刪除的元素個(gè)數(shù)(0表示元素不存在,1表示刪除成功)
size_type erase(const key_type& k);

// 查找函數(shù)：查找指定key的元素
// 參數(shù)：要查找的key
// 返回：指向找到元素的迭代器,未找到返回end()
iterator find(const key_type& k);

#include<unordered_set>  // 無序集合容器
#include<unordered_map> // 無序映射容器  
#include<set>          // 有序集合容器
#include<iostream>
using namespace std;

int test_set2()
{
    const size_t N = 1000000;  // 測試數(shù)據(jù)量100萬
    unordered_set<int> us;     // 聲明無序集合
    set<int> s;                // 聲明有序集合
    vector<int> v;             // 存儲(chǔ)測試數(shù)據(jù)的vector
    v.reserve(N);              // 預(yù)留空間,避免動(dòng)態(tài)擴(kuò)容
    srand(time(0));            // 隨機(jī)種子
    
    // 生成測試數(shù)據(jù)
    for (size_t i = 0; i < N; ++i)
    {
        //v.push_back(rand());     // N較大時(shí)重復(fù)值較多
        v.push_back(rand()+i);     // 加上i使重復(fù)值較少
        //v.push_back(i);          // 完全有序無重復(fù)
    }

    // 測試set的插入性能
    size_t begin1 = clock();
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;

    // 測試unordered_set的插入性能
    size_t begin2 = clock();
    us.reserve(N);             // 預(yù)留空間,避免rehash
    for (auto e : v)
    {
        us.insert(e);  
    }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;

    // 測試set的查找性能
    int m1 = 0;                // 記錄查找成功次數(shù)
    size_t begin3 = clock();
    for (auto e : v)
    {
        auto ret = s.find(e);
        if (ret != s.end())    // 找到元素
        {
            ++m1;
        }
    }
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << "->" << m1 << endl;

    // 測試unordered_set的查找性能
    int m2 = 0;                // 記錄查找成功次數(shù)
    size_t begin4 = clock();
    for (auto e : v)
    {
        auto ret = us.find(e);
        if (ret != us.end())   // 找到元素
        {
            ++m2;
        }
    }
    size_t end4 = clock();
    cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;

    // 輸出實(shí)際插入數(shù)據(jù)量(因?yàn)橛兄貜?fù)值,所以小于N)
    cout << "插入數(shù)據(jù)個(gè)數(shù)：" << s.size() << endl;
    cout << "插入數(shù)據(jù)個(gè)數(shù)：" << us.size() << endl << endl;

    // 測試set的刪除性能
    size_t begin5 = clock();
    for (auto e : v)
    {
        s.erase(e);
    }
    size_t end5 = clock();
    cout << "set erase:" << end5 - begin5 << endl;

    // 測試unordered_set的刪除性能
    size_t begin6 = clock();
    for (auto e : v)
    {
        us.erase(e);
    }
    size_t end6 = clock();
    cout << "unordered_set erase:" << end6 - begin6 << endl << endl;

    return 0;
}

int main()
{
    test_set2();    // 執(zhí)行性能測試
    return 0;
}

// 插入函數(shù)
// 參數(shù)：要插入的鍵值對或元素值
// 返回：pair<迭代器,bool>組合
//      迭代器指向插入位置或已存在元素位置
//      bool表示是否插入成功(true插入成功,false表示已存在)
pair<iterator,bool> insert(const value_type& val);

// 刪除函數(shù)
// 參數(shù)：要?jiǎng)h除元素的key
// 返回：實(shí)際刪除的元素個(gè)數(shù)
//      對于set/map返回0(不存在)或1(刪除成功)
size_type erase(const key_type& k);

// 查找函數(shù)
// 參數(shù)：要查找的key
// 返回：指向找到元素的迭代器
//      如果沒找到返回end()迭代器
iterator find(const key_type& k);

// map中的[]運(yùn)算符重載
// 參數(shù)：關(guān)鍵字key
// 返回：key對應(yīng)的value的引用
// 特點(diǎn)：如果key不存在則自動(dòng)插入,value默認(rèn)初始化
mapped_type& operator[](const key_type& k);

#pragma once  // 防止頭文件被重復(fù)包含
#include"HashTable.h"  // 引入哈希表的實(shí)現(xiàn)

namespace bit
{
    // unordered_map類模板，實(shí)現(xiàn)鍵值對的無序映射
    template<class K, class V>
    class unordered_map
    {
        // 仿函數(shù)類，用于從pair中提取key值
        struct MapKeyOfT
        {
            // 重載()運(yùn)算符，返回pair中的first成員(鍵值)
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };

    public:
        // 使用類型別名簡化迭代器類型的書寫
        // 注意這里的模板參數(shù)：
        // K: 鍵類型
        // pair<K,V>: 實(shí)際存儲(chǔ)的值類型(鍵值對)
        // MapKeyOfT: 提取鍵的仿函數(shù)
        typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;

        // 返回容器的起始迭代器
        iterator begin()
        {
            return _ht.begin();
        }

        // 返回容器的結(jié)束迭代器
        iterator end()
        {
            return _ht.end();
        }

        // 插入鍵值對
        // 參數(shù)kv: 要插入的鍵值對
        // 返回值: 插入是否成功
        bool insert(const pair<K, V>& kv)
        {
            return _ht.Insert(kv);
        }

    private:
        // 底層哈希表對象
        // K: 鍵類型
        // pair<K,V>: 存儲(chǔ)的值類型
        // MapKeyOfT: 提取鍵的仿函數(shù)
        hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
    };
}

#pragma once  // 防止頭文件被重復(fù)包含
#include"HashTable.h"  // 引入哈希表的實(shí)現(xiàn)

namespace bit
{
    // unordered_set類模板，實(shí)現(xiàn)無序集合
    // 特點(diǎn)：不重復(fù)、無序、只存儲(chǔ)key
    template<class K>
    class unordered_set
    {
        // 仿函數(shù)類，用于返回key值本身
        // 因?yàn)閟et只存儲(chǔ)key，所以key和value是同一個(gè)值
        struct SetKeyOfT
        {
            // 重載()運(yùn)算符，直接返回key
            const K& operator()(const K& key)
            {
                return key;
            }
        };

    public:
        // 使用類型別名簡化迭代器類型的書寫
        // 注意這里的模板參數(shù)：
        // K: 鍵類型
        // K: 值類型(與鍵相同)
        // SetKeyOfT: 提取鍵的仿函數(shù)
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;

        // 返回容器的起始迭代器
        iterator begin()
        {
            return _ht.begin();
        }

        // 返回容器的結(jié)束迭代器
        iterator end()
        {
            return _ht.end();
        }

        // 插入元素
        // 參數(shù)key: 要插入的值
        // 返回值: 插入是否成功（如果元素已存在則返回false）
        bool insert(const K& key)
        {
            return _ht.Insert(key);
        }

    private:
        // 底層哈希表對象
        // K: 鍵類型
        // K: 值類型(與鍵相同)
        // SetKeyOfT: 提取鍵的仿函數(shù)
        hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
    };
}