C++ unordered_set的迭代器失效

# 1. C++ unordered_set概述

在现代C++编程中，`unordered_set` 是一个非常有用的容器，它是标准模板库（STL）的一部分，用于存储唯一元素，并提供对这些元素的快速访问。与 `std::set` 不同，`unordered_set` 不会对存储的元素进行排序，而是使用哈希函数将元素映射到桶（bucket）中以提供更快的查找速度。本章旨在向读者介绍 `unordered_set` 的基本概念、用法及其在不同场景下的优势。

由于它不关心元素的顺序，`unordered_set` 通常比有序集合如 `std::set` 或 `std::map` 在执行插入、删除和查找操作时具有更好的平均性能表现。它特别适合那些元素顺序无关紧要，而执行速度是关键考虑的应用场景。通过本章节的介绍，我们将揭开 `unordered_set` 的神秘面纱，为你深入理解后续章节中的高级概念和用法打下坚实的基础。

# 2. unordered_set的内部机制

### 2.1 哈希表基础

#### 2.1.1 哈希函数和哈希冲突

在了解C++中的unordered_set之前，我们首先需要理解它背后的哈希表（Hash Table）机制。哈希表是根据关键码值（Key value）而直接进行访问的数据结构，它通过一个哈希函数将关键字映射到表中的一个位置来访问记录。

哈希函数设计的目标是将输入的关键字均匀分布到哈希表中，以降低冲突的可能性。然而，由于哈希函数的输出空间通常小于输入空间，即不同的关键字可能映射到同一个值，这就是所谓的哈希冲突。解决哈希冲突的常见策略有开放定址法（如线性探测、二次探测和双重哈希）和链地址法。

#include <iostream>

// 示例哈希函数
size_t simple_hash(const std::string& key) {
    size_t hash = 0;
    for (char c : key) {
        hash = (hash * 101 + c) % ***; // 一个简单的哈希公式
    }
    return hash;
}

int main() {
    std::string key = "example";
    size_t hash_value = simple_hash(key);
    std::cout << "The hash value of \"" << key << "\" is " << hash_value << std::endl;
    return 0;
}

在上述代码中，我们定义了一个简单的哈希函数`simple_hash`，用于计算一个字符串的关键字的哈希值。我们通过遍历每个字符并应用一个简单的数学公式来生成哈希值。虽然这不是一个高效的哈希函数，但它足以说明哈希函数的工作原理。

#### 2.1.2 哈希表的动态扩展

当哈希表中的元素数量不断增加时，表的负载因子（通常定义为元素数量与桶（bucket）数量的比值）会增加。随着负载因子的增长，哈希冲突的可能性也会增加，从而导致性能下降。为了避免这种情况，哈希表通常会在负载因子达到某个阈值时进行动态扩展（rehashing）。

动态扩展涉及创建一个新的更大的哈希表，并将所有旧表中的元素重新哈希到新表中。这一步骤确保了哈希表的性能不会因为负载因子过高而下降。

### 2.2 unordered_set的实现原理

#### 2.2.1 节点和桶的概念

在C++中，unordered_set是由节点（node）组成的集合。每个节点包含一个元素值和指向下一个节点的指针。此外，unordered_set将存储空间划分为多个桶（bucket），每个桶可以包含多个节点。通过将元素均匀地分布在各个桶中，可以有效地减少冲突，提高操作效率。

#### 2.2.2 插入、查找和删除操作的内部流程

当执行插入操作时，unordered_set首先计算元素的哈希值，然后确定元素应该放在哪个桶中。如果这个桶中已经有了相同的元素，则插入操作失败；否则，新元素被添加到桶中。

查找操作的工作原理类似，首先计算要查找元素的哈希值，然后在对应的桶中寻找。如果在桶内遍历过程中没有找到元素，则表示unordered_set中不存在该元素。

删除操作首先查找要删除的元素，如果找到，则从桶中移除该元素，并对可能的冲突链进行调整。由于unordered_set的特性，删除操作可能需要额外的步骤来维护桶内的顺序和结构。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> my_set;
    // 插入操作
    my_set.insert(10);
    // 查找操作
    auto it = my_set.find(10);
    if (it != my_set.end()) {
        std::cout << "Element found: " << *it << std::endl;
    }
    // 删除操作
    if (my_set.erase(10) == 1) {
        std::cout << "Element removed." << std::endl;
    }
    return 0;
}

在上述代码中，我们通过`std::unordered_set`演示了插入、查找和删除操作的使用方法。每个操作都有其对应的API函数，开发者可以通过这些函数完成对集合的操作。

# 3. 迭代器失效的理论分析

迭代器失效是指在使用标准模板库（STL）中的容器进行操作（如插入、删除元素）时，原有迭代器失去有效性的现象。由于迭代器失效通常会导致未定义行为，因此是C++开发者必须深入理解的重要概念