深入了解unorder_map

一、概述

unorder_map 是 C++ STL 中的一种关联容器，它允许存储一组具有映射关系的数据。这些映射关系是由键和值组成的，每个键只能对应一个值。unorder_map 内部使用哈希表来实现数据的快速查找，因此可以在 O(1) 的时间复杂度内完成元素的查找、添加和删除操作。

二、基本使用

要使用 unorder_map，通常需要包含头文件 ，在代码中定义一个对象，对象的类型应该是 unorder_map 的模板参数，该参数有两个类型 T1 和 T2，代表键和值的类型，可以使用下面的代码来定义一个 unorder_map 对象：

#include 
#include 

int main()
{
    std::unordered_map mymap;
    ...
}

在上面的代码中，我们定义了一个字符串类型的键和一个整数类型的值，因为 unorder_map 内部使用哈希表，因此键可以是任何可以哈希的类型。插入元素可以使用以下语句：

mymap["hello"] = 1;
mymap["world"] = 2;
mymap.insert(std::make_pair("good", 3));

可以使用下面的方法来查找元素：

it = mymap.find("hello");
if (it != mymap.end())
    std::cout << "Value: " <second << std::endl;

其中，it 是一个迭代器，可以通过 it->first 和 it->second 来访问键和值。

删除元素可以使用以下语句：

mymap.erase("hello");

三、几个需要注意的细节问题

虽然 unorder_map 实现了 O(1) 时间复杂度的元素查找、添加和删除操作，但在使用时还需要注意一些细节问题，否则可能会出现一些难以察觉的问题。

1.哈希函数冲突问题

在哈希表内部，数据被分成一组桶，每个桶中存放了一些元素。哈希函数用于将元素映射到不同的桶内，但可能会出现多个元素映射到同一个桶的情况，这就叫做哈希冲突。当哈希表中的元素数量较少时，哈希冲突的影响并不显著，但当元素数量增加时，哈希冲突的影响会越来越大，影响整个哈希表的性能。

为了解决哈希冲突问题，unorder_map 通常会使用链表来存储每个桶内的元素，每个桶内的元素都按照添加的顺序存储，因此在查找元素时需要遍历整个链表。链表太长会导致查找的复杂度从 O(1) 增加到O(n)，因此需要使用哈希函数来减少哈希冲突的可能，从而降低整个哈希表的查找复杂度。

2.对于自定义类型的元素，需要重载哈希函数和比较函数

当 unorder_map 存储自定义类型的元素时，需要实现哈希函数和比较函数，以便 unorder_map 能够正确地处理这些类型的元素。

下面是一个自定义类型的哈希函数和比较函数的示例：

struct MyStruct
{
    int x;
    int y;
};

struct MyStructHash
{
    size_t operator()(const MyStruct& mystruct) const
    {
        return std::hash()(mystruct.x) ^ std::hash()(mystruct.y);
    }
};

struct MyStructEqual
{
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const
    {
        return lhs.x == rhs.x && lhs.y == rhs.y;
    }
};

std::unordered_map mymap;

在上面的代码中，MyStructHash 是哈希函数的实现，MyStructEqual 是比较函数的实现。mymap 对象的第三个和第四个参数分别是哈希函数和比较函数。注意，这些函数需要满足特定的签名，否则代码无法编译通过。

四、总结

unorder_map 是一个非常有用且性能出色的 C++ STL 容器，它允许存储一组具有映射关系的数据，并在 O(1) 的时间复杂度内完成元素的查找、添加和删除操作。使用 unorder_map 时，我们需要注意哈希冲突问题和自定义类型的哈希函数和比较函数的实现。