学习 C++ 中的 set、unordered_set 和 priority_queue

Source: Dev.to

set

概述

• 唯一 + 已排序的数据
• 存储唯一元素
• 保持排序顺序
• 使用自平衡二叉搜索树（红黑树）实现

示例

std::set

#include 
#include 

int main() {
    std::set s = {3, 1, 2, 2};
    for (int x : s) std::cout 
}

std::unordered_set

#include 

int main() {
    std::unordered_set us = {3, 1, 2, 2};
    for (int x : us) std::cout 
}

std::priority_queue（最大堆）

int main() {
    std::priority_queue pq;
    pq.push(3);
    pq.push(1);
    pq.push(5);
    std::cout 
}

使用 std::greater 的最小堆

#include 
#include 

std::priority_queue, std::greater> minHeap;

时间复杂度

• 插入 / 删除：O(log n)
• 访问顶部元素：O(1)
• 空间：O(n)

适用场景

• 需要第 k 大或第 k 小的元素
• 重复的最大/最小值提取
• 调度与贪心问题