[C++] STL Map（映射容器）

#include <map>
#include <iostream>
#include <string>

std::map<int, std::string> myMap;                    // 空 map
std::map<int, std::string> myMap2 = {{1, "one"}, {2, "two"}};  // 初始化列表
std::map<std::string, int> myMap3;                   // string -> int 映射

#include <map>
#include <iostream>
#include <string>

int main() {
    // 預設構造
    std::map<int, std::string> map1;

    // 初始化列表
    std::map<int, std::string> map2 = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 拷貝構造
    std::map<int, std::string> map3(map2);

    // 移動構造
    std::map<int, std::string> map4(std::move(map3));

    // 範圍構造
    std::pair<int, std::string> arr[] = {{4, "four"}, {5, "five"}};
    std::map<int, std::string> map5(arr, arr + 2);

    // 自訂比較函式
    std::map<int, std::string, std::greater<int>> map6;  // 降序排列

    return 0;
}

// 64 位元系統
sizeof(map<int, int>::node):
  key:    4 bytes
  value:  4 bytes
  left:   8 bytes (指標)
  right:  8 bytes (指標)
  parent: 8 bytes (指標)
  color:  1 byte
  總計：  ~40 bytes（含對齊）

100 個元素的 map<int, int> ≈ 4000 bytes
100 個元素的 vector<pair<int, int>> ≈ 800 bytes

map 記憶體開銷約為 vector 的 5 倍

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<int, std::string> myMap;

    // 方法1：使用 insert()
    myMap.insert({1, "one"});
    myMap.insert(std::make_pair(2, "two"));
    myMap.insert(std::pair<int, std::string>(3, "three"));

    // 方法2：使用 operator[]
    myMap[4] = "four";
    myMap[5] = "five";

    // 方法3：使用 emplace()（原地構造）
    myMap.emplace(6, "six");

    // 檢查插入是否成功
    auto result = myMap.insert({1, "ONE"});  // 鍵 1 已存在
    if (!result.second) {
        std::cout << "插入失敗，鍵 1 已存在" << std::endl;
    }

    // 輸出
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"}, {2, "two"}, {3, "three"}
    };

    // 方法1：使用 operator[]（如果鍵不存在會插入）
    std::cout << "myMap[1] = " << myMap[1] << std::endl;
    std::cout << "myMap[10] = " << myMap[10] << std::endl;  // 插入 {10, ""}
    std::cout << "myMap.size() = " << myMap.size() << std::endl;  // 4

    // 方法2：使用 at()（如果鍵不存在會拋出異常）
    try {
        std::cout << "myMap.at(2) = " << myMap.at(2) << std::endl;
        std::cout << "myMap.at(20) = " << myMap.at(20) << std::endl;  // 異常
    } catch (const std::out_of_range& e) {
        std::cout << "錯誤: " << e.what() << std::endl;
    }

    // 方法3：使用 find()（最安全）
    auto it = myMap.find(3);
    if (it != myMap.end()) {
        std::cout << "找到 3: " << it->second << std::endl;
    }

    it = myMap.find(30);
    if (it == myMap.end()) {
        std::cout << "未找到 30" << std::endl;
    }

    return 0;
}

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}
    };

    // 方法1：通過鍵刪除
    myMap.erase(3);
    std::cout << "刪除 3 後，size = " << myMap.size() << std::endl;

    // 方法2：通過迭代器刪除
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        myMap.erase(it);
    }

    // 方法3：刪除範圍
    auto first = myMap.find(1);
    auto last = myMap.find(5);
    myMap.erase(first, last);  // 刪除 [1, 5)，即 1 和 4

    std::cout << "剩餘元素: ";
    for (const auto& pair : myMap) {
        std::cout << pair.first << " ";
    }
    std::cout << std::endl;

    return 0;
}

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92},
        {"David", 88}
    };

    // 使用 find() 查找
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << it->first << " 的分數: " << it->second << std::endl;
    }

    // 使用 count() 檢查是否存在
    if (scores.count("Charlie") > 0) {
        std::cout << "Charlie 存在" << std::endl;
    }

    if (scores.count("Eve") == 0) {
        std::cout << "Eve 不存在" << std::endl;
    }

    // 使用 contains()（C++20）
    // if (scores.contains("Alice")) {
    //     std::cout << "Alice 存在" << std::endl;
    // }

    return 0;
}

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {3, "three"}, {1, "one"}, {4, "four"}, {2, "two"}
    };

    // 方法1：範圍 for 迴圈（自動按鍵排序）
    std::cout << "方法1（自動排序）: " << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 方法2：迭代器
    std::cout << "\n方法2（迭代器）: " << std::endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // 方法3：反向遍歷
    std::cout << "\n方法3（反向）: " << std::endl;
    for (auto it = myMap.rbegin(); it != myMap.rend(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // 方法4：結構化綁定（C++17）
    std::cout << "\n方法4（結構化綁定）: " << std::endl;
    for (const auto& [key, value] : myMap) {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> myMap = {
        {10, "ten"}, {20, "twenty"}, {30, "thirty"},
        {40, "forty"}, {50, "fifty"}
    };

    // lower_bound：>= key 的第一個元素
    auto lb = myMap.lower_bound(25);
    if (lb != myMap.end()) {
        std::cout << "lower_bound(25): " << lb->first << std::endl;  // 30
    }

    // upper_bound：> key 的第一個元素
    auto ub = myMap.upper_bound(30);
    if (ub != myMap.end()) {
        std::cout << "upper_bound(30): " << ub->first << std::endl;  // 40
    }

    // equal_range：等於 key 的範圍
    auto range = myMap.equal_range(30);
    std::cout << "equal_range(30): ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->first << " ";
    }
    std::cout << std::endl;

    // 查詢範圍 [20, 40)
    std::cout << "\n範圍 [20, 40) 的元素: " << std::endl;
    auto start = myMap.lower_bound(20);
    auto end = myMap.lower_bound(40);
    for (auto it = start; it != end; ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.begin();

    // 雙向迭代器支援的操作
    ++it;      // 前進
    --it;      // 後退
    it->first;   // 訪問鍵
    it->second;  // 訪問值

    // 不支援的操作
    // it + 3;    // 錯誤！不支援隨機訪問
    // it[2];     // 錯誤！不支援下標操作

    // 使用 std::advance 移動
    std::advance(it, 2);
    std::cout << "移動後: " << it->first << std::endl;

    return 0;
}

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}
    };

    auto it1 = myMap.find(1);
    auto it2 = myMap.find(3);
    auto it5 = myMap.find(5);

    std::cout << "刪除前: it1=" << it1->first
              << ", it2=" << it2->first
              << ", it5=" << it5->first << std::endl;

    // 刪除 3
    myMap.erase(3);

    // it1 和 it5 仍然有效！
    std::cout << "刪除後: it1=" << it1->first
              << ", it5=" << it5->first << std::endl;
    // it2 已失效，不能使用

    // 插入也不會使迭代器失效
    myMap.insert({6, "six"});
    std::cout << "插入後: it1=" << it1->first
              << ", it5=" << it5->first << std::endl;

    return 0;
}

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

// ❌ 常見錯誤：以為只是查詢
std::string val = myMap[3];  // 插入了 {3, ""}！
std::cout << "size: " << myMap.size() << std::endl;  // 3

// ✅ 正確：使用 find() 或 at()
auto it = myMap.find(3);
if (it != myMap.end()) {
    std::string val = it->second;
}

// 或使用 at()（會拋出異常）
try {
    std::string val = myMap.at(3);
} catch (...) {
    // 處理不存在的情況
}

struct Point {
    int x, y;
};

// ❌ 錯誤：Point 沒有定義 operator<
// std::map<Point, std::string> myMap;  // 編譯錯誤！

// ✅ 解決方案1：定義 operator<
struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// ✅ 解決方案2：提供自訂比較函式
struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};
std::map<Point, std::string, PointCompare> myMap;

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

// ❌ 錯誤：遍歷時刪除會使迭代器失效
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    if (it->first == 2) {
        myMap.erase(it);  // it 失效，++it 未定義行為！
    }
}

// ✅ 正確：使用 erase 的返回值
for (auto it = myMap.begin(); it != myMap.end(); ) {
    if (it->first == 2) {
        it = myMap.erase(it);  // erase 返回下一個有效迭代器
    } else {
        ++it;
    }
}

// ❌ 錯誤：不滿足嚴格弱序
struct BadCompare {
    bool operator()(int a, int b) const {
        return a <= b;  // 錯誤！應該是 <
    }
};
// 這會導致未定義行為

// ✅ 正確：使用 < 運算子
struct GoodCompare {
    bool operator()(int a, int b) const {
        return a < b;
    }
};

struct LargeObject {
    char data[1000];
};

std::map<int, LargeObject> myMap;

// ❌ 效率低：返回拷貝
LargeObject obj = myMap[1];  // 拷貝 1000 bytes

// ✅ 推薦：使用參考
const LargeObject& obj = myMap.at(1);  // 無拷貝

// ✅ 或使用指標
auto it = myMap.find(1);
if (it != myMap.end()) {
    const LargeObject& obj = it->second;  // 無拷貝
}

#include <map>
#include <iostream>
#include <string>
#include <sstream>

std::map<std::string, int> wordCount(const std::string& text) {
    std::map<std::string, int> counts;
    std::istringstream iss(text);
    std::string word;

    while (iss >> word) {
        // 移除標點符號（簡化處理）
        word.erase(std::remove_if(word.begin(), word.end(), ::ispunct), word.end());

        // 轉小寫
        std::transform(word.begin(), word.end(), word.begin(), ::tolower);

        // 計數
        counts[word]++;  // 如果不存在會自動插入 {word, 0} 然後 +1
    }

    return counts;
}

int main() {
    std::string text = "Hello world! Hello C++ programming. "
                       "C++ is great for programming.";

    auto counts = wordCount(text);

    std::cout << "單字出現次數（按字母順序）:" << std::endl;
    for (const auto& [word, count] : counts) {
        std::cout << word << ": " << count << std::endl;
    }

    return 0;
}

#include <map>
#include <iostream>
#include <string>
#include <iomanip>

class GradeManager {
private:
    std::map<std::string, std::map<std::string, double>> grades;
    // 外層 map：學生名 -> 內層 map
    // 內層 map：科目 -> 分數

public:
    void addGrade(const std::string& student, const std::string& subject, double score) {
        grades[student][subject] = score;
    }

    double getGrade(const std::string& student, const std::string& subject) const {
        auto studentIt = grades.find(student);
        if (studentIt != grades.end()) {
            auto subjectIt = studentIt->second.find(subject);
            if (subjectIt != studentIt->second.end()) {
                return subjectIt->second;
            }
        }
        return -1;  // 未找到
    }

    double getAverage(const std::string& student) const {
        auto it = grades.find(student);
        if (it == grades.end() || it->second.empty()) {
            return 0;
        }

        double sum = 0;
        for (const auto& [subject, score] : it->second) {
            sum += score;
        }
        return sum / it->second.size();
    }

    void printReport() const {
        std::cout << std::fixed << std::setprecision(2);
        for (const auto& [student, subjects] : grades) {
            std::cout << "\n學生: " << student << std::endl;
            for (const auto& [subject, score] : subjects) {
                std::cout << "  " << subject << ": " << score << std::endl;
            }
            std::cout << "  平均: " << getAverage(student) << std::endl;
        }
    }
};

int main() {
    GradeManager gm;

    gm.addGrade("Alice", "Math", 95);
    gm.addGrade("Alice", "English", 88);
    gm.addGrade("Alice", "Physics", 92);

    gm.addGrade("Bob", "Math", 87);
    gm.addGrade("Bob", "English", 90);

    gm.addGrade("Charlie", "Math", 78);
    gm.addGrade("Charlie", "Physics", 85);

    gm.printReport();

    std::cout << "\nAlice 的數學成績: " << gm.getGrade("Alice", "Math") << std::endl;

    return 0;
}

#include <map>
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>

class ConfigParser {
private:
    std::map<std::string, std::string> config;

public:
    bool loadFromString(const std::string& content) {
        std::istringstream iss(content);
        std::string line;

        while (std::getline(iss, line)) {
            // 移除註解
            size_t commentPos = line.find('#');
            if (commentPos != std::string::npos) {
                line = line.substr(0, commentPos);
            }

            // 解析 key=value
            size_t equalPos = line.find('=');
            if (equalPos != std::string::npos) {
                std::string key = line.substr(0, equalPos);
                std::string value = line.substr(equalPos + 1);

                // 移除前後空白
                key.erase(0, key.find_first_not_of(" \t"));
                key.erase(key.find_last_not_of(" \t") + 1);
                value.erase(0, value.find_first_not_of(" \t"));
                value.erase(value.find_last_not_of(" \t") + 1);

                if (!key.empty()) {
                    config[key] = value;
                }
            }
        }

        return true;
    }

    std::string get(const std::string& key, const std::string& defaultValue = "") const {
        auto it = config.find(key);
        return (it != config.end()) ? it->second : defaultValue;
    }

    int getInt(const std::string& key, int defaultValue = 0) const {
        auto it = config.find(key);
        if (it != config.end()) {
            try {
                return std::stoi(it->second);
            } catch (...) {
                return defaultValue;
            }
        }
        return defaultValue;
    }

    void print() const {
        std::cout << "配置項目:" << std::endl;
        for (const auto& [key, value] : config) {
            std::cout << "  " << key << " = " << value << std::endl;
        }
    }
};

int main() {
    std::string configContent = R"(
# 伺服器配置
server_host = localhost
server_port = 8080

# 資料庫配置
db_host = 127.0.0.1
db_port = 3306
db_name = mydb
db_user = admin

# 其他設定
max_connections = 100
timeout = 30  # 秒
)";

    ConfigParser parser;
    parser.loadFromString(configContent);

    parser.print();

    std::cout << "\n查詢配置:" << std::endl;
    std::cout << "Server: " << parser.get("server_host")
              << ":" << parser.getInt("server_port") << std::endl;
    std::cout << "Max connections: " << parser.getInt("max_connections") << std::endl;

    return 0;
}

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

// ✅ 推薦：使用 find()（不會插入）
auto it = myMap.find(3);
if (it != myMap.end()) {
    std::cout << it->second << std::endl;
}

// ❌ 避免：使用 operator[]（會插入 {3, ""}）
// if (!myMap[3].empty()) {  // 已經插入了！
//     std::cout << myMap[3] << std::endl;
// }

std::map<int, std::string> myMap;

// ✅ 推薦：使用 emplace（原地構造）
myMap.emplace(1, "one");

// ❌ 避免：使用 insert（可能有額外複製）
// myMap.insert({1, "one"});
// myMap.insert(std::make_pair(1, "one"));

std::map<std::string, int> myMap = {{"Alice", 95}, {"Bob", 87}};

// ✅ 推薦：結構化綁定（清晰易讀）
for (const auto& [name, score] : myMap) {
    std::cout << name << ": " << score << std::endl;
}

// ❌ 較繁瑣：使用 pair
// for (const auto& pair : myMap) {
//     std::cout << pair.first << ": " << pair.second << std::endl;
// }

std::map<int, std::string> myMap = {
    {10, "ten"}, {20, "twenty"}, {30, "thirty"}, {40, "forty"}
};

// ✅ 推薦：使用 lower_bound/upper_bound
auto start = myMap.lower_bound(15);
auto end = myMap.upper_bound(35);

std::cout << "範圍 [15, 35] 的元素:" << std::endl;
for (auto it = start; it != end; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

// ✅ 推薦：使用 at()（有異常保護）
try {
    std::string val = myMap.at(10);
} catch (const std::out_of_range&) {
    std::cout << "鍵不存在" << std::endl;
}

// ❌ 危險：使用 operator[]
// std::string val = myMap[10];  // 插入 {10, ""}

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

// ✅ 推薦：使用 erase 的返回值
for (auto it = myMap.begin(); it != myMap.end(); ) {
    if (it->first % 2 == 0) {
        it = myMap.erase(it);  // 返回下一個有效迭代器
    } else {
        ++it;
    }
}

std::map<std::string, int> myMap = {{"Alice", 95}, {"Bob", 87}};

// ✅ 推薦：使用 count()（清晰表達意圖）
if (myMap.count("Charlie") > 0) {
    // 存在
}

// ✅ 也可以：使用 find()
if (myMap.find("Charlie") != myMap.end()) {
    // 存在
}

// ✅ 推薦：const 參考（避免拷貝）
void processMap(const std::map<int, std::string>& myMap) {
    for (const auto& [key, value] : myMap) {
        // 處理...
    }
}

// ❌ 避免：值傳遞（拷貝整個 map）
// void processMap(std::map<int, std::string> myMap) {
//     // 拷貝開銷大！
// }

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

// ❌ 錯誤：會插入不存在的鍵
if (myMap[3].empty()) {  // 已經插入 {3, ""}！
    std::cout << "不存在" << std::endl;
}
std::cout << "size: " << myMap.size() << std::endl;  // 3

// ✅ 正確：使用 find() 或 count()
if (myMap.find(3) == myMap.end()) {
    std::cout << "不存在" << std::endl;
}
std::cout << "size: " << myMap.size() << std::endl;  // 2

// ❌ 浪費：只需要快速查找，不需要排序
std::map<std::string, int> cache;  // O(log n) 查找

// ✅ 推薦：使用 unordered_map
std::unordered_map<std::string, int> cache;  // O(1) 平均查找

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

auto it = myMap.find(1);
if (it != myMap.end()) {
    // ❌ 錯誤：不能修改鍵（編譯錯誤）
    // it->first = 10;

    // ✅ 正確：只能修改值
    it->second = "ONE";
}

std::map<int, std::string> myMap = {{1, "one"}};

// ❌ 忽略返回值：不知道是否插入成功
myMap.insert({1, "ONE"});  // 插入失敗，鍵 1 已存在

// ✅ 檢查返回值
auto [it, success] = myMap.insert({1, "ONE"});
if (!success) {
    std::cout << "插入失敗，鍵已存在" << std::endl;
    // 如果需要更新，使用 operator[] 或 insert_or_assign
    myMap[1] = "ONE";
}

struct LargeValue {
    char data[10000];
};

std::map<int, LargeValue> myMap;

// ❌ 避免：返回值拷貝
void processValue(LargeValue val) {  // 拷貝 10000 bytes
    // 處理...
}

auto it = myMap.find(1);
if (it != myMap.end()) {
    processValue(it->second);  // 拷貝！
}

// ✅ 推薦：使用 const 參考
void processValue(const LargeValue& val) {
    // 處理...
}

auto it = myMap.find(1);
if (it != myMap.end()) {
    processValue(it->second);  // 無拷貝
}

std::map<int, std::string> myMap;

myMap.insert({3, "three"});
myMap.insert({1, "one"});
myMap.insert({2, "two"});

// ❌ 錯誤假設：按插入順序遍歷
// 實際上會按鍵排序：1, 2, 3

for (const auto& [key, value] : myMap) {
    std::cout << key << " ";  // 輸出: 1 2 3（不是 3 1 2）
}

std::map<int, int> myMap;

// ❌ 效率低：頻繁插入刪除（每次 O(log n) + 平衡操作）
for (int i = 0; i < 1000000; ++i) {
    myMap[i] = i * 2;
}
for (int i = 0; i < 500000; ++i) {
    myMap.erase(i);
}

// ✅ 考慮：如果不需要排序，使用 unordered_map
// ✅ 或者：批次操作，減少插入刪除次數

struct Person {
    std::string name;
    int age;
};

// ❌ 錯誤：Person 沒有定義 operator<
// std::map<Person, int> myMap;  // 編譯錯誤！

// ✅ 解決方案：定義 operator< 或提供比較函式
struct Person {
    std::string name;
    int age;

    bool operator<(const Person& other) const {
        if (name != other.name) return name < other.name;
        return age < other.age;
    }
};

std::map<Person, int> myMap;  // OK