算法竞赛 C++ STL 与内置函数速查手册

手册说明：本文按数据结构/算法类别组织，每个条目标明头文件、函数签名、关键说明、使用案例与易错点。所有复杂度使用标准记号（O(1), O(logn), O(n) 等），未特别说明时均指平均/摊还复杂度。

竞赛级 I/O 优化 (Fast I/O)

//常用的万能头
#include<bits/stdc++.h>

输出的时候

控制小数点后的位数 (最常用)

使用 std::fixed 和 std::setprecision(n) 的组合。

• std::fixed：强制以定点数（常规小数）格式显示，而不是科学计数法。

• std::setprecision(n)：在使用了 fixed 的情况下，它表示小数点后保留 n 位（会自动四舍五入）。

#include <iostream>
#include <iomanip>
int main() {
    double pi = 3.1415926535;
    std::cout << std::fixed << std::setprecision(2) << pi << "\n"; // 输出: 3.14
    std::cout << std::fixed << std::setprecision(4) << pi << "\n"; // 输出: 3.1416
    return 0;
}

控制总有效数字位数

如果不使用 std::fixed，单单使用 std::setprecision(n) 控制的是总有效数字的位数。

double num = 123.4567;
std::cout << std::setprecision(4) << num << "\n"; // 输出: 123.5 (总共4位有效数字)

科学计数法

使用 std::scientific。

C++

double num = 12345.67;
std::cout << std::scientific << num << "\n"; // 输出: 1.234567e+04

在算法竞赛中，C++ 原生的 cin/cout 速度极慢，如果不解除与 C 语言标准流的同步，在处理百万级数据时必然 Time Limit Exceeded (TLE)。

• 适用场景：所有输入输出数据量大于$10^5$ 的竞赛题目。

• 复杂度：O(1)，直接将读写速度提升至接近甚至超越 scanf/printf。

宽度、对齐与填充

这类格式化在打印表格或对齐数据时非常有用。

1. 设置输出宽度 std::setw(n)

设置下一个输出项的最小宽度为 n。

注意： 与其他具有持久性的格式化符（如 setprecision 会一直生效直到被更改）不同，std::setw 仅对紧跟其后的那一个输出项有效，输出一次后立刻失效。

2. 设置填充字符 std::setfill(char)

如果输出内容小于 setw 设定的宽度，默认用空格填充。你可以用 setfill 改变填充字符。

3. 对齐方式 std::left, std::right, std::internal

• std::right：右对齐（默认）。

• std::left：左对齐。

• std::internal：符号左对齐，数值右对齐，中间填充。

C++

#include <iostream>
#include <iomanip>

int main() {
    int num = 42;
    
    // 默认右对齐，占8个字符宽度，不足用 '*' 填充
    std::cout << std::setfill('*') << std::setw(8) << num << "\n"; 
    // 输出: ******42
    
    // 左对齐
    std::cout << std::left << std::setfill('-') << std::setw(8) << num << "END\n"; 
    // 输出: 42------END
    
    return 0;
}

进制与其他格式

1. 输出不同的进制

• std::dec：十进制（默认）

• std::hex：十六进制

• std::oct：八进制

• std::showbase：显示进制前缀（如十六进制的 0x，八进制的 0）

C++

int val = 255;
std::cout << std::showbase; // 开启前缀显示
std::cout << std::hex << val << "\n"; // 输出: 0xff
std::cout << std::oct << val << "\n"; // 输出: 0377
std::cout << std::dec << val << "\n"; // 恢复十进制, 输出: 255

2. 布尔值格式化

默认情况下，true 输出 1，false 输出 0。使用 std::boolalpha 可以让其输出文本。

C++

bool is_valid = true;
std::cout << std::boolalpha << is_valid << "\n"; // 输出: true

C++

#include <iostream>

using namespace std;

int main() {
    // 必须放在 main 函数的第一行！
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); // 可选

    int n;
    cin >> n;
    
    // ⚠️ 易错点：使用了 Fast I/O 后，绝对不能再混用 scanf, printf, puts, gets！
    // ⚠️ 易错点：永远使用 '\n' 换行，坚决不要用 endl！(endl 会强制刷新缓冲区，导致极度卡顿)
    cout << n << '\n'; 
    return 0;
}

一、核心数据结构

1. 列表 C++ std::vector

• 对应关系： std::vector（动态数组）。C++ 中虽然也有 std::list，但那是双向链表，由于内存不连续，查询速度慢，日常开发中远不如 vector 常用。

• 头文件：#include <vector>

• 易错点

  reserve ≠ resize

  v.reserve(100);

  只是预留容量。

  size 仍然是 0。

  下面是错误写法：

  v.reserve(100);
  
  v[0] = 1; // ❌ 越界

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 定义与初始化 (必须指定类型为 int)
    vector<int> my_list = {10, 20, 30};

    // 追加元素 (相当于 append)
    my_list.push_back(40);

    // 插入元素 (在索引 1 的位置插入 15)
    my_list.insert(my_list.begin() + 1, 15);

    // 访问与修改
    cout << my_list[0] << endl; // 输出: 10
    my_list[0] = 99;            // 修改第一个元素

    // 遍历
    for (int item : my_list) {
        cout << item << " ";
    }
    return 0;
}

2. 字典 C++ std::unordered_map / std::map

• 对应关系：底层基于哈希表，对应的 C++ 实现是 std::unordered_map（无序，查询$O(1)$）。C++ 还有一个 std::map（基于红黑树，按键排序，查询$O(\log N)$）。

• 头文件：#include <unordered_map>

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    // 定义与初始化 <键类型, 值类型>
    unordered_map<string, int> student = {
        {"Alice", 20},
        {"Bob", 22}
    };

    // 访问元素
    cout << student["Alice"] << endl; 

    // 安全访问 (相当于 python 的 get)
    if (student.count("Charlie") > 0) {
        cout << student["Charlie"] << endl;
    }

    // 增加或修改
    student["Alice"] = 21;       // 修改
    student["David"] = 19;       // 新增

    // 遍历 (C++11 语法)
    for (const auto& pair : student) {
        cout << pair.first << ": " << pair.second << endl;
    }
    // C++17 结构化绑定语法（更像 Python）
    // for (auto const& [key, value] : student) { ... }
    return 0;
}

3. 集合 (Set) ➡️ C++ std::unordered_set / std::set

• 对应关系：同字典一样 C++ 的 std::unordered_set（哈希表去重）。

• 头文件：#include <unordered_set>

C++

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    // 定义与自动去重
    unordered_set<int> my_set = {1, 2, 2, 3, 4, 4};

    // 添加与删除
    my_set.insert(5);
    my_set.erase(1); // 删除 1

    // 检查元素是否存在
    if (my_set.count(3) > 0) {
        cout << "3 is in the set" << endl;
    }
    return 0;
}
// 注意：C++ 的 set 没有重载 &, | 操作符直接求交并集，需要用到 <algorithm> 里的 std::set_intersection 等函数。

4. 字符串 (String) ➡️ C++ std::string

• 重大区别 而 C++ 的 std::string 是可变的（你可以直接修改原字符串中的某个字符 text[0] = 'a'，这在 Python 中是报错的）。

• 头文件：#include <string>

字符串高级匹配 (处理 Word Break 等问题)

在解决“单词拆分”或字符串状态转移的 DP 时，经常需要快速判定子串和前缀。

子串查找与比较

• 复杂度：find 的平均复杂度通常为$O(N)$，最坏为$O(N \times M)$。

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    string text = "competitive programming";
    
    // 1. 查找子串 (返回起始索引，找不到返回 std::string::npos)
    size_t pos = text.find("pro");
    if (pos != string::npos) {
        cout << "Found at: " << pos << "\n";
    }

    // 2. 匹配特定前缀 (C++20 新特性，极其好用)
    // 替代了以前繁琐的 text.substr(0, prefix.length()) == prefix
    #if __cplusplus >= 202002L
        if (text.starts_with("comp")) cout << "Yes\n";
        if (text.ends_with("ing")) cout << "Yes\n";
    #endif

    return 0;
}

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    string text = "C++ is awesome";

    // 索引与修改 (可直接修改)
    cout << text[0] << endl; // 输出: C
    text[0] = 'c';           // 变成 "c++ is awesome"

    // 切片 (相当于 text[0:3]) -> substr(起始位置, 长度)
    cout << text.substr(0, 3) << endl; // 输出: c++

    // 拼接
    text += "!!!";
    return 0;
}

5. 栈 (Stack) ➡️ C++ std::stack

• 对应关系：C++ 提供了专门的容器适配器 std::stack。

• 头文件：#include <stack>

C++

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    stack<string> s;

    // 压栈
    s.push("A");
    s.push("B");
    s.push("C");

    // 查看栈顶元素 (但不移除)
    cout << s.top() << endl; // 输出: C

    // 出栈 (注意：C++ 的 pop() 不返回值，只负责弹出)
    s.pop();

    cout << s.top() << endl; // 输出: B
    return 0;
}

6. 队列 (Queue) ➡️ C++ std::queue

• 对应关系：相当于 Python 的 deque 限制了只能单向进出。

• 头文件：#include <queue>

C++

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    queue<string> q;

    // 入队 (加在尾部)
    q.push("Alice");
    q.push("Bob");

    // 查看队首元素
    cout << q.front() << endl; // 输出: Alice

    // 出队 (从头部弹出，不返回值)
    q.pop();

    cout << q.front() << endl; // 输出: Bob
    return 0;
}

7. 堆 (Heap) ➡️ C++ std::priority_queue

• 对应关系：C++ 中叫做优先队列。

• 重大区别：而 C++ 的 priority_queue 默认是大顶堆（最大的先出）。

• 头文件：#include <queue>

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 默认是大顶堆 (Max-Heap)
    priority_queue<int> max_pq;
    max_pq.push(5);
    max_pq.push(9);
    max_pq.push(1);
    cout << max_pq.top() << endl; // 输出: 9 (最大的)

    // 如果要改成跟 Python 一样的小顶堆 (Min-Heap)，写法比较长：
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(5);
    min_pq.push(9);
    min_pq.push(1);
    cout << min_pq.top() << endl; // 输出: 1 (最小的)
    
    // 弹出堆顶
    min_pq.pop(); 
    return 0;
}

8. 元组 (Tuple) ➡️ C++ std::tuple / std::pair

• 对应关系：如果只有两个元素，C++ 程序员通常使用更简单的 std::pair；如果是多个元素，则使用 C++11 引入的 std::tuple。

• 头文件：#include <tuple> 或 #include <utility> (针对 pair)

C++

#include <iostream>
#include <tuple>
#include <utility> // for std::pair
#include <string>

using namespace std;

int main() {
    // 1. 使用 Pair (仅限两个元素)
    pair<int, string> p = {10, "Apple"};
    cout << p.first << ", " << p.second << endl;

    // 2. 使用 Tuple (任意数量元素)
    tuple<int, double, string> t = make_tuple(1, 3.14, "hello");

    // 访问 Tuple 元素 (需要使用 std::get<索引>)
    cout << get<0>(t) << endl; // 输出: 1

    // C++17 的解包 (Structured Binding，极其类似 Python)
    auto [x, y, z] = t;
    cout << z << endl; // 输出: hello

    return 0;
}
```</Type>

9. 数组容器 ➡️ C++ std::array

• 特点：固定大小的数组。它封装了 C 风格的裸数组（如 int arr[5];），提供了 STL 的迭代器接口和更安全的边界检查（通过 .at() 方法）。由于大小固定，它的元素是在栈（Stack）上分配的，性能极高，没有动态内存分配的开销。

• 适用场景：当你知道数据量是固定的，且永远不会改变时使用，性能优于 std::vector。

• 头文件：#include <array>

C++

#include <iostream>
#include <array>

using namespace std;

int main() {
    // 定义一个大小为 5 的整型数组
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问元素
    cout << arr[0] << endl;       // 正常访问，越界不报错（行为未定义）
    cout << arr.at(1) << endl;    // 安全访问，越界抛出 std::out_of_range 异常

    // 常用操作
    cout << arr.size() << endl;   // 输出: 5
    cout << arr.front() << endl;  // 输出: 1
    cout << arr.back() << endl;   // 输出: 5

    // 遍历
    for(int val : arr) {
        cout << val << " ";
    }
    return 0;
}

10. 正向链表 ➡️ C++ std::forward_list

• 特点：单向链表。它比双向链表（std::list）更轻量级，因为每个节点只保留指向下一个节点的指针。这意味着你只能从头向后遍历，不能向前遍历。它没有提供 .size() 方法（因为计算大小需要遍历一遍，复杂度是$O(N)$，STL 设计者为了强调效率而故意去掉了这个接口）。

• 适用场景：对内存占用极其敏感，且只需要单向遍历和在头部（或已知节点后）插入/删除的场景。

• 头文件：#include <forward_list>

C++

#include <iostream>
#include <forward_list>

using namespace std;

int main() {
    forward_list<int> flist = {10, 20, 30};

    // 在头部插入元素 (时间复杂度 O(1))
    flist.push_front(5);

    // 在指定位置后插入元素 (由于是单向，只能在某个元素 "之后" 插入)
    auto it = flist.begin();
    flist.insert_after(it, 15); // 在第一个元素后插入 15

    // 遍历
    for (int val : flist) {
        cout << val << " "; // 输出: 5 15 10 20 30 
    }
    return 0;
}

11. 位集合 ➡️ C++ std::bitset

• 特点：专门用于存储和操作位（bit）的定长容器。相当于一个只能存 0 和 1 的超级数组，但它的底层做了极其优秀的内存压缩（1个字节存 8 个布尔值）。它支持所有位运算符（&, |, ^, ~, <<, >>）。

• 适用场景：状态压缩、位运算优化、布隆过滤器（Bloom Filter）的底层实现、处理大量的真/假状态。

• 头文件：#include <bitset>

C++

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    // 定义一个 8 位的位集合，初始化为二进制 1010
    bitset<8> b1(string("1010")); 
    // 或者用整数初始化
    bitset<8> b2(12); // 12 的二进制是 00001100

    // 访问特定位
    cout << b1[1] << endl; // 输出: 1 (注意，索引是从右往左数的，即第 1 位)

    // 常用方法
    cout << b1.count() << endl; // 输出: 2 (统计二进制中 1 的个数)
    cout << b1.any() << endl;   // 输出: 1 (是否有任意一位是 1)
    cout << b1.none() << endl;  // 输出: 0 (是否全为 0)

    // 位运算
    bitset<8> b3 = b1 & b2;     // 按位与
    cout << b3 << endl;         // 输出: 00001000

    // 翻转
    b1.flip();                  // 全部取反
    cout << b1 << endl;         // 输出: 11110101

    return 0;
}

12. 多重集合 / 多重字典 ➡️ C++ std::multiset / std::multimap

• 特点：它们分别是 std::set 和 std::map 的变体。唯一的区别是：它们允许键（Key）重复。底层同样基于红黑树，是有序的。

• 适用场景：

  • multiset：经常用于作为有序的数组，且需要频繁插入/删除/求最值（比优先队列更灵活，因为可以删除任意元素）。

  • multimap：用于一对多的映射关系。

• 头文件：#include <set> 或 #include <map>

C++

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> mset = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // 插入元素
    mset.insert(1); // 允许重复插入

    // 统计某个元素出现的次数
    cout << mset.count(1) << endl; // 输出: 3

    // 遍历 (由于底层是红黑树，输出是有序的)
    for (int val : mset) {
        cout << val << " "; // 输出: 1 1 1 2 3 4 5 5 6 9 
    }
    cout << endl;

    // ⚠️ 陷阱：删除操作
    // 如果直接 erase(1)，会把所有等于 1 的元素全删掉！
    // mset.erase(1); 
    
    // 如果只想删掉一个 1，需要用迭代器：
    auto it = mset.find(1); // find 会找到第一个匹配的元素
    if (it != mset.end()) {
        mset.erase(it);     // 只删掉这一个迭代器指向的元素
    }

    return 0;
}

13. 双端队列 ➡️ C++ std::deque

特点：全称 Double-Ended Queue。它和 std::vector 非常像，都支持通过索引随机访问（[i]），但 deque 的两端（头部和尾部）都可以进行$O(1)$ 的快速插入和删除。

与 Python 的区别：Python 的 collections.deque 底层通常是双向链表块，不支持高效的随机访问；而 C++ 的 deque 底层是由一段段定长数组拼接而成的“分段连续空间”，既支持双端操作，又保留了$O(1)$ 的随机访问能力。

适用场景：需要频繁在头部和尾部增删元素，同时又需要像数组一样通过索引读取数据。

头文件：#include <deque>

C++

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> d = {2, 3, 4};

    // 尾部插入
    d.push_back(5);
    // 头部插入 (vector 做不到 O(1) 的头部插入)
    d.push_front(1);

    // 随机访问 (O(1) 复杂度)
    cout << d[2] << endl; // 输出: 3

    // 遍历
    for (int val : d) cout << val << " "; // 输出: 1 2 3 4 5
    return 0;
}

14. 双向链表 ➡️ C++ std::list

特点：标准的双向链表。虽然你在第一条中提到了它不如 vector 常用，但它作为基础容器依然不可或缺。它的节点在内存中是分散的，包含指向前一个和后一个节点的指针。

适用场景：需要在序列的任意位置频繁进行插入和删除操作，且不在乎随机访问性能（不支持 list[i]）。在实现 LRU Cache 等高级数据结构时必不可少。

头文件：#include <list>

C++

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> l = {10, 20, 30};

    // 双端操作
    l.push_back(40);
    l.push_front(0);

    // 任意位置插入/删除 (需要借助迭代器)
    auto it = l.begin();
    advance(it, 2); // 移动迭代器到第 3 个位置
    l.insert(it, 15);

    // list 特有的高效操作：将另一个 list 拼接到自己身上 (O(1) 复杂度)
    list<int> l2 = {100, 200};
    l.splice(l.end(), l2); // 把 l2 的节点全部“剪切”到 l 的尾部

    return 0;
}

15. 无序多重集合/字典 ➡️ C++ std::unordered_multiset / std::unordered_multimap

特点：它们是你提到的 multiset / multimap 的哈希表版本。允许键重复，但不保证顺序。

适用场景：需要存储重复的键值，且不需要数据有序，只追求极速的 查找和插入。#include <iostream>
#include <unordered_set> // 注意：多重集合的头文件依然是 unordered_set
#include <string>

int main() {
    // 1. 初始化
    std::unordered_multiset<std::string> gacha_results;

    // 2. 插入元素 (允许重复)
    gacha_results.insert("SSR_Arthur");
    gacha_results.insert("R_Slime");
    gacha_results.insert("SR_Merlin");
    gacha_results.insert("R_Slime");   // 再次抽到史莱姆
    gacha_results.insert("R_Slime");   // 第三次抽到史莱姆

    std::cout << "总共抽卡次数 (size): " << gacha_results.size() << "\n";

    // 3. 核心用法：查询某个元素出现了几次 (count)
    std::string target = "R_Slime";
    std::cout << target << " 抽到的次数: " << gacha_results.count(target) << "\n";

    // 4. 遍历所有元素 (注意：输出顺序与插入顺序完全无关)
    std::cout << "\n当前背包里的所有卡牌:\n";
    for (const std::string& card : gacha_results) {
        std::cout << "- " << card << "\n";
    }

    // 5. 删除元素
    // 注意：如果直接传值给 erase，会把所有叫 "R_Slime" 的全删掉！
    // gacha_results.erase("R_Slime"); 

    // 如果只想删除【一个】重复元素，需要用到迭代器：
    auto it = gacha_results.find("R_Slime"); // 找到其中一个史莱姆的迭代器
    if (it != gacha_results.end()) {
        gacha_results.erase(it); // 只删掉这一个
        std::cout << "\n献祭掉一个 R_Slime 后，还剩: " << gacha_results.count("R_Slime") << " 个\n";
    }

    return 0;
}

16. 字符串视图 ➡️ C++ std::string_view (C++17)

特点：它本质上是一个只读的指针 + 长度。传统的 std::string 在传递或截取子串时，往往会发生内存拷贝（深拷贝）；而 string_view 直接“借用”原有字符串的内存，绝对不发生拷贝。

适用场景：所有只需要读、不需要修改字符串的场景，能极大提升程序性能。

C++

#include <iostream>
#include <string_view>

using namespace std;

// 传递 string_view 代替 const string&，速度更快，且兼容 C 风格字符串
void printSub(string_view sv) {
    cout << sv.substr(0, 3) << endl; // 这里的 substr 不会产生任何内存分配！
}

int main() {
    string s = "Hello World";
    printSub(s); 
    printSub("C-Style String"); // 同样适用
    return 0;
}

17. 连续内存视图 ➡️ C++ std::span (C++20)

特点：可以把它看作是 std::string_view 的泛型数组版本。它是一个轻量级的对象，代表了一段连续的内存（可以是指向 vector、array 或纯 C 数组的一段区间），且可读可写（不同于 view 的只读）。

适用场景：用来替代传统的 void func(int* arr, int size) 传参方式，更加安全且带有边界检查。

C++

#include <iostream>
#include <vector>
#include <span>

using namespace std;

// span 可以接收任何连续的内存块
void modifySpan(span<int> s) {
    for (int& val : s) {
        val *= 2; // 直接修改原内存中的数据
    }
}

int main() {
    vector<int> v = {1, 2, 3};
    int arr[3] = {4, 5, 6};

    modifySpan(v);   // 传 vector
    modifySpan(arr); // 传 原生数组
    return 0;
}

二、排序与二分查找 (Sorting & Binary Search)

11. 排序 std::sort

• 头文件：<algorithm>

• 签名：std::sort(RandomIt first, RandomIt last, Compare comp = less<>{})

• 复杂度：平均 O(nlog⁡n)O(nlogn)，最坏 O(nlog⁡n)O(nlogn)（introsort 混合算法）。

• 典型用法：

  cpp

  std::vector<int> v = {3, 1, 4, 1, 5};
  std::sort(v.begin(), v.end());                       // 升序
  std::sort(v.begin(), v.end(), std::greater<>{});    // 降序
  std::sort(v.begin(), v.end(), [](int a, int b) {
      return a > b;                                    // 自定义
  });
  
  
  #include <iostream>
  #include <vector>
  #include <algorithm> // std::sort 必须包含此头文件
  #include <string>
  
  // 定义玩家结构体
  struct Player {
      std::string name;
      int score;
      int level;
  };
  
  int main() {
      std::vector<Player> players = {
          {"Alice", 1500, 10},
          {"Bob",   2000, 15},
          {"Charlie", 1500, 12}, // 分数和 Alice 一样，但等级高
          {"David", 1800, 8}
      };
  
      // 使用 Lambda 表达式进行多条件自定义排序
      std::sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
          if (a.score != b.score) {
              return a.score > b.score; // 规则 1：分数高的排前面 (降序)
          }
          return a.level > b.level;     // 规则 2：分数相同时，等级高的排前面 (降序)
      });
  
      std::cout << "--- 排行榜 ---\n";
      for (const auto& p : players) {
          std::cout << p.name << " - 分数: " << p.score << ", 等级: " << p.level << "\n";
      }
      // 输出预期：Bob, David, Charlie, Alice
  
      return 0;
  }
  
  int main() {
      std::vector<std::string> words = {"banana", "apple", "kiwi", "watermelon", "pear"};
  
      // 默认的 std::sort 会按字母字典序 (a-z) 排序
      // std::sort(words.begin(), words.end()); 
  
      // 自定义：按字符串长度从短到长排序 (升序)
      std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {
          return a.length() < b.length(); // 长度小的排前面
      });
  
      std::cout << "按长度排序后:\n";
      for (const auto& w : words) {
          std::cout << w << " "; 
      }
      // 输出: kiwi pear apple banana watermelon
  
      return 0;
  }

• 重要注意事项：

  • 非稳定排序：相等元素的相对顺序可能改变；需要稳定性请用 std::stable_sort。

  • 要求随机访问迭代器，std::list 应使用其成员函数 sort()。

  • 比较函数必须满足严格弱序（strict weak ordering），否则行为未定义（典型错误：使用 <= 而非 <）。

12. 稳定排序 std::stable_sort

• 头文件：<algorithm>

• 签名：std::stable_sort(RandomIt first, RandomIt last, Compare comp = less<>{})

• 复杂度：O(nlog⁡n)O(nlogn)，有足够额外内存时为 O(nlog⁡n)O(nlogn) 次比较，否则 O(nlog⁡2n)O(nlog2n)。

• 典型用法：

  cpp

  std::stable_sort(v.begin(), v.end());
  std::stable_sort(v.begin(), v.end(), std::greater<>{});

• 重要注意事项：

  • 保证相等元素的相对顺序不变。使用场景：先按某个字段排序，再按另一个字段稳定排序实现多关键字排序。

  • 通常比 sort() 稍慢，仅当确实需要稳定性时使用。

13. 局部排序 std::partial_sort

• 头文件：<algorithm>

• 签名：std::partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp = less<>{})

• 复杂度：O(nlog⁡k)O(nlogk)，其中 k=middle−firstk=middle−first。

• 典型用法：

  cpp

  std::vector<int> v = {5, 9, 1, 3, 8, 2};
  std::partial_sort(v.begin(), v.begin() + 3, v.end());
  // 前 3 个元素变为最小的 3 个且有序，其余顺序未定义
  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <string>
  
  // 定义敌人结构体
  struct Enemy {
      std::string name;
      float distance; // 距离玩家的物理距离
  };
  
  int main() {
      // 模拟场景中存在的多个敌人
      std::vector<Enemy> enemies = {
          {"哥布林 A", 15.5f},
          {"兽人战士", 102.0f},
          {"史莱姆", 3.2f},
          {"巨龙", 500.0f},
          {"哥布林 B", 12.1f},
          {"野狼", 8.5f},
          {"巨魔", 45.0f}
      };
  
      // 我们只想锁定最近的 3 个敌人
      int k = 3;
  
      // 使用 partial_sort 找出距离最小的前 3 个敌人
      std::partial_sort(
          enemies.begin(), 
          enemies.begin() + k, // 排序的边界：确保前 K 个元素是有序的
          enemies.end(), 
          // 自定义排序规则：按距离从小到大（升序）
          [](const Enemy& a, const Enemy& b) {
              return a.distance < b.distance; 
          }
      );
  
      std::cout << "🔥 --- 已锁定最近的 " << k << " 个目标 (准备攻击) --- 🔥\n";
      // 只有前 K 个元素的顺序是可靠的
      for (int i = 0; i < k; ++i) {
          std::cout << "目标 " << i+1 << ": " << enemies[i].name 
                    << " (距离: " << enemies[i].distance << "m)\n";
      }
  
      std::cout << "\n👀 --- 视野外/未锁定的其他敌人 (顺序混乱) ---\n";
      // K 之后的元素顺序是未定义的，C++ 只保证它们都比前 K 个元素大
      for (size_t i = k; i < enemies.size(); ++i) {
          std::cout << enemies[i].name << " (距离: " << enemies[i].distance << "m)\n";
      }
  
      return 0;
  }

• 重要注意事项：

  • 是 Top-K 场景的最优解：需要"最小的 K 个元素且有序"时，比全排序 O(nlog⁡n)O(nlogn) 更高效。

  • 如果只需要第 K 个元素的值而不需要有序，可用 std::nth_element（O(n)O(n)）。

14. 第 K 个元素 std::nth_element

• 头文件：<algorithm>

• 签名：std::nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp = less<>{})

• 复杂度：平均 O(n)O(n)（基于快速选择算法）。

• 典型用法：

  cpp

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  int main() {
      // 模拟收集到的一组玩家的 Ping 值 (毫秒)
      // 实际业务中这可能是一个包含数十万数据的 vector
      std::vector<int> pings = {45, 120, 22, 33, 50, 200, 18, 40, 25, 90, 88};
  
      std::cout << "总数据量: " << pings.size() << " 个\n";
  
      // 1. 计算中位数的索引
      // 比如 11 个数据，中位数索引就是 5 (即第 6 个元素)
      size_t mid_index = pings.size() / 2;
  
      // 2. 召唤 O(N) 的神：nth_element
      std::nth_element(
          pings.begin(), 
          pings.begin() + mid_index, // 你的目标位置
          pings.end()
      );
  
      // 3. 此时，中位数已经稳稳地坐在 mid_index 的位置上了
      int median_ping = pings[mid_index];
      
      std::cout << ">>> 网络延迟中位数 (P50): " << median_ping << " ms <<<\n\n";
  
      // 4. 验证魔法效果：看看此时数组变成了什么样子
      std::cout << "现在的数组状态:\n";
      
      std::cout << "左边 (<= " << median_ping << "): ";
      for (size_t i = 0; i < mid_index; ++i) {
          std::cout << pings[i] << " ";
      }
      
      std::cout << "\n[目标] " << pings[mid_index] << " \n";
      
      std::cout << "右边 (>= " << median_ping << "): ";
      for (size_t i = mid_index + 1; i < pings.size(); ++i) {
          std::cout << pings[i] << " ";
      }
      std::cout << "\n";
  
      return 0;
  }

• 重要注意事项：

  • 除 nth 位置外，其余元素是无序的。

  • 第 K 大元素可以用降序比较器实现：std::nth_element(v.begin(), v.end() - k, v.end())。

  • 比 partial_sort 更快但结果只有 nth 位置准确，适合只需中位数或 Top-K 值的场景。

15. 二分查找下界 std::lower_bound

• 头文件：<algorithm>

• 签名：std::lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp = less<>{})

• 复杂度：O(log⁡n)O(logn)（要求随机访问迭代器，否则为 O(n)O(n) 次比较）。

• 使用前，你的 vector 必须是排好序的（升序）！ 如果是乱序的，它会返回一个完全不可预测的错误结果。

  假设我们有一个排好序的数组（比如衣服的尺码）：

  std::vector<int> v = {10, 20, 30, 30, 50};

  场景 1：找的数字刚好在数组里

  你想找 30。数组里有两个 30，它会怎么做？

  C++

  auto it = std::lower_bound(v.begin(), v.end(), 30);
  int pos = std::distance(v.begin(), it); 
  
  // 结果：它会精确定位到【第一个】 30。
  // pos 的结果是 2。
  

  场景 2：找的数字不在数组里（找替代品/插入位置）

  你想找 25，但是数组里没有 25。

  C++

  auto it = std::lower_bound(v.begin(), v.end(), 25);
  int pos = std::distance(v.begin(), it); 
  
  // 结果：它会寻找第一个 >= 25 的数字，也就是 30。
  // pos 的结果依然是 2。
  // 业务应用：如果你要买 25 码的衣服没货，系统会自动给你推荐稍大一点的 30 码。
  

  场景 3：找的数字比数组里所有的数都大（容易出 Bug 的地方）

  你想找 99，数组里最大的才 50。

  C++

  auto it = std::lower_bound(v.begin(), v.end(), 99);
  
  // 结果：因为找不着任何 >= 99 的数字，它会直接返回 v.end()（数组越界位置）。
  // ⚠️ 致命错误警告：这时候你千万不能直接用 *it 去获取值，程序会直接崩溃！
  

  ---

  标准且安全的实战模板

  日常写代码时，为了防止“场景 3”导致程序崩溃，以及判断到底“有没有找到精确的数字”，你只需要背下这个固定模板：

  C++

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  int main() {
      std::vector<int> v = {10, 20, 30, 30, 50};
      int target = 30; // 你可以把这里改成 25, 99 试试看效果
  
      // 1. 查找
      auto it = std::lower_bound(v.begin(), v.end(), target);
  
      // 2. 安全检查与结果判断
      if (it == v.end()) {
          std::cout << "你要找的数字太大了，数组里所有的数都比它小！\n";
      } 
      else if (*it == target) {
          // 找到了完全一模一样的数字
          int pos = std::distance(v.begin(), it); // 或者直接用 it - v.begin() 也可以
          std::cout << "找到了！第一个等于 " << target << " 的位置是索引: " << pos << "\n";
      } 
      else {
          // 没找到一模一样的，但找到了第一个比它大的数字
          int pos = std::distance(v.begin(), it);
          std::cout << "没找到 " << target << "，但找到了第一个大于它的数字 " << *it 
                    << "，它的位置是索引: " << pos << "\n";
      }
  
      return 0;
  }

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 4, 6, 8};
  auto it = std::lower_bound(v.begin(), v.end(), 4);
  // it 指向第一个 ≥ 4 的元素（即 4）
  int pos = std::distance(v.begin(), it);  // pos == 2

• 重要注意事项：

  • 要求序列升序排列（或按给定比较器有序），否则行为未定义。

  • 返回第一个 ≥ value 的位置；若所有元素都小于 value，返回 last。

  • 降序序列需传入降序比较器。

std::set 与 std::map 的专属二分查找

• 易错点：千万不要写 std::lower_bound(s.begin(), s.end(), x)！虽然能编译通过，但由于 set 的迭代器不是随机访问迭代器，这行代码会在底层进行$O(N)$ 次遍历，导致直接 TLE。

• 正确做法：必须使用容器自带的成员函数。

C++

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s = {1, 3, 5, 7, 9};

    // ❌ 错误写法 (复杂度 O(N))
    // auto it = std::lower_bound(s.begin(), s.end(), 5);

    // ✅ 正确写法 (复杂度 O(log N))
    auto it = s.lower_bound(5); 

    if (it != s.end()) {
        cout << "找到了 >= 5 的最小值: " << *it << "\n";
    }

    return 0;
}

16. 二分查找上界 std::upper_bound

• 头文件：<algorithm>

• 签名：std::upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp = less<>{})

• 复杂度：O(log⁡n)O(logn)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 2, 2, 3};
  auto it = std::upper_bound(v.begin(), v.end(), 2);
  // it 指向第一个 > 2 的元素（即 3）
  int cnt = std::distance(v.begin(), it) 
            - std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), 2));
  // cnt = 3（值为 2 的元素个数）

• 重要注意事项：

  • 返回第一个 > value 的位置。

  • 与 lower_bound 配合使用可得到 [lower, upper) 等于 value 的元素范围（即 equal_range 的效果）。

17. 等值区间查找 std::equal_range

• 头文件：<algorithm>

• 签名：std::equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp = less<>{})

• 返回值：std::pair<ForwardIt, ForwardIt>，分别为 lower_bound 和 upper_bound 的结果。

• 复杂度：O(log⁡n)O(logn)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 2, 3, 3, 3, 4};
  auto [lb, ub] = std::equal_range(v.begin(), v.end(), 3);
  int cnt = std::distance(lb, ub);  // 3

• 批量处理相同标签的数据

  除了用来“数个数”（像你的代码那样用 std::distance），std::equal_range 最大的用途是把一堆一模一样的数据从大数组里“框”出来，然后进行批量修改或打印。

  业务场景： 假设你正在做一个商品评价系统。所有的评价按星级（1~5星）排好序了。现在老板说：“把所有的 3 星评价挑出来，给它们打个‘中评’的标签。”

  C++

  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <string>
  
  // 简单的评价结构体
  struct Review {
      int stars;
      std::string content;
      std::string tag; // 等待我们去打标签
  };
  
  int main() {
      // 假设这些评价已经按星级 (stars) 升序排列好了
      std::vector<Review> reviews = {
          {1, "太差了！", ""},
          {2, "一般般", ""},
          {3, "还行吧", ""},     // <-- 目标开始
          {3, "能用，但不惊艳", ""},
          {3, "凑合", ""},       // <-- 目标结束
          {4, "挺好的", ""},
          {5, "完美！绝绝子！", ""}
      };
  
      // 1. 使用 equal_range 框出所有 3 星评价
      // 注意：因为是自定义结构体，我们要提供 Lambda 告诉它按星级找
      auto [lb, ub] = std::equal_range(
          reviews.begin(), 
          reviews.end(), 
          3, // 找 3 星
          [](const Review& r, int target) { return r.stars < target; }
      );
  
      // 2. 批量处理这批数据 (给它们打上标签)
      // lb 到 ub 就是所有 3 星评价的地盘
      for (auto it = lb; it != ub; ++it) {
          it->tag = "【中评】";
      }
  
      // 3. 统计一下个数
      std::cout << "总共处理了 " << std::distance(lb, ub) << " 条 3 星评价。\n\n";
  
      // 打印全部结果看看效果
      for (const auto& r : reviews) {
          std::cout << r.stars << "星: " << r.content << " " << r.tag << "\n";
      }
  
      return 0;
  }
  

• 重要注意事项：

  • 等价于一次调用同时获取 lower_bound 和 upper_bound，比分别调用两次更高效。

  • 返回的 first 等于 last 表示 value 不存在。

18. 二分查找判定 std::binary_search

• 头文件：<algorithm>

• 签名：std::binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp = less<>{})

• 返回值：bool，表示 value 是否存在。

• 复杂度：O(log⁡n)O(logn)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 4, 8, 16};
  if (std::binary_search(v.begin(), v.end(), 4)) {
      // 4 存在于 v 中
  }

• 重要注意事项：

  • 仅返回布尔值，不返回位置。需要获取位置时直接用 std::lower_bound + 解引用比较，避免两次二分查询。

  • 标准用法：auto it = std::lower_bound(...); if (it != end && *it == value) { ... }。

三、极值、查找与判定 (Extremes, Query & Logic)

19. 查找特定元素 std::find

• 头文件：<algorithm>

• 签名：std::find(InputIt first, InputIt last, const T& value)

• 复杂度：O(n)O(n)（线性扫描）。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3, 4, 5};
  auto it = std::find(v.begin(), v.end(), 3);
  if (it != v.end()) {
      int pos = std::distance(v.begin(), it);
  }

• 重要注意事项：

  • 仅对已排序的数据才应考虑使用二分查找；无序数据只能用 find。

  • 使用 operator== 比较，自定义类型需重载 operator==。

20. 统计特定元素个数 std::count

• 头文件：<algorithm>

• 签名：std::count(InputIt first, InputIt last, const T& value)

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  int cnt = std::count(v.begin(), v.end(), 2);

• 重要注意事项：

  • 仅适用于精确匹配；需要条件统计时使用 std::count_if（传入谓词）。

  • 对 set/map 等关联容器，优先使用其成员函数 count()（O(log⁡n)O(logn)）。

21. 最大/最小元素 std::max_element / std::min_element

• 头文件：<algorithm>

• 复杂度：O(n)O(n)，精确比较 n−1n−1 次。

• 典型用法：

  cpp

  auto max_it = std::max_element(v.begin(), v.end());
  auto min_it = std::min_element(v.begin(), v.end());
  if (max_it != v.end()) { int maxVal = *max_it; }

• 重要注意事项：

  • 空范围返回 last 迭代器，务必检查后再解引用。

  • 多个最大元素时返回第一个的迭代器。

22. 一次遍历极值 std::minmax_element

• 头文件：<algorithm>

• 返回值：std::pair<ForwardIt, ForwardIt> — first 指向最小元素，second 指向最大元素。

• 复杂度：O(n)O(n)，最多 ⌊32(n−1)⌋⌊23​(n−1)⌋ 次比较。比分别调用 min_element + max_element 更高效。

• 典型用法：

  cpp

  auto [min_it, max_it] = std::minmax_element(v.begin(), v.end());
  if (min_it != v.end()) {
      int minVal = *min_it, maxVal = *max_it;
  }

• 重要注意事项：

  • 返回的是迭代器对，不是值本身，需要解引用。

  • 空范围时返回 {first, first}（两者均为 end()），直接解引用导致未定义行为。

  • 若容器只有一个元素，两个迭代器指向同一位置。

  • std::minmax 用于值/初始化列表，std::minmax_element 用于迭代器范围，不要混淆。

23. 条件全满足 std::all_of

• 头文件：<algorithm>

• 签名：std::all_of(InputIt first, InputIt last, UnaryPred p)

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  bool allPositive = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });

  优雅的字符串合法性校验 (all_of)

  竞赛题中经常需要处理非常脏的字符串输入，比如判断读入的字符串是否完全由数字组成。

  C++

  #include <iostream>
  #include <string>
  #include <algorithm>
  
  using namespace std;
  
  int main() {
      string s1 = "123456";
      string s2 = "123a45";
  
      // 结合 <cctype> 头文件里的 ::isdigit 极其优雅
      // 注意：::isdigit 前面有两个冒号，表示使用全局 C 标准库函数
      bool is_s1_num = all_of(s1.begin(), s1.end(), ::isdigit); // true
      bool is_s2_num = all_of(s2.begin(), s2.end(), ::isdigit); // false，遇到 'a' 瞬间短路退出
  
      if (is_s1_num) cout << "s1 是纯数字\n";
      return 0;
  }

24. 条件任意满足 std::any_of

• 头文件：<algorithm>

• 复杂度：O(n)O(n)，遇到第一个满足条件的元素即返回。

• 典型用法：

  cpp

  bool hasEven = std::any_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

  假设你在做一个迷宫 BFS 题，你需要快速检查某一行是否存在任何障碍物（比如 1 表示障碍物，0 表示空地）。

  C++

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  int main() {
      // 迷宫的一行
      vector<int> row = {0, 0, 0, 1, 0, 0};
  
      // 检查这一行是否有障碍物
      bool has_obstacle = any_of(row.begin(), row.end(), [](int cell) {
          return cell == 1; 
      });
  
      if (has_obstacle) {
          cout << "此路不通，有障碍物！\n";
      }
  
      return 0;
  }

25. 条件全不满足 std::none_of

• 头文件：<algorithm>

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  bool noneNegative = std::none_of(v.begin(), v.end(), [](int x) { return x < 0; });
  // 等价于 !std::any_of(...)

  假设你要检查一个玩家的装备列表，要求绝不能携带任何被诅咒的物品（负战力）。

  C++

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  int main() {
      vector<int> equipments = {50, 120, 300, 80}; // 战力值
  
      // 判定：没有任何一件装备是负战力
      bool safe = none_of(equipments.begin(), equipments.end(), [](int power) {
          return power < 0; 
      });
  
      if (safe) {
          cout << "装备检查通过，允许进入副本。\n";
      }
  
      return 0;
  }

四、数值与前缀和计算 (Numeric Algorithms)

本节函数定义于 <numeric> 头文件（除特别注明外）。

26. 累加求和 std::accumulate

• 签名：std::accumulate(InputIt first, InputIt last, T init, BinaryOp op = plus<>{})

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3, 4, 5};
  int sum = std::accumulate(v.begin(), v.end(), 0);          // 15
  int prod = std::accumulate(v.begin(), v.end(), 1,
               std::multiplies<>{});                          // 120
  // 字符串拼接
  std::vector<std::string> ws = {"a", "b", "c"};
  std::string cat = std::accumulate(ws.begin(), ws.end(), std::string{});

27. 并行归约 std::reduce

• 头文件：<numeric>（C++17 起）

• 签名：std::reduce(InputIt first, InputIt last, T init, BinaryOp op = plus<>{})
  （另有支持 ExecutionPolicy 的重载）

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  int sum = std::reduce(v.begin(), v.end());
  int sum2 = std::reduce(v.begin(), v.end(), 0);
  int max_val = std::reduce(std::execution::par, v.begin(), v.end(),
                              v[0], [](int a, int b) { return std::max(a, b); });

• 与 accumulate 的区别：

  • accumulate 严格从左到右计算（确定的运算顺序）。

  • reduce 运算顺序不确定（可并行），因此要求二元操作满足结合律和交换律，非交换/非结合操作（如字符串拼接）不要使用。

  • 支持 std::execution::par 策略实现并行加速。

28. 前缀和 std::partial_sum

• 签名：std::partial_sum(InputIt first, InputIt last, OutputIt d_first, BinaryOp op = plus<>{})

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> in = {1, 2, 3, 4};
  std::vector<int> out(in.size());
  std::partial_sum(in.begin(), in.end(), out.begin());
  // out: {1, 3, 6, 10}

• 重要注意事项：

  • 输出序列的第 i 个元素是输入前 i+1 个元素的累积结果（包含当前元素）。

  • 支持自定义二元运算（如乘法前缀积）。

29. 包含性前缀和 std::inclusive_scan

• 头文件：<numeric>（C++17 起）

• 签名：std::inclusive_scan(InputIt first, InputIt last, OutputIt d_first, BinaryOp op = plus<>{}, T init = *first)

• 复杂度：O(n)O(n)。

• 与 partial_sum 类似但提供更好的并行支持；partial_sum 在 C++17 之前就存在且确定顺序执行。

30. 排除性前缀和 std::exclusive_scan

• 头文件：<numeric>（C++17 起）

• 签名：std::exclusive_scan(InputIt first, InputIt last, OutputIt d_first, T init, BinaryOp op = plus<>{})

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> in = {1, 2, 3, 4};
  std::vector<int> out(in.size());
  std::exclusive_scan(in.begin(), in.end(), out.begin(), 0);
  // out: {0, 1, 3, 6}

• 重要注意事项：

  • 输出第 i 个元素是输入前 i 个元素的累积（不包含当前元素）。

  • 必须提供初始值 init，它同时也是输出序列的第一个元素。

  • 输出容器必须预先分配足够的空间（与输入长度相同），否则行为未定义。

31. 递增序列填充 std::iota

• 头文件：<numeric>（C++11 起）

• 签名：std::iota(ForwardIt first, ForwardIt last, T value)

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> v(5);
  std::iota(v.begin(), v.end(), 10);  // {10, 11, 12, 13, 14}
  // 常用于生成排列的初始序列
  std::vector<int> perm(5);
  std::iota(perm.begin(), perm.end(), 0);
  do { /* process permutation */ } while (std::next_permutation(perm.begin(), perm.end()));

32. 最大公约数 std::gcd

• 头文件：<numeric>（C++17 起）

• 签名：std::gcd(M m, N n)，返回 std::common_type_t<M, N>。

• 复杂度：O(log⁡min⁡(∣m∣,∣n∣))O(logmin(∣m∣,∣n∣))（欧几里得算法）。

• 典型用法：

  cpp

  int g = std::gcd(48, 18);  // 6
  long long lg = std::gcd(48LL, 18LL);

• 重要注意事项：

  • 输入必须为整数类型（包括有符号/无符号，但不包括 bool），否则程序格式错误。

  • 结果为非负值。

  • 配套函数 std::lcm（最小公倍数）同样于 C++17 引入。

五、序列操作与变换 (Sequence Operations)

33. 反转序列 std::reverse

• 头文件：<algorithm>

• 复杂度：O(n)O(n)，精确进行 n/2n/2 次交换。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3};
  std::reverse(v.begin(), v.end());  // {3, 2, 1}

34. 批量填充 std::fill

• 头文件：<algorithm>

• 复杂度：O(n)O(n)，精确进行 nn 次赋值。

• 典型用法：

  cpp

  std::vector<int> v(10);
  std::fill(v.begin(), v.end(), -1);  // 全部填 -1

• 重要注意事项：

  • 对于原始内存填充，std::fill 类型安全；memset 仅建议用于 POD 类型（且非零值填充可能出错）。

35. 复制序列 std::copy

• 头文件：<algorithm>

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> src = {1, 2, 3};
  std::vector<int> dest(src.size());
  std::copy(src.begin(), src.end(), dest.begin());
  // 动态扩容
  std::vector<int> dest2;
  std::copy(src.begin(), src.end(), std::back_inserter(dest2));

• 重要注意事项：

  • 目标容器必须预先分配足够空间，否则会导致内存越界写入。

  • 使用 std::back_inserter 可自动扩容（调用 push_back）。

36. 移除指定元素 std::remove

• 头文件：<algorithm>

• 核心机制：不改变容器大小，仅将"不删除"的元素前移，返回新逻辑结尾迭代器。必须配合 erase 才能实际删除。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 5, 3, 5, 4};
  // 移除所有 5
  auto newEnd = std::remove(v.begin(), v.end(), 5);
  v.erase(newEnd, v.end());  // {1, 2, 3, 4}

• 重要注意事项：

  • Erase-Remove 惯用法：v.erase(std::remove(v.begin(), v.end(), val), v.end());。

  • 条件移除使用 std::remove_if（传入谓词）。

37. 相邻去重 std::unique

• 头文件：<algorithm>

• 核心机制：将连续的重复元素前移，返回新逻辑结尾迭代器。仅移除相邻重复，通常需先排序再使用。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 2, 3, 3, 3, 4};
  std::sort(v.begin(), v.end());
  auto newEnd = std::unique(v.begin(), v.end());
  v.erase(newEnd, v.end());  // {1, 2, 3, 4}

• 重要注意事项：

  • Sort + Unique + Erase 是 C++ STL 容器去重的标准模式。

  • std::list 有成员函数 unique()，更直接高效。

  • 全局去重应使用 std::set 或 std::unordered_set。

38. 映射变换 std::transform

• 头文件：<algorithm>

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> in = {1, 2, 3};
  std::vector<int> out(in.size());
  // 一元变换：每个元素 × 2
  std::transform(in.begin(), in.end(), out.begin(),
                 [](int x) { return x * 2; });
  // 二元变换：逐元素相加
  std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
  std::transform(a.begin(), a.end(), b.begin(), out.begin(),
                 std::plus<>{});

39. 随机打乱 std::shuffle

• 头文件：<algorithm> + <random>（C++11 起）

• 复杂度：O(n)O(n)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3, 4, 5};
  std::random_device rd;
  std::mt19937 gen(rd());
  std::shuffle(v.begin(), v.end(), gen);

• 重要注意事项：

  • std::random_shuffle 已在 C++14 弃用、C++17 移除，必须使用 std::shuffle。

  • 必须传入随机数引擎（如 std::mt19937），不可省略。

40. 全排列生成 std::next_permutation

• 头文件：<algorithm>

• 返回值：bool — true 表示生成下一个字典序更大的排列；false 表示已到达最大排列并重置为最小排列。

• 复杂度：最多 O(n)O(n) 次交换。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3};
  do {
      for (int x : v) std::cout << x << " ";
      std::cout << "\n";
  } while (std::next_permutation(v.begin(), v.end()));
  // 输出：1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1

• 重要注意事项：

  • 输入序列必须先排序为最小排列，否则只会生成从当前排列起更大的排列。

  • 配套函数 std::prev_permutation 生成字典序更小的排列。

六、划分、归并与集合 (Partition, Merge & Sets)

41. 条件划分 std::partition

• 头文件：<algorithm>

• 复杂度：O(n)O(n) 次谓词调用，O(1)O(1) 额外空间。

• 典型用法：

  cpp

  std::vector<int> v = {1, 2, 3, 4, 5, 6};
  auto pivot = std::partition(v.begin(), v.end(),
      [](int x) { return x % 2 != 0; });
  // 奇数在前，偶数在后（内部顺序不保证）

• 重要注意事项：

  • 不稳定：满足/不满足条件的元素各自内部顺序不被保持。

  • 需要稳定划分时请用 std::stable_partition。

42. 稳定条件划分 std::stable_partition

• 头文件：<algorithm>

• 复杂度：O(n)O(n) 如果有足够额外内存，否则 O(nlog⁡n)O(nlogn) 次交换。

• 典型用法：

  cpp

  auto pivot = std::stable_partition(v.begin(), v.end(),
      [](int x) { return x % 2 != 0; });
  // 奇数在前且保持原顺序，偶数在后且保持原顺序

• 重要注意事项：

  • 保证了稳定性，但需要额外内存开销（或更多交换次数）。

43. 寻找划分分界点 std::partition_point

• 头文件：<algorithm>（C++11 起）

• 复杂度：O(log⁡n)O(logn) 次谓词调用。

• 典型用法：

  cpp

  auto pivot = std::partition_point(v.begin(), v.end(),
      [](int x) { return x % 2 != 0; });
  // 返回第一个不满足谓词的位置

• 这段关于 std::partition_point 的总结非常精炼！在算法竞赛和现代 C++ 开发中，它是一个常常被低估、但一旦用好就能极大提升代码优雅度的“高级二分利器”。

  你提到它是 lower_bound 的更一般形式，这是极其准确的。为了让你在竞赛中能肌肉记忆般地运用它，我们来把它的底层逻辑和不可替代的实战场景彻底打通。

  ---

  一、 核心原理解析：寻找“楚河汉界”

  std::partition_point 的本质，是在一个已经被划分为两派的数组中，找出它们的分界线。

  想象你的数组经过某个条件（谓词）判断后，结果变成了这样：

  [ True, True, True, True, False, False, False ]

  std::partition_point 会用$O(\log N)$ 的极快速度（二分查找），精准定位到第一个 False 的位置。

  • 前提条件（生死线）： 数组必须是 [全 True, 全 False] 的排布。如果是 [True, False, True] 这种交替的，它会直接迷失，返回错误结果。

  ---

  二、 为什么有了 lower_bound 还要它？（竞赛痛点）

  在竞赛中，我们经常对结构体（Struct）组成的数组进行操作。

  假设你有一个怪物数组，按等级排好序了。你想找到第一个血量$> 500$ 的怪物。

  如果你用 std::lower_bound，会极其痛苦，因为你要么得重载乱七八糟的比较运算符，要么得强行构造一个“假怪物”作为基准去比较：

  C++

  // lower_bound 的痛苦写法：被迫造一个假数据
  Monster dummy = {0, 500, ""};
  auto it = std::lower_bound(monsters.begin(), monsters.end(), dummy, [](const Monster& a, const Monster& b){
  return a.hp < b.hp;
  });
  

  而 std::partition_point 就是为了拯救这种局面而生的！ 它不需要你传入任何用来比较的“实体值”，只需要你描述一个规则。

  ---

  三、 实战案例：优雅处理复杂结构体

  让我们用一段完整的代码，看看它有多干净：

  C++

  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <string>
  
  struct Monster {
      std::string name;
      int level;
      int hp;
  };
  
  int main() {
      // 假设怪物已经按等级 (level) 升序排好
      std::vector<Monster> monsters = {
          {"史莱姆", 1, 50},
          {"哥布林", 5, 200},
          {"兽人", 10, 800},     // <-- 分界点在这里！
          {"巨魔", 15, 1500},
          {"黑龙", 50, 99999}
      };
  
      // 我们的条件是：血量 <= 500 (符合这个条件的在左边，不符合的在右边)
      // partition_point 会返回【第一个】打破这个规则（即血量 > 500）的怪物！
      
      auto it = std::partition_point(
          monsters.begin(), 
          monsters.end(),
          [](const Monster& m) { return m.hp <= 500; } // 描述左半部分的共同特征
      );
  
      if (it != monsters.end()) {
          std::cout << "你遇到的第一个高血量(>500)怪物是: " 
                    << it->name << "，血量: " << it->hp << "\n";
      }
  
      // 结果预期：输出“兽人，血量: 800”
      return 0;
  }
  

• 重要注意事项：

  • 要求范围已按谓词划分。是 std::lower_bound 的更一般形式。

  • 若范围未正确划分，行为未定义。

44. 原地归并两个有序段 std::inplace_merge

• 头文件：<algorithm>

• 复杂度：有足够额外内存时为 O(n)O(n)，否则 O(nlog⁡n)O(nlogn)。

• 典型用法：

  cpp

  std::vector<int> v = {1, 4, 7, 2, 5, 8};
  // 前 3 个和后 3 个分别有序
  std::inplace_merge(v.begin(), v.begin() + 3, v.end());
  // {1, 2, 4, 5, 7, 8}

• 重要注意事项：

  • 两段必须连续且各自有序，且使用相同的排序规则。

  • 是稳定的：相等元素的相对顺序被保留。

45. 集合交集 std::set_intersection

• 头文件：<algorithm>

• 复杂度：O(n+m)O(n+m)。

• 典型用法：

  cpp

  std::vector<int> a = {1, 2, 4, 5}, b = {2, 3, 5, 7};
  std::vector<int> result;
  std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                        std::back_inserter(result));
  // result: {2, 5}

• 重要注意事项：

  • 两个输入范围必须已升序排列。

  • 目标容器需预分配空间或使用 back_inserter。

46. 集合并集 std::set_union

• 头文件：<algorithm>

• 复杂度：O(n+m)O(n+m)。

• 典型用法：

  cpp

  std::vector<int> a = {1, 2, 5}, b = {2, 3, 5, 7};
  std::vector<int> out;
  out.resize(a.size() + b.size());
  auto it = std::set_union(a.begin(), a.end(), b.begin(), b.end(), out.begin());
  out.resize(it - out.begin());  // {1, 2, 3, 5, 7}

• 重要注意事项：

  • 两个输入范围必须已升序排列，否则行为未定义。

  • 输出到 std::set 时需使用 std::inserter(result, result.end())，不能用 begin()（set 的迭代器不支持直接赋值写入）。

七、底层堆操作与特殊工具 (Heap & Utilities)

以下堆操作定义于 <algorithm> 头文件。

47. 数组原地建堆 std::make_heap

• 复杂度：O(n)O(n)，最多 3n3n 次比较。

• 典型用法：

  cpp

  std::vector<int> v = {3, 1, 4, 1, 5, 9};
  std::make_heap(v.begin(), v.end());              // 大顶堆
  std::make_heap(v.begin(), v.end(), std::greater<>{}); // 小顶堆

• 重要注意事项：

  • 默认构建大顶堆。top() 等价于 v.front()。

  • 要求随机访问迭代器。

48. 堆中插入 std::push_heap

• 复杂度：O(log⁡n)O(logn)。

• 典型用法：

  cpp

  v.push_back(7);
  std::push_heap(v.begin(), v.end());

• 重要注意事项：

  • 调用前需先通过 push_back 将元素添加到末尾。

  • 要求 [first, last-1) 已是有效堆。

49. 堆顶出队 std::pop_heap

• 复杂度：O(log⁡n)O(logn)。

• 典型用法：

  cpp

  std::pop_heap(v.begin(), v.end());  // 将最大值移到末尾
  int max_val = v.back();
  v.pop_back();                        // 实际删除

• 重要注意事项：

  • pop_heap 不删除元素，仅将根元素交换到末尾并重建堆，必须手动 pop_back() 完成删除。

50. 字符串与数字互转

典型用法：

cpp

std::string s = std::to_string(42);           // "42"
std::string s2 = std::to_string(3.14159);      // "3.141590"
int x = std::stoi("123");                     // 123
long long y = std::stoll("9876543210");       // 9876543210
double d = std::stod("2.71828");               // 2.71828

重要注意事项：

• std::stoi / std::stoll / std::stod 在无法转换时抛出 std::invalid_argument，超出范围时抛出 std::out_of_range，建议使用 try-catch。

• 竞赛中常用 stoi 和 to_string 进行快速输入/输出转换。

• stoi 比 C 语言的 atoi 更安全（有异常检测），但 atoi 解析失败时静默返回 0。

• to_string 对浮点数的精度有限（默认 6 位有效数字），高精度需求请使用 std::ostringstream 或 std::format（C++20）。

八、竞赛开挂宏 (GCC Built-in Functions)

以下函数为 GCC/Clang 编译器内置函数，无需头文件，无需 std:: 前缀，直接调用即可。它们通常编译为单条 CPU 指令（如 POPCNT、TZCNT），性能远超手动循环实现。

51. 二进制中 1 的个数

典型用法：

cpp

int cnt = __builtin_popcount(0b10100101);   // 4
int cnt64 = __builtin_popcountll(0xF0000000000000FFULL); // 12

52. 二进制末尾 0 的个数（Count Trailing Zeros）

典型用法：

cpp

int tz = __builtin_ctz(12);  // 12 二进制 1100，末尾 2 个 0 → 结果 2

53. 二进制前导 0 的个数（Count Leading Zeros）

典型用法：

cpp

int lz = __builtin_clz(0x00080000);  // 11

54. 其他常用内置函数

综合示例：

cpp

unsigned int x = 0b1010010100;
// 1 的个数
int pc = __builtin_popcount(x);          // 4
// 最低位 1 的位置（1-based）
int ffs = __builtin_ffs(x);              // 3（最低位 1 在第 3 位）
// 末尾 0 的个数
int tz = __builtin_ctz(x);               // 2
// 判断是否为 2 的幂
bool isPow2 = __builtin_popcountll(x) == 1;

核心注意事项：

• __builtin_ctz(0) 和 __builtin_clz(0) 的行为是未定义的（不同平台可能返回不同值），使用前必须检查参数是否为 0。

• 若需包括 0 的安全版本，可封装：

  cpp

  inline int safe_ctz(unsigned int x) {
      return x == 0 ? 32 : __builtin_ctz(x);
  }

• 这些函数为 GNU 扩展（GCC/Clang），在 MSVC 上不可用；MSVC 中对应的内建函数为 __popcnt、_BitScanForward/_BitScanReverse 等，需要在跨平台项目中通过条件编译处理。

• 编译器会自动优化为单条 CPU 指令，比手动用循环或位运算实现快几个数量级。

九、C++ 代码中的数字直接表示法

在代码里给变量赋值时，你可以直接写不同进制的数字。从 C++14 开始，官方终于加入了原生二进制表示法：

C++

int dec_val = 42;        // 十进制 (默认)
int hex_val = 0x2A;      // 十六进制 (以 0x 开头)
int oct_val = 052;       // 八进制 (⚠️ 极易踩坑：以数字 0 开头)
int bin_val = 0b101010;  // 二进制 (C++14 引入，以 0b 开头)

// 小贴士：C++14 还支持单引号作为数字分隔符，方便数 0
int big_bin = 0b1100'1010'1111'0000; 

55. 核心转换：字符串与数字的互转

日常开发中最常见的需求是：读取了一个特定进制的字符串，要把它转成整数计算；计算完后，又需要把它以特定进制打印出来。

1. 字符串 ➡️ 数字 (解析进制)

现代 C++ 首选 std::stoi (String TO Integer) 或 std::stoll (针对 long long)。它的第三个参数可以直接指定原字符串是几进制！

C++

#include <iostream>
#include <string>

int main() {
    std::string bin_str = "1010";
    std::string hex_str = "FF";

    // std::stoi(字符串, 停止位置指针(通常填nullptr), 进制基数)
    int a = std::stoi(bin_str, nullptr, 2);  // 二进制转十进制 -> 10
    int b = std::stoi(hex_str, nullptr, 16); // 十六进制转十进制 -> 255

    std::cout << a << " " << b << "\n";
    return 0;
}

2. 数字 ➡️ 字符串/输出 (格式化进制)

这里要分情况：十六进制/八进制有原生流控制符，而二进制需要借助工具。

• 十六进制 / 八进制： 使用 std::hex 和 std::oct。

• 二进制： C++ 没有原生 std::bin 流控制符，最标准的做法是使用 std::bitset。

C++

#include <iostream>
#include <bitset>
#include <sstream>

int main() {
    int num = 255;

    // 1. 转十六进制和八进制 (直接影响 cout 输出状态)
    std::cout << "十六进制: " << std::hex << num << "\n"; // 输出 ff
    std::cout << "八进制: " << std::oct << num << "\n";   // 输出 377
    std::cout << std::dec; // ⚠️ 记得切回十进制！否则后面的数字全乱套

    // 2. 转二进制字符串 (使用 std::bitset，需要指定位宽，比如 8 位)
    std::string bin_str = std::bitset<8>(num).to_string();
    std::cout << "二进制: " << bin_str << "\n"; // 输出 11111111

    return 0;
}

💡 进阶提示：如果你使用的是 C++20 及以上版本，有了 std::format，一切都变得像 Python 一样简单了：std::format("{:b}", 255) 直接输出 "11111111"。

56. 进制操作（位操作）实战指南

位操作直接作用于二进制层，速度极快（CPU 指令级支持）。这 6 个符号必须烂熟于心：

• & (按位与)：有 0 出 0，全 1 出 1。

• | (按位或)：有 1 出 1，全 0 出 0。

• ^ (按位异或)：相同为 0，不同为 1。

• ~ (按位取反)：0 变 1，1 变 0。

• << (左移)：各二进位全部左移若干位，低位补 0。

• >> (右移)：各二进位全部右移若干位。

（实战技巧）：

技巧 1：判断奇偶数 (代替 % 2)

C++

int n = 5;
if (n & 1) {
    // 奇数 (因为二进制最后一位是 1)
} else {
    // 偶数
}

技巧 2：乘以或除以 2 的次幂 位移操作比乘除法快得多，常用于底层性能优化。

C++

int n = 10;
int mul = n << 1; // 相当于 n * 2  -> 20
int div = n >> 1; // 相当于 n / 2  -> 5

技巧 3：交换两个变量（无需中间变量） 经典面试题，利用异或 A ^ A = 0 的特性。

C++

int a = 10, b = 20;
a = a ^ b;
b = a ^ b; // 此时 b 变成 10
a = a ^ b; // 此时 a 变成 20

技巧 4：特定位的“增删改查” (位掩码 Bit Masking) 这在配置系统、权限判定或者单片机操作寄存器时是绝对的刚需。

C++

#include <iostream>
#include <bitset>

int main() {
    // 假设 8 位二进制代表 8 个不同开关的状态
    unsigned char status = 0b00001010; // 初始状态

    // 1. 【查】判断第 1 位（从 0 开始算右数第二位）是否为 1
    // 将 1 左移 1 位凑出掩码 0b00000010，然后进行 & 操作
    bool isOn = (status & (1 << 1)) != 0; 
    
    // 2. 【增】将第 2 位置为 1 (用 |)
    status = status | (1 << 2); 
    
    // 3. 【删】将第 1 位置为 0 (用 & 和 ~)
    status = status & ~(1 << 1); 
    
    // 4. 【反转】将第 3 位状态取反 (用 ^)
    status = status ^ (1 << 3); 

    std::cout << "最终状态: " << std::bitset<8>(status) << "\n";
    return 0;
}

57. 判断一个「字符」(char) 是不是数字

这是最基础的，C++ 标准库在 <cctype> 头文件中提供了一系列字符分类函数。

• 核心函数： isdigit(char c)

• 返回值： 如果是 '0' 到 '9' 之间的字符，返回非零值（true）；否则返回 0（false）。

C++

#include <iostream>
#include <cctype> // 必须包含这个头文件

using namespace std;

int main() {
    char c1 = '7';
    char c2 = 'a';

    if (isdigit(c1)) {
        cout << c1 << " 是数字\n";
    }

    if (!isdigit(c2)) {
        cout << c2 << " 不是数字\n";
    }

    return 0;
}

58.判断一个「字符串」(string) 是不是数字

判断字符串要复杂一点，因为你要区分你是只需要“纯数字”，还是需要允许“负号”或“小数点”。

场景 1：严格的纯数字（非负整数，如 "12345"）

这是最优雅的写法，直接结合咱们之前讲的 std::all_of 和 isdigit。

C++

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

int main() {
    string s1 = "123456";
    string s2 = "123a45";

    // ⚠️ 注意这里的 ::isdigit
    // 因为 C++ 中有多个版本的 isdigit，加上 :: 表示明确使用全局 C 标准库里的那个
    bool is_pure_num = all_of(s1.begin(), s1.end(), ::isdigit);

    cout << s1 << (is_pure_num ? " 是纯数字" : " 不是纯数字") << "\n";
    
    return 0;
}

场景 2：允许负号和正号的整数（如 "-123", "+456"）

在算法竞赛中，读入的数据经常带有负号。此时纯 all_of 会把 '-' 误杀。我们需要手动跳过第一个符号位。

C++

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

bool isInteger(const string& s) {
    if (s.empty()) return false; // 空字符串直接 false

    // 如果第一个字符是 + 或 -，我们的检查起点就从索引 1 开始，否则从 0 开始
    size_t start = (s[0] == '-' || s[0] == '+') ? 1 : 0;

    // 必须确保除了符号位之外，还有其他字符（防止只有单个 "-" 或 "+"）
    if (start >= s.length()) return false;

    // 检查剩下的部分是不是全为数字
    return all_of(s.begin() + start, s.end(), ::isdigit);
}

int main() {
    cout << "-1234 : " << isInteger("-1234") << "\n"; // true
    cout << "+567  : " << isInteger("+567") << "\n";  // true
    cout << "123a  : " << isInteger("123a") << "\n";   // false
    cout << "-"     : " << isInteger("-") << "\n";      // false (极易错的边界情况)
    return 0;
}

场景 3：工业级做法（判断浮点数或极大数值）

如果你在做工程开发，允许科学计数法（如 1.2e5）或者带有小数点的数字，自己写规则会非常麻烦且容易漏掉边界（比如 12.3.4 有两个点）。

此时，直接用 std::stod（转 double）配合 try-catch 是最稳妥的：

C++

#include <iostream>
#include <string>

using namespace std;

bool isNumeric(const string& s) {
    try {
        size_t pos;
        stod(s, &pos); // 尝试将其转换为 double
        
        // 确保转换耗尽了整个字符串 (防止 "123abc" 前半部分被成功转换的情况)
        return pos == s.length(); 
    } catch (...) {
        // 如果抛出 invalid_argument 或 out_of_range 异常，说明不是数字
        return false; 
    }
}

int main() {
    cout << "-3.14  : " << isNumeric("-3.14") << "\n";   // true
    cout << "1.2e-5 : " << isNumeric("1.2e-5") << "\n";  // true
    cout << "12.3.4 : " << isNumeric("12.3.4") << "\n";  // false
    return 0;
}

十、 核心数学运算 (The Heavy Artillery) ➡️ <cmath>

这是 C++ 最古老也是最强大的数学基石，处理绝大多数浮点数运算。

59. 基础算术与极值

• 绝对值：std::abs(x)

  ⚠️ 易错点：C 语言时期整数用 <cstdlib> 的 abs，浮点数用 <cmath> 的 fabs。在现代 C++ 中，统一包含 <cmath> 并使用 std::abs，编译器会通过函数重载自动推导类型。

• 取整三剑客：

  • std::ceil(x)：向上取整（天花板），如 ceil(3.1)$\rightarrow 4.0$。

  • std::floor(x)：向下取整（地板），如 floor(3.9)$\rightarrow 3.0$。

  • std::round(x)：四舍五入。

• 浮点余数：std::fmod(x, y)。处理小数求余时必须用它，不能用 % 操作符。

60. 指数与对数

• 幂运算：std::pow(x, y) 计算$x^y$。

  ⚠️ 竞赛大坑：pow 的返回值是浮点数（double），存在精度误差！绝对不要用 pow 来计算大整数的幂（比如$2^{60}$），整数幂请手写$O(\log n)$ 的快速幂算法。

• 开方：std::sqrt(x) 计算$\sqrt{x}$，std::cbrt(x) 计算立方根$\sqrt[3]{x}$。

• 对数：

  • std::log(x)：以自然常数$e$ 为底的对数（即$\ln x$）。

  • std::log10(x)：以 10 为底。

  • std::log2(x)：以 2 为底。

61. 几何与三角函数 (防溢出神器)

• 安全斜边 / 欧几里得距离：std::hypot(x, y)

  底层魔法：计算$\sqrt{x^2 + y^2}$。手动写 sqrt(x*x + y*y) 时，若 x 和 y 很大，平方操作极易导致数值溢出（Overflow）。hypot 在底层做了缩放防御，绝对安全。C++17 甚至支持三维距离 std::hypot(x, y, z)。

• 全角反正切：std::atan2(y, x)

  实战价值：计算坐标$(x, y)$ 的极角，范围是$[-\pi, \pi]$。永远不要用 atan(y / x)，因为它处理不了 x = 0 的除零崩溃，且无法区分所在象限。

62. 融合乘加 (Fused Multiply-Add)

• 高精度乘加：std::fma(x, y, z)

  底层魔法：计算$x \times y + z$。普通的 x * y + z 会发生两次浮点舍入误差。fma 调用 CPU 的 FMA 硬件指令，只在最后进行一次舍入，精度更高且速度极快。

63. 数论利器 (C++17 引入)

• 最大公约数：std::gcd(m, n)

• 最小公倍数：std::lcm(m, n)

⚠️ 竞赛福音：告别手写辗转相除法，直接调用标准库，底层经过高度优化。

64. 位运算

• 算“1”的个数：std::popcount(x)

  底层魔法：返回无符号整数二进制表示中 1 的个数。直接调用 CPU 指令，跨平台且速度极快。

• 2的幂次判定：std::has_single_bit(x)

  底层魔法：检查 x 是否是 2 的幂次方（即二进制中只有一个 1）。取代古老的位运算魔法 x && !(x & (x - 1))。

• 向上取2的幂：std::bit_ceil(x)

  实战价值：找到大于等于 x 的最小的 2 的幂次方。在给哈希表、内存池、线段树分配空间时非常关键。