SET

C++ std::set 的实现方式、常用函数与复杂度
也叫做 有序集合

一、实现方式

  • 底层结构：红黑树（Red-Black Tree）
  • 特点：
    • 自平衡二叉搜索树，树高 O(log n)
    • 插入、删除、查找均为 O(log n)
    • 元素有序且唯一

二、常用函数与复杂度

  1. 构造与初始化
    set<int> s; O(1)
    set<int> s(a.begin(), a.end()); O(n log n)
    set<int> s = {1,2,3}; O(n log n)

  2. 插入
    s.insert(x); O(log n)
    s.emplace(args...); O(log n)

  3. 删除
    s.erase(it); O(log n)
    s.erase(x); O(log n)
    s.erase(first, last); O(k log n)

  4. 查找
    s.find(x); O(log n)
    s.count(x); O(log n)

  5. 范围查询
    s.lower_bound(x); O(log n)
    s.upper_bound(x); O(log n)
    s.equal_range(x); O(log n)

  6. 迭代器与遍历
    s.begin(), s.end() O(1)
    遍历所有元素 O(n)

三、空间复杂度

  • 每个元素节点包含：值 + 父/左/右指针 + 颜色标记
  • 单元素比 vector 消耗多（约 2~3 倍）
  • 总体空间复杂度 O(n)，但常数因子较大

四、复杂度表

操作 时间复杂度
insert/emplace O(log n)
erase O(log n)
find/count O(log n)
lower_bound/upper_bound O(log n)
遍历全部元素 O(n)
空间复杂度 O(n) (常数因子大)

五、小结

  • 需要有序集合、范围查询时用 set
  • 仅需快速查找时用 unordered_set (均摊 O(1))


PRIORITY_QUEUE

C++ std::priority_queue 的实现方式、常用函数与复杂度
也叫做 优先队列 或者 堆

一、实现方式

  • 底层结构：默认基于 最大堆（max-heap） 实现，通常用 std::vector + 堆算法 (push_heap / pop_heap) 完成。
  • 元素默认按 operator< 排序，即堆顶元素为最大值。
  • 通过自定义比较函数可以实现最小堆或其他顺序。
  • 时间复杂度：插入、删除均为 O(log n)，取堆顶为 O(1)。

二、常用函数与复杂度

  1. 构造与初始化
    priority_queue<int> q; 默认最大堆，O(1)
    priority_queue<int, vector<int>, greater<int>> q; 最小堆，O(1)
    priority_queue<int>(v.begin(), v.end()); 区间构造，O(n) 建堆

  2. 插入
    q.push(x); 插入元素，O(log n)
    q.emplace(args...); 原地构造并插入，O(log n)

  3. 删除
    q.pop(); 删除堆顶，O(log n)

  4. 访问
    q.top(); 访问堆顶，O(1)
    q.size(); 返回大小，O(1)
    q.empty(); 判断是否为空，O(1)

三、空间复杂度

  • 底层使用 vector 存储元素，空间复杂度 O(n)。
  • 相比 set，没有指针/颜色等额外开销，更节省内存。

四、复杂度表

操作 时间复杂度
push/emplace O(log n)
pop O(log n)
top O(1)
size/empty O(1)

空间复杂度 O(n)