平时写代码，最常听到的一句话就是“STL里啥都有，别整天造轮子”。但真到用的时候，不少人面对一长串算法头文件，却只认识 sort 和 find。今天借一个学习笔记类的话题，把两个非常实用、但经常被低估的算法 ——merge（合并）和reverse（反转）彻底讲透。它们一个负责把有序数据快速融合，一个负责把序列原地调头，看似简单，背后牵扯的迭代器类别、稳定性语义和泛型设计思路，才是真正值得花时间琢磨的东西。
这个话题适合谁看？我建议这几类人重点留意：一是刚把 C++ 语法过完一遍、准备系统啃算法库的初学者；二是写过一些业务代码，但一遇到“两个有序表合成一个”“列表要倒序展示”之类的需求，还在用循环硬怼的开发者；三是在校生，准备面试时被问到“归并排序的核心子过程”或者“std::reverse 为什么不能在单链表上直接用”这类问题。文章不会只贴代码就完事，我会把接口背后的原理、我和同事在项目中踩过的坑，以及完整的可编译示例都放在后面，尽量让每个看完的人都能直接照着用。
1. 整体思路：两个算法在STL里的定位
1.1 先澄清一个概念：merge严格来说不算排序算法
项目标题用的是“常用排序算法”这个说法，这点我得先较个真：在 C++ 标准库里，严格意义上的排序算法是 sort、stable_sort、partial_sort、nth_element 这些。merge 干的事情叫做“归并”，它默认输入区间必须已经有序，输出结果才有序。换句话说，merge 是排序工作流里“最后一公里”的粘合剂，而不是从无序到有序的那个起点。
这个区分很重要，因为很多人学 merge 的时候会犯迷糊：既然 merge 也能让结果有序，那它能不能替代 sort？不行。sort 的核心是基于快速排序的内省排序，平均复杂度 O(n log n)，面对的是无序输入；merge 是基于线性扫描，复杂度 O(n + m)，但要求输入有序。这就像做菜，sort 是“从食材零基础开始炒出一盘菜”，merge 是“把两锅已经做好的菜拼盘摆好”，职责完全不同。
也正因为 merge 能在线性时间内完成合并，它成了归并排序算法的灵魂子过程。手写归并排序的时候，你把一个数组拆成两半、各自排序，最后合并的那一步，本质上就是在调 merge 的逻辑。理解这一点，再回头看你以前背过的归并排序模板，很多细节会一下子通掉。
1.2 什么业务场景会用到这两个算法
merge 的典型场景，我平时接触得最多的有这么几类：
- 多路有序数据合并。比如多个分片日志文件，每个文件内部按时间戳有序，要汇总成一份全局有序的日志，直接两两 merge 就能搞定，没必要全部读进内存重新 sort。我们以前做一个离线日志分析工具，一天几十个文件，就是靠 merge 一层层合成的，内存占用很小。
- 增量更新场景。程序启动时加载一份全量有序配置，运行过程中又来了一批增量配置（这批增量也保持有序），你希望合并成一份新配置，merge 就是最稳的做法。
- 数据库/搜索引擎里归并倒排链。这类后端场景普通人接触不到，但原理完全一样——多个有序 id 列表求并集，merge 的变体是核心操作。
reverse 的场景就更直白了：
- 展示层需要倒序列表、倒序遍历数据。
- 字符串反转、回文判断等经典面试题。
- 某些算法里需要逆序处理步骤，比如从结果反推来源。
- 和 sort 搭配做降序输出：可以先按升序排序，再 reverse 一下，虽然效率不如直接给 sort 传 greater 比较器，但有些场景下逻辑会更清晰。
这两个算法一个处理“有序结构的融合”，一个处理“序列方向的翻转”，用途都很基础，但当你真正高频地使用标准库而不是手写循环时，代码的稳定性和可读性都会上一个台阶。
2. 核心细节：接口、原理与选型参考
2.1 merge 的接口形态与底层推进逻辑
merge 在标准库里的声明一般是下面两组重载，定义在<algorithm>头文件中：
template<class InputIt1, class InputIt2, class OutputIt> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first); template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp);两个输入区间用两对迭代器指定，分别叫做 first1/last1 和 first2/last2，输出端给一个目标区间的起始迭代器 d_first。没有 comp 参数的版本用 operator< 做比较，有 comp 的版本允许你自定义排序规则，比如合并两段按降序排列的数据、合并结构体数组等。
底层逻辑其实不复杂：两个指针（或者迭代器）分别指向两个区间的头部，每次比较当前指向的元素，谁小就把谁写到输出位置，然后对应指针前进一位。某一区间走完之后，直接把另一个区间的剩余元素全部拷贝到输出位置。这个流程决定了三件事：
第一，merge 需要输出区间有足够的容量。它不会自己扩容，如果你把目标放在一个空的 vector 里而不预先 reserve，代码会直接崩，或者使用 back_insert_iterator 这类插入迭代器自动扩展。
第二，merge 是稳定算法。这里的“稳定”指的是，如果两个区间里存在值相等的元素，最终输出里，第一个区间的元素会排在第二个区间的前面。这个语义在归并排序里尤其重要，重点要先记下来：merge 天然是稳定归并。
第三，merge 的两个输入区间都必须是前向迭代器（ForwardIterator）或更强。它要求能反复读取、递增比较，所以像单向链表 std::forward_list 的迭代器也能用；相比之下，reverse 的要求反而更高，后面再说。
2.2 inplace_merge 与函数式组合的延伸
除了把结果写到新位置的 merge，标准库还提供了一个就地版本：inplace_merge。它的典型用法是，一个区间内部恰好由两段有序数据拼接而成，比如 [first, middle) 有序、[middle, last) 也有序，你想让整个 [first, last) 变成完全有序，不额外开一块大空间。
template<class BidirIt> void inplace_merge(BidirIt first, BidirIt middle, BidirIt last);inplace_merge 的名字起的很直白——“在原始位置合并”。它有两种常见命运：如果内部剩余空间足够，它会尝试借助缓冲区（比如调用方预分配的临时内存）完成合并；空间不够的时候，算法会退化成一种更慢的原地归并。换言之，它的时间复杂度和空间占用都比较灵活，使用时要心里有数：没有额外缓冲时，性能可能明显下降。
在实战里，我把 merge 和 sort、unique、copy_if 这些算法组合起来用，效果出奇地好。比如要先合并，再去重，再筛选符合条件的元素，一行链式调用就能写清楚。标准库算法的组合能力，恰恰是手写循环最大的劣势——手写代码一长，逻辑噪音一堆，维护起来很痛苦。
2.3 reverse 的接口限制与 reverse_copy 的补偿
reverse 的接口比 merge 简单很多：
template<class BidirIt> void reverse(BidirectionalIterator first, BidirectionalIterator last);它的语义是：把 [first, last) 区间里的元素顺序原地翻转，第一个变最后一个，最后一个变第一个。这里要注意核心限制：reverse 要求输入迭代器至少是双向迭代器（BidirectionalIterator）。这就是我在开头提到的关键点——像 std::forward_list（单链表）只有前向迭代器，不能直接对整个链表调用 std::reverse；但 std::list 有双向迭代器，可以用。
很多人会想，单链表反转不是很容易吗？把指针指来指去不就行了。但标准库这里的设计哲学是：算法只通过迭代器接口操作元素，不直接触碰容器的内部指针结构。对于前向链表，要反转节点关系就得动容器内部结构，所以 std::forward_list 自己提供了一个成员函数 reverse()，专门干这件事。这种“算法和容器解耦、特殊情况容器自备成员函数”的设计，是 STL 非常重要的一种风格，理解它你才不容易写出“明明迭代器类型不对还硬调”的编译错误。
reverse 的实现复杂度是 O(n)，元素被交换的次数大约是区间长度的一半。它不会返回值，直接操作原区间。如果你的原始数据还要留着，可以考虑reverse_copy：
template<class BidirIt, class OutputIt> OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first);reverse_copy 是“边反转边拷贝”的实用工具：从源区间尾部开始向头部遍历，把每个元素顺序写入目标区间。这样你可以保留原容器不变，同时得到一个逆序副本。反过来，如果你有几份数据要同时反转，也可以各调各的 reverse，然后直接继续用。
2.4 C++20 ranges 版本带来的新写法
如果你是 C++20 及以上环境，标准库还提供了 ranges 命名空间下的重载：
std::ranges::merge(first1, last1, first2, last2, out); std::ranges::reverse(vec.begin(), vec.end());有的编译器还支持直接传容器名，配合视图和管道操作符，比如把一个算法串联起来。ranges 版本最大的优势是：接口更安全、组合性更强、代码阅读起来更接近自然语言。如果你的项目编译器比较新，我建议优先用 ranges 风格写新代码；如果是老项目、老标准，那还是 std:: 名字空间下的经典接口稳妥。
3. 实操：完整示例与运行解析
3.1 环境准备与基础框架
在展开代码之前，先说下环境：我测试用的是一台 Linux 机器，GCC 版本支持 C++17，编译命令是g++ -std=c++17 -O2 -Wall main.cpp -o demo。如果是 Windows 上用 Visual Studio，选 x64 的 Debug 或 Release 都行，C++ 标准设为 C++17 即可。下面的示例不依赖第三方库，用标准头文件就能跑。
正式开始前，先列一下会用到的头文件：
#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <iterator>说明一下各头文件的用途：
<algorithm>是今天的主角所在地：std::merge、std::reverse、std::reverse_copy、std::inplace_merge、std::sort。<vector>、<list>、<string>都是我们要操作的容器类型。<iterator>主要为了用 std::back_inserter，它能让输出容器在写入时自动扩展空间。<iostream>用来打印结果。
3.2 merge 合并有序序列的完整示例
我先写一个最经典的 merge 示例：合并两个有序 vector。
int main() { // 两个已经升序排列的 vector std::vector<int> left = {1, 3, 5, 5, 7, 9}; std::vector<int> right = {2, 4, 5, 6, 8}; // 输出容器先空着，用 back_inserter 自动扩容 std::vector<int> result; // 调 merge，把 left 和 right 合并到 result std::merge(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(result)); // 打印结果 std::cout << "merge result: "; for (int x : result) { std::cout << x << ' '; } std::cout << '\n'; return 0; }运行结果是：
merge result: 1 2 3 4 5 5 5 6 7 8 9我自己调试这段代码的时候，第一次把输出位置写成了result.begin()，结果程序直接崩了——因为 result 是空的，begin() 根本没有可写空间。后来换成std::back_inserter(result)才算正常。初学者建议优先背下这个写法：当目标容器是空的或者不确定容量时，用 back_inserter 包裹容器作为输出迭代器。
3.3 reverse 反转容器的完整示例
reverse 的用法没有 merge 那么多弯弯绕绕，直接操作容器区间：
int main() { std::vector<int> vec = {10, 20, 30, 40, 50}; // 原地反转 std::reverse(vec.begin(), vec.end()); std::cout << "reversed vector: "; for (int x : vec) std::cout << x << ' '; std::cout << '\n'; // 字符串反转 std::string s = "hello good sir"; std::reverse(s.begin(), s.end()); std::cout << "reversed string: " << s << '\n'; return 0; }输出：
reversed vector: 50 40 30 20 10 reversed string: ris doog olleh这里顺便提醒一句：字符串内容如果是普通 ASCII，反转后结果正常；如果里面夹了中文等多字节字符，直接用 reverse 按字节翻转，会得到乱码。这个问题我单独放在第四部分详细说，因为真的很常见，也很坑。
如果你想保留原数组，又想要一个逆序版本，可以直接用 reverse_copy：
std::vector<int> origin = {5, 4, 3, 2, 1}; std::vector<int> copy; std::reverse_copy(origin.begin(), origin.end(), std::back_inserter(copy)); // 输出 origin 还是 {5,4,3,2,1} // copy 为 {1,2,3,4,5}有一说一，这个函数在一些“既要正向又要反向数据”的场景里非常省事，比如做双向列表展示时，一份数据拉两份倒序副本，完事。
3.4 进阶组合：排序、合并与反转的综合实验
很多实际需求不是单独调一个算法就能解决的，而是几个算法连起来用。我平时做过不少这类调研，所以这里安排一个综合性更强的 demo，把 sort、merge、reverse 串起来演示一遍，方便你理解它们之间的关系。
场景：现在有两组用户评分数据，每组内部都是乱序的。我希望把它们合成一组整体按“分数从高到低”排列的数据。
int main() { // 第一组评分数据，乱序 std::vector<int> groupA = {85, 90, 78, 95, 88}; // 第二组评分数据，乱序 std::vector<int> groupB = {99, 72, 93, 81, 76}; // 第一步：各自排序（升序） std::sort(groupA.begin(), groupA.end()); std::sort(groupB.begin(), groupB.end()); // 第二步：升序合并 std::vector<int> merged; std::merge(groupA.begin(), groupA.end(), groupB.begin(), groupB.end(), std::back_inserter(merged)); // 第三步：整体反转，变成降序 std::reverse(merged.begin(), merged.end()); // 打印 std::cout << "high -> low scores: "; for (int s : merged) { std::cout << s << ' '; } std::cout << '\n'; return 0; }输出：
high -> low scores: 99 95 93 90 88 85 81 78 76 72这个例子说明一个组合套路：先 sort 保证有序，再用 merge 完成线性合并，最后用 reverse 调整方向。这样的组合拳在一些数据处理 pipeline 里非常常见。当然，如果一开始就想按降序合并，你也可以在 sort 时传 std::greater ()，或者给 merge 传自定义 comp，记得把升序逻辑反过来就行。两种做法最终效果一样，看哪个更贴合你的场景。
4. 常见问题与排查技巧实录
4.1 头文件、命名空间、容器选择等基础坑
不是开玩笑，我见过不少人写 merge 报错，结果原因就是<algorithm>头文件没包含。标准库算法大多在<algorithm>里，但有些被分到了别的头文件，比如<numeric>里才有 iota、accumulate。如果出现 “merge is not a member of std” 这种错误，第一反应检查头文件：
<algorithm>：merge、sort、reverse、swap、find 等<numeric>：accumulate、inner_product 等<memory>：unique_ptr、make_unique 等
另外，如果你们项目里用了using namespace std;，偶尔会和自定义的 merge 或 reverse 函数产生歧义，建议避免这种写法，显式加std::前缀。
容器选择方面，注意两点：
- vector、deque、list、string 的迭代器都支持 reverse，可以直接反转；
- forward_list（单链表）不支持 std::reverse，必须用它的成员函数
fl.reverse()； - 数组也可以通过
std::begin(arr)/std::end(arr)拿到迭代器，同样可以反转。
4.2 迭代器要求不满足引发的编译失败
这个错误很典型：如果你尝试对一个std::forward_list<int>实例调用std::reverse，编译器会直接报错，因为 reverse 需要双向迭代器，而 forward_list 的迭代器只满足前向迭代器要求。报错信息在不同编译器下会非常抽象，甚至可能甩出一长串模板实例化过程。我的建议是：遇到这类报错，先回头确认容器的迭代器类别。快速判断方法：
- 支持快速随机访问的容器（vector、deque、array、string）：迭代器是随机访问迭代器；
- 双向链表（list、forward_list）：list 是双向迭代器，forward_list 只有前向迭代器；
- 输入流、输出流这类特殊迭代器：只有输入或输出能力，几乎不能用于这种可变区间算法。
merge 对输入迭代器要求相对宽松，只要前向迭代器即可，所以 forward_list 可以传给 merge 当输入，但不能传给 reverse 当整个区间处理。
4.3 输出区间容量不足与迭代器失效问题
继续讲一个我在 merge 上遇到的经典问题。当你说“我要把合并结果放到 result”时，如果 result 是个空 vector，然后你直接写std::merge(..., result.begin())，程序运行时会崩出 “segmentation fault” 或类似错误。原因很简单：result.begin() 指向一个空区间，merge 尝试往这个位置写元素，越界访问。
三种推荐的解决方式：
- 使用
std::back_inserter(result)，它每次写入都会调用 push_back，自动扩容； - 预估好大小，先
result.resize(left.size() + right.size())，再传result.begin()； - 如果不想用 resizing，也可以用
result.reserve(...)，但重点提醒：reserve 只改变容量，不改变 size。如果只调用 reserve 而不 resize，然后用 result.begin() 当输出迭代器，同样会出问题。
我用表格整理一下常见输出方式对比，方便你快速判断：
| 输出迭代器方式 | 是否会扩容 | 适用场景 | 注意事项 |
|---|---|---|---|
result.begin() | 不会 | 目标容器已提前 resize，空间确定 | 必须先保证 size 足够大 |
std::back_inserter(result) | 自动 | 目标容器为空或不明确大小 | 性能略低于预留空间的方式 |
| 原始数组 + 手算下标 | 不会 | 数组空间足够，底层性能要求高 | 容易越界，谨慎使用 |
迭代器失效问题同样值得提一句。在调用 merge 等算法期间，如果往里写的是 vector，而 vector 因扩容导致迭代器失效，可能会引发未定义行为。使用 back_inserter 时，每次写入都通过 push_back，如果越过容量边界就动态扩容，但算法内部感知不到旧迭代器失效——实际上 back_inserter 每次访问容器对象，而不是长期持有旧迭代器，所以相对安全。但如果你提前取了auto it = result.begin()，再在算法里使用这个 it 而非 back_inserter，一旦扩容发生，it 就是失效状态，后患无穷。
4.4 中文反转乱码问题
reverse 对 string 是逐字节操作的。拿 “你好” 举例，它在 UTF-8 编码下占 6 个字节，直接 reverse 会使字节顺序整个颠倒，输出一堆乱码。这个坑很多人第一次处理中文字符串反转时都会踩。
如果确实需要反转一个可能包含多字节字符的字符串，我建议不要直接用 std::reverse，而是先把字符串按字符拆开。最简单的方式是用std::wstring_convert或手动按 UTF-8 字节头解析，也可以借助第三方字符编码库。这里给一个简化的示例思路：
// 不推荐直接反转 UTF-8 字符串 // 应该先拆成字符序列，再反转字符序列这种场景实际开发中不算高频，但遇到了很头疼。我一直的做法是：先确认字符串编码，是 UTF-8 就必须走字符边界解析，不能拿字节数组瞎 reverse。业务篇也建议要么先转成宽字符再处理。
4.5 常见误区速查表
| 误区 | 正确理解 |
|---|---|
| merge 能做完整排序 | 错，merge 只合并不输入两个有序区间，无序数据请先用 sort |
| merge 输出目标可以随意放 | 错，必须保证输出区间容量或使用插入迭代器 |
| reverse 所有容器都能用 | 错，forward_list 需要成员函数 |
| reverse_copy 会修改原数据 | 不会，它只读原区间，拷贝到新目标 |
| merge 会去重 | 不会，等价元素会被全部保留，去重要配 unique 使用 |
| inplace_merge 速度永远很快 | 不一定，无缓冲时可能变慢 |
这张表算是我个人从项目里总结出来的“排雷手册”，内容不多，但基本覆盖了平时最容易出错的地方。你用的时候可以把它当 check list，写完代码后对一遍，能省不少调试时间。
结尾
最后按惯例聊点个人经验。我在实际项目里用 merge 和 reverse 最大的感触是：标准库算法不是背完接口就完事，关键要理解它“为什么这样设计”。reverse 坚持双向迭代器而不是为每个容器单独提供版本，是为了保持算法和容器解耦；merge 要求输入有序，是为了换取 O(n) 的合并效率。这些设计逻辑你吃透了，写出来的代码自然会往“用标准库解决问题”的方向靠，而不是又回去写一堆手糊的循环。
另一个小技巧是调试算法时多用小数据模拟。我之前写 merge 相关逻辑，测试数据从来不用特别大，但一定会包含重复元素、空区间、一个区间只有一个元素这种边界情况。拿这种小测例跑一遍，错了肉眼就能看出来，比直接上生产数据省心得多。这个习惯如果你也能养成，对排查标准库算法的行为很有帮助。
如果你看完这篇，还是觉得 merge 和 reverse 的使用场景不够清晰，建议你先从最简单的需求入手：给自己写一个小工具，输入两个有序数组，输出一个合并结果；再写一个函数，把输入的字符串反转并返回。这样亲自动手跑一遍，远比盯着接口文档来得深刻。希望这篇内容对你有用，也欢迎你在实际使用中遇到其他坑时回来一起交流。
