set 和 unordered_set

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

set

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

1. 创建 set

#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. 插入元素

#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. 查找元素

#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. 删除元素

#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

#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. 插入元素

#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. 查找元素

#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. 删除元素

#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：

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