C++ STL 常用容器核心用法与性能解析

排序规则

默认按字典序比较：先比较 first，若相同则比较 second。对于嵌套结构如 pair<int, pair<int, int>>，同样遵循此规则。

String：字符串封装

C++ 的 string 类封装了字符数组，提供了丰富的操作方法。

• size() / length(): 获取长度。
• substr(pos, len): 截取子串。
• c_str(): 获取 C 风格字符串指针。
• clear(), empty(): 基础状态检查。

线性结构：Queue, Stack, Deque

Queue & Stack

队列遵循 FIFO（先进先出），栈遵循 LIFO（后进先出）。两者接口相似，但语义不同。

#include <queue>
#include <stack>

std::queue<int> q;
q.push(1);      // 入队
int front = q.front();
q.pop();        // 出队

std::stack<int> s;
s.push(1);
int top = s.top();
s.pop();

Deque：双端队列

deque 允许在头部和尾部高效插入删除，功能类似增强版 vector。虽然灵活性高，但在某些极端性能要求下，由于内存管理开销，可能不如 vector 紧凑。

Priority Queue：优先队列

优先队列基于堆实现，默认是大根堆（最大值优先）。

构造小根堆

若要实现最小值优先，需指定比较函数：

#include <queue>
#include <functional>

// 定义小根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(5);
pq.push(1);
// top() 返回 1

或者在插入前取负值（仅适用于数值类型）。

Set & Map：有序关联容器

set 和 map 基于红黑树实现，所有操作平均时间复杂度为 O(log n)。

• insert(): 插入元素。
• find(): 查找元素。
• count(): 统计出现次数。
• erase(): 删除元素。
• lower_bound(x) / upper_bound(x): 二分查找边界迭代器。

multiset 和 multimap 允许重复键值。注意 multimap 不支持 [] 运算符直接赋值。

#include <set>
#include <map>

std::set<int> s;
s.insert(10);
auto it = s.lower_bound(5); // 指向第一个 >= 5 的元素

Unordered 系列：哈希表

unordered_set, unordered_map 等基于哈希表实现。

• 优势: 增删改查平均复杂度为 O(1)。
• 劣势: 无序，不支持 lower_bound 等二分操作，迭代器不支持自增/自减遍历顺序。

适用于对顺序无要求且追求极致查询速度的场景。

Bitset：位运算优化

bitset 用于压缩存储布尔值，支持位运算。

#include <bitset>

std::bitset<1000> b;
b.set(0);       // 第 0 位设为 1
b.flip();       // 全部取反
b.count();      // 统计 1 的个数

掌握这些容器的特性与性能差异，能帮助你在算法设计与工程实践中做出更优选择。根据数据规模、访问模式及是否需要排序，灵活选用合适的容器是编写高效 C++ 代码的关键。