标准模板库核心组件
STL（Standard Template Library）是C++标准库的重要组成部分，提供了通用的数据结构和算法。
存储元素线性序列的容器
| 容器 | 特点 | 访问 | 插入/删除 | 适用场景 |
|---|---|---|---|---|
| vector | 动态数组 | O(1) | O(n) | 随机访问频繁 |
| deque | 双端队列 | O(1) | O(1) | 两端操作频繁 |
| list | 双向链表 | O(n) | O(1) | 中间插入删除频繁 |
#include <vector>
using namespace std;
int main() {
// 创建vector
vector v;
vector v2(10); // 大小为10，初始值为0
vector v3(10, 5); // 大小为10，初始值为5
vector v4 = {1, 2, 3, 4, 5};
// 添加元素
v.push_back(10);
v.push_back(20);
v.push_back(30);
// 访问元素
cout << v[0] << endl; // 10
cout << v.at(1) << endl; // 20（带边界检查）
cout << v.front() << endl; // 第一个元素
cout << v.back() << endl; // 最后一个元素
// 大小操作
cout << v.size() << endl; // 3
cout << v.empty() << endl; // false
v.resize(5); // 调整大小
// 删除元素
v.pop_back(); // 删除最后一个
v.erase(v.begin() + 1); // 删除第二个元素
v.clear(); // 清空所有元素
// 遍历
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
// 使用迭代器
for (vector::iterator it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
// C++11 范围for循环
for (int x : v) {
cout << x << " ";
}
return 0;
}
#include <deque>
using namespace std;
int main() {
deque dq;
// 两端操作
dq.push_back(1); // 后端插入
dq.push_front(2); // 前端插入
dq.push_back(3);
dq.push_front(4);
// dq: 4 2 1 3
cout << dq.front() << endl; // 4
cout << dq.back() << endl; // 3
// 两端删除
dq.pop_front(); // 删除前端
dq.pop_back(); // 删除后端
// dq: 2 1
return 0;
}
#include <list>
using namespace std;
int main() {
list lst = {1, 2, 3, 4, 5};
// 任意位置插入
auto it = lst.begin();
advance(it, 2); // 移动到第三个位置
lst.insert(it, 99); // 在位置2插入99
// 任意位置删除
it = lst.begin();
advance(it, 3);
lst.erase(it);
// 拼接列表
list lst2 = {6, 7, 8};
lst.splice(lst.end(), lst2); // 将lst2拼接到lst末尾
return 0;
}
迭代器是访问容器元素的通用接口，类似指针。
| 迭代器类型 | 支持的操作 |
|---|---|
| 输入迭代器 | ++、*、==、!= |
| 输出迭代器 | ++、* |
| 前向迭代器 | 输入迭代器 + 多次遍历 |
| 双向迭代器 | 前向迭代器 + -- |
| 随机访问迭代器 | 双向迭代器 + []、+、- |
vector v = {1, 2, 3, 4, 5};
// begin() 和 end()
vector::iterator it = v.begin(); // 指向第一个元素
vector::iterator end = v.end(); // 指向最后一个元素之后
// 解引用
cout << *it << endl; // 1
// 前进
it++;
cout << *it << endl; // 2
// 后退
it--;
cout << *it << endl; // 1
// 随机访问
cout << *(it + 2) << endl; // 3
// 距离
int distance = end - it; // 5
// rbegin() 和 rend() (反向迭代器)
vector::reverse_iterator rit = v.rbegin();
cout << *rit << endl; // 5
基于序列容器的简化接口
| 适配器 | 底层容器 | 特点 |
|---|---|---|
| stack | deque | LIFO（后进先出） |
| queue | deque | FIFO（先进先出） |
| priority_queue | vector | 优先级队列 |
#include <stack>
#include <queue>
int main() {
// 栈 (Stack)
stack s;
s.push(1);
s.push(2);
cout << s.top() << endl; // 2
s.pop();
// 队列 (Queue)
queue q;
q.push(1);
q.push(2);
cout << q.front() << endl; // 1
cout << q.back() << endl; // 2
q.pop();
// 优先队列 (Priority Queue)
priority_queue pq; // 大顶堆
pq.push(3);
pq.push(1);
pq.push(4);
cout << pq.top() << endl; // 4
// 小顶堆
priority_queue, greater> min_pq;
min_pq.push(3);
min_pq.push(1);
cout << min_pq.top() << endl; // 1
return 0;
}