容器类 <set>

C++ 标准库中的 <set> 是一个关联容器，它存储了一组唯一的元素，并按照一定的顺序进行排序。提供了高效的元素查找、插入和删除操作。它是基于红黑树实现的，因此具有对数时间复杂度的查找、插入和删除性能。

<set> 容器中存储的元素类型必须满足以下条件：

• 元素类型必须可以比较大小。
• 元素类型必须可以被复制和赋值。

语法

包含头文件:

#include <set>

声明 set 容器

std::set<元素类型> 容器名;

常用操作

• insert(元素): 插入一个元素。
• erase(元素): 删除一个元素。
• find(元素): 查找一个元素。
• size(): 返回容器中元素的数量。
• empty(): 检查容器是否为空。

实例

下面是一个使用 <set> 的简单示例，包括元素的插入、查找、删除和输出结果。

#include <iostream>
#include <set>

int main() {
    // 声明一个整型 set 容器
    std::set<int> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);
    mySet.insert(40);

    // 输出 set 中的元素
    std::cout << "Set contains: ";
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 查找元素
    if (mySet.find(20) != mySet.end()) {
        std::cout << "20 is in the set." << std::endl;
    } else {
        std::cout << "20 is not in the set." << std::endl;
    }

    // 删除元素
    mySet.erase(20);

    // 再次输出 set 中的元素
    std::cout << "After erasing 20, set contains: ";
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 检查 set 是否为空
    if (mySet.empty()) {
        std::cout << "The set is empty." << std::endl;
    } else {
        std::cout << "The set is not empty." << std::endl;
    }

    // 输出 set 中元素的数量
    std::cout << "The set contains " << mySet.size() << " elements." << std::endl;

    return 0;
}

输出结果:

Set contains: 10 20 30 40 
20 is in the set.
After erasing 20, set contains: 10 30 40 
The set is not empty.
The set contains 3 elements.

总结

<set> 是 C++ 标准库中一个非常有用的容器，特别适合需要快速查找、插入和删除操作的场景

<unordered_set>

<unordered_set> 是标准模板库（STL）的一部分，提供了一种基于哈希表的容器，用于存储唯一的元素集合。与 set 不同，unordered_set 不保证元素的排序，但通常提供更快的查找、插入和删除操作。

unordered_set 是一个模板类，其定义如下：

#include <unordered_set>

std::unordered_set<Key, Hash = std::hash<Key>, Pred = std::equal_to<Key>, Alloc = std::allocator<Key>>

• Key 是存储在 unordered_set 中的元素类型。
• Hash 是一个函数或函数对象，用于生成元素的哈希值，默认为 std::hash<Key>。
• Pred 是一个二元谓词，用于比较两个元素是否相等，默认为 std::equal_to<Key>。
• Alloc 是分配器类型，用于管理内存分配，默认为 std::allocator<Key>。

语法

以下是一些基本的 unordered_set 操作：

• 构造函数：创建一个空的 unordered_set。

  std::unordered_set<int> uset;

• 插入元素：使用 insert() 方法。

  uset.insert(10);

• 查找元素：使用 find() 方法。

  auto it = uset.find(10);
  if (it != uset.end()) {
    // 元素存在
  }

• 删除元素：使用 erase() 方法。

  uset.erase(10);

• 大小和空检查：使用 size() 和 empty() 方法。

  size_t size = uset.size();
  bool isEmpty = uset.empty();

• 清空容器：使用 clear() 方法。

  uset.clear();

实例

下面是一个使用 unordered_set 的简单示例，包括输出结果。

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个整数类型的 unordered_set
    std::unordered_set<int> uset;

    // 插入元素
    uset.insert(10);
    uset.insert(20);
    uset.insert(30);

    // 打印 unordered_set 中的元素
    std::cout << "Elements in uset: ";
    for (int elem : uset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = uset.find(20);
    if (it != uset.end()) {
        std::cout << "Element 20 found in uset." << std::endl;
    }
    else {
        std::cout << "Element 20 not found in uset." << std::endl;
    }

    // 删除元素
    uset.erase(20);
    std::cout << "After erasing 20, elements in uset: ";
    for (int elem : uset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 检查大小和是否为空
    std::cout << "Size of uset: " << uset.size() << std::endl;
    std::cout << "Is uset empty? " << (uset.empty() ? "Yes" : "No") << std::endl;

    // 清空 unordered_set
    uset.clear();
    std::cout << "After clearing, is uset empty? " << (uset.empty() ? "Yes" : "No") << std::endl;

    return 0;
}

find() 方法用于查找指定元素。当查找成功时，它会返回一个指向该元素的迭代器；当查找失败时，它会返回一个特殊的迭代器 ——end()。

end() 并不指向容器中的任何实际元素，而是作为一个 "哨兵"（sentinel）标记着容器的末尾位置。因此，it != uset.end() 这个判断的含义是：

• 如果 it 不等于 end() 迭代器，说明 find() 找到了目标元素，it 指向该元素
• 如果 it 等于 end() 迭代器，说明 find() 没有找到目标元素

如果查找的元素是在最后一个 也可以用if (it != uset.end())这个来判断吗？不会产生歧义吗

完全可以用 if (it != uset.end()) 来判断，即使查找的元素恰好是容器中的最后一个元素，也不会产生歧义。

原因是：end() 迭代器从不指向容器中的任何实际元素，它始终是一个 "超出末尾" 的标记。

• 当查找最后一个元素时，find() 返回的是指向该元素的有效迭代器（it_last）
• 这个迭代器与 end() 仍然不相等（it_last != end()）

这也是 C++ 容器迭代器设计的精妙之处 —— 通过 "前闭后开" 的区间规则（[begin, end)），让所有元素的判断逻辑保持一致