C++ STL 常用容器使用详解

常用函数

• size(), empty(), clear()
• front()/back()
• push_back()/pop_back()
• push_front()/pop_front()
• begin()/end()
• []

set, multiset

基于平衡二叉树（红黑树），动态维护有序序列。set 内不能包含重复元素，multiset 允许重复。所有操作时间复杂度为 O(log n)。

常用函数

• insert(): 插入一个数
• find(): 查找一个数
• count(): 返回某一个数的个数
• erase(): 删除元素（支持输入数值或迭代器）
• lower_bound()/upper_bound(): 返回大于等于/大于 x 的最小的数的迭代器
• ++/--: 返回前驱和后继

map, multimap

基于平衡二叉树，键值对映射。multimap 不支持 [] 操作符直接赋值。

常用函数

• insert(): 插入 pair
• erase(): 删除（参数为 pair 或迭代器）
• find(): 查找
• lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap

基于哈希表实现。增删改查的时间复杂度为 O(1)。不支持 lower_bound/upper_bound 及迭代器的 ++/-- 操作，因为是无序的。

常用函数速查表

// Vector
vector<int> v;
v.size(); v.empty(); v.clear();
v.front(); v.back();
v.push_back(x); v.pop_back();
v.begin(); v.end();
v[i];

// Pair
pair<int, int> p;
p.first; p.second;

// String
s.size(); s.length(); s.substr(pos, len); s.c_str();

// Queue
q.push(x); q.pop(); q.front(); q.back();

// Priority Queue
priority_queue<int> pq; // 大根堆
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
pq.top(); pq.pop();

// Stack
s.push(x); s.pop(); s.top();

// Deque
d.push_front(x); d.push_back(x);

// Set / Map
st.insert(x); st.find(x); st.erase(x);
st.lower_bound(x); st.upper_bound(x);

// Unordered
us.insert(x); us.count(x);