unordered-set-map/Windows_Unordered_Set_Map/Main.cpp

#include "Unordered_Set.hpp"
#include "Unordered_Map.hpp"

#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <time.h>

void Test_unordered_set()
{
    std::unordered_set<int> us; // Java里面取名叫HashSet
    us.insert(4);
    us.insert(2);
    us.insert(1);
    std::cout << "us 的 bucket 数量是: " << us.bucket_count()
        << "\tus 的 负载因子 是: " << us.load_factor() << std::endl;
    us.insert(5);
    us.insert(6);
    us.insert(3);
    us.insert(5);
    us.insert(6);
    us.insert(3);
    us.insert(15);
    us.insert(16);
    us.insert(13);
    std::cout << "us 的 bucket 数量是: " << us.bucket_count()
        << "\tus 的 负载因子 是: " << us.load_factor() << std::endl;
    us.insert(15);
    us.insert(16);
    us.insert(13);
    us.insert(9);
    us.insert(8);
    us.insert(10);
    us.insert(7);
    us.insert(12);
    std::cout << "us 的 bucket 数量是: " << us.bucket_count()
        << "\tus 的 负载因子 是: " << us.load_factor() << std::endl;

    // 会去重，但是不会自动排序
    std::unordered_set<int>::iterator it = us.begin();
    while (it != us.end())
    {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << std::endl;

    std::set<int> s; // Java里面取名叫TreeSet
    s.insert(4);
    s.insert(2);
    s.insert(1);
    s.insert(5);
    s.insert(6);
    s.insert(3);
    s.insert(5);
    s.insert(6);
    s.insert(3);
    s.insert(15);
    s.insert(16);
    s.insert(13);
    s.insert(15);
    s.insert(16);
    s.insert(13);
    s.insert(9);
    s.insert(8);
    s.insert(10);
    s.insert(7);
    s.insert(12);
    // set会去重，会自动排序
    std::set<int>::iterator its = s.begin();
    while (its != s.end())
    {
        std::cout << *its << " ";
        ++its;
    }
    std::cout << std::endl;
}

void Test_unordered_map()
{
    std::unordered_map<std::string, std::string> dict;
    dict.insert(std::make_pair("hello", "你好"));
    dict.insert(std::make_pair("world", "世界"));
    dict.insert(std::make_pair("apple", "苹果"));
    dict.insert(std::make_pair("orange", "橘子"));
    dict.insert(std::make_pair("banana", "香蕉"));
    dict.insert(std::make_pair("peach", "桃子"));
    dict.insert(std::make_pair("peach", "桃子"));
    dict.insert(std::make_pair("peach", "桃子"));

    dict.insert(std::make_pair("sort", "排序"));
    dict["string"] = "字符串";

    std::unordered_map<std::string, std::string>::iterator it = dict.begin();
    while (it != dict.end())
    {
        std::cout << it->first << " " << it->second << std::endl;
        ++it;
    }
    std::cout << std::endl;

    std::map<std::string, std::string> mdict;
    mdict.insert(std::make_pair("hello", "你好"));
    mdict.insert(std::make_pair("world", "世界"));
    mdict.insert(std::make_pair("apple", "苹果"));
    mdict.insert(std::make_pair("orange", "橘子"));
    mdict.insert(std::make_pair("banana", "香蕉"));
    mdict.insert(std::make_pair("peach", "桃子"));
    mdict.insert(std::make_pair("peach", "桃子"));
    mdict.insert(std::make_pair("peach", "桃子"));

    mdict.insert(std::make_pair("sort", "排序"));
    mdict["string"] = "字符串";

    std::map<std::string, std::string>::iterator mit = mdict.begin();
    while (mit != mdict.end())
    {
        std::cout << mit->first << " " << mit->second << std::endl;
        ++mit;
    }
}

void Test_OP()
{
    std::unordered_set<int> us;
    std::set<int> s;

    const size_t n = 100000;
    std::vector<int> v;
    v.reserve(n); // reserve()函数是vector预留空间的，但是并不真正创建元素对象。
    // resize()函数是开空间+初始化
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        v.push_back(rand());
    }

    // 插入
    clock_t begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        us.insert(v[i]);
    }
    clock_t end = clock();
    std::cout << "unordered_set insert time:\t" << end - begin << std::endl;

    begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        s.insert(v[i]);
    }
    end = clock();
    std::cout << "set insert time:\t\t" << end - begin << std::endl;

    // 查找
    begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        us.find(v[i]);
    }
    end = clock();
    std::cout << "unordered_set find time:\t" << end - begin << std::endl;

    begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        s.find(v[i]);
    }
    end = clock();
    std::cout << "set find time:\t\t\t" << end - begin << std::endl;

    // 删除
    begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        us.erase(v[i]);
    }
    end = clock();
    std::cout << "unordered_set erase time:\t" << end - begin << std::endl;

    begin = clock();
    for (size_t i = 0; i < n; ++i)
    {
        s.erase(v[i]);
    }
    end = clock();
    std::cout << "set erase time:\t\t\t" << end - begin << std::endl;
}

void Test_Close_HashTable()
{
    Lenyiin::Close_HashTable<int, int, Lenyiin::SetKeyOfT<int>> ht;
    ht.Insert(4);
    ht.Insert(14);
    ht.Insert(24);
    ht.Insert(5);
    ht.Insert(15);
    ht.Insert(25);
    ht.Insert(6);
    ht.Insert(16);

    ht.Print();

    ht.Erase(14);
    ht.Erase(24);
    ht.Print();

    std::cout << "是否存在 5 ? " << (ht.Find(5) ? "true" : "false") << std::endl;
}

void Test_Open_HashTable_1()
{
    Lenyiin::Open_HashTable<int, int, Lenyiin::SetKeyOfT<int>, Lenyiin::_Hash<int>> ht;
    ht.Insert(4);
    ht.Insert(14);
    ht.Insert(24);
    ht.Insert(5);
    ht.Insert(15);
    ht.Insert(25);
    ht.Insert(6);
    ht.Insert(16);
    ht.Insert(26);
    ht.Insert(36);
    ht.Insert(33);
    ht.Insert(37);
    ht.Insert(32);

    ht.Print();

    ht.Erase(4);
    ht.Erase(14);

    ht.Print();
}

void Test_Open_HashTable_2()
{
    Lenyiin::Open_HashTable<std::string, std::string, Lenyiin::SetKeyOfT<std::string>, Lenyiin::_Hash<std::string>> ht;
    ht.Insert("sort");
    ht.Insert("string");
    ht.Insert("left");
    ht.Insert("right");

    std::cout << ht.HashFunc("abcd") << std::endl;
    std::cout << ht.HashFunc("aadd") << std::endl;
}

void Test_Unordered_Set()
{
    Lenyiin::Unordered_Set<int> s;
    s.Insert(1);
    s.Insert(5);
    s.Insert(4);
    s.Insert(2);
    s.Insert(5);
    s.Insert(5);
    s.Insert(53);
    s.Insert(54);

    Lenyiin::Unordered_Set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << std::endl;

    s.Print();

    std::cout << "查找 4: " << (s.Find(4) ? "true" : "false") << std::endl;
    std::cout << "查找 6: " << (s.Find(6) ? "true" : "false") << std::endl;

    std::cout << "删除 2" << std::endl;
    s.Erase(2);
    s.Print();
}

void Test_Unordered_Map()
{
    Lenyiin::Unordered_Map<std::string, std::string> dict;
    dict.Insert(std::make_pair("sort", "排序"));
    dict.Insert(std::make_pair("left", "左边"));
    dict.Insert(std::make_pair("string", "字符串"));

    dict["left"] = "剩余"; // 修改
    dict["end"] = "尾部";  // 插入 + 修改

    // Unordered_Map<string, string>::iterator it = dict.begin();
    auto it = dict.begin();
    while (it != dict.end())
    {
        // cout << it->first << ":" << it->second << endl;
        std::cout << (*it).first << ":" << (*it).second << std::endl;
        ++it;
    }
    std::cout << std::endl;

    dict.Print();

    std::cout << "查找 left: " << (dict.Find("left") ? "true" : "false") << std::endl;
    std::cout << "查找 up: " << (dict.Find("up") ? "true" : "false") << std::endl;

    std::cout << "删除 left" << std::endl;
    dict.Erase("left");
    dict.Print();
}

int main()
{
    Test_unordered_set();
    Test_unordered_map();
    Test_OP();

    Test_Close_HashTable();
    Test_Open_HashTable_1();
    Test_Open_HashTable_2();

    Test_Unordered_Set();
    Test_Unordered_Map();

    return 0;
}