在 C++ 中，STL（标准模板库）提供了各种容器用于存储和管理数据，其中无序容器是处理无序数据集的重要工具。本篇总结将详细解析 C++ STL 中的无序容器，包括 unordered_set、unordered_map、unordered_multiset 和 unordered_multimap。

1. 无序容器概述

无序容器是基于哈希表实现的，提供常数时间复杂度的平均查找、插入和删除操作，适用于需要快速访问数据的场景。

2. unordered_set 和 unordered_multiset

• unordered_set：用于存储唯一的元素，元素的顺序不被保证。常用于需要快速查找唯一值的场景。

  • 常用操作：
  • insert(elem): 插入元素。
  • erase(elem): 删除元素。
  • find(elem): 查找元素，返回迭代器。
  • size(): 返回元素数量。

• unordered_multiset：类似于 unordered_set，但是允许存储重复的元素。

  • 常用操作：
  • insert(elem): 插入元素。
  • count(elem): 返回某个元素出现的次数。
  • erase(elem): 删除指定元素，可以通过迭代器删除单个元素。

3. unordered_map 和 unordered_multimap

• unordered_map：是一种关联容器，存储键值对（key-value），需要保证键的唯一性，通过键进行快速查找。

  • 常用操作：
  • operator[]: 访问或插入键值对。
  • insert(pair): 插入键值对。
  • erase(key): 删除指定键的元素。
  • find(key): 查找键，返回迭代器。
  • size(): 返回键值对的数量。

• unordered_multimap：与 unordered_map 类似，但允许键重复。

  • 常用操作：
  • insert(pair): 插入可能重复的键值对。
  • count(key): 返回某个键的所有键值对数量。
  • find(key): 查找指定键，返回指向第一个匹配值的迭代器。

4. 哈希函数与自定义类型

无序容器的高效性依赖于哈希函数，当使用自定义类或特殊类型作为键时，可能需要提供自定义的哈希函数和相等比较函数。标准库中的 std::hash 可以用于基础类型，以下是如何针对自定义类型实现哈希：

#include <iostream>  
#include <unordered_set>  
#include <string>  
struct MyType {  
    int a;  
    std::string b;  
    bool operator==(const MyType& other) const {  
        return a == other.a && b == other.b;  
    }  
};  
namespace std {  
    template <>  
    struct hash<MyType> {  
        std::size_t operator()(const MyType& mt) const {  
            return std::hash<int>()(mt.a) ^ std::hash<std::string>()(mt.b);  
        }  
    };  
}  

5. 应用场景与总结

无序容器在需要高效查找和插入的应用场景下非常有用，比如实现词典、缓存机制、唯一元素集等。使用无序容器要注意它们的非确定性顺序特性以及可能的哈希冲突处理。

总的来说，无序容器是 C++ STL 中强大的工具之一，理解其特性和操作可以帮助开发者高效地管理和访问数据。