C++ std::set 有序集合指南

概述

std::set 是 C++ 标准库中的有序关联容器，存储唯一元素（自动去重），默认按升序排列。基于红黑树实现，提供高效的查找、插入和删除操作（O(log n) 复杂度）。

1. 包含头文件

#include <set>

2. 声明与初始化

初始化方式	示例	说明
空集合	std::set<int> mySet;	创建空集合
初始化列表	std::set<int> mySet = {3, 1, 4, 1, 5};	自动去重排序 → {1, 3, 4, 5}
拷贝构造	std::set<int> setCopy(mySet);	复制已有集合
迭代器范围	std::set<int> setRange(vec.begin(), vec.end());	从其他容器初始化

// 自定义排序规则（降序）
auto cmp = [](int a, int b) { return a > b; };
std::set<int, decltype(cmp)> descendingSet(cmp);
descendingSet = {5, 2, 8, 1}; // 排序后: {8, 5, 2, 1}

3. 核心操作

插入元素 (insert())

std::set<int> s;

// 插入单个元素
auto [pos1, inserted1] = s.insert(10);  // C++17 结构化绑定

// 插入多个元素
s.insert({20, 30, 15});

// 插入结果处理
if (inserted1) {
    std::cout << "10 inserted successfully\n";
}

// 使用迭代器提示位置（优化插入效率）
auto hint = s.lower_bound(25);
s.insert(hint, 25);

删除元素

方法	示例	说明
erase(key)	s.erase(20);	删除值为20的元素
erase(iterator)	s.erase(s.begin());	删除首个元素
erase(range)	s.erase(s.find(15), s.end());	删除15到末尾
clear()	s.clear();	清空整个集合

查找元素

方法	示例	说明
find()	auto it = s.find(30);	返回迭代器（未找到返回end）
count()	if (s.count(25)) {...}	存在返回1，否则0
contains() (C++20)	if (s.contains(42)) {...}	更直观的存在检查
lower_bound()	auto lb = s.lower_bound(20);	返回首个≥20的元素迭代器
upper_bound()	auto ub = s.upper_bound(20);	返回首个>20的元素迭代器
equal_range()	auto [lb, ub] = s.equal_range(20);	返回等于20的范围

访问元素

// 获取首元素（最小元素）
if (!s.empty()) {
    int minVal = *s.begin();  // 注意：不是front()
}

// 获取尾元素（最大元素）
if (!s.empty()) {
    int maxVal = *s.rbegin(); // 注意：不是back()
}

4. 集合遍历

顺序遍历（升序）

for (const auto& num : s) {
    std::cout << num << " ";
}
// 输出: 10 15 25 30

逆序遍历（降序）

for (auto it = s.rbegin(); it != s.rend(); ++it) {
    std::cout << *it << " ";
}
// 输出: 30 25 15 10

使用迭代器遍历

std::cout << "Set elements: ";
for (auto it = s.begin(); it != s.end(); ) {
    std::cout << *it;
    if (++it != s.end()) std::cout << " -> ";
}
// 输出: 10 -> 15 -> 25 -> 30

5. 容量与状态查询

方法	示例	说明
size()	size_t count = s.size();	返回元素数量
empty()	if (s.empty()) {...}	检查是否为空
max_size()	size_t max = s.max_size();	返回理论最大容量

6. 特殊操作

交换两个集合

std::set<int> setA = {1, 2, 3};
std::set<int> setB = {4, 5, 6};
setA.swap(setB); // setA = {4,5,6}, setB = {1,2,3}

集合比较

std::set<int> setX = {1, 2, 3};
std::set<int> setY = {1, 2, 3};

if (setX == setY) { // 按元素顺序比较
    std::cout << "Sets are equal\n";
}

7. 性能特性与注意事项

时间复杂度

操作	时间复杂度	说明
插入	O(log n)	红黑树平衡操作
删除
查找		二叉树搜索
遍历	O(n)	线性遍历所有节点

关键注意事项

1. 元素唯一性：自动去重，插入重复值会被忽略

   std::set<int> s = {1, 1, 2}; // 实际存储 {1, 2}
   

2. 元素不可变性：集合元素为const，不能直接修改

   // 错误示例（编译失败）：
   // *s.begin() = 100; 
   
   // 正确修改方式：
   int oldValue = 10;
   if (s.erase(oldValue)) {
       s.insert(100); // 先删除再插入新值
   }
   

3. 自定义类型支持：需提供比较函数

   struct Point { int x, y; };
   auto pointCmp = [](const Point& a, const Point& b) {
       return a.x < b.x || (a.x == b.x && a.y < b.y);
   };
   std::set<Point, decltype(pointCmp)> pointSet(pointCmp);
   

8. 应用场景

• 数据去重：自动去除重复元素

  std::vector<int> data = {5, 2, 5, 1, 3, 2};
  std::set<int> uniqueData(data.begin(), data.end());
  // uniqueData = {1, 2, 3, 5}
  

• 有序存储：自动维护排序状态

  std::set<std::string> names = {"Charlie", "Alice", "Bob"};
  // 自动排序: {"Alice", "Bob", "Charlie"}
  

• 快速查找：对数时间查找

  // 比排序后的vector更适用于频繁插入/删除的场景
  if (names.find("Bob") != names.end()) {
      // 找到元素
  }
  

• 范围查询：高效获取区间元素

  std::set<int> scores = {50, 65, 80, 90, 100};
  auto low = scores.lower_bound(60); // >=60
  auto high = scores.upper_bound(90); // >90
  for (auto it = low; it != high; ++it) {
      std::cout << *it << " "; // 输出: 65 80 90
  }
  

9. 与其他容器对比

特性	std::set	std::unordered_set	std::vector
排序	有序	无序	可排序（需手动）
查找复杂度	O(log n)	O(1)平均	O(n)
插入/删除
内存布局	非连续		连续
重复元素	自动去重		允许重复
迭代器稳定性	稳定	插入可能失效	可能失效

选择建议：需要有序存储且频繁查找时用std::set；只需快速查找不关心顺序用std::unordered_set；需要连续存储或随机访问用std::vector。