在算法竞赛中， 头文件是高频工具库，封装了排序、查找、遍历、修改、最值、区间操作等核心函数，能大幅简化代码、提升效率。以下按竞赛高频使用场景分类，讲解函数的原型、用法、竞赛考点、坑点，所有函数均适配竞赛主流编译器（GCC/Dev-C++），且附带竞赛风格的极简示例。

核心说明
1.所有函数的区间参数均为左闭右开 [first, last)，即包含 first 迭代器，不包含 last 迭代器（数组 /vector 通用）；
2.函数参数中的比较器（comp） 均为可选，默认按 **< 运算符升序 / 默认规则，自定义比较器可写Lambda 表达式、函数指针、仿函数 **（竞赛中 Lambda 最简洁）；
3.迭代器类型：竞赛中常用随机访问迭代器（vector / 数组的迭代器），所有讲解函数均支持该类型。

一、排序类（竞赛最核心，必考）
1.sort — 快速排序（不稳定，O (nlogn)）
原型：void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
核心用法：
(1)默认升序排序，自定义比较器可实现降序、按结构体成员排序、pair 多关键字排序；
(2)竞赛中数组 /vector排序的首选，效率最高，适配绝大多数场景。

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

int main() {
    vector<int> v = {5,2,9,1,5,6};
    sort(v.begin(), v.end()); // 升序：1 2 5 5 6 9
    sort(v.begin(), v.end(), greater<int>()); // 降序：9 6 5 5 2 1

    // pair排序：默认先按first升序，first相同按second升序
    vector<pair<int, int>> p = {{3,2}, {1,5}, {3,1}};
    sort(p.begin(), p.end()); // 结果：(1,5) (3,1) (3,2)
    // 自定义：按second降序，second相同按first升序
    sort(p.begin(), p.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        return a.second > b.second || (a.second == b.second && a.first < b.first);
    });
    return 0;
}

竞赛考点
结构体排序：必须自定义比较器（不能直接用 >/<）；
pair 多关键字排序：利用 Lambda 实现灵活规则；
数组排序：sort(a, a + n)（a 为数组名，n 为元素个数）。

2.stable_sort — 稳定排序（O (nlog²n)）
与 sort 用法完全一致，保留相等元素的相对顺序，竞赛中仅在需要稳定顺序时使用（如按成绩排序后，相同成绩保留原排名）。

3.nth_element — 第 k 小 / 大元素定位（O (n)）
原型：void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

核心用法
(1)将区间中第 nth 个位置设为按默认规则排序后的该位置元素；
(2)左边元素均≤该元素，右边元素均≥该元素（左右内部无序）；
(3)竞赛中快速找第 k 小 / 大元素、topk 问题的最优解（比排序后取值效率高）。

vector<int> v = {5,2,9,1,5,6};
// 找第3小元素（从0开始计数，nth=v.begin()+2）
nth_element(v.begin(), v.begin()+2, v.end());
cout << v[2]; // 结果：5（第3小）
// 找第2大元素：用greater<int>()，nth=v.begin()+1
nth_element(v.begin(), v.begin()+1, v.end(), greater<int>());
cout << v[1]; // 结果：6（第2大）

二、查找类（与排序配合使用，高频）
所有查找类函数（除find）均要求区间已排序（否则结果未定义），竞赛中常与 sort 配合实现快速查找、去重、判断存在。
1.binary_search — 二分查找是否存在（O (logn)）
原型：bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);
返回bool 值，判断区间中是否存在值为 val 的元素，默认升序区间。

vector<int> v = {1,2,5,5,6,9};
sort(v.begin(), v.end()); // 必须先排序
cout << binary_search(v.begin(), v.end(), 5); // true
cout << binary_search(v.begin(), v.end(), 3); // false

2.lower_bound — 找第一个≥val 的元素（O (logn)）
原型：ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);
返回迭代器，指向区间中第一个大于等于 val的元素；若所有元素都 < val，返回 last。

竞赛考点
结合 upper_bound 求元素的出现次数。
找元素的插入位置（保证插入后区间仍有序）；

3.upper_bound — 找第一个 > val 的元素（O (logn)）
原型：ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val);
返回迭代器，指向区间中第一个大于 val的元素；若所有元素都≤val，返回 last。

vector<int> v = {1,2,5,5,6,9};
sort(v.begin(), v.end());
auto l = lower_bound(v.begin(), v.end(), 5); // 指向第一个5
auto r = upper_bound(v.begin(), v.end(), 5); // 指向6
int cnt = r - l; // 5的出现次数：2

4.find — 线性查找元素（O (n)）
原型：InputIterator find(InputIterator first, InputIterator last, const T& val);
无需区间排序，线性遍历找第一个值为 val 的元素，返回迭代器；未找到返回 last。
竞赛中小规模数据查找，或无序区间的单次查找（大数据用 sort + 二分）。

三、最值 / 统计类（基础工具，随处可用）
用于快速找区间最值、统计元素出现次数，max_element/min_element 为必考，count 为基础工具。
1. max_element — 找最大值元素（O (n)）
2. min_element — 找最小值元素（O (n)）
原型：
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);
返回迭代器，指向区间最值元素；多个最值返回第一个；自定义比较器可实现按成员找最值（如 pair 的 first/second、结构体成员）。

3.count — 统计元素出现次数（O (n)）
原型：count(InputIterator first, InputIterator last, const T& val);
返回区间中值为 val 的元素个数，无需排序，线性统计。

vector<int> v = {5,2,9,1,5,6};
int cnt = count(v.begin(), v.end(), 5); // 2

四、区间修改类（简化数组 /vector 操作，高频）
用于对区间元素进行填充、替换、反转、去重，均为原地修改，竞赛中能大幅减少循环代码。
1.fill — 区间填充指定值（O (n)）
原型：void fill(ForwardIterator first, ForwardIterator last, const T& val);
将区间内所有元素设为 val，竞赛中用于数组 /vector 初始化、重置。

vector<int> v(5);
fill(v.begin(), v.end(), 0); // 全部填充0：{0,0,0,0,0}
fill(v.begin()+2, v.end(), 5); // 从第3个元素开始填充5：{0,0,5,5,5}

2.reverse — 区间反转（O (n)）
原型：void reverse(BidirectionalIterator first, BidirectionalIterator last);
将区间内元素逆序排列，竞赛中用于字符串反转、数组逆序、回文判断等场景。

vector<int> v = {1,2,3,4,5};
reverse(v.begin(), v.end()); // {5,4,3,2,1}
string s = "abcde";
reverse(s.begin(), s.end()); // "edcba"

3.unique — 区间去重（O (n)）
原型：ForwardIterator unique(ForwardIterator first, ForwardIterator last);
要求区间已排序，将区间内连续的重复元素去重（仅保留一个）；
返回去重后区间的尾迭代器（原容器长度不变，需配合 erase 删去多余元素）；
未排序的区间使用 unique 无效，仅会去重连续的重复元素。

vector<int> v = {5,2,9,1,5,6,5};
sort(v.begin(), v.end()); // 先排序：{1,2,5,5,5,6,9}
auto it = unique(v.begin(), v.end()); // 去重后：{1,2,5,6,9,?,?}
v.erase(it, v.end()); // 删去多余元素，最终v：{1,2,5,6,9}

4.replace — 区间替换指定值（O (n)）
原型：void replace(ForwardIterator first, ForwardIterator last, const T& old_val, const T& new_val);
将区间内所有 old_val替换为 new_val，竞赛中用于元素值的批量修改。

vector<int> v = {1,2,3,2,4,2};
replace(v.begin(), v.end(), 2, 0); // {1,0,3,0,4,0}

五、区间合并 / 交换类（竞赛进阶，偏题高频）
用于交换两个区间、合并两个有序区间，merge 为归并排序核心，swap_ranges 简化区间交换。
1. merge — 合并两个有序区间（O (n+m)）
原型：OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
两个输入区间必须均有序（默认升序），将其合并为一个有序区间，存入 result（需提前分配空间）；
竞赛中用于归并排序实现、两个有序数组的合并。

vector<int> a = {1,3,5}, b = {2,4,6}, res(6);
merge(a.begin(), a.end(), b.begin(), b.end(), res.begin());
// res：{1,2,3,4,5,6}

2.swap_ranges — 交换两个区间的元素（O (n)）
原型：ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
交换第一个区间和以 first2 为起始的等长区间的元素，竞赛中用于数组 /vector 的区间交换。

vector<int> a = {1,2,3}, b = {4,5,6};
swap_ranges(a.begin(), a.end(), b.begin());
// a：{4,5,6}，b：{1,2,3}

六、排列组合类（竞赛特判 / 枚举，低频但易考）
用于生成元素的下一个 / 上一个排列，仅适用于有序区间，竞赛中用于全排列枚举、排列合法性判断。1.next_permutation — 生成下一个字典序排列（O (n)）
2. prev_permutation — 生成上一个字典序排列（O (n)）
原型：bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
默认按升序字典序，将区间修改为下一个更大的排列，返回 true；若已是最大排列，返回 false 并将区间改为最小排列（升序）；
prev_permutation 则生成上一个更小的排列，返回规则相反；
竞赛中用于枚举全排列（配合循环）。若初始区间不是最小排列，next_permutation 会从当前排列的下一个开始枚举，需先排序保证枚举所有排列。

vector<int> v = {1,2,3};
// 枚举所有全排列（按字典序）
do {
    for (int x : v) cout << x << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

七、竞赛通用技巧 & 避坑指南
1.排序 + 二分是黄金组合：所有查找类问题，先排序再用 lower_bound/upper_bound/binary_search，效率远高于线性查找；
2.unique 必须配合 sort+erase：单独用 unique 仅去重连续重复元素，无法实现真正去重；
3.迭代器相减：vector / 数组的随机访问迭代器可直接相减，得到元素个数（如 r-l 求区间长度）；
4.Lambda 表达式简化比较器：竞赛中所有需要自定义比较的场景，优先用 Lambda（代码简洁，无需额外写函数）；
5.空区间判断：使用 max_element/find 等返回迭代器的函数时，若区间为空，返回 last，直接解引用会 RE（运行时错误）；
6.next_permutation 的全排列枚举：必须先排序，否则会遗漏排列。