引言

关联容器（Associative Containers）是一类通过键值对（key-value）进行数据管理的数据结构，支持高效的查找、插入和删除操作。分为有序关联容器和无序关联容器。

本文主要介绍无序关联容器：

• 包含：std::unordered_set、std::unordered_map、std::unordered_multiset、std::unordered_multimap

• 底层实现：哈希表。哈希表通过哈希函数将键（key）映射到桶（bucket），从而高效地定位元素。

• 特点：元素无序排列，查找效率更高，所有操作平均复杂度O(1)（极端情况下O(n)）。

1 std::unordered_set

定义与特性

• 只存储唯一元素（key），无value。

• 元素无序，底层为哈希表。

• 查找、插入、删除均为均摊O(1)复杂度。

• 只关心元素是否存在。

代码示例

#include <unordered_set>
#include <iostream>

// 示例：unordered_set的基本用法
void UnorderedSetExample() {
  std::unordered_set<int> numbers;
  numbers.insert(4);
  numbers.insert(2);
  numbers.insert(4);  // 重复插入无效

  numbers.erase(2);

  // 查找
  if (numbers.find(4) != numbers.end()) {
    std::cout << "4 exists in unordered_set" << std::endl;
  }

  // 遍历（顺序不保证）
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;
}

适用场景

• 判重（如去重集合、唯一ID集合）。

• 只关心元素是否存在，不关心顺序。

2 std::unordered_multiset

定义与特性

• 存储可重复元素（key），无value。

• 元素无序，底层为哈希表。

• 查找、插入、删除均为均摊O(1)复杂度。

• 可统计某元素出现次数。

代码示例

#include <unordered_set>
#include <iostream>

// 示例：unordered_multiset的用法
void UnorderedMultisetExample() {
  std::unordered_multiset<int> numbers;
  numbers.insert(4);
  numbers.insert(2);
  numbers.insert(4);  // 可重复插入

  std::cout << "Count of 4: " << numbers.count(4) << std::endl;

  // 删除所有值为4的元素
  numbers.erase(4);

  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;
}

适用场景

• 需要存储可重复且无序的数据。

• 统计元素频次。

3 std::unordered_map

定义与特性

• 存储唯一键值对（key-value）。

• key唯一，value可重复。

• 元素无序，底层为哈希表。

• 查找、插入、删除均为均摊O(1)复杂度。

• 支持operator[]访问和插入。

代码示例

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

// 示例：unordered_map的基本用法
void UnorderedMapExample() {
  std::unordered_map<std::string, int> ages;
  ages["Tom"] = 18;
  ages["Jerry"] = 20;

  if (ages.count("Tom")) {
    std::cout << "Tom's age: " << ages["Tom"] << std::endl;
  }

  // 遍历（顺序不保证）
  for (const auto& kv : ages) {
    std::cout << kv.first << ": " << kv.second << std::endl;
  }

  // operator[]会插入默认值
  std::cout << "Bob's age: " << ages["Bob"] << std::endl;  // 插入Bob，值为0
}

适用场景

• 需要唯一key映射value，且高效查找。

• 适用于缓存、计数、字典等需求。

4 std::unordered_multimap

定义与特性

• 存储可重复键值对（key-value）。

• key可重复，value可重复。

• 元素无序，底层为哈希表。

• 查找、插入、删除均为均摊O(1)复杂度。

• 不支持operator[]，需用insert插入。

代码示例

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

// 示例：unordered_multimap的基本用法
void UnorderedMultimapExample() {
  std::unordered_multimap<std::string, int> scores;
  scores.insert({"Tom", 90});
  scores.insert({"Tom", 85});
  scores.insert({"Jerry", 88});

  // 查找Tom的所有分数
  auto range = scores.equal_range("Tom");
  std::cout << "Tom's scores: ";
  for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
  }
  std::cout << std::endl;

  // 遍历
  for (const auto& kv : scores) {
    std::cout << kv.first << ": " << kv.second << std::endl;
  }

  // 删除某个key的所有元素
  scores.erase("Tom");
}

适用场景

• 一对多关系存储（如学生选课、商品多标签）。

• 需要高效查找所有同key的元素。

5 无序关联容器对比

6 注意事项

1. 哈希函数与相等比较器：可自定义以支持复杂类型。

2. 遍历顺序不可依赖：哈希表结构会随操作而变化。

3. 元素不可直接修改：修改key会导致哈希失效。

4. 高性能但内存开销略大：哈希表需预留空间，适合大数据量高频查找。

5. 极端情况下复杂度退化：哈希冲突严重时，复杂度可能退化到O(n)。

6. 线程安全：STL无序容器本身非线程安全，多线程需加锁。

7. 迭代器失效：删除元素后相关迭代器会失效。

7 与有序关联容器对比