vector

• 序列式容器(按顺序存储，元素可重复)

• 随机访问快$(O(1))$ , 尾部插入/删除快 $(O(1))$, 中间插入/删除慢$(O(n))$

• 核心函数

  • #include <vector>
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4);       // 尾部添加
    vec.pop_back();         // 尾部删除
    vec.size();             // 元素个数
    vec.empty();            // 是否为空
    vec[0];                 // 随机访问（无越界检查）
    vec.at(0);              // 随机访问（有越界检查，抛异常）
    vec.insert(vec.begin()+1, 5); // 插入到指定位置
    vec.erase(vec.begin()+1);     // 删除指定位置元素
    vec.clear();            // 清空
    

set

• 有序唯一集合

• 元素自动排序(默认升序) ， 无重复元素，查找/插入/删除 $O(logn)$ , 不支持随机访问

• 适用于有序且唯一的结合（去重+排序）

• 核心函数

  • #include <set>
    std::set<int> s = {3, 1, 2}; // 自动排序为 {1,2,3}
    s.insert(4);               // 插入
    s.erase(2);                // 删除指定值
    auto it = s.find(3);       // 查找（返回迭代器，未找到则为 s.end()）
    if (it != s.end()) { /* 找到 */ }
    s.count(1);                // 统计元素个数（0或1）
    

unordered_set

• 无序唯一集合
• 基于哈希表，元素无序，查找/插入/删除 平均 $O(1)$, 最坏 $O(n)$ ,元素唯一
• 常用场景：快速查找/去重（无需排序，比 set 高效）

multiset

• 有序可重复集合
• 与 $set$ 类似，但允许重复元素， cout() 可返回大于 $1$ 的值
• 适用于有序且可重复的集合（如统计元素出现次数）

map

• 键值对，键唯一且有序

• 键值对(key - value) , 键自动排序（默认升序），键唯一，查找/插入/删除 $O(logn)$

• 适用于需要键值且键有序的场景（如字典、配置表）

• 核心函数

  • #include <map>
    std::map<int, std::string> mp = {{1, "a"}, {2, "b"}};
    mp[3] = "c";               // 插入/修改键值对
    mp.insert({4, "d"});       // 插入（键存在则不修改）
    mp.erase(2);               // 删除指定键
    auto it = mp.find(1);      // 查找键
    if (it != mp.end()) {
        std::cout << it->second << std::endl; // 输出 "a"
    }
    mp.count(1);               // 统计键的个数（0或1）
    

unordered_map

• 无序键值对，键唯一
• 基于哈希表，键值对无需，查找/插入/删除平均 $O(1)$, 比 map 更高效（无需排序）
• 适用于高频键值查找（如缓存，哈希表）

priority_queue

• 优先队列，默认大顶堆（最大值优先）

• 核心函数

  • #include <queue>
    std::priority_queue<int> pq; // 大顶堆
    pq.push(3); pq.push(1); pq.push(2); // 堆顶为3
    pq.top();    // 访问堆顶（3）
    pq.pop();    // 弹出堆顶（3）
    // 小顶堆写法
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
    

sort

• 排序（默认升序，可自定义比较函数）

• 核心函数

  • std::sort(vec.begin(), vec.end()); // 升序
    std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
    
    bool cmp(int a,int b){
        return abs(a) < abs(b); 
    }
    
    // 自定义排序（按绝对值）
    std::sort(vec.begin(), vec.end(), cmp);
    

reverse

• 反转容器

• std::reverse(vec.begin(), vec.end());
  

unique

• 去重（需先排序，仅删除相邻重复元素）

• std::sort(vec.begin(), vec.end());
  auto last = std::unique(vec.begin(), vec.end());
  vec.erase(last, vec.end()); // 真正删除重复元素