unordered_map 基础

unordered_map 是 C++ 标准模板库（STL）中的一个非常有用的容器。它被用来存储键值对，其中每个键都是唯一的。这个容器使用哈希表来实现，因此其在平均情况下为键的查找、插入和删除操作提供了常数时间复杂度（O(1)）。下面是关于 unordered_map 的详细介绍：

基本用法

1. 初始化：可以通过直接声明或使用初始化列表来创建 unordered_map。
2. 插入元素：使用 insert 方法或 [] 操作符来插入新元素。
3. 访问元素：使用 [] 操作符或 at 方法来访问元素。
4. 删除元素：使用 erase 方法来删除元素。
5. 查找元素：使用 find 方法来查找特定键的元素。
6. 大小和容量：使用 size 方法获取元素个数，empty 检查是否为空。

特点和注意事项

1. 性能：在平均情况下，插入、删除和查找操作的时间复杂度都是 O(1)。但在最坏情况下，这些操作的时间复杂度可能退化为 O(n)。
2. 哈希函数：unordered_map 使用哈希函数将键映射到哈希表中的桶。对于自定义类型，可能需要定义自己的哈希函数。
3. 碰撞处理：当两个键映射到同一个桶时，unordered_map 通过链表来处理碰撞。
4. 无序性：如其名所示，unordered_map 中的元素是无序存储的，不保证元素的顺序。
5. 唯一键：每个键在 unordered_map 中必须是唯一的。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap;

    // 插入元素
    umap["apple"] = 5;
    umap["banana"] = 8;

    // 访问元素
    std::cout << "apple count: " << umap["apple"] << std::endl;

    // 查找元素
    if (umap.find("banana") != umap.end()) {
        std::cout << "banana found" << std::endl;
    }

    // 删除元素
    umap.erase("apple");

    // 遍历元素
    for (auto& item : umap) {
        std::cout << item.first << " => " << item.second << std::endl;
    }

    return 0;
}

这个示例展示了 unordered_map 的基本用法，包括如何插入、访问、查找和删除元素。使用 unordered_map 可以有效地处理大量的数据，尤其是在需要快速查找和更新数据的场合。