Day 13

1.map函数

C++ 中的 std::map 是一个关联容器 (Associative Container)，它存储的是键值对 (key-value pairs)。它的主要特点是能够根据键（key）快速、高效地查找对应的值（value）。

std::map 的底层实现通常是红黑树 (Red-Black Tree)，这是一种自平衡的二叉搜索树。

1. 键值对存储：每个元素都是一个 std::pair<const Key, Value> 对象。
2. 键的唯一性：在一个 map 中，所有的键都是唯一的，不能重复。
3. 自动排序：map 中的元素会自动根据键的大小进行排序。默认情况下，它使用 < 运算符进行比较，实现升序排列。
4. 高效查找：由于其底层是树结构，查找、插入和删除操作的平均时间复杂度都是 O(log n)。

C++ std::map 完整示例代码

下面的代码演示了 std::map 的常用操作，包括头文件、创建、插入、访问、查找、遍历和删除。

cpp

运行

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

int main() {
    // 1. 创建一个 map
    // 键的类型是 int，值的类型是 std::string
    std::map<int, std::string> userMap;

    // 2. 插入元素
    // 方法一：使用 insert() 成员函数
    userMap.insert(std::make_pair(102, "Bob"));
    userMap.insert(std::pair<int, std::string>(101, "Alice")); // 插入时会自动排序

    // 方法二：使用 [] 操作符 (最常用)
    // 如果键不存在，则插入新元素；如果键已存在，则修改其对应的值
    userMap[103] = "Charlie";
    userMap[101] = "Alice Smith"; // 键 101 已存在，这里会更新它的值

    // 3. 访问元素
    // 方法一：使用 [] 操作符
    std::cout << "ID 101's name is: " << userMap[101] << std::endl;
    // 注意：如果使用 [] 访问一个不存在的键，map 会自动插入这个键，并为其值类型创建一个默认对象
    // 例如，下面这行代码会插入一个键为 999，值为 "" (空字符串) 的元素
    std::cout << "ID 999's name is: " << userMap[999] << std::endl; // 这会导致 map 大小增加

    // 方法二：使用 at() 成员函数 (更安全)
    // at() 只在键存在时返回值，如果键不存在，会抛出 std::out_of_range 异常
    try {
        std::cout << "ID 103's name is: " << userMap.at(103) << std::endl;
        // std::cout << "ID 500's name is: " << userMap.at(500) << std::endl; // 这行会抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }

    // 4. 查找元素
    // 使用 find() 成员函数，它返回一个迭代器
    int searchKey = 102;
    auto it = userMap.find(searchKey);
    if (it != userMap.end()) {
        // 找到了，it 指向找到的元素 (一个 pair)
        std::cout << "Found user with ID " << searchKey << ": " << it->second << std::endl;
    } else {
        std::cout << "User with ID " << searchKey << " not found." << std::endl;
    }

    // 5. 遍历 map
    std::cout << "\n--- All Users (sorted by ID) ---" << std::endl;

    // 方法一：使用范围 for 循环 (C++11 及以上，推荐)
    for (const auto& pair : userMap) {
        std::cout << "ID: " << pair.first << ", Name: " << pair.second << std::endl;
    }

    std::cout << "-----------------------------" << std::endl;

    // 方法二：使用迭代器
    for (std::map<int, std::string>::iterator i = userMap.begin(); i != userMap.end(); ++i) {
        std::cout << "ID: " << i->first << ", Name: " << i->second << std::endl;
    }

    // 6. 删除元素
    // 方法一：根据键删除
    userMap.erase(103);
    std::cout << "\nAfter deleting ID 103, size is: " << userMap.size() << std::endl;

    // 方法二：根据迭代器删除
    it = userMap.find(102);
    if (it != userMap.end()) {
        userMap.erase(it);
    }
    std::cout << "After deleting ID 102, size is: " << userMap.size() << std::endl;

    // 7. 清空 map
    userMap.clear();
    if (userMap.empty()) {
        std::cout << "\nThe map is now empty." << std::endl;
    }

    return 0;
}

运行结果

plaintext

ID 101's name is: Alice Smith
ID 999's name is: 
ID 103's name is: Charlie
Found user with ID 102: Bob

--- All Users (sorted by ID) ---
ID: 999, Name: 
ID: 101, Name: Alice Smith
ID: 102, Name: Bob
ID: 103, Name: Charlie
-----------------------------
ID: 999, Name: 
ID: 101, Name: Alice Smith
ID: 102, Name: Bob
ID: 103, Name: Charlie

After deleting ID 103, size is: 3
After deleting ID 102, size is: 2

The map is now empty.

std::map vs std::unordered_map

C++ 标准库中还有一个非常相似的容器 std::unordered_map，它们的主要区别在于底层实现和排序特性：

简单来说：

• 如果你需要一个有序的键值对集合，或者希望在最坏情况下也能保证良好的性能，请使用 std::map。
• 如果你只关心最快的平均查找速度，并且不关心元素的顺序，请使用 std::unordered_map。

2.unordered_map函数

它的核心目标是提供比 std::map 更极致的查找效率。

• 键 (Key)：就是你要查的单词。
• 哈希函数 (Hash Function)：一个特殊的函数，能快速将单词转换成一个数字地址。
• 值 (Value)：这个单词的解释就存放在这个地址对应的 “抽屉” 里。

不会自动排序