C++ 新手指南：如何使用 set 和 unordered_set

在C++编程中，set 和 unordered_set 是两个常用的容器，它们分别属于有序集合和无序集合。无论您是刚接触编程的小白，还是希望更深入了解C++ STL的使用者，理解它们的区别和使用场景，能够帮助您更高效地处理数据。

在本文中，我们将深入介绍这两个容器的使用方法、实现原理，并通过示例代码详细讲解如何应用它们。

set 和 unordered_set 的区别

1. 排序：set 是有序的，即元素会按升序自动排列。unordered_set 是无序的，元素存储的顺序不固定。

2. 底层实现：set 使用红黑树（红黑树是一种平衡二叉树结构），unordered_set 使用哈希表。

3. 时间复杂度：由于底层结构不同，二者的操作性能也有所差异。

   操作类型	set 的时间复杂度	unordered_set 的时间复杂度
   插入、删除	O(log n)	平均 O(1)，最坏 O(n)
   查找	O(log n)	平均 O(1)，最坏 O(n)

哈希（Hashing）是一种通过哈希函数将数据映射到固定大小的数组（称为哈希表）中的技术。哈希函数根据输入的元素值计算出一个哈希值，并根据哈希值将元素存储在哈希表的对应位置。哈希表的优势在于它能够在常数时间（O(1)）内执行插入、查找和删除操作，特别适用于需要快速查找和去重的场景。对于 unordered_set 来说，它依赖哈希表来存储数据，因此可以在平均常数时间内完成元素的查找、插入和删除操作。

set 的使用方法

set 是一种自动排序的集合，它只存储唯一的元素。如果尝试插入重复的元素，set 会自动忽略。

代码示例

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(15);
    mySet.insert(10);  // 重复元素，插入无效

    // 遍历元素
    std::cout << "Set 中的元素：";
    for (const auto &elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 查找元素
    int key = 10;
    if (mySet.find(key) != mySet.end()) {
        std::cout << key << " 存在于 set 中。" << std::endl;
    } else {
        std::cout << key << " 不存在于 set 中。" << std::endl;
    }

    return 0;
}

代码讲解

• insert()：用于将元素插入到set中，若元素已存在则不插入。
• find()：检查特定元素是否存在于集合中。
• 迭代器遍历：for 循环通过 set 的迭代器实现遍历。

使用场景

当需要保持数据的有序性并确保唯一性时，set 是很好的选择。例如：处理排序后用户不重复的输入数据。

unordered_set 的使用方法

unordered_set 使用哈希表实现，因此插入和查找操作在平均情况下更高效，但数据存储顺序不固定。

代码示例

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    // 插入元素
    myUnorderedSet.insert(10);
    myUnorderedSet.insert(5);
    myUnorderedSet.insert(15);
    myUnorderedSet.insert(10);  // 重复元素，插入无效

    // 遍历元素
    std::cout << "Unordered Set 中的元素：";
    for (const auto &elem : myUnorderedSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 查找元素
    int key = 10;
    if (myUnorderedSet.find(key) != myUnorderedSet.end()) {
        std::cout << key << " 存在于 unordered_set 中。" << std::endl;
    } else {
        std::cout << key << " 不存在于 unordered_set 中。" << std::endl;
    }

    return 0;
}

代码讲解

• insert()：将元素插入 unordered_set，重复元素会被自动忽略。
• find()：查找某元素是否在集合中。
• 由于元素无序，遍历时输出的顺序不可预测。

使用场景

当您只关注集合元素的唯一性，并希望插入和查找操作尽可能高效时，可以选择 unordered_set。如：快速去重的哈希检查。

set 和 unordered_set 的选择建议

常见的 set 操作方法与注意事项

常见操作

1. insert(value)

   • 将元素插入 set 中。如果元素已经存在，插入操作会失败（即不会插入重复元素）。
   • 返回值：返回一个 pair，first 是插入的元素，second 是一个布尔值，指示元素是否成功插入。

2. erase(value)

   • 删除指定元素。如果元素存在，它将从 set 中移除。
   • 返回值：删除操作返回一个整数，表示删除的元素数量（通常为 0 或 1）。

3. find(value)

   • 查找指定元素。如果元素存在，返回指向该元素的迭代器；否则，返回 end()。

4. count(value)

   • 返回指定元素在 set 中的出现次数。由于 set 中的元素是唯一的，因此该操作的结果要么是 0，要么是 1。

5. clear()

   • 删除 set 中的所有元素。

6. size()

   • 返回 set 中的元素个数。

7. empty()

   • 如果 set 为空，返回 true，否则返回 false。

注意事项

• 元素的唯一性：set 会自动删除重复元素，因此插入重复元素时不会出错，但也不会插入新元素。
• 元素顺序：set 保证元素按升序排列，插入元素时会根据其值自动排序。
• 性能考虑：set 的插入、删除和查找操作时间复杂度为 O(log n)，适合中等规模的数据集。如果只关心操作性能，可以考虑使用 unordered_set，它在大多数情况下能提供常数时间复杂度的操作。

常见问题解答

1. 为什么插入重复元素时不会成功？

   • set 和 unordered_set 的特性是只存储唯一的元素，因此不会添加相同值的元素。

2. 我可以手动控制 unordered_set 中的元素顺序吗？

   • 不可以，unordered_set 中的元素顺序完全取决于哈希表结构。

总结

• set 是基于树的有序集合，适用于需要顺序保证的情况。
• unordered_set 基于哈希表，适合无序、高效的数据存储需求。