🗺️ std::map & unordered_map — Key-Value Storage

std::map và std::unordered_map là associative containers — lưu trữ dữ liệu theo key-value pairs.

---

map vs unordered_map

Feature	std::map	std::unordered_map
Implementation	Red-Black Tree	Hash Table
Key order	✅ Sorted	❌ No order
Lookup	O(log n)	O(1) average
Insert	O(log n)	O(1) average
Memory	Less	More (hash buckets)
Key requirement	operator<	std::hash + operator==

📌 Khi nào dùng cái nào?

• unordered_map: Default choice — faster lookup
• map: Khi cần iteration theo sorted order

---

std::map — Ordered Map

Tạo và Insert

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

int main() {
    // Empty map
    std::map<std::string, int> ages;
    
    // Insert methods
    ages["Alice"] = 25;                    // operator[]
    ages.insert({"Bob", 30});              // C++11 initializer
    ages.insert(std::make_pair("Charlie", 35));
    ages.emplace("David", 40);             // C++11 in-place construct
    
    // Initializer list
    std::map<std::string, int> scores = {
        {"Math", 95},
        {"Physics", 88},
        {"Chemistry", 92}
    };
    
    return 0;
}

Access

std::map<std::string, int> ages = {
    {"Alice", 25},
    {"Bob", 30}
};

// operator[] — ⚠️ Creates entry if not exists!
int age1 = ages["Alice"];   // 25
int age2 = ages["Unknown"]; // Creates {"Unknown", 0}!

// at() — throws if not exists
int age3 = ages.at("Alice");  // 25
// ages.at("Unknown");        // ❌ throws std::out_of_range

// Check existence first
if (ages.count("Alice") > 0) {
    std::cout << ages["Alice"] << std::endl;
}

// C++20 contains()
if (ages.contains("Alice")) {  // C++20
    // ...
}

// find() — returns iterator
auto it = ages.find("Alice");
if (it != ages.end()) {
    std::cout << it->first << ": " << it->second << std::endl;
}

⚠️ operator[] Side Effect

map["key"] sẽ tạo entry mới với default value nếu key không tồn tại!

std::map<std::string, int> m;
if (m["test"] > 0) { }  // Side effect: m now contains {"test", 0}

Dùng find() hoặc count() để check existence mà không tạo entry.

Iterate

std::map<std::string, int> ages = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};

// Range-based (C++11)
for (const auto& [name, age] : ages) {  // Structured bindings (C++17)
    std::cout << name << ": " << age << std::endl;
}

// Old style
for (const auto& pair : ages) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

// Iterator
for (auto it = ages.begin(); it != ages.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// ✅ Output is SORTED by key:
// Alice: 25
// Bob: 30
// Charlie: 35

Erase

std::map<std::string, int> ages = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};

ages.erase("Alice");         // By key
ages.erase(ages.begin());    // By iterator

// Erase with condition (C++20 erase_if)
std::erase_if(ages, [](const auto& pair) {
    return pair.second < 30;
});

---

std::unordered_map — Hash Map

Basic Usage (Same API)

#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> ages;
    
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages.insert({"Charlie", 35});
    
    // Access — same as map
    int age = ages["Alice"];
    
    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << it->second << std::endl;
    }
    
    // ⚠️ Iteration order is NOT sorted, NOT insertion order!
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << std::endl;
    }
    // Order có thể là: Bob, Charlie, Alice, ... (unpredictable)
    
    return 0;
}

Custom Key Type

#include <unordered_map>
#include <string>

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

// Custom hash function
struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> pointNames;
    pointNames[{0, 0}] = "Origin";
    pointNames[{1, 1}] = "Unit";
    
    return 0;
}

---

std::multimap — Multiple Values per Key

#include <map>

int main() {
    std::multimap<std::string, int> scores;
    
    // Same key, multiple values
    scores.insert({"Alice", 95});
    scores.insert({"Alice", 88});
    scores.insert({"Alice", 92});
    scores.insert({"Bob", 85});
    
    // Count entries for a key
    size_t count = scores.count("Alice");  // 3
    
    // Get all entries for a key
    auto range = scores.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";  // 95 88 92
    }
    
    return 0;
}

---

Performance Comparison

┌─────────────────────────────────────────────────────────────────┐
│                  MAP vs UNORDERED_MAP                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  std::map (Red-Black Tree):                                     │
│                                                                 │
│           ┌───┐                                                 │
│           │ M │                                                 │
│          /     \                                                │
│       ┌───┐   ┌───┐                                            │
│       │ D │   │ T │                                            │
│      /   \   /   \                                              │
│    ┌──┐┌──┐┌──┐┌──┐                                            │
│    │B ││G ││P ││Z │   O(log n) lookup                          │
│                                                                 │
│  std::unordered_map (Hash Table):                               │
│                                                                 │
│    Bucket 0: [A:1] → [F:6]                                     │
│    Bucket 1: [B:2]                                             │
│    Bucket 2: [C:3] → [H:8] → [M:13]                            │
│    Bucket 3: [D:4]          O(1) average lookup                │
│    ...                                                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Operation	std::map	std::unordered_map
Insert	O(log n)	O(1) avg, O(n) worst
Lookup	O(log n)	O(1) avg, O(n) worst
Erase	O(log n)	O(1) avg, O(n) worst
Iterate sorted	✅ O(n)	❌ Need to sort first
Memory overhead	Low	Higher (buckets)

---

Common Patterns

Word Frequency Counter

#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox";
    std::unordered_map<std::string, int> freq;
    
    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        freq[word]++;  // ✅ operator[] creates 0 if not exists
    }
    
    for (const auto& [word, count] : freq) {
        std::cout << word << ": " << count << std::endl;
    }
    
    return 0;
}

Two-way Lookup

#include <map>
#include <string>

int main() {
    std::map<std::string, int> nameToId;
    std::map<int, std::string> idToName;
    
    auto addPerson = [&](const std::string& name, int id) {
        nameToId[name] = id;
        idToName[id] = name;
    };
    
    addPerson("Alice", 1001);
    addPerson("Bob", 1002);
    
    // Lookup both ways
    int aliceId = nameToId["Alice"];          // 1001
    std::string name = idToName[1002];        // "Bob"
    
    return 0;
}

---

📚 Tổng kết

Container	Use When
std::map	Need sorted keys, guaranteed O(log n)
std::unordered_map	Fast lookup, don't care about order
std::multimap	Multiple values per key
std::unordered_multimap	Multi-value + hash-based

---

➡️ Tiếp theo

Tiếp theo: Performance Analysis — Big O của tất cả containers.