【数据结构与算法】C++ STL容器完整API参考

C++ STL容器完整API参考

STL容器全览图

1
2
3
4
5
6
容器分类：
├─ 顺序容器：vector, deque, list
├─ 关联容器：map, set, multimap, multiset
├─ 无序容器：unordered_map, unordered_set
├─ 容器适配器：stack, queue, priority_queue
└─ 特殊容器：array, bitset

1. Vector（向量/动态数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <vector>
vector<int> v;

// 基础操作
v.push_back(x);              // 末尾添加
v.pop_back();                // 末尾删除
v.insert(v.begin() + i, x);  // 位置i插入
v.erase(v.begin() + i);      // 删除位置i
v.clear();                   // 清空

// 访问
v[i];                        // 下标访问（无边界检查）
v.at(i);                     // 下标访问（有边界检查）
v.front();                   // 首元素
v.back();                    // 末元素

// 查询
v.size();                    // 长度
v.empty();                   // 是否为空
v.capacity();                // 容量

// 迭代器
v.begin(), v.end();          // 首尾迭代器
v.rbegin(), v.rend();        // 反向迭代器

// 其他
v.resize(n);                 // 改变大小
v.reserve(n);                // 预留空间
v.swap(v2);                  // 交换

2. Deque（双向队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <deque>
deque<int> dq;

// 特殊之处：支持两端快速操作
dq.push_front(x);            // 前端添加
dq.push_back(x);             // 后端添加
dq.pop_front();              // 前端删除
dq.pop_back();               // 后端删除

dq[i];                       // 随机访问
dq.front(), dq.back();       // 访问两端

// 其他操作同vector

3. List（链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <list>
list<int> l;

// 添加删除
l.push_back(x);              // 末尾添加
l.push_front(x);             // 前端添加
l.pop_back();                // 末尾删除
l.pop_front();               // 前端删除
l.insert(iter, x);           // 指定位置插入
l.erase(iter);               // 删除指定位置

// 访问
l.front(), l.back();         // 只能访问两端，不支持v[i]

// 查询
l.size();
l.empty();

// 链表特有操作
l.reverse();                 // 反转
l.sort();                    // 排序
l.unique();                  // 去重（需要先排序）
l.remove(x);                 // 删除所有值为x的元素
l.merge(l2);                 // 合并两个链表

// 迭代器
l.begin(), l.end();

4. Map（映射/字典）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <map>
map<string, int> m;

// 基础操作
m[key] = value;              // 插入/更新
m.insert({key, value});      // 插入（不覆盖）
m.erase(key);                // 删除
m.clear();                   // 清空

// 查询
m[key];                      // 访问（不存在则创建）
m.at(key);                   // 访问（不存在抛异常）
m.count(key);                // 是否存在（0或1）
m.find(key);                 // 返回迭代器（end()表示不存在）

// 遍历
for(auto& [k, v] : m) { }    // C++17 结构化绑定
for(auto& p : m) {           // p是pair<const Key, Value>
    p.first;  // 键
    p.second; // 值
}

// 大小
m.size();
m.empty();

// 范围查询
m.lower_bound(key);          // >= key的第一个位置
m.upper_bound(key);          // > key的第一个位置
m.equal_range(key);          // 返回{lower_bound, upper_bound}

5. Set（集合）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <set>
set<int> s;

// 基础操作
s.insert(x);                 // 添加
s.erase(x);                  // 删除
s.clear();                   // 清空

// 查询
s.count(x);                  // 是否存在（0或1）
s.find(x);                   // 返回迭代器

// 遍历（自动排序）
for(auto x : s) { }
s.begin(), s.end();

// 范围查询
s.lower_bound(x);
s.upper_bound(x);
s.equal_range(x);

// 大小
s.size();
s.empty();

6. Multimap/Multiset（多重映射/多重集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <map>
#include <set>

multimap<int, string> mm;    // 允许重复键
multiset<int> ms;            // 允许重复值

// 基础操作同map/set，但：
mm.insert({key, value});     // 直接插入（允许重复）
mm.erase(key);               // 删除所有相同键的项

// 查询重复元素
auto range = mm.equal_range(key);
for(auto it = range.first; it != range.second; ++it) {
    cout << it->second << endl;
}

// 计数
mm.count(key);               // 返回该键出现的次数

7. Unordered_map/Unordered_set（哈希表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <unordered_map>
#include <unordered_set>

unordered_map<int, string> um;
unordered_set<int> us;

// 操作同map/set，但：
// ✓ 平均查找O(1)，最坏O(n)
// ✗ 不排序，无序遍历

um[key] = value;
um.count(key);
um.erase(key);

// 其他操作基本相同

8. Stack（栈）

1
2
3
4
5
6
7
8
9
10
11
#include <stack>
stack<int> st;

// 操作
st.push(x);                  // 入栈
st.pop();                    // 出栈（无返回值）
st.top();                    // 栈顶元素
st.empty();                  // 是否为空
st.size();                   // 大小

// 注意：pop()无返回值，需要先top()再pop()

9. Queue（队列）

1
2
3
4
5
6
7
8
9
10
#include <queue>
queue<int> q;

// 操作
q.push(x);                   // 入队
q.pop();                     // 出队（无返回值）
q.front();                   // 队首元素
q.back();                    // 队末元素
q.empty();
q.size();

10. Priority_queue（优先队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>

// 最大堆（默认）
priority_queue<int> pq;

// 最小堆
priority_queue<int, vector<int>, greater<int>> pq_min;

// 自定义优先级
struct Node {
    int val, priority;
    bool operator<(const Node& other) const {
        return priority < other.priority;  // 大堆
    }
};
priority_queue<Node> pq_custom;

// 操作
pq.push(x);                  // 添加
pq.pop();                    // 删除顶部
pq.top();                    // 查看顶部
pq.empty();
pq.size();

11. Array（静态数组）

1
2
3
4
5
6
7
8
9
10
#include <array>
array<int, 5> arr;           // 大小固定为5

arr[i];                      // 访问
arr.at(i);                   // 越界检查访问
arr.size();                  // 总是5
arr.fill(x);                 // 填充所有元素

// 迭代器
arr.begin(), arr.end();

12. Bitset（位集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bitset>
bitset<10> bs;               // 10位的位集

// 操作
bs[i];                       // 访问第i位
bs.set(i);                   // 第i位设为1
bs.reset(i);                 // 第i位设为0
bs.flip(i);                   // 第i位翻转
bs.count();                  // 1的个数
bs.size();                   // 总位数
bs.any();                    // 是否有1
bs.none();                   // 是否全是0

// 整体操作
bs.set();                    // 全设为1
bs.reset();                  // 全设为0
bs.flip();                   // 全部翻转

13. Pair（对）

1
2
3
4
5
6
7
8
9
#include <utility>

pair<int, string> p = {10, "hello"};
p.first;                     // 第一个元素
p.second;                    // 第二个元素

// 创建
auto p2 = make_pair(5, "world");
pair<int, string> p3 = {1, "test"};

常用迭代器操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 迭代器类型
auto it = v.begin();         // 前向迭代器
auto rit = v.rbegin();       // 反向迭代器

// 迭代器运算
++it, --it;                  // 前进/后退
it + 5;                      // 前进5个（仅随机访问）
it - rit;                    // 距离（仅随机访问）
*it;                         // 解引用
it->member;                  // 成员访问

// 转换
distance(it1, it2);          // 两迭代器间距离
advance(it, n);              // 迭代器移动n步

快速参考表

容器查找插入删除排序随机访问
vectorO(n)O(1)/O(n)O(n)✓✓
dequeO(n)O(1)O(1)✓✓
listO(n)O(1)O(1)✓✗
setO(log n)O(log n)O(log n)自动✗
mapO(log n)O(log n)O(log n)自动✗
unordered_setO(1)O(1)O(1)✗✗
unordered_mapO(1)O(1)O(1)✗✗

常见用途总结

  • vector：默认选择，需要随机访问
  • deque：需要两端快速操作
  • list：需要频繁的中间插入/删除
  • set/map：需要排序和快速查找
  • unordered_set/map：需要O(1)平均查找，不需要排序
  • stack/queue：特定的LIFO/FIFO需求
  • priority_queue：需要堆（优先级队列）