std::map和std::unordered_map区别

区别

std::map 和 std::unordered_map 是 C++ 标准库中的两个容器，用于实现键值对的关联。它们之间的主要区别在于底层实现和性能特征。

底层实现：std::map 是基于红黑树（一种平衡二叉搜索树）实现的有序映射容器，而 std::unordered_map 是基于哈希表实现的无序映射容器。

排序：std::map 中的元素是按照键的排序顺序进行存储的，因此在遍历时会按照键的升序输出。而 std::unordered_map 中的元素是根据哈希函数计算的哈希值存储的，没有固定的顺序。

查找效率：在平均情况下，std::map 的查找操作的时间复杂度为 O(log n)，其中 n 是元素的数量。而 std::unordered_map 的查找操作的平均时间复杂度为 O(1)，即常数时间。这是因为哈希表可以通过哈希函数直接计算出元素所在的位置，而不需要进行比较操作。

内存占用：由于 std::map 使用红黑树存储元素，并且需要维护树的平衡性，因此它通常占用的内存比 std::unordered_map 多。而 std::unordered_map 使用哈希表存储元素，其内存占用相对较少。

对于存储大量数据并需要快速查找的场景，std::unordered_map 通常具有更好的性能，因为它的查找操作更快速。但是，如果你需要按照键的顺序进行遍历或者需要有序的存储，那么 std::map 是更合适的选择。

需要注意的是，由于哈希表的实现依赖于哈希函数，因此 std::unordered_map 在某些情况下可能会出现哈希冲突，导致性能下降。另外，std::map 支持自定义的比较函数来定义键的排序方式，而 std::unordered_map 则需要提供自定义的哈希函数。

根据具体的使用场景和需求，你可以选择适合的容器来实现键值对的关联。

std::unordered_map使用示例

在 C++ 中，你可以使用标准库中的 std::unordered_map 类来创建一个哈希表（无序映射）。std::unordered_map 提供了一种将键和值关联起来的方式，并使用哈希函数来快速查找和访问元素。

以下是一个示例代码，演示如何创建和使用 std::unordered_map：

#include 
#include 
#include 

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

    // 向哈希表中插入键值对
    hashTable["apple"] = 1;
    hashTable["banana"] = 2;
    hashTable["orange"] = 3;

    // 访问哈希表中的元素
    std::cout << "apple 的值为：" << hashTable["apple"] << std::endl;

    // 检查哈希表中是否存在某个键
    if (hashTable.count("banana") > 0)
    {
        std::cout << "哈希表中存在 banana 键" << std::endl;
    }

    // 遍历哈希表中的所有键值对
    for (const auto& pair : hashTable)
    {
        std::cout << "键：" << pair.first << "，值：" << pair.second << std::endl;
    }

    return 0;
}
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
29
30

在上述代码中，我们首先包含了 头文件，并使用 std::unordered_map 定义了一个哈希表，其中键的类型是 std::string，值的类型是 int。

然后，我们使用插入操作 hashTable[“key”] = value 向哈希表中插入键值对。我们可以使用方括号操作符来访问哈希表中的元素，例如 hashTable[“apple”]。

我们还可以使用 count() 函数来检查哈希表中是否存在某个键。如果 count(“key”) 的返回值大于 0，则表示哈希表中存在该键。

最后，我们使用范围循环遍历哈希表中的所有键值对，并输出它们的键和值。

运行上述代码将输出以下结果：

apple 的值为：1
哈希表中存在 banana 键
键：banana，值：2
键：orange，值：3
键：apple，值：1
1
2
3
4
5

为什么 查找哈希表的时候，要判断.end()，如下代码：

auto it = myHashMap.find(key);
if (it != myHashMap.end())
1
2

在 C++ 的 std::unordered_map 中，find 函数在找到指定键的情况下会返回一个指向该键的迭代器，如果没有找到指定键，则返回一个指向容器末尾的迭代器，即 end()。因此，我们可以通过判断迭代器是否等于 end() 来确定是否找到了指定的键。

当 find 函数没有找到指定键时，它会返回一个指向容器末尾的迭代器，这是一个特殊的迭代器，表示查找失败。通过判断迭代器是否等于 end()，我们可以确定是否找到了指定的键。

在你提供的代码中，auto it = myHashMap.find(key); 将查找结果赋值给 it，然后通过 it != myHashMap.end() 来判断是否找到了指定键。如果 it 等于 myHashMap.end()，则说明没有找到指定键；否则，说明找到了指定键。

这种判断方式可以避免在未找到键的情况下访问不存在的迭代器或者无效的值，从而防止程序运行时出现错误或异常情况。因此，在使用 find 函数进行哈希表的查找时，通常会结合判断迭代器是否等于 end() 来确保查找的安全性。

std::map 的简单示例

下面是一个使用 std::map 的简单示例：

#include 
#include 

int main() {
    // 创建一个 std::map 容器，键的类型为 int，值的类型为 std::string
    std::map<int, std::string> myMap;

    // 向 map 中插入键值对
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    // 使用下标操作符访问键值对
    std::cout << "Value at key 2: " << myMap[2] << std::endl;

    // 使用迭代器遍历 map
    std::cout << "All key-value pairs in the map:" << std::endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 查找特定的键
    int key = 3;
    auto it = myMap.find(key);
    if (it != myMap.end()) {
        std::cout << "Value found at key " << key << ": " << it->second << std::endl;
    } else {
        std::cout << "Key " << key << " not found in the map." << std::endl;
    }

    // 删除特定的键值对
    myMap.erase(2);

    // 检查键是否存在
    if (myMap.count(2) > 0) {
        std::cout << "Key 2 exists in the map." << std::endl;
    } else {
        std::cout << "Key 2 does not exist in the map." << std::endl;
    }

    return 0;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

这个示例展示了如何使用 std::map 创建、插入、访问、遍历、查找和删除键值对。你可以根据自己的需求修改和扩展这个示例。