C++标准模板库（STL）unordered_map

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

一、定义与头文件

1. 定义

在C++中，unordered_map是一种无序的关联容器。它存储键 - 值对（key - value），其中键是唯一的。与map不同的是，unordered_map中的元素没有按照键进行排序（map默认按照键的升序排列），而是基于哈希表实现，这使得查找、插入和删除操作在平均情况下具有常数时间复杂度。

2. 头文件

要使用unordered_map，需要包含<unordered_map>头文件。

二、基本操作

1. 创建unordered_map对象

创建空的unordered_map：

std::unordered_map<int, std::string> myMap;

这里创建了一个键为int类型，值为std::string类型的unordered_map。

初始化创建：

std::unordered_map<int, std::string> myMap = { {1, "Alice"}, {2, "Bob"} };

2. 插入元素

使用insert方法：

#include <iostream>
#include <unordered_map>
int main() {
    std::unordered_map<std::string, int> myMap;
    myMap.insert({"apple", 1});
    myMap.insert(std::make_pair("banana", 2));
    return 0;
}

也可以使用下标操作符（如果键不存在则插入新元素，如果键存在则更新值）：

myMap[4] = "David";

3. 查找元素

使用find方法。例如：

std::unordered_map<int, std::string>::iterator it = myMap.find(3);

如果it!= myMap.end()，则表示找到了键为3的元素，可以通过it->second访问对应的值。

4. 遍历unordered_map

使用迭代器遍历：

for (auto it = myMap.begin(); it!= myMap.end(); ++it) {
    std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

或者使用基于范围的for循环（C++11及以上）：

for (const auto& [key, value] : myMap) {
    std::cout << "Key: " << key << ", Value: " << value << std::endl;
}

5. 删除元素

使用erase方法。例如：

要删除键为3的元素：myMap.erase(3);

也可以通过迭代器删除：

auto it = myMap.find(3);
if (it!= myMap.end()) {
    myMap.erase(it);
}

三、自定义哈希函数和相等比较器（针对自定义类型键）

1. 自定义哈希函数

当unordered_map的键为自定义类型时，需要提供自定义的哈希函数。例如，对于自定义结构体MyKey：

struct MyKey {
    int id;
    std::string name;
};
struct MyHash {
    std::size_t operator()(const MyKey& key) const {
        return std::hash<int>()(key.id) ^ std::hash<std::string>()(key.name);
    }
};

然后创建unordered_map时使用自定义哈希函数：

std::unordered_map<MyKey, std::string, MyHash> myCustomMap;

2. 自定义相等比较器

如果默认的相等比较（基于operator==）不满足需求，可以定义自定义的相等比较器。例如：

struct MyEqual {
    bool operator()(const MyKey& a, const MyKey& b) const {
        return a.id == b.id && a.name == b.name;
    }
};

然后创建unordered_map时同时使用自定义哈希函数和相等比较器：

std::unordered_map<MyKey, std::string, MyHash, MyEqual> myFullCustomMap;

C++编程语言基础