find_end：在C++里找子序列“最后一次露面”的正确姿势

你有没有试过，在一长串数字或字符串里，想找某个模式最后出现的位置？比如日志里查某次错误的末次发生点，或者解析协议时定位最后一个分隔符块。这时候，std::find_end 就不是个冷门函数，而是能省下十几行手写循环的实用工具。

但现实是，很多人一看到 find_end 就绕道走——文档里那句“查找范围中最后一个匹配子序列”太抽象；示例又总拿 vector<int> 配 array<int,2> 演示，跟真实开发场景脱节；更别提它和 search、find_first_of 的边界容易混淆。结果就是，宁可写个反向遍历+search，也不敢信它一次到位。

其实，find_end 并不难，只是需要把它从“算法手册配图”拉回真实代码现场。

先说最常踩的坑：它找的不是“子串”，而是“子序列”（subsequence）的连续匹配块。注意，这里的“子序列”不是动态规划里那个可以跳着选的 subsequence，而是 STL 文档里特指的 连续、完整、顺序一致的一段值——换句话说，它等价于“最后出现的子数组”或“最后出现的子字符串”。别被术语吓住，你就当它是 search 的“倒放版”：search 找第一次，find_end 找最后一次。

它的签名长这样：

template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );

两个区间：大容器 [first1, last1) 是主战场，小容器 [first2, last2) 是你要找的“模板”。返回的是最后一次匹配起始位置的迭代器；如果没找到，返回 last1。

关键来了：find_end 不会自动帮你处理“重叠匹配”。比如在 "aaaa" 中找 "aa"，它返回的是第二个 "aa" 的起点（即索引 2），而不是最后一个可能的重叠位置（索引 3）。因为标准规定：每次匹配后，搜索窗口会从本次匹配的下一个元素开始继续找，不回退。这点和正则里的 g 标志不同，得心里有数。

实战中，我常用它干三件事：

第一，定位配置项最后一次覆盖位置。
比如解析一段类似 ini 的文本，多处出现 timeout=，你只想取最终生效的那个值：

vector<string> lines = {"timeout=30", "log=on", "timeout=60", "timeout=45"};
auto pattern = vector<string>{"timeout="};
auto it = find_end(lines.begin(), lines.end(), pattern.begin(), pattern.end());
if (it != lines.end()) {
    cout << "最终超时：" << it->substr(9) << "\n"; // 输出 45
}

这里 pattern 是单元素 vector，匹配逻辑清晰，比手写逆向循环 + string::find 更直给。

第二，在二进制协议解析中抓最后一帧头。
假设帧头是固定的 4 字节 0x55 0xAA 0x55 0xAA，数据存在 vector<uint8_t> 里：

array<uint8_t, 4> header = {0x55, 0xAA, 0x55, 0xAA};
auto pos = find_end(data.begin(), data.end(), header.begin(), header.end());
if (pos != data.end()) {
    size_t offset = distance(data.begin(), pos);
    // 从 offset 开始解析最后一帧
}

注意：array 这种固定大小容器，配合 find_end 效率高、无拷贝，比用 vector 存 header 更贴近底层习惯。

第三，规避 rfind 的局限性。
string::rfind 只能找子串，不能带自定义谓词。而 find_end 支持五参数重载：

find_end(first1, last1, first2, last2, pred)

你可以传入 [](char a, char b) { return toupper(a) == toupper(b); } 实现忽略大小写的末次子串查找——这功能，rfind 做不到，search 也得配合 make_reverse_iterator 绕一大圈。

顺带提一句：别用 find_end 找单个元素。虽然语法上可行（把 first2,last2 设为一对相邻迭代器），但语义错位，且性能不如 find 或 find_if 直观。工具对口，事半功倍。

最后划个重点：find_end 的时间复杂度是 O((last1 - first1) × (last2 - first2))，最坏情况接近暴力匹配。所以它适合中小规模数据（比如几千字节的日志片段、几百项的配置列表）。如果你要在 MB 级内存块里高频搜，得考虑 KMP 或 Boyer-Moore 变体——但那是另一个故事了。

回到开头的问题：为什么值得花两分钟记住 find_end？因为它把“找最后一次”这个高频动作，从“写循环+记位置+判边界”的三步操作，压缩成一行语义明确的调用。代码少一行，出错概率少一分，后来人读起来也少一分困惑。

下次当你又想 for (int i = size-1; i >= 0; --i) 的时候，不妨停半秒——试试 find_end。它不炫技，不藏私，就老老实实站在 <algorithm> 里，等你真正需要它的时候，伸手就够得着。