STL 是什么：竞赛选手的"军火库"

上一篇我们用数组手撸了栈、队列和链表。实际竞赛里，没人这么干——因为 C++ 标准库 STL 已经把这些结构都实现好了，而且是经过千锤百炼的优化版。你只要 `#include` 一下，就能直接用。

STL = Standard Template Library，标准模板库。它是 C++ 自带的一套"工具包"，里面有各种常用容器和算法。竞赛里 80% 的数据结构需求，STL 都能直接满足。

会用 STL，竞赛代码量直接减半。
本文核心知识点
  • vector动态数组，自动扩容。
  • stack/queue现成的栈和队列。
  • sort一行排序，比手写快十倍。
  • pair把两个数打包成一个。
C++ STL 配图：蓝色渐变背景上一排彩色空方框是 vector，下面一摞白盘子是栈，一排彩色圆圈是队列，一棵绿色小树是树结构，一个玻璃漏斗把彩色小球排序倒进方框，齿轮漂浮
vector、栈、队列、sort：STL 四件套。

vector：会自动扩容的动态数组

普通数组大小固定，开小了不够用，开大了浪费内存。vector 解决了这个问题：你只管 `push_back` 加元素，它自己会扩容。

#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(3);
    v.push_back(7);
    v.push_back(1);
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

常用操作：`push_back` 末尾加、`pop_back` 末尾删、`size()` 长度、`v[i]` 访问第 i 个元素、`v.clear()` 清空。

竞赛里 vector 几乎替代了普通数组。只有需要开很大数组（超过 100 万）时，才用全局数组，因为 vector 在函数内开大数组会栈溢出。

stack 与 queue：直接调包不用手写

#include <stack>
#include <queue>

stack<int> st;
st.push(10);
st.push(20);
cout << st.top() << endl;   // 输出 20
st.pop();

queue<int> q;
q.push(1);
q.push(2);
cout << q.front() << endl;  // 输出 1
q.pop();

对比上一篇手写的版本，STL 版只有三五行代码，而且内部实现经过优化，不会出现数组越界、指针错误。竞赛里直接用就好。

sort：一行代码排好一万个数

上一篇写冒泡排序写了 8 行，而且慢。STL 的 sort 函数一行搞定，而且是 O(n log n) 的快速排序，比冒泡快几十倍。

#include <algorithm>
#include <vector>

int main() {
    vector<int> v = {5, 2, 9, 1, 5, 6};
    sort(v.begin(), v.end());
    // 现在 v 是 {1, 2, 5, 5, 6, 9}
    return 0;
}

默认从小到大排。想从大到小排？加一句：

sort(v.begin(), v.end(), greater<int>());

10 万个数 sort 只要千分之一秒。这就是为什么竞赛里没人手写排序。

pair 与自定义排序：让 sort 按规则排

竞赛里经常要排"有两个关键字"的数据：比如按分数从高到低排，分数相同按学号从小到大排。这时候用 pair。

#include <utility>

pair<int,int> students[105];
// first 存分数, second 存学号
students[0] = {95, 1001};
students[1] = {88, 1002};
students[2] = {95, 1003};

sort(students, students + 3);

pair 默认先按 first 排，first 相同再按 second 排。正好满足"分数高在前，同分学号小在前"。如果要分数从高到低，就存 `-分数`，或者写一个自定义比较函数。

本节用到的核心结构
  • vector动态数组。
  • sort一行排序。
  • pair两个关键字打包。
  • greater降序排列。