C++ unordered_set深度使用

# 1. C++ unordered_set简介

`unordered_set` 是C++标准库中的一个容器，它提供了一种在无序集合中存储唯一元素的方式。与其它标准容器如 `set` 不同，`unordered_set` 的元素不按照任何特定顺序存储，而是通过哈希表机制来快速进行元素的插入、删除和查找操作。由于避免了排序的开销，`unordered_set` 在大多数情况下能够提供比 `set` 更快的访问速度。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet;
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);
    for (auto i : mySet) {
        std::cout << i << " ";
    }
    return 0;
}

在上述代码示例中，我们创建了一个 `unordered_set` 的实例，并插入了三个整数元素。通过遍历，我们可以看到元素被存储在容器中。需要注意的是，元素的输出顺序可能每次都不同，因为它们是无序存储的。

# 2. unordered_set的内部机制

### 2.1 哈希表的原理

#### 2.1.1 哈希函数的概念及其作用
哈希函数是将输入（也称为键）转换为整数或浮点数（统称为哈希码）的函数。在哈希表中，哈希函数的作用是将键映射到存储桶的索引。这样做的目的是为了能够快速地定位数据项，使得查找、插入和删除操作的时间复杂度接近常数时间。

理想的哈希函数会将输入均匀地映射到哈希表的存储桶中，以最小化冲突的概率。在C++的`unordered_set`中，标准库提供了默认的哈希函数实现，但是当存储特定类型的元素时，可以自定义哈希函数来优化性能。

#### 2.1.2 冲突解决策略
冲突是指当两个不同的键在哈希函数的作用下产生相同的哈希码，从而映射到同一个存储桶。解决冲突的常见策略有以下几种：

- **开放寻址法**：所有元素都存储在哈希表数组中。当发生冲突时，会尝试在数组中寻找另一个位置。常见的开放寻址法有线性探测、二次探测和双重哈希。

- **链表法**：每个存储桶维护一个链表，所有哈希到该桶的元素都放入链表中。当发生冲突时，元素简单地添加到链表的末尾。

在`unordered_set`中，使用的是链表法来解决冲突。由于链表可以有效地处理冲突并且不需要预先分配大量空间，这使得`unordered_set`在大多数情况下拥有很好的性能。

### 2.2 unordered_set的实现细节

#### 2.2.1 容器的内存分配
`unordered_set`需要为存储数据和管理节点分配内存。内存分配策略包括：

- **动态内存分配**：当容器中元素的数量超过当前存储桶的数量时，`unordered_set`可能会增加存储桶的数量并重新分配内存。

- **内存池**：为了减少内存分配操作的开销，`unordered_set`可能会使用内存池来存储和重用节点。

#### 2.2.2 桶(buckets)的概念及其管理
在`unordered_set`中，"桶"是一个用于存储具有相同哈希值的元素链表的容器。管理桶的方式对性能至关重要：

- **负载因子**：负载因子决定了何时需要进行再哈希操作。负载因子越大，存储桶越满，冲突的可能性也越大，但是内存使用效率更高。

- **再哈希**：当元素数量增加，导致负载因子超过某个阈值时，`unordered_set`会创建更多的桶并将所有元素重新哈希到新的桶数组中。

#### 2.2.3 插入和查找算法
插入和查找操作是`unordered_set`中的核心功能，它们通常具有以下步骤：

- **哈希值计算**：使用哈希函数计算键的哈希值，得到对应的存储桶索引。
- **冲突解决**：如果存储桶索引已被占用，则遍历该桶的链表解决冲突，找到正确的插入位置或确定元素是否已存在。
- **插入**：将新元素添加到存储桶链表的头部。
- **查找**：从存储桶索引开始，遍历链表直到找到元素或到达链表末尾。

### 2.3 性能考量

#### 2.3.1 时间复杂度分析
`unordered_set`操作的平均时间复杂度为O(1)，这是因为哈希表通常在大多数情况下可以实现常数时间的查找、插入和删除。然而，最坏情况下，如果哈希函数性能差，或者负载因子过高，操作的时间复杂度可能退化到O(n)，其中n是元素的数量。

#### 2.3.2 空间复杂度分析
`unordered_set`的空间复杂度为O(n)，其中n是元素的数量。除了存储元素本身，每个存储桶需要存储一个链表的头指针，以及可能的额外控制信息。空间的使用在很大程度上取决于哈希函数的质量和负载因子。

接下来，我们将通过代码示例和详细的逻辑分析进一步探讨这些概念。

# 3. C++ unordered_set的基本用法

在本章节中，我们将深入了解和探讨C++中unordered_set容器的基本用法。首先会涉及创建和初始化容器的方法，然后逐步过渡到展示如何使用各种成员函数来操作unordered_set。此外，我们还将研究迭代器的使用方法以及它们的类别和特点。本章节会通过实例代码和详细的解释，帮助读者掌握unordered_set的实用技能。

## 3.1 容器的创建和初始化

### 3.1.1 构造函数的使用

在C++中，创建一个`unordered_set`容器可以通过多种构造函数来实现。默认构造函数将创建一个空的容器，这个容器是动态增长的，可以根据需要存储元素。除了默认构造函数之外，还可以使用拷贝构造函数或者提供一个范围来初始化容器。

#include <unordered_set>

int main() {
    // 创建一个空的unordered_set容器
    std::unordered_set<int> mySet;

    // 使用拷贝构造函数
    std::unordered_set<int> mySetCopy(mySet);

    // 使用初始化列表创建并初始化
    std::unordered_set<int> mySetFromInitializer = {1, 2, 3, 4, 5};

    // 使用一个范围来初始化
    std::vector<int> vec = {6, 7, 8, 9, 10};
    std::unordered_set<int> mySetFromRange(vec.begin(), vec.end());

    // 使用预分配空间的构造函数
    std::unordered_set<int> mySetWithHint(20); // 预先分配20个桶的空间

    return 0;
}

#### 参数说明

- `unordered_set()`：创建一个空的unordered_set。
- `unordered_set(const unordered_set& other)`：拷贝构造函数，创建一个包含与`other`相同元素的新unordered_set。
- `unordered_set(InputIterator first, InputIterator last)`：使用在`first`和`last`范围内的元素创建unordered_set。
- `unordered_set(size_type n, const value_type& value = value_type())`：创建一个具有n个元素的unordered_set，每个元素都被初始化为value。

#### 代码逻辑说明

- 默认构造函数创建了一个空容器，此时容器不持有任何元素。
- 拷贝构造函数通过复制现有unordered_set的所有元素来创建新的unordered_set。
- 初始化列表构造函数允许我们通过提供一个初始化列表来直接创建并初始化容器，非常方便。
- 使用范围构造函数需要两个迭代器参数，这两个参数指向容器中的一个范围，该范围内的元素将被复制到新创建的unordered_set中。
- 预分配空间的构造函数允许我们指定一个初步的桶数，这有助于在某些情况下提升性能，因为桶的数量会决定内部存储结构的大小和复杂度。

### 3.1.2 initializer_list的使用

C++11标准引入了一个新的类型`initializer_list`，允许我们使用花括号内的初始化列表。对于`unordered_set`而言，`initializer_list`可以让我们以一种非常简洁的方式来初始化容器。

#include <unordered_set>
#include <initializer_list>

int main() {
    std::unordered_set<int> mySet {1, 2, 3, 4, 5};

    // 使用initializer_list作为构造函数参数
    std::unordered_set<int> mySetWithInitializer = {1, 2, 3, 4, 5};

    return 0;
}

使用`initializer_list`的好处是代码更加简洁和直观，而且它提供了更好的性能优化的可能性，因为编译器可以优化以`initializer_list`作为参数的构造函数调用。

## 3.2 常用成员函数

### 3.2.1 插入元素的方法

`unordered_set`提供了多个函数来进行元素的插入操作。通常使用`insert`方法添加单个元素，或使用`emplace`方法在容器内直接构造元素，这样可以避免不必要的拷贝和移动操作。

#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert({30, 40, 50});

    // emplace可以更高效地插入元素
    mySet.emplace(60);

    return 0;
}

#### 参数说明

- `insert(const value_type& value)`：插入value到unordered_set中。
- `insert(value_type&& value)`：移动插入value到unordered_set中。
- `insert(std::initializer_list<value_type> ilist)`：插入ilist中的所有元素。
- `emplace(const value_type& value)`：在unordered_set中就地构造一个元素。
- `emplace(value_type&& value)`：在unordered_set中就地移动构造一个元素。

#### 代码逻辑说明

- `insert`函数可以接受单个值、一个初始化列表或移动插入值。
- `emplace`函数与`insert`类似，但是