# set 和 unordered_set

URL: https://caijiao.org/cpp/stl/set
Source: docs/cpp/stl/set.md
Description: 本节介绍 C++ 标准库中的 'set' 和 'unordered_set' 容器，讲解其基本操作、区别以及适用场景。

C++ 提供了两种常用的集合类型：`set` 和 `unordered_set`。这两者都用于存储唯一的元素，但它们在底层实现、元素的存储顺序和操作效率上有所不同。了解它们的特点和使用场景，可以帮助开发者根据需要选择合适的容器。

## set

`set` 是一个基于红黑树实现的有序集合。它自动将元素按照键的顺序排列，并保证集合中的元素是唯一的。由于使用红黑树，`set` 提供对元素的对数时间复杂度查找、插入和删除操作。

### 1. 创建 set

```cpp
#include <iostream>
#include <set>

int main() {
    // 创建一个空的 set
    std::set<int> set1;

    // 使用初始化列表初始化
    std::set<int> set2 = {3, 1, 4, 1, 5, 9};

    // 打印 set，元素按升序排序
    for (const auto& item : set2) {
        std::cout << item << " ";
    }

    return 0;
}
````

### 2. 插入元素

```cpp
#include <iostream>
#include <set>

int main() {
    std::set<int> set = {3, 1, 4};

    // 插入新元素
    set.insert(5);
    set.insert(1);  // 插入重复元素将失败

    // 打印 set
    for (const auto& item : set) {
        std::cout << item << " ";
    }

    return 0;
}
```

### 3. 查找元素

```cpp
#include <iostream>
#include <set>

int main() {
    std::set<int> set = {3, 1, 4, 5};

    // 查找元素
    auto it = set.find(4);
    if (it != set.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found!" << std::endl;
    }

    return 0;
}
```

### 4. 删除元素

```cpp
#include <iostream>
#include <set>

int main() {
    std::set<int> set = {3, 1, 4, 5};

    // 删除指定元素
    set.erase(4);

    // 打印 set
    for (const auto& item : set) {
        std::cout << item << " ";
    }

    return 0;
}
```

## unordered\_set

`unordered_set` 是基于哈希表实现的集合，它不像 `set` 那样按照元素的顺序存储，而是根据哈希值来存储元素。`unordered_set` 提供常数时间复杂度的插入、查找和删除操作，适用于对元素顺序无要求的场景。

### 1. 创建 unordered\_set

```cpp
#include <iostream>
#include <unordered_set>

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

    // 使用初始化列表初始化
    std::unordered_set<int> set2 = {3, 1, 4, 1, 5, 9};

    // 打印 unordered_set，元素顺序不确定
    for (const auto& item : set2) {
        std::cout << item << " ";
    }

    return 0;
}
```

### 2. 插入元素

```cpp
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> set = {3, 1, 4};

    // 插入新元素
    set.insert(5);
    set.insert(1);  // 插入重复元素将失败

    // 打印 unordered_set，元素顺序不确定
    for (const auto& item : set) {
        std::cout << item << " ";
    }

    return 0;
}
```

### 3. 查找元素

```cpp
#include <iostream>
#include <unordered_set>

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

    // 查找元素
    auto it = set.find(4);
    if (it != set.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found!" << std::endl;
    }

    return 0;
}
```

### 4. 删除元素

```cpp
#include <iostream>
#include <unordered_set>

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

    // 删除指定元素
    set.erase(4);

    // 打印 unordered_set，元素顺序不确定
    for (const auto& item : set) {
        std::cout << item << " ";
    }

    return 0;
}
```

## set 与 unordered\_set 的区别

* **排序顺序**：

  * `set` 是有序的，元素会按照键的顺序（升序）排列。
  * `unordered_set` 是无序的，元素的顺序是根据哈希值决定的，不保证按任何顺序排列。

* **底层实现**：

  * `set` 基于红黑树（自平衡二叉搜索树）实现，提供对数时间复杂度的查找、插入和删除操作。
  * `unordered_set` 基于哈希表实现，提供常数时间复杂度的查找、插入和删除操作，但元素顺序不可预测。

* **性能**：

  * `set` 适用于需要保持元素有序的场景，但它的操作复杂度较高（O(log n)）。
  * `unordered_set` 适用于不关心元素顺序、只关心快速查找和插入的场景，提供更好的性能（O(1) 平均时间复杂度）。

## 何时选择 `set` 或 `unordered_set`

* 使用 `set`：

  * 当需要保持元素的有序性时。
  * 当需要进行范围查找（如查找一个范围内的所有元素）时。
* 使用 `unordered_set`：

  * 当不关心元素顺序，只需要快速查找、插入和删除时。
  * 当对性能要求较高，且元素数量较大时。