普及组常用 STL

STL 简介

在 OI 信息学竞赛中，STL（Standard Template Library，标准模板库）是一个强大且实用的工具，能显著提升编程效率。

STL 是 C++ 标准库的重要组成部分，由惠普实验室开发，于 1998 年被纳入 C++ 标准。它运用模板技术，实现了数据结构和算法的泛型化，使代码具备高度的可复用性和灵活性。

STL 主要包含容器、算法和迭代器三大部分。

• 容器：用于存储和管理数据，提供了多种数据结构。
• 算法：提供了一系列通用算法，如排序、查找、替换、合并等。这些算法可以与各种容器配合使用，无需考虑容器的具体类型，大大提高了代码的编写效率。
• 迭代器：作为容器和算法之间的桥梁，迭代器提供了一种统一的方式来访问容器中的元素。它类似于指针，但具有更高的抽象性和安全性。通过迭代器，算法可以在不了解容器内部实现的情况下对容器元素进行操作。

在竞赛中，时间紧迫，使用 STL 可以快速实现常见的数据结构和算法，减少代码编写时间，让选手能够将更多精力放在问题的解决思路上。

vector

简介与概述、功能介绍

vector 是 C++ 标准模板库（STL）里的动态数组容器。和普通数组不同，vector 能够在运行时动态调整大小。它支持随机访问，意味着可以像操作普通数组那样通过下标快速访问元素。同时，还能方便地在末尾添加或删除元素。

适用场景

• 数据数量不确定时：当你不清楚要存储的数据量，或者数据量会动态变化，vector 能根据需求自动调整大小。
• 需要随机访问元素：若要频繁地通过下标访问元素，vector 提供了高效的随机访问能力。
• 替代普通数组：可以避免手动管理内存，减少因内存管理不当引发的错误。

原理和使用

vector 内部借助动态数组来实现。当元素数量超出当前容量时，会重新分配更大的内存空间，再把原有的元素复制到新空间里。常用操作及其时间复杂度如下：

• push_back()：在末尾添加元素，平均时间复杂度为 $O(1)$，但在需要重新分配内存时为 $O(n)$。
• pop_back()：删除末尾元素，时间复杂度为 $O(1)$。
• size()：获取元素数量，时间复杂度为 $O(1)$。
• [] 或 at()：随机访问元素，时间复杂度为 $O(1)$。

经典例题及代码实现

题面描述

输入 $n$ 个整数，将它们存储在 vector 中，然后逆序输出这些整数。

输入输出样例

• 输入：

5
1 2 3 4 5

第一行的 5 表示整数的个数，第二行是这 5 个整数。

• 输出：

5 4 3 2 1

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n; // 读入整数的个数
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // 读入每个整数
        v.push_back(x);
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

总结

vector 是 OI 竞赛中非常实用的容器，它结合了数组的随机访问特性和动态调整大小的能力。在数据量不确定或者需要随机访问元素的场景下，vector 是很好的选择。不过，要注意 push_back() 可能导致的内存重新分配问题，这会带来额外的时间开销。

stack

简介与概述、功能介绍

stack 是遵循后进先出（LIFO，Last In First Out）原则的数据结构。它只允许在栈顶进行插入（入栈，push）和删除（出栈，pop）操作，还能查看栈顶元素（top）。

适用场景

• 括号匹配问题：通过栈来检查括号是否成对出现，遇到左括号入栈，遇到右括号时检查栈顶元素是否为对应的左括号。
• 递归模拟：将递归过程转化为栈的操作，避免递归深度过大导致栈溢出。
• 表达式求值：在处理后缀表达式求值等问题时发挥作用。

原理和使用

stack 基于其他容器（如 vector、deque 等）实现，默认使用 deque。它只暴露栈顶元素，通过 push() 将元素压入栈顶，pop() 移除栈顶元素，top() 获取栈顶元素。这些操作的时间复杂度均为 $O(1)$。

经典例题及代码实现

题面描述

给定一个只包含 ( 和 ) 的字符串，判断括号是否匹配。

输入输出样例

• 输入：

(()())

• 输出：

Yes

代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s; // 读入字符串
    stack<char> st;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            st.push(s[i]);
        } else {
            if (st.empty()) {
                cout << "No" << endl;
                return 0;
            }
            st.pop();
        }
    }
    if (st.empty()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

总结

stack 的后进先出特性使其在处理具有嵌套或逆序逻辑的问题时非常高效。在括号匹配、递归模拟等场景中，stack 是不可或缺的工具。使用时要注意栈为空的情况，避免出现访问空栈的错误。

queue

简介与概述、功能介绍

queue 是遵循先进先出（FIFO，First In First Out）原则的数据结构。元素从队列尾部插入（入队，push），从队列头部删除（出队，pop），还能查看队头元素（front）和队尾元素（back）。

适用场景

• 广度优先搜索（BFS）：在 BFS 算法中，队列用于存储待访问的节点，保证节点按照层次顺序被访问。
• 任务调度：按照任务到达的顺序依次处理任务，例如操作系统中的任务队列。

原理和使用

queue 通常基于 deque 实现。通过 push() 在队尾插入元素，pop() 删除队头元素，front() 获取队头元素，back() 获取队尾元素。这些操作的时间复杂度均为 $O(1)$。

经典例题及代码实现

题面描述

在一个 $n\times m$ 的迷宫中，从起点 $(x_1, y_1)$ 走到终点 $(x_2, y_2)$，每次只能向上下左右四个方向移动一步，求最短路径长度。迷宫中 0 表示可以通行，1 表示障碍物。

输入输出样例

• 输入：

3 3
0 0 0
0 1 0
0 0 0
1 1
3 3

第一行的 3 和 3 表示迷宫的行数和列数，接下来三行是迷宫的布局，最后两行分别是起点和终点的坐标。

• 输出：

4

代码实现

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 105;
int n, m;
int g[MAXN][MAXN];
int vis[MAXN][MAXN];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct Node {
    int x, y, step;
};

int bfs(int x1, int y1, int x2, int y2) {
    queue<Node> q;
    q.push({x1, y1, 0});
    vis[x1][y1] = 1;
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        if (cur.x == x2 && cur.y == y2) {
            return cur.step;
        }
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) {
                q.push({nx, ny, cur.step + 1});
                vis[nx][ny] = 1;
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m; // 读入迷宫的行数和列数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j]; // 读入迷宫的布局
        }
    }
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2; // 读入起点和终点的坐标
    int res = bfs(x1, y1, x2, y2);
    cout << res << endl;
    return 0;
}

总结

queue 的先进先出特性使其在广度优先搜索和任务调度等场景中非常有用。在 BFS 中，队列确保了节点按照层次顺序被访问，从而能找到最短路径。使用时要注意队列的初始化和判空操作。

list

简介与概述、功能介绍

list 是一种双向链表容器，它支持在任意位置高效地插入和删除元素。与 vector 不同，list 不支持随机访问，访问元素需要从头或尾开始遍历。

适用场景

• 频繁插入和删除操作：当需要在容器中间频繁插入或删除元素时，list 的效率比 vector 高，因为链表的插入和删除操作只需要修改指针。
• 实现双向链表相关算法：可以利用 list 的双向链表特性实现一些特定的算法。

原理和使用

list 使用双向链表实现，每个节点包含指向前一个节点和后一个节点的指针。插入和删除操作只需要修改指针，时间复杂度为 $O(1)$。但访问元素需要从头或尾开始遍历，时间复杂度为 $O(n)$。常用操作有 push_back()（在末尾插入元素）、push_front()（在头部插入元素）、erase()（删除指定位置的元素）等。

经典例题及代码实现

题面描述

有一个整数序列，需要在指定位置插入一个新的整数，然后输出序列。

输入输出样例

• 输入：

5
1 2 3 4 5
3 10

第一行的 5 表示序列的长度，第二行是序列的元素，第三行的 3 表示插入位置，10 表示要插入的整数。

• 输出：

1 2 10 3 4 5

代码实现

#include <iostream>
#include <list>
using namespace std;

int main() {
    int n;
    cin >> n; // 读入序列的长度
    list<int> l;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // 读入序列的元素
        l.push_back(x);
    }
    int pos, val;
    cin >> pos >> val; // 读入插入位置和要插入的整数
    auto it = l.begin();
    for (int i = 1; i < pos; i++) {
        it++;
    }
    l.insert(it, val);
    for (auto x : l) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

总结

list 在需要频繁进行插入和删除操作的场景中表现出色。但由于不支持随机访问，在需要随机访问元素的场景中效率较低。使用 list 时，要注意迭代器的使用，避免迭代器失效的问题。

priority_queue

简介与概述、功能介绍

priority_queue 是一种优先队列，它会根据元素的优先级对元素进行排序。默认情况下，最大的元素总是位于队列的顶部。可以通过自定义比较函数来改变优先级规则。

适用场景

• 求最大或最小元素：例如在 Dijkstra 算法中，用于选择距离最小的节点。
• 任务调度：根据任务的优先级进行处理，优先级高的任务先被处理。

原理和使用

priority_queue 通常使用堆（如大顶堆或小顶堆）实现。插入元素时，会将元素插入到堆中并调整堆的结构；删除元素时，会删除堆顶元素并重新调整堆。插入和删除操作的时间复杂度均为 $O(log n)$，获取堆顶元素的时间复杂度为 $O(1)$。

经典例题及代码实现

题面描述

给定 $n$ 个整数，每次取出最大的数，将其减 1 后放回队列，重复 $k$ 次，最后输出队列中所有元素的和。

输入输出样例

• 输入：

5 3
3 2 1 4 5

第一行的 5 表示整数的个数，3 表示操作次数，第二行是这 5 个整数。

• 输出：

13

代码实现

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k; // 读入整数的个数和操作次数
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // 读入每个整数
        pq.push(x);
    }
    for (int i = 0; i < k; i++) {
        int top = pq.top();
        pq.pop();
        pq.push(top - 1);
    }
    int sum = 0;
    while (!pq.empty()) {
        sum += pq.top();
        pq.pop();
    }
    cout << sum << endl;
    return 0;
}

总结

priority_queue 在需要动态维护最大或最小元素的场景中非常有用。通过堆的实现，它能高效地完成插入、删除和获取最大（小）元素的操作。使用时要注意默认是大顶堆，如果需要小顶堆，可以自定义比较函数。