STL模板

约 4177 字大约 14 分钟

2025-06-25

常用函数与算法模板：min、max、swap、sort

常用函数与算法模板

在C++信奥赛中，STL（标准模板库）提供的min、max、swap和sort是最常用的工具，它们能大幅简化代码、提高效率。下面详细讲解这些函数的用法及实战模板。

一、`min`与`max`：取最小值与最大值

min与max：取最小值与最大值

min和max用于获取两个或多个元素中的最小值和最大值，定义在<algorithm>头文件中。

1. 基本用法（两个元素）

c++

#include <algorithm>  // 必须包含
#include <iostream>
using namespace std;

int main() {
    int a = 3, b = 5;
    cout << min(a, b) << endl;  // 输出3（最小值）
    cout << max(a, b) << endl;  // 输出5（最大值）

    double c = 2.5, d = 1.8;
    cout << min(c, d) << endl;  // 输出1.8（支持浮点型）

    char e = 'a', f = 'z';
    cout << min(e, f) << endl;  // 输出'a'（字符按ASCII码比较）
    return 0;
}

2. 多个元素的最值（`initializer_list`）

C++11起支持传入初始化列表（用{}包裹）求多个元素的最值：

c++

int main() {
    int m = min({1, 5, 2, 9, 3});  // 多个整数的最小值
    int M = max({1, 5, 2, 9, 3});  // 多个整数的最大值
    cout << m << " " << M;  // 输出1 9
    return 0;
}

3. 自定义比较（结构体/对象）

对结构体或自定义类型，需指定比较规则（通过lambda或函数）：

c++

struct Student {
    string name;
    int score;
};

int main() {
    Student s1 = {"Alice", 92};
    Student s2 = {"Bob", 88};
    
    // 按分数比较，取分数低的学生
    Student minStu = min(s1, s2, 
        [](const Student &a, const Student &b) {
            return a.score < b.score;  // 自定义比较规则
        }
    );
    cout << minStu.name;  // 输出Bob
    return 0;
}

二、`swap`：交换两个元素的值

swap：交换两个元素的值

swap用于交换两个同类型变量的值，定义在<algorithm>中，无需手动实现临时变量。

1. 基本用法

c++

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

int main() {
    int a = 3, b = 5;
    swap(a, b);  // 交换a和b的值
    cout << a << " " << b;  // 输出5 3

    string s1 = "hello", s2 = "world";
    swap(s1, s2);  // 交换字符串
    cout << s1 << " " << s2;  // 输出world hello
    return 0;
}

2. 交换数组元素或结构体

c++

int main() {
    int arr[] = {10, 20};
    swap(arr[0], arr[1]);  // 交换数组元素
    cout << arr[0] << " " << arr[1];  // 20 10

    Student s1 = {"Alice", 92};
    Student s2 = {"Bob", 88};
    swap(s1, s2);  // 交换结构体（成员全部交换）
    return 0;
}

三、`sort`：排序算法（核心）

sort：排序算法（核心）

sort是信奥赛中最常用的排序函数，基于快速排序的优化版本（平均时间复杂度O(n log n)），定义在<algorithm>中。

1. 基本用法（默认升序）

c++

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

int main() {
    // 1. 排序数组
    int arr[] = {3, 1, 4, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + n);  // 排序范围：[首地址, 尾地址)
    for (int x : arr) cout << x << " ";  // 1 1 3 4 5

    // 2. 排序vector
    vector<int> v = {5, 3, 8, 1};
    sort(v.begin(), v.end());  // vector用迭代器指定范围
    for (int x : v) cout << x << " ";  // 1 3 5 8
    return 0;
}

2. 降序排序（自定义比较）

通过greater<类型>()或lambda表达式实现降序：

c++

int main() {
    int arr[] = {3, 1, 4, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 方式1：用greater<int>()
    sort(arr, arr + n, greater<int>());  // 降序
    // 输出：5 4 3 1 1

    // 方式2：用lambda表达式（更灵活）
    sort(arr, arr + n, [](int a, int b) {
        return a > b;  // a > b时a排在前（降序）
    });
    return 0;
}

3. 排序结构体/自定义类型

必须指定比较规则（按结构体成员排序）：

c++

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> students = {
        {"Alice", 92},
        {"Bob", 88},
        {"Charlie", 95}
    };

    // 按分数升序排序（分数低的在前）
    sort(students.begin(), students.end(), 
        [](const Student &a, const Student &b) {
            return a.score < b.score;  // 核心：定义排序规则
        }
    );

    // 输出结果
    for (auto &s : students) {
        cout << s.name << " " << s.score << endl;
    }
    // 输出：
    // Bob 88
    // Alice 92
    // Charlie 95
    return 0;
}

4. 部分排序（指定范围）

可只排序数组的前k个元素或中间一段：

c++

int main() {
    int arr[] = {5, 3, 8, 1, 2, 7};
    int n = 6;

    // 只排序前3个元素（[0,3)）
    sort(arr, arr + 3);
    // 结果：3 5 8 1 2 7

    // 排序中间一段（[2,5)）
    sort(arr + 2, arr + 5);
    // 结果：3 5 1 2 8 7
    return 0;
}

四、信奥赛实战模板

信奥赛实战模板

1. 数组排序模板

c++

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

// 对数组arr[0..n-1]排序
void sortArray(int arr[], int n, bool ascending = true) {
    if (ascending) {
        sort(arr, arr + n);  // 升序
    } else {
        sort(arr, arr + n, greater<int>());  // 降序
    }
}

int main() {
    int arr[] = {3, 1, 4, 1, 5};
    int n = 5;
    sortArray(arr, n, false);  // 降序排序
    for (int x : arr) cout << x << " ";  // 5 4 3 1 1
    return 0;
}

2. 结构体排序模板（按多关键字）

c++

struct Person {
    int age;    // 第一关键字
    int score;  // 第二关键字
};

// 按年龄升序，年龄相同则按分数降序
bool comparePerson(const Person &a, const Person &b) {
    if (a.age != b.age) {
        return a.age < b.age;  // 年龄升序
    } else {
        return a.score > b.score;  // 分数降序
    }
}

int main() {
    Person people[] = {{15, 90}, {16, 85}, {15, 95}};
    int n = 3;
    sort(people, people + n, comparePerson);
    // 输出：(15,95) (15,90) (16,85)
    return 0;
}

3. 查找第k小元素（利用sort）

c++

// 查找数组中第k小的元素（k从1开始）
int findKthSmallest(int arr[], int n, int k) {
    sort(arr, arr + n);  // 升序排序
    return arr[k - 1];   // 第k小元素在索引k-1
}

五、避坑指南

避坑指南

sort的范围是左闭右开：
sort(begin, end)排序的是[begin, end)区间，即包含begin指向的元素，不包含end指向的元素：
c++
```
int arr[5] = {3,1,4,1,5};
sort(arr, arr + 3);  // 只排序前3个元素（索引0,1,2）
```

自定义比较函数的返回值：
比较函数cmp(a,b)返回true表示a应排在b前面，需确保逻辑正确（避免矛盾）：

c++

// 错误：可能导致排序异常
bool badCmp(int a, int b) {
    return a >= b;  // 存在a==b时返回true，违反严格弱序
}

min/max的参数类型需一致：
不能比较不同类型的元素（如int和double需显式转换）：

c++

int a = 3;
double b = 2.5;
// min(a, b);  // 错误：类型不一致
min((double)a, b);  // 正确：转换为同一类型

swap对容器的效率：
swap两个容器（如vector）时，内部仅交换指针，效率极高（无需复制元素）：
c++
```
vector<int> v1(1000000), v2;
swap(v1, v2);  // 瞬间完成，不会复制百万元素
```

重要

实战中需重点掌握sort的自定义排序（尤其是结构体多关键字排序），这是解决复杂排序问题的核心。同时注意函数的参数范围和类型匹配，避免常见错误。
STL的min、max、swap和sort是信奥赛的“利器”，掌握它们能：
- 减少重复代码（无需手动实现排序、交换等逻辑）。
- 保证算法效率（sort的性能接近最优）。
- 提升代码可读性（函数名直观，逻辑清晰）。

栈(stack)、队列(queue)、链表(list)、向量(vector)等容器

容器

在C++信奥赛中，STL（标准模板库）提供的容器是处理数据的核心工具。栈（stack）、队列（queue）、链表（list）、向量（vector）是最常用的四大容器，它们各有特性，适用于不同场景。

一、向量（`vector`）：动态数组（最常用）

向量（vector）：动态数组（最常用）

vector是动态数组，支持随机访问，大小可自动调整，是信奥赛中使用频率最高的容器。其底层是连续内存空间，兼顾数组的高效访问和动态扩展能力。

1. 核心特性

随机访问：通过下标[]或at()访问元素，时间复杂度O(1)。
动态扩容：当元素数量超过当前容量时，自动分配更大的内存（通常是原容量的2倍）。
尾部操作高效：在末尾插入（push_back）或删除（pop_back）元素，时间复杂度O(1)。
中间操作低效：在中间插入/删除元素需移动后续元素，时间复杂度O(n)。

2. 头文件与基本用法

c++

#include <vector>  // 必须包含
#include <iostream>
using namespace std;

int main() {
    // 1. 创建vector（默认空）
    vector<int> v;  // 存储int类型的vector

    // 2. 尾部插入元素（push_back）
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);  // 此时v = [10, 20, 30]

    // 3. 访问元素（下标或at()）
    cout << v[0] << endl;    // 10（不检查越界）
    cout << v.at(1) << endl; // 20（越界时抛出异常）

    // 4. 常用属性
    cout << "大小：" << v.size() << endl;       // 3（元素个数）
    cout << "容量：" << v.capacity() << endl;   // 4（当前可容纳的元素数，可能大于size）
    cout << "是否为空：" << v.empty() << endl;  // 0（false，非空）

    // 5. 尾部删除元素（pop_back）
    v.pop_back();  // 删除最后一个元素，v = [10, 20]

    // 6. 遍历（下标/迭代器/范围for）
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";  // 10 20
    }

    for (auto it = v.begin(); it != v.end(); it++) {  // 迭代器遍历
        cout << *it << " ";  // 10 20
    }

    for (int x : v) {  // 范围for（C++11）
        cout << x << " ";  // 10 20
    }

    return 0;
}

3. 信奥赛应用场景

存储动态大小的数组（如输入数据量未知时）。
需要随机访问元素的场景（如模拟数组、存储坐标等）。
作为其他算法的基础容器（如排序、查找）。

示例：存储并排序未知数量的整数

c++

vector<int> nums;
int x;
while (cin >> x) {  // 读入未知数量的整数
    nums.push_back(x);
}
sort(nums.begin(), nums.end());  // 排序

二、栈（`stack`）：后进先出（LIFO）

栈（stack）：后进先出（LIFO）

stack是后进先出（Last In First Out） 的容器，仅允许在顶部（栈顶）进行插入和删除操作，类似“叠盘子”。

1. 核心特性

操作受限：只能访问栈顶元素，不能遍历或随机访问中间元素。
高效操作：入栈（push）、出栈（pop）、访问栈顶（top）均为O(1)。

2. 头文件与基本用法

c++

#include <stack>  // 必须包含
#include <iostream>
using namespace std;

int main() {
    // 1. 创建栈
    stack<int> st;

    // 2. 入栈（push）
    st.push(1);
    st.push(2);
    st.push(3);  // 栈顶是3，栈为[1, 2, 3]（底部→顶部）

    // 3. 访问栈顶元素（top）
    cout << st.top() << endl;  // 3

    // 4. 出栈（pop，删除栈顶元素，无返回值）
    st.pop();  // 栈变为[1, 2]，栈顶是2

    // 5. 常用属性
    cout << "大小：" << st.size() << endl;    // 2
    cout << "是否为空：" << st.empty() << endl;  // 0（非空）

    // 6. 清空栈
    while (!st.empty()) {
        st.pop();
    }
    return 0;
}

3. 信奥赛应用场景

括号匹配问题：用栈存储左括号，遇到右括号时弹出栈顶检查匹配。
深度优先搜索（DFS）：手动模拟递归（避免递归栈溢出）。
表达式求值：如后缀表达式计算、中缀转后缀。
单调栈问题：求Next Greater Element等。

示例：括号匹配检查

c++

bool isMatch(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);  // 左括号入栈
        } else {
            if (st.empty()) return false;  // 右括号多了
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) {
                return false;  // 不匹配
            }
        }
    }
    return st.empty();  // 左括号不能有剩余
}

三、队列（`queue`）：先进先出（FIFO）

队列（queue）：先进先出（FIFO）

queue是先进先出（First In First Out） 的容器，仅允许在队尾插入、队头删除，类似“排队”。

1. 核心特性

操作受限：只能访问队头和队尾元素，不能遍历或随机访问。
高效操作：入队（push）、出队（pop）、访问队头（front）、队尾（back）均为O(1)。

2. 头文件与基本用法

c++

#include <queue>  // 必须包含
#include <iostream>
using namespace std;

int main() {
    // 1. 创建队列
    queue<int> q;

    // 2. 入队（push，从队尾加入）
    q.push(10);
    q.push(20);
    q.push(30);  // 队列：队头10 → 20 → 队尾30

    // 3. 访问队头和队尾
    cout << "队头：" << q.front() << endl;  // 10
    cout << "队尾：" << q.back() << endl;   // 30

    // 4. 出队（pop，删除队头元素，无返回值）
    q.pop();  // 队列变为：20 → 30

    // 5. 常用属性
    cout << "大小：" << q.size() << endl;    // 2
    cout << "是否为空：" << q.empty() << endl;  // 0（非空）

    // 6. 清空队列
    while (!q.empty()) {
        q.pop();
    }
    return 0;
}

3. 信奥赛应用场景

广度优先搜索（BFS）：层次遍历（如二叉树层序遍历、最短路径问题）。
模拟排队问题：如银行排队、打印机队列等。
滑动窗口：维护窗口内的元素（结合其他容器）。

示例：BFS求无权图的最短路径

c++

// 邻接表存储图，start到end的最短距离
int bfs(vector<vector<int>>& graph, int start, int end) {
    queue<int> q;
    vector<int> dist(graph.size(), -1);  // 距离数组，-1表示未访问
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == end) return dist[u];  // 找到终点，返回距离
        for (int v : graph[u]) {  // 遍历邻居
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;  // 距离+1
                q.push(v);
            }
        }
    }
    return -1;  // 无法到达
}

四、链表（`list`）：双向链表

链表（list）：双向链表

list是双向链表，每个元素独立存储，通过指针连接，支持高效的插入和删除操作。

1. 核心特性

非连续内存：元素在内存中不连续，通过指针连接。
插入删除高效：在任意位置插入/删除元素，时间复杂度O(1)（已知位置时）。
随机访问低效：访问第i个元素需从头遍历，时间复杂度O(n)。
双向遍历：可从头部或尾部开始遍历。

2. 头文件与基本用法

c++

#include <list>  // 必须包含
#include <iostream>
using namespace std;

int main() {
    // 1. 创建链表
    list<int> lst;

    // 2. 插入元素（头部/尾部/中间）
    lst.push_back(20);    // 尾部插入：[20]
    lst.push_front(10);   // 头部插入：[10, 20]
    auto it = lst.begin();  // 迭代器指向10
    lst.insert(++it, 15);  // 在10之后插入15：[10, 15, 20]

    // 3. 访问元素（只能通过迭代器，无下标访问）
    for (int x : lst) {
        cout << x << " ";  // 10 15 20
    }

    // 4. 删除元素
    lst.pop_front();  // 删除头部：[15, 20]
    lst.pop_back();   // 删除尾部：[15]
    it = lst.begin();
    lst.erase(it);    // 删除迭代器指向的元素：[]

    // 5. 常用属性
    cout << "大小：" << lst.size() << endl;    // 0
    cout << "是否为空：" << lst.empty() << endl;  // 1（true）

    return 0;
}

3. 信奥赛应用场景

频繁在中间插入/删除元素：如模拟链表操作、实现复杂数据结构（如邻接表）。
需要双向遍历：如某些约瑟夫环问题、双向队列场景（但更推荐deque）。

注意：信奥赛中list使用频率低于vector，因为大多数场景需要随机访问，而list的遍历效率较低。

五、容器对比与选择指南

容器	随机访问	尾部插入/删除	中间插入/删除	遍历效率	适用场景
`vector`	`O(1)`	`O(1)`	`O(n)`	高	动态数组、随机访问、排序查找
`stack`	不支持	不支持（仅栈顶）	不支持	不支持遍历	括号匹配、DFS、单调栈
`queue`	不支持	不支持（仅队尾入、队头出）	不支持	不支持遍历	BFS、排队模拟
`list`	`O(n)`	`O(1)`	`O(1)`	低	频繁中间插入/删除、双向遍历

六、避坑指南

避坑指南

vector的效率优化：
- 已知大致大小时，用reserve(n)预留容量，避免多次扩容：
c++
```
vector<int> v;
v.reserve(100000);  // 预留10万个元素的空间
```
- 清空元素用clear()（仅销毁元素，不释放容量），释放容量用swap：
c++
```
vector<int>().swap(v);  // 交换临时对象，释放v的容量
```

stack/queue的遍历限制：
这两个容器没有迭代器，不能直接遍历所有元素。若需遍历，可先复制到vector再操作：

c++

stack<int> st;
// ... 入栈操作 ...
vector<int> temp;
while (!st.empty()) {
    temp.push_back(st.top());
    st.pop();
}
// 此时temp中存储栈的元素（逆序）

避免滥用list：
除非必须频繁在中间插入删除，否则优先用vector（随机访问和遍历效率更高）。

重要

熟练掌握这些容器的特性和操作，能轻松应对信奥赛中大多数数据处理问题。
STL容器是信奥赛的“瑞士军刀”，选择合适的容器能大幅简化代码并提升效率：
- 需随机访问或动态数组：选vector。
- 后进先出场景（如DFS、括号匹配）：选stack。
- 先进先出场景（如BFS、排队）：选queue。
- 频繁中间插入删除：选list。

基础知识与编程环境

C++程序设计

数据结构

算法

数学与其他

基础知识与编程环境

C++程序设计

STL模板