unordered_containers.cpp

// unordered_containers.cpp
// unordered_map 與 unordered_set 的完整用法示範
// 編譯：g++ -std=c++17 -Wall -o unordered_containers unordered_containers.cpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
#include <algorithm>

// ============================================================
// 自訂雜湊函式範例：讓 struct Point 可作為 unordered 容器的 key
// ============================================================
struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // 簡易組合雜湊
    }
};

int main() {
    std::cout << "========================================" << std::endl;
    std::cout << "  unordered_map / unordered_set 示範" << std::endl;
    std::cout << "========================================\n" << std::endl;

    // ========================================================
    // Part A: std::unordered_map
    // ========================================================
    std::cout << "==================== std::unordered_map ====================" << std::endl;

    // --- 1. 基本操作 ---
    std::cout << "\n--- 1. 基本操作 ---" << std::endl;

    std::unordered_map<std::string, int> ages;

    // 插入方式
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages.insert({"Charlie", 28});
    ages.emplace("David", 22);

    // 遍歷（順序不保證）
    std::cout << "所有人的年齡（順序不保證）:" << std::endl;
    for (const auto& [name, age] : ages) {
        std::cout << "  " << name << ": " << age << std::endl;
    }

    // --- 2. 查找 ---
    std::cout << "\n--- 2. 查找 ---" << std::endl;

    // find
    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << "找到 Bob, 年齡: " << it->second << std::endl;
    }

    // count
    std::cout << "count(\"Alice\")   = " << ages.count("Alice") << std::endl;
    std::cout << "count(\"Unknown\") = " << ages.count("Unknown") << std::endl;

    // contains (C++20, 但可用 count 替代)
    // if (ages.contains("Alice")) { ... }

    // --- 3. erase ---
    std::cout << "\n--- 3. erase ---" << std::endl;

    std::cout << "刪除前 size = " << ages.size() << std::endl;
    ages.erase("David");
    std::cout << "erase(\"David\") 後 size = " << ages.size() << std::endl;

    // --- 4. bucket 相關資訊 ---
    std::cout << "\n--- 4. 雜湊表內部資訊 ---" << std::endl;

    std::cout << "bucket_count  = " << ages.bucket_count() << std::endl;
    std::cout << "load_factor   = " << ages.load_factor() << std::endl;
    std::cout << "max_load_factor = " << ages.max_load_factor() << std::endl;

    // 每個 bucket 的大小
    std::cout << "各 bucket 大小:" << std::endl;
    for (std::size_t i = 0; i < ages.bucket_count(); ++i) {
        if (ages.bucket_size(i) > 0) {
            std::cout << "  bucket[" << i << "]: "
                      << ages.bucket_size(i) << " 個元素" << std::endl;
        }
    }

    // --- 5. 應用：快速查詢表 ---
    std::cout << "\n--- 5. 應用：HTTP 狀態碼查詢表 ---" << std::endl;

    std::unordered_map<int, std::string> http_status = {
        {200, "OK"},
        {201, "Created"},
        {301, "Moved Permanently"},
        {400, "Bad Request"},
        {401, "Unauthorized"},
        {403, "Forbidden"},
        {404, "Not Found"},
        {500, "Internal Server Error"},
        {502, "Bad Gateway"},
        {503, "Service Unavailable"}
    };

    std::vector<int> codes_to_check = {200, 404, 500, 999};
    for (int code : codes_to_check) {
        auto search = http_status.find(code);
        if (search != http_status.end()) {
            std::cout << "  " << code << " → " << search->second << std::endl;
        } else {
            std::cout << "  " << code << " → 未知狀態碼" << std::endl;
        }
    }

    // --- 6. 應用：字串中字元頻率統計 ---
    std::cout << "\n--- 6. 應用：字元頻率統計 ---" << std::endl;

    std::string sentence = "hello world, this is a c++ example!";
    std::unordered_map<char, int> char_count;

    for (char c : sentence) {
        if (c != ' ') {
            char_count[c]++;
        }
    }

    std::cout << "字串: \"" << sentence << "\"" << std::endl;
    std::cout << "字元頻率:" << std::endl;

    // 收集到 vector 排序後輸出（因為 unordered_map 無序）
    std::vector<std::pair<char, int>> sorted_chars(
        char_count.begin(), char_count.end());
    std::sort(sorted_chars.begin(), sorted_chars.end());

    for (const auto& [ch, cnt] : sorted_chars) {
        std::cout << "  '" << ch << "': " << cnt << std::endl;
    }

    // ========================================================
    // Part B: std::unordered_set
    // ========================================================
    std::cout << "\n==================== std::unordered_set ====================" << std::endl;

    // --- 1. 基本操作 ---
    std::cout << "\n--- 1. 基本操作 ---" << std::endl;

    std::unordered_set<int> us = {5, 3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::cout << "初始化 {5,3,1,4,1,5,9,2,6,5}" << std::endl;
    std::cout << "內容（去重，順序不保證）: {";
    bool first = true;
    for (int val : us) {
        if (!first) std::cout << ", ";
        std::cout << val;
        first = false;
    }
    std::cout << "}" << std::endl;
    std::cout << "size = " << us.size() << std::endl;

    // --- 2. insert ---
    std::cout << "\n--- 2. insert ---" << std::endl;

    auto [iter1, ok1] = us.insert(7);
    std::cout << "insert(7): " << (ok1 ? "成功" : "已存在") << std::endl;

    auto [iter2, ok2] = us.insert(5);
    std::cout << "insert(5): " << (ok2 ? "成功" : "已存在") << std::endl;

    // --- 3. find / count / erase ---
    std::cout << "\n--- 3. find / count / erase ---" << std::endl;

    if (us.find(4) != us.end()) {
        std::cout << "找到 4" << std::endl;
    }

    std::cout << "count(9) = " << us.count(9) << std::endl;

    us.erase(3);
    std::cout << "erase(3) 後 size = " << us.size() << std::endl;

    // --- 4. 應用：快速判斷元素是否存在 ---
    std::cout << "\n--- 4. 應用：快速判斷元素是否存在 ---" << std::endl;

    std::unordered_set<std::string> valid_commands = {
        "help", "quit", "status", "run", "stop", "restart"
    };

    std::vector<std::string> user_inputs = {"run", "hello", "quit", "dance"};
    for (const auto& input : user_inputs) {
        bool is_valid = valid_commands.count(input) > 0;
        std::cout << "  \"" << input << "\" → "
                  << (is_valid ? "有效指令" : "未知指令") << std::endl;
    }

    // --- 5. 應用：兩陣列交集 ---
    std::cout << "\n--- 5. 應用：兩陣列交集 ---" << std::endl;

    std::vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    std::vector<int> arr2 = {4, 5, 6, 7, 8, 9};

    std::unordered_set<int> set1(arr1.begin(), arr1.end());
    std::vector<int> intersection;

    for (int val : arr2) {
        if (set1.count(val) > 0) {
            intersection.push_back(val);
        }
    }

    std::cout << "arr1 = [";
    first = true;
    for (int v : arr1) { if (!first) std::cout << ", "; std::cout << v; first = false; }
    std::cout << "]" << std::endl;

    std::cout << "arr2 = [";
    first = true;
    for (int v : arr2) { if (!first) std::cout << ", "; std::cout << v; first = false; }
    std::cout << "]" << std::endl;

    std::cout << "交集 = [";
    first = true;
    for (int v : intersection) { if (!first) std::cout << ", "; std::cout << v; first = false; }
    std::cout << "]" << std::endl;

    // ========================================================
    // Part C: 自訂雜湊函式
    // ========================================================
    std::cout << "\n==================== 自訂雜湊函式 ====================" << std::endl;

    std::unordered_set<Point, PointHash> point_set;
    point_set.insert({1, 2});
    point_set.insert({3, 4});
    point_set.insert({1, 2});  // 重複，不會插入

    std::cout << "Point set size = " << point_set.size() << std::endl;
    std::cout << "Points:" << std::endl;
    for (const auto& p : point_set) {
        std::cout << "  (" << p.x << ", " << p.y << ")" << std::endl;
    }

    // ========================================================
    // map vs unordered_map 比較
    // ========================================================
    std::cout << "\n==================== map vs unordered_map 比較 ====================" << std::endl;

    std::cout << "┌─────────────────┬───────────┬─────────────────┐" << std::endl;
    std::cout << "│      特性       │    map    │  unordered_map  │" << std::endl;
    std::cout << "├─────────────────┼───────────┼─────────────────┤" << std::endl;
    std::cout << "│ 底層結構        │  紅黑樹   │     雜湊表      │" << std::endl;
    std::cout << "│ 插入/查找/刪除  │ O(log n)  │  平均 O(1)      │" << std::endl;
    std::cout << "│ 元素順序        │  有序     │     無序        │" << std::endl;
    std::cout << "│ 記憶體使用      │  較少     │     較多        │" << std::endl;
    std::cout << "│ 需要 operator<  │   是      │      否         │" << std::endl;
    std::cout << "│ 需要 hash 函式  │   否      │      是         │" << std::endl;
    std::cout << "└─────────────────┴───────────┴─────────────────┘" << std::endl;

    std::cout << "\n========================================" << std::endl;
    std::cout << "  unordered 容器示範結束" << std::endl;
    std::cout << "========================================" << std::endl;

    return 0;
}