C++ std::set

1. 什么是 std::set？

std::set 是 C++ 标准库提供的一种关联容器，用于存储唯一的元素并且根据元素的大小自动排序。set 中的元素按照升序（默认）或自定义的顺序进行排列，并且每个元素在 set 中是唯一的，不能重复。

2. std::set 的特点

  • 自动排序：set 会根据元素的值进行自动排序，默认为升序排列，也可以自定义排序规则。
  • 唯一性：set 中的元素是唯一的，不能重复插入相同的元素。
  • 不支持索引访问：与 vector 或 list 不同，set 不支持通过下标访问元素，只能通过迭代器遍历。
  • 高效查找：set 采用平衡二叉树（如红黑树）实现，具有 O(log n) 的查找、插入和删除操作的时间复杂度。

3. std::set 常用操作

操作 描述
insert() 插入一个元素，如果元素已存在则不会插入。
find() 查找指定元素，返回指向该元素的迭代器，若找不到则返回 end()。
count() 查找指定元素是否存在，返回元素出现的次数（对于 set 来说，最多为 1）。
erase() 删除指定元素或指定范围内的元素。
size() 返回 set 中的元素数量。
empty() 检查 set 是否为空。
begin() 返回指向第一个元素的迭代器。
end() 返回指向最后一个元素之后位置的迭代器。
lower_bound() 返回指向第一个 不小于 指定值的元素的迭代器。
upper_bound() 返回指向第一个 大于 指定值的元素的迭代器。

4. std::set 示例代码

  1. #include <iostream>
  2. #include <set>
  4. using namespace std;
  6. int main() {
  7.     // 创建一个 set，存储整数
  8.     set<int> s;
  10.     // 插入元素
  11.     s.insert(10);
  12.     s.insert(20);
  13.     s.insert(15);
  14.     s.insert(10);  // 插入重复元素不会生效
  16.     // 输出 set 的大小
  17.     cout << "Size of set: " << s.size() << endl;
  19.     // 查找元素 15 是否存在
  20.     if (s.find(15) != s.end()) {
  21.         cout << "15 exists in the set." << endl;
  22.     } else {
  23.         cout << "15 does not exist in the set." << endl;
  24.     }
  26.     // 查找元素 25 是否存在
  27.     if (s.find(25) != s.end()) {
  28.         cout << "25 exists in the set." << endl;
  29.     } else {
  30.         cout << "25 does not exist in the set." << endl;
  31.     }
  33.     // 使用 count 检查元素是否存在
  34.     if (s.count(20)) {
  35.         cout << "20 exists." << endl;
  36.     }
  38.     // 使用 lower_bound 查找第一个大于或等于 15 的元素
  39.     auto it = s.lower_bound(15);
  40.     if (it != s.end()) {
  41.         cout << "Lower bound of 15: " << *it << endl;
  42.     }
  44.     // 输出 set 中的元素
  45.     cout << "Elements in set: ";
  46.     for (const auto& elem : s) {
  47.         cout << elem << " ";
  48.     }
  49.     cout << endl;
  51.     // 删除元素 20
  52.     s.erase(20);
  54.     // 输出删除后的 set
  55.     cout << "After erase(20), elements in set: ";
  56.     for (const auto& elem : s) {
  57.         cout << elem << " ";
  58.     }
  59.     cout << endl;
  61.     // 清空 set
  62.     s.clear();
  63.     if (s.empty()) {
  64.         cout << "The set is now empty." << endl;
  65.     }
  67.     return 0;
  68. }

5. 代码解析

  1. 插入元素：

    1.  s.insert(10);
    2.  s.insert(20);
    3.  s.insert(15);
    4.  s.insert(10);  // 插入重复元素不会生效

    使用 insert 向 set 中插入元素。如果插入的元素已存在，set 不会插入该元素，因此每个元素在 set 中是唯一的。

  2. 查找元素：

    1.  if (s.find(15) != s.end()) {
    2.      cout << "15 exists in the set." << endl;
    3.  }

    使用 find 查找指定元素，返回一个迭代器指向找到的元素，如果找不到，则返回 end()。

  3. 使用 count 检查元素是否存在：

    1.  if (s.count(20)) {
    2.      cout << "20 exists." << endl;
    3.  }

    使用 count 检查元素是否存在。对于 set，count 要么返回 0（元素不存在），要么返回 1（元素存在）。

  4. 使用 lower_bound 查找第一个不小于指定值的元素：

    1.  auto it = s.lower_bound(15);
    2.  if (it != s.end()) {
    3.      cout << "Lower bound of 15: " << *it << endl;
    4.  }

    lower_bound 返回一个指向第一个不小于指定值的元素的迭代器。如果没有找到合适的元素，则返回 end()。

  5. 遍历 set：

    1.  for (const auto& elem : s) {
    2.      cout << elem << " ";
    3.  }

    使用范围基 for 循环遍历 set 中的元素。由于 set 是自动排序的，遍历时的顺序是升序排列。

  6. 删除元素：

    1.  s.erase(20);

    使用 erase 删除指定元素。如果指定元素存在，它会从 set 中移除。

  7. 清空 set：

    1.  s.clear();
    2.  if (s.empty()) {
    3.      cout << "The set is now empty." << endl;
    4.  }

    使用 clear 清空 set 中的所有元素。使用 empty 检查 set 是否为空。

6. 小结

  • std::set 是一个有序的集合容器，元素在 set 中是唯一且自动排序的。
  • 常用操作包括插入、查找、删除、遍历以及查找指定位置的元素（如使用 lower_bound 和 upper_bound）。
  • set 提供了高效的查找和插入操作，适用于需要按顺序存储并去重的场景。