在C++98中，STL提供了底层为红黑树结构的一系列关联式容器（set, map, multiset, multimap），它们在查询时效率可达到 O(log_2 N)，且元素是有序的。然而，在C++11中，STL又引入了四个unordered系列关联式容器。今天我们就来深入探讨这四个基于哈希表实现的容器。

unordered系列关联式容器

unordered系列关联式容器与红黑树结构的关联式容器在使用方式上基本类似，最核心的区别在于：它们的底层结构是哈希表（Hash Table）。

这意味着：

1. 无序性：遍历这些容器时，得到的元素顺序与插入顺序无关，也并非按照大小排序。

2. 极速查询：它们的平均查找、插入和删除时间复杂度都能达到惊人的 O(1)，在处理大量且无需排序的数据时，性能远超基于红黑树的容器。

unordered_set的介绍

unordered_set 是一种用于存储唯一元素的容器。

• 它的元素既是键值（key）也是实值（value），即集合中的每个元素只包含一个值。

• 容器中的元素不能被修改（底层元素被 const 修饰），因为修改元素会破坏哈希表的结构。但可以插入和删除元素。

• 内部没有对元素进行任何特定顺序的排序。

unordered_set的使用

要使用 unordered_set，首先需要包含对应的头文件：

#include <unordered_set>
using namespace std;

unordered_set的定义方式

unordered_set 提供了多种构造方式，最常用的有以下几种：

// 1. 默认构造：构造一个空的 unordered_set
unordered_set<int> us1;

// 2. 迭代器区间构造：用已有容器的区间初始化
vector<int> v = {1, 2, 3, 4, 5};
unordered_set<int> us2(v.begin(), v.end());

// 3. 拷贝构造
unordered_set<int> us3(us2);

// 4. 初始化列表构造 (C++11)
unordered_set<int> us4 = {1, 2, 3, 4, 5, 5, 6}; // 注意：重复的5会被自动去重

unordered_set接口的使用

unordered_set 的核心接口非常直观，主要围绕增删查改（改只能删了再增）：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> us;

    // 1. 插入元素 (insert)
    us.insert(3);
    us.insert(1);
    us.insert(4);
    us.insert(1); // 重复元素，插入失败

    // 2. 遍历 (迭代器)
    // 注意：输出顺序大概率不是 3, 1, 4，因为它是无序的
    for (auto it = us.begin(); it != us.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 3. 查找元素 (find)
    auto pos = us.find(3);
    if (pos != us.end()) {
        std::cout << "找到了元素: " << *pos << "\n";
    }

    // 4. 判断元素是否存在 (count)
    // 对于 set 而言，count 的返回值只能是 0 或 1
    if (us.count(4)) {
        std::cout << "4 在容器中\n";
    }

    // 5. 删除元素 (erase)
    us.erase(3); // 直接按值删除
    
    // 6. 容量与清理
    std::cout << "大小: " << us.size() << "\n";
    us.clear(); // 清空容器
    std::cout << "是否为空: " << us.empty() << "\n";

    return 0;
}

unordered_multiset

unordered_multiset 与 unordered_set 的底层原理和大部分接口完全相同。唯一的区别在于：它允许容器中存在重复的元素。

• 在 unordered_multiset 中，insert 永远会成功。

• 它的 count(key) 接口非常有意义，可以返回该 key 在容器中出现的次数。

• 如果使用 erase(key)，会把容器中所有等于该 key 的元素全部删除。如果只想删除其中一个，需要传入特定的迭代器。

unordered_map的介绍

unordered_map 是用来存储 <key, value> 键值对的容器。

• 它的键（key）是唯一的，用于唯一标识元素；而值（value）是与键关联的内容。

• 通过 key 检索单个元素的速度非常快（平均 O(1)）。

• 键也是不可修改的，但可以通过键来修改其映射的值（value）。

unordered_map的使用

使用前需包含头文件：

#include <unordered_map>
#include <string>
using namespace std;

unordered_map的定义方式

与 set 类似，unordered_map 也有多种初始化方式：

// 1. 默认构造
unordered_map<string, int> dict1;

// 2. 初始化列表构造 (常用)
unordered_map<string, string> dict2 = {
    {"apple", "苹果"},
    {"banana", "香蕉"},
    {"orange", "橙子"}
};

// 3. 拷贝构造
unordered_map<string, string> dict3(dict2);

unordered_map接口的使用

unordered_map 最具特色的接口是 operator[]。它不仅能访问元素，还能实现插入和修改。

#include <iostream>
#include <unordered_map>
#include <string>

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

    // 1. 插入元素 (insert)
    dict.insert(std::make_pair("sort", "排序"));
    dict.insert({"string", "字符串"}); // C++11 花括号法

    // 2. operator[] 的神奇用法
    dict["left"] = "左边"; // "left" 不存在，插入 {"left", "左边"}
    dict["left"] = "剩余"; // "left" 已存在，将 value 修改为 "剩余"
    std::cout << "left 对应的中文是: " << dict["left"] << "\n"; // 查找

    // 3. 遍历 (注意取出的元素是 pair)
    for (auto& kv : dict) {
        std::cout << kv.first << " : " << kv.second << "\n";
    }

    // 4. 查找元素 (find)
    auto it = dict.find("sort");
    if (it != dict.end()) {
        std::cout << "找到了，" << it->first << " 意思是: " << it->second << "\n";
    }

    // 5. 删除元素 (erase)
    dict.erase("string");

    return 0;
}

注意：如果不确定键是否存在，且只是想查找而不想意外插入新节点，请使用 find 或者 at() 方法，千万不要随便使用 operator[]。

unordered_multimap

unordered_multimap 是 unordered_map 的允许键重复版本。

• 它可以存储多个具有相同 key 的 <key, value> 键值对。

• 常用于类似“字典”的应用场景：一个单词（key）可能对应多个不同的释义（value）。

• 核心注意点：由于一个 key 可能对应多个 value，因此 unordered_multimap 没有重载 operator[]。想要插入数据只能老老实实使用 insert。

总结

C++11 引入的 unordered 系列容器，彻底补齐了哈希表这一数据结构的官方实现。在不需要对数据进行排序，仅仅只是进行高频查询、去重、统计的场景下，请毫不犹豫地把它们作为你的首选容器！