STL（Standard Template Library）是C++的核心优势，理解其架构对竞赛编程至关重要。
一、STL的六大组件
STL主要包含以下六大组件：
在竞赛中，我们主要关注前三个：容器、迭代器和算法。
二、容器详解
2.1 序列容器
vector（动态数组）
#include <vector>
vector<int> arr;
// 基本操作
arr.push_back(10); // 在末尾添加元素
arr.pop_back(); // 删除末尾元素
arr.size(); // 获取元素个数
arr[0]; // 访问第0个元素
arr.empty(); // 判断是否为空
arr.clear(); // 清空所有元素
// 实战例子：读入n个数字
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
string（字符串）
#include <string>
string s = "hello";
// 基本操作
s += " world"; // 字符串连接
s.length(); // 获取长度
s.substr(1, 3); // 获取子串，从位置1开始，长度为3
s.find("lo"); // 查找子串位置
// 实战技巧：字符串比较
string a = "abc", b = "abd";
if (a < b) { // 字典序比较
cout << "a < b" << endl;
}
2.2 关联容器
set（集合）
#include <set>
set<int> s;
// 基本操作
s.insert(10); // 插入元素
s.erase(10); // 删除元素
s.count(10); // 统计元素个数（0或1）
s.find(10); // 查找元素
s.size(); // 获取元素个数
// 实战例子：去重
vector<int> arr = {1, 2, 2, 3, 3, 3};
set<int> unique_elements;
for (int x : arr) {
unique_elements.insert(x);
}
// unique_elements现在包含{1, 2, 3}
map（映射）
#include <map>
map<string, int> mp;
// 基本操作
mp["apple"] = 5; // 设置键值对
mp["banana"] = 3;
cout << mp["apple"]; // 访问值
mp.count("apple"); // 检查键是否存在
// 实战例子：统计单词出现次数
vector<string> words = {"apple", "banana", "apple", "cherry", "banana"};
map<string, int> count;
for (auto word : words) {
count[word]++;
}
// count["apple"] = 2, count["banana"] = 2, count["cherry"] = 1
1.map是一种关联容器，储存一组键值对<key,value>，每个键都是唯一的。
2.插入，删除和查找操作的时间复杂度为O(logn)。
3.定义和结构如下：
template<class Key,class T,class Compare = less<Key>,class Allocator = allocator<pair<const Key,T>>>
class map;
Key : 表示存储在map中的键(key)的类型。
T：表示存储在map中的值(value)的类型。
操作
1.插入元素
map<int,string> mp;
// 1. insert 插入
mp.insert({1, "Apple"});
mp.insert(make_pair(2, "Banana"));
mp.insert(pair<int, string>(3, "Cherry"));
// 2. 下标插入（若键不存在则创建）
mp[4] = "Orange"; // 若键4不存在，会先创建默认值，再赋值
mp[5]; // 仅创建键5，值为空字符串（对string）
// 3. emplace 直接构造
mp.emplace(6, "Grape"); // 避免临时对象
2.删除元素
map<int,string> mp = {{1,"A"},{2,"B"},{3,"C"}};
// 1. erase 按键删除
mp.erase(2); // 删除键为2的元素
// 2. 按迭代器删除
auto it = mp.find(3);
if (it != mp.end()) {
mp.erase(it);
}
// 3. 删除范围
mp.erase(mp.begin(), mp.find(3)); // 删除[begin, 键3)区间
3.查找与访问
map<int, string> mp = {{1, "Alice"}, {2, "Bob"}};
// 1. find 查找迭代器
auto it = mp.find(1);
if (it != mp.end()) {
cout << it->first << ": " << it->second << endl;
}
// 2. count 检查键是否存在（返回0或1）
if (mp.count(2) > 0) {
cout << "键2存在" << endl;
}
// 3. 下标访问（若键不存在会自动插入！）
string val = mp[3]; // 键3不存在时会插入{3, ""}
cout << val << endl;
// 4. at 访问（会检查，键不存在时抛出异常）
try {
string safe_val = mp.at(4); // 若键4不存在抛出 out_of_range
} catch (const out_of_range& e) {
cout << e.what() << endl;
}
4。容量查询
map<int, int> mp = {{1, 10}, {2, 20}};
mp.empty(); // 是否为空
mp.size(); // 元素个数
mp.max_size(); // 可容纳的最大元素数（理论值）
2.3 容器适配器
stack（栈）
#include <stack>
stack<int> st;
st.push(10); // 入栈
st.push(20);
cout << st.top(); // 访问栈顶元素（20）
st.pop(); // 出栈
st.empty(); // 判断是否为空
// 实战例子：括号匹配
string s = "((()))";
stack<char> st;
bool valid = true;
for (char c : s) {
if (c == '(') {
st.push(c);
} else if (c == ')') {
if (st.empty()) {
valid = false;
break;
}
st.pop();
}
}
if (!st.empty()) valid = false;
queue（队列）
#include <queue>
queue<int> q;
q.push(10); // 入队
q.push(20);
cout << q.front(); // 访问队首元素（10）
q.pop(); // 出队
q.empty(); // 判断是否为空
// 实战例子：BFS遍历
queue<int> q;
vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
// 处理current节点
for (int next : graph[current]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
三、迭代器详解
迭代器是STL的核心概念，它提供了统一的方式来访问容器元素，你可以理解为指针。
3.1 迭代器基本用法
vector<int> arr = {1, 2, 3, 4, 5};
// 获取迭代器
auto begin_it = arr.begin(); // 指向第一个元素
auto end_it = arr.end(); // 指向最后一个元素的下一位置
// 使用迭代器遍历
for (auto it = arr.begin(); it != arr.end(); it++) {
cout << *it << " "; // *it获取迭代器指向的值
}
3.2 不同容器的迭代器
// vector的迭代器
vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); it++) {
cout << *it << " ";
}
// set的迭代器（自动排序）
set<int> s = {3, 1, 2};
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << " "; // 输出：1 2 3
}
// map的迭代器
map<string, int> mp = {{"apple", 5}, {"banana", 3}};
for (auto it = mp.begin(); it != mp.end(); it++) {
cout << it->first << ": " << it->second << endl;
// it->first是键，it->second是值
}
四、算法详解
STL提供了丰富的算法，让我们能够快速实现常见操作。
4.1 排序算法
#include <algorithm>
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
// 升序排序
sort(arr.begin(), arr.end());
// 降序排序
sort(arr.begin(), arr.end(), greater<int>());
// 自定义比较函数
struct Point {
int x, y;
};
vector<Point> points = {{1, 3}, {2, 1}, {0, 5}};
sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
return a.x + a.y < b.x + b.y; // 按坐标和排序
});
4.2 查找算法
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 二分查找（数组必须有序）
bool found = binary_search(arr.begin(), arr.end(), 5);
// 查找第一个大于等于x的位置
auto it = lower_bound(arr.begin(), arr.end(), 5);
int pos = it – arr.begin(); // 位置索引
// 查找第一个大于x的位置
auto it2 = upper_bound(arr.begin(), arr.end(), 5);
// 实战例子：查找某个值的出现次数
int count = upper_bound(arr.begin(), arr.end(), 5) – lower_bound(arr.begin(), arr.end(), 5);
4.3 其他常用算法
vector<int> arr = {1, 2, 3, 4, 5};
// 求最大最小值
auto max_it = max_element(arr.begin(), arr.end());
auto min_it = min_element(arr.begin(), arr.end());
cout << "Max: " << *max_it << ", Min: " << *min_it << endl;
// 反转数组
reverse(arr.begin(), arr.end());
// 生成下一个排列
vector<int> perm = {1, 2, 3};
do {
for (int x : perm) cout << x;
cout << " ";
} while (next_permutation(perm.begin(), perm.end()));
// 输出所有排列：123 132 213 231 312 321
// 去重（需要先排序）
vector<int> arr2 = {1, 1, 2, 2, 3, 3};
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
// arr2现在是{1, 2, 3}
