日志告警收敛那阵子我在几十万行日志里找连续出现3次的 ERROR 码。同事第一版是手写双层循环外层记录起始位置里层用计数器去点算代码勉强能跑但换个容器类型就得重写一遍。后来我换成algorithm头文件里的search_n三行代码解决问题。类似的场景你可能也遇到过文本里找某段模式、传感器数据里找连续重复值、行情序列里判断连续上涨——这些都不是find能直接搞定的而是search和search_n的主场。这篇文章就把这两个 C 标准库算法彻底讲透从函数签名、返回值语义到边界条件、谓词版本、性能底层再到实际项目里的用法一次说清楚。1. 从 find 单点查找到 search 子序列查找两种需求一开始就分岔很多人刚开始学 STL 算法时最先上手的是find和find_if它们解决的是在序列里找到一个满足条件的元素。但现实中的需求往往更复杂——你要找的不是一个点而是一段模式。1.1 一个让我改用 search_n 的日志需求举个例子。假设日志文件按行写入每行是一个状态码INFO、WARN、ERROR。业务规则是只要连续出现 3 个 ERROR就判定为服务异常需要触发告警。这个需求如果用find完全没用因为find只知道某个位置有一个 ERROR它不知道 ERROR 是不是连续的更不知道有几个。手写循环呢思路也不复杂// 手写版查找连续 3 个 ERROR for (size_t i 0; i 2 lines.size(); i) { if (lines[i] ERROR lines[i 1] ERROR lines[i 2] ERROR) { found i; break; } }看着还行但一遇到连续 5 个连续 10 个代码就膨胀成循环套循环还得自己小心索引越界。更要命的是如果数据存在std::list里这个基于下标i 2的写法直接作废。1.2 手写循环为什么会出问题手写这类匹配逻辑我见过太多次翻车了。最常见的就是 off-by-one 错误也就是差一错误想着从当前位置往后数count个元素结果边界判断少了 1或者多了 1恰好漏掉真正匹配的位置。再一个问题是可读性代码里的三层缩进和临时计数器别人 review 时一眼看不出来你到底在找什么。还有泛化能力的问题今天是std::vector明天是std::deque后天是std::list手写版本要么依赖随机访问要么改到天荒地老。1.3 search 和 search_n 的分工algorithm里这两个算法的定位其实很清楚std::search在序列中查找一个子序列。你给它一段模式它告诉你这段模式第一次出现在哪里。std::search_n在序列中查找连续出现指定次数的某个值。你给它一个值它告诉你连续出现count次这段连续区的起点。两者都是序列级查找但关注点不同search关心一段内容的位置search_n关心一种内容的重复度。把这层逻辑想明白后面用起来就顺了。2. search 的完整使用路书签名、返回值与一个能抄的示例std::search是 C 标准库里资格最老的算法之一功能稳定接口清晰。我们先把它的函数签名摊开看。2.1 函数签名到底在说什么标准库给出的两个主要重载长这样templateclass ForwardIt1, class ForwardIt2 ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2); // 带二元谓词的版本 templateclass ForwardIt1, class ForwardIt2, class BinaryPredicate ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p);简单解读一下。first1到last1是你要被检索的文本区我叫它主序列first2到last2是你想找的模式模式序列。函数在主序列里寻找第一个与模式序列完全相等的片段。模板参数是ForwardIt也就是前向迭代器这说明std::list、std::forward_list这种单链表容器照样能用不要求随机访问。2.2 返回值的准确含义返回值有三种情况如果找到了匹配片段返回指向主序列中该片段第一个元素的迭代器。如果模式序列为空也就是first2 last2标准规定直接返回first1。想想也有道理空序列在任何位置都算匹配干脆在最前面的位置匹配。如果整个主序列里都没有这个模式返回last1。这里最容易误解的一点是返回的迭代器指向的是模式段的起点不是终点。你要访问整段匹配内容得自己用std::distance或者循环从it往后走。2.3 从 vector 到 string 到 list迭代器泛型的自由度我直接给一个可以照抄的示例#include algorithm #include iostream #include vector int main() { std::vectorint text {1, 2, 3, 4, 5, 1, 2, 6, 8, 9}; std::vectorint pattern {1, 2}; auto it std::search(text.begin(), text.end(), pattern.begin(), pattern.end()); if (it ! text.end()) { std::cout 模式首次出现在位置: std::distance(text.begin(), it) \n; } else { std::cout 没找到\n; } return 0; }这段代码输出模式首次出现在位置: 0因为{1, 2}在开头的索引 0 处就匹配了。把text换成std::list或者把模式换成std::string的子串迭代器写法完全不用改这就是迭代器泛型的好处。不过要注意std::distance对std::list的迭代器是 O(n) 的获取索引没问题但如果只是判断有没有直接用it ! container.end()就够了别多做一次距离计算。3. search_n 的完整使用路书count、value 和谓词std::search_n比search用起来更直观因为你不需要特意构造一个模式序列直接告诉算法我要找连续多少个什么值。3.1 函数签名与三个参数的含义templateclass ForwardIt, class Size, class T ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T value); // 带二元谓词版本 templateclass ForwardIt, class Size, class T, class BinaryPredicate ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T value, BinaryPredicate p);参数拆开看first、last主序列的迭代器范围。count要找的连续个数。比如count 3就是找连续 3 个相同元素。value要找的那个值。p二元谓词用来定义什么算相等。如果不提供默认用operator。返回值逻辑和search一致找到返回连续区间的第一个元素的迭代器找不到返回last。3.2 实际代码找连续三个 5#include algorithm #include iostream #include vector int main() { std::vectorint data {2, 3, 5, 5, 5, 7, 8, 5, 5, 9}; auto it std::search_n(data.begin(), data.end(), 3, 5); if (it ! data.end()) { std::cout 连续 3 个 5起始位置: std::distance(data.begin(), it) \n; } return 0; }输出连续 3 个 5起始位置: 2。数据里最后还有两个 5但那个连续段长度不够 3不会被选中。这就是search_n的语义必须是连续的、数量足够的匹配。3.3 用二元谓词做模糊连续匹配默认相等很多时候太死板。比如传感器采集的温度值会有轻微抖动你要找的是连续 3 个大致都等于 25 度的数据段这时候就可以用谓词#include algorithm #include cmath #include iostream #include vector int main() { std::vectordouble temps {24.8, 25.1, 30.2, 24.9, 25.2, 25.0, 28.5}; auto it std::search_n(temps.begin(), temps.end(), 3, 25.0, [](double a, double b) { return std::abs(a - b) 0.5; }); if (it ! temps.end()) { std::cout 连续 3 个接近 25 度的数据起始位置: std::distance(temps.begin(), it) \n; } return 0; }这段代码找到的是索引 3 到 5 的24.9、25.2、25.0因为它们和中心值 25.0 的差值都小于 0.5。谓词版本极大的扩展了这个算法的适用范围你可以用它做近似匹配阈值匹配甚至自定义一种比较规则。注意谓词的参数顺序是固定的第一个参数是序列里的元素第二个参数是你传入的value写反了会有微妙的行为问题。4. 边界条件与返回值陷阱这些坑我在踩过之后才懂实战里最坑的不是正常情况而是边界情况。我在这里把search和search_n的边界行为全部梳理一遍都是标准里明确写了、但很多人不看的细节。4.1 空序列、空模式、count0 时的标准行为这几个情况反直觉建议直接背结论场景search 的行为search_n 的行为主序列为空first last返回 last返回 last模式序列为空first2 last2返回 first1视为在开头匹配不适用count 0不适用返回 first标准对search_n的描述是count 0时寻找连续count个满足条件的元素如果count 0直接返回first。所以如果你不小心把count传成 0代码不会报错也不会一直跑到last而是返回开头的迭代器——这大概率不是你想要的但它不会崩。传负数就更危险了因为Size通常是无符号整数别在生产代码里玩这个。4.2 找不到时为什么返回 lastsearch和search_n找不到匹配时都返回last而不是end() - 1或者空迭代器。这是一个统一约定所有 STL 查找算法都以返回 [first, last) 中的某个位置或 last 为标准答案。这样做的逻辑是返回last不但是没找到的哨兵还保持了区间语义的完整性拿到返回值后可以直接判断it last不需要特殊处理。4.3 索引计算与迭代器无效化的注意事项找到了位置有时需要换算成索引用std::distance(first, it)就行。但如果容器是std::list这个计算是 O(n) 的。另外这些算法都是只读操作不修改容器内容。问题往往出在并发场景一边search另一边其他线程往容器里push_back迭代器一旦失效行为就是未定义的。所以要么保证容器不动要么加锁要么直接在拷贝或只读快照上操作。还有一个实际教训search默认用operator也就是区分大小写的。有次同事查日志里的error日志里写的是ERROR结果search一直返回end()查了半天。遇上不区分大小写的需求别犹豫直接用谓词版本自己写个比较函数。5. 近亲算法大对比find、find_end、adjacent_find、contains谁更合适algorithm里跟查找相关的算法有一大家子。选错了也不是不能跑但代码读起来会很拧巴。我整理了一张对比表算法查找目标返回结果find单个元素等于给定值第一个匹配元素的迭代器find_if单个元素满足一元谓词第一个满足条件元素的迭代器search一段指定的子序列子序列第一次出现的起点迭代器search_n连续 count 个相同的值连续段起点的迭代器find_end一段指定的子序列子序列最后一次出现的起点迭代器adjacent_find相邻两个相等或满足条件的元素第一个相邻对中前一个元素的迭代器ends_with/starts_with序列是否以某个子序列结束/开始boolC20contains序列里是否存在某个值boolC235.1 选型经验根据最后一次出现和相邻重复区分场景我实际选型时的判断逻辑很简单只找单个元素看值用find看条件用find_if。要找一整段模式还要第一次出现的位置用search。要找一整段模式但需要最后一次出现的位置用find_end。要找连续重复的相同值用search_n。只是判断两个相邻元素是否满足某种关系不限定具体值用adjacent_find。举个例子字符串abcabcabc里找abcsearch返回开头的位置find_end返回第二个abc结束的位置不对find_end返回最后一次出现的起点也就是索引 6。想验证模式是否出现在末尾或者统计数据里某模式的分布范围时find_end特别有用。还有个实用组合search找到第一次出现然后用这个迭代器继续调用search就能循环找出所有匹配位置实现一个简单的模式统计器。6. 实战三个真实代码场景光讲原理不够我把自己实际写过的三个场景拿出来直接上代码和思路。6.1 日志告警中的连续错误检测这是最典型的一个。假设日志状态码是字符串检测连续 3 个及以上ERROR#include algorithm #include iostream #include string #include vector int main() { std::vectorstd::string log_lines { INFO, ERROR, ERROR, ERROR, WARN, ERROR }; auto it std::search_n(log_lines.begin(), log_lines.end(), 3, std::string(ERROR)); if (it ! log_lines.end()) { std::cout 发现连续 3 个 ERROR从第 std::distance(log_lines.begin(), it) 1 行开始\n; } return 0; }注意这里value参数的类型是std::string(ERROR)必须和容器元素类型一致。输出第 2 行开始。如果日志量几十万行search_n内部会尽量提前终止——找到第一个长度为 3 的连续段就停不会傻傻扫到尾。6.2 二进制特征码的内存扫描做文件分析时有时需要在缓冲区里找一段二进制特征码比如定位某个文件头的魔数#include algorithm #include cstdint #include vector std::vectoruint8_t make_buffer(); std::vectoruint8_t signature {0x89, 0x50, 0x4E, 0x47}; // PNG 头 auto it std::search(buffer.begin(), buffer.end(), signature.begin(), signature.end()); if (it ! buffer.end()) { // 找到特征码it 指向 0x89 }这段代码优雅且容器无关。以后看到手写的for (int i 0; i size; i)配memcmp的二进制匹配代码我都建议先考虑换成search可读性立刻就上来了。6.3 行情数据中的连续上涨判断K 线数据里判断最近有没有连续 3 天上涨可以这样写#include algorithm #include iostream #include vector int main() { std::vectordouble closes {10.0, 10.5, 10.8, 10.4, 11.0, 11.2}; auto it std::search_n(closes.begin(), closes.end(), 3, 0.0, [](double cur, double /*unused*/) { // 这种写法不对见下方说明 return false; }); return 0; }这里我要说清楚search_n的谓词版本比较的是序列里的元素和你传入的固定 value它没法直接表达连续上涨这种元素之间的相对关系。连续上涨的判断需要比较相邻两个元素这个场景更适合用std::adjacent_find来自定义连续上涨条件或者配合std::is_sorted。所以search_n适合连续等于某个基准值或连续接近某个基准值的场景如果是连续满足某个演化规则你要换算法。这个区分想明白能省不少调试时间。7. 底层原理、性能与 C20 ranges 的现代化写法search和search_n的底层实现并不神秘但理解它有助于合理预期性能。7.1 复杂度最坏情况下的朴素匹配标准规定std::search最多进行(last1 - first1) * (last2 - first2)次比较。std::search_n最多进行(last - first) * count次比较。也就是说典型实现就是朴素的滑动窗口匹配从主序列每个位置出发逐一和模式序列比较一旦失配就平移一个位置。如果主序列长度是 N模式长度是 M最坏时间复杂度是 O(N×M)。对于大多数实际场景——文本片段、日志状态码、短线特征值——这个复杂度完全够用因为分布通常比较稀疏匹配很快就能命中或失败。7.2 标准库实现里的小心思现代标准库实现不会傻到每个位置都从头开始比。GCC 的 libstdc 在实现search时有一些优化思路如果模式序列长度为 1直接退化为findO(N) 完成。模式长度大于 1 时会先用快速的单值查找机制在主序列里定位模式首元素的候选位置然后再做完整比较这样能跳过大量明显不匹配的位置。这也是为什么我建议优先用标准库算法而不是手写循环的原因之一你手写的朴素循环没有任何优化标准库的实现则集成了各种工程智慧。7.3 C17 并行策略如果你的主序列很大比如几 GB 的日志文件可以考虑 C17 引入的执行策略#include algorithm #include execution auto it std::search(std::execution::par, buffer.begin(), buffer.end(), signature.begin(), signature.end());加上execution头文件传入std::execution::par就可以在多核上并行查找。不是所有场景都能受益碎片化的模式匹配并行收益有限但值得知道有这个选项。search_n同样支持这种写法。7.4 C20 ranges 版本更直观的调用方式C20 以后std::ranges命名空间提供了更现代的接口#include algorithm #include iostream #include ranges #include vector int main() { std::vectorint text {5, 6, 7, 5, 6, 7}; std::vectorint pattern {6, 7}; auto result std::ranges::search(text, pattern); // 返回的是 subrange不是裸迭代器 if (!result.empty()) { std::cout 找到起点 std::distance(text.begin(), result.begin()) \n; } auto result2 std::ranges::search_n(text, 2, 6); if (!result2.empty()) { std::cout 连续 2 个 6起点 std::distance(text.begin(), result2.begin()) \n; } return 0; }std::ranges::search返回的是一个subrange对象它直接把匹配段的开始和结束都给你了不用像老版本那样自己根据起点推算范围。判断是否找到用result.empty()语义上比it ! end()更清晰。7.5 什么时候不要用它没有哪个算法是全能的。如果你的主序列和模式都非常大比如在几 GB 的文本搜索几百 MB 的模式O(N×M) 的朴素匹配就太慢此时该考虑 KMP、Boyer-Moore或者直接引入现成的字符串搜索库。如果检索对象是 Unicode 文本还涉及规范化比较search的默认行为也不够用。判断标准很简单模式很短而且主搜索是常规文本时标准库算法是最优选择模式很长或者追求极致性能时才有必要专门设计匹配算法。我在实际项目中用过很多次这两个算法说点个人体会。search和search_n的定位看似简单但它们是用算法名表达代码意图的绝佳例子——看到search读者马上明白你在找一段子序列看到search_n读者立刻知道你在查连续重复。相比手写循环这种语义价值完全不输性能优化。我现在的习惯是凡是遇到在序列中找片段或找连续重复的需求第一反应永远是先翻algorithm而不是立刻开 for 循环。这两个算法用熟之后你的 C 代码会干净很多bug 也会少很多。
日志告警收敛那阵子我在几十万行日志里找连续出现3次的 ERROR 码。同事第一版是手写双层循环外层记录起始位置里层用计数器去点算代码勉强能跑但换个容器类型就得重写一遍。后来我换成algorithm头文件里的search_n三行代码解决问题。类似的场景你可能也遇到过文本里找某段模式、传感器数据里找连续重复值、行情序列里判断连续上涨——这些都不是find能直接搞定的而是search和search_n的主场。这篇文章就把这两个 C 标准库算法彻底讲透从函数签名、返回值语义到边界条件、谓词版本、性能底层再到实际项目里的用法一次说清楚。1. 从 find 单点查找到 search 子序列查找两种需求一开始就分岔很多人刚开始学 STL 算法时最先上手的是find和find_if它们解决的是在序列里找到一个满足条件的元素。但现实中的需求往往更复杂——你要找的不是一个点而是一段模式。1.1 一个让我改用 search_n 的日志需求举个例子。假设日志文件按行写入每行是一个状态码INFO、WARN、ERROR。业务规则是只要连续出现 3 个 ERROR就判定为服务异常需要触发告警。这个需求如果用find完全没用因为find只知道某个位置有一个 ERROR它不知道 ERROR 是不是连续的更不知道有几个。手写循环呢思路也不复杂// 手写版查找连续 3 个 ERROR for (size_t i 0; i 2 lines.size(); i) { if (lines[i] ERROR lines[i 1] ERROR lines[i 2] ERROR) { found i; break; } }看着还行但一遇到连续 5 个连续 10 个代码就膨胀成循环套循环还得自己小心索引越界。更要命的是如果数据存在std::list里这个基于下标i 2的写法直接作废。1.2 手写循环为什么会出问题手写这类匹配逻辑我见过太多次翻车了。最常见的就是 off-by-one 错误也就是差一错误想着从当前位置往后数count个元素结果边界判断少了 1或者多了 1恰好漏掉真正匹配的位置。再一个问题是可读性代码里的三层缩进和临时计数器别人 review 时一眼看不出来你到底在找什么。还有泛化能力的问题今天是std::vector明天是std::deque后天是std::list手写版本要么依赖随机访问要么改到天荒地老。1.3 search 和 search_n 的分工algorithm里这两个算法的定位其实很清楚std::search在序列中查找一个子序列。你给它一段模式它告诉你这段模式第一次出现在哪里。std::search_n在序列中查找连续出现指定次数的某个值。你给它一个值它告诉你连续出现count次这段连续区的起点。两者都是序列级查找但关注点不同search关心一段内容的位置search_n关心一种内容的重复度。把这层逻辑想明白后面用起来就顺了。2. search 的完整使用路书签名、返回值与一个能抄的示例std::search是 C 标准库里资格最老的算法之一功能稳定接口清晰。我们先把它的函数签名摊开看。2.1 函数签名到底在说什么标准库给出的两个主要重载长这样templateclass ForwardIt1, class ForwardIt2 ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2); // 带二元谓词的版本 templateclass ForwardIt1, class ForwardIt2, class BinaryPredicate ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p);简单解读一下。first1到last1是你要被检索的文本区我叫它主序列first2到last2是你想找的模式模式序列。函数在主序列里寻找第一个与模式序列完全相等的片段。模板参数是ForwardIt也就是前向迭代器这说明std::list、std::forward_list这种单链表容器照样能用不要求随机访问。2.2 返回值的准确含义返回值有三种情况如果找到了匹配片段返回指向主序列中该片段第一个元素的迭代器。如果模式序列为空也就是first2 last2标准规定直接返回first1。想想也有道理空序列在任何位置都算匹配干脆在最前面的位置匹配。如果整个主序列里都没有这个模式返回last1。这里最容易误解的一点是返回的迭代器指向的是模式段的起点不是终点。你要访问整段匹配内容得自己用std::distance或者循环从it往后走。2.3 从 vector 到 string 到 list迭代器泛型的自由度我直接给一个可以照抄的示例#include algorithm #include iostream #include vector int main() { std::vectorint text {1, 2, 3, 4, 5, 1, 2, 6, 8, 9}; std::vectorint pattern {1, 2}; auto it std::search(text.begin(), text.end(), pattern.begin(), pattern.end()); if (it ! text.end()) { std::cout 模式首次出现在位置: std::distance(text.begin(), it) \n; } else { std::cout 没找到\n; } return 0; }这段代码输出模式首次出现在位置: 0因为{1, 2}在开头的索引 0 处就匹配了。把text换成std::list或者把模式换成std::string的子串迭代器写法完全不用改这就是迭代器泛型的好处。不过要注意std::distance对std::list的迭代器是 O(n) 的获取索引没问题但如果只是判断有没有直接用it ! container.end()就够了别多做一次距离计算。3. search_n 的完整使用路书count、value 和谓词std::search_n比search用起来更直观因为你不需要特意构造一个模式序列直接告诉算法我要找连续多少个什么值。3.1 函数签名与三个参数的含义templateclass ForwardIt, class Size, class T ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T value); // 带二元谓词版本 templateclass ForwardIt, class Size, class T, class BinaryPredicate ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T value, BinaryPredicate p);参数拆开看first、last主序列的迭代器范围。count要找的连续个数。比如count 3就是找连续 3 个相同元素。value要找的那个值。p二元谓词用来定义什么算相等。如果不提供默认用operator。返回值逻辑和search一致找到返回连续区间的第一个元素的迭代器找不到返回last。3.2 实际代码找连续三个 5#include algorithm #include iostream #include vector int main() { std::vectorint data {2, 3, 5, 5, 5, 7, 8, 5, 5, 9}; auto it std::search_n(data.begin(), data.end(), 3, 5); if (it ! data.end()) { std::cout 连续 3 个 5起始位置: std::distance(data.begin(), it) \n; } return 0; }输出连续 3 个 5起始位置: 2。数据里最后还有两个 5但那个连续段长度不够 3不会被选中。这就是search_n的语义必须是连续的、数量足够的匹配。3.3 用二元谓词做模糊连续匹配默认相等很多时候太死板。比如传感器采集的温度值会有轻微抖动你要找的是连续 3 个大致都等于 25 度的数据段这时候就可以用谓词#include algorithm #include cmath #include iostream #include vector int main() { std::vectordouble temps {24.8, 25.1, 30.2, 24.9, 25.2, 25.0, 28.5}; auto it std::search_n(temps.begin(), temps.end(), 3, 25.0, [](double a, double b) { return std::abs(a - b) 0.5; }); if (it ! temps.end()) { std::cout 连续 3 个接近 25 度的数据起始位置: std::distance(temps.begin(), it) \n; } return 0; }这段代码找到的是索引 3 到 5 的24.9、25.2、25.0因为它们和中心值 25.0 的差值都小于 0.5。谓词版本极大的扩展了这个算法的适用范围你可以用它做近似匹配阈值匹配甚至自定义一种比较规则。注意谓词的参数顺序是固定的第一个参数是序列里的元素第二个参数是你传入的value写反了会有微妙的行为问题。4. 边界条件与返回值陷阱这些坑我在踩过之后才懂实战里最坑的不是正常情况而是边界情况。我在这里把search和search_n的边界行为全部梳理一遍都是标准里明确写了、但很多人不看的细节。4.1 空序列、空模式、count0 时的标准行为这几个情况反直觉建议直接背结论场景search 的行为search_n 的行为主序列为空first last返回 last返回 last模式序列为空first2 last2返回 first1视为在开头匹配不适用count 0不适用返回 first标准对search_n的描述是count 0时寻找连续count个满足条件的元素如果count 0直接返回first。所以如果你不小心把count传成 0代码不会报错也不会一直跑到last而是返回开头的迭代器——这大概率不是你想要的但它不会崩。传负数就更危险了因为Size通常是无符号整数别在生产代码里玩这个。4.2 找不到时为什么返回 lastsearch和search_n找不到匹配时都返回last而不是end() - 1或者空迭代器。这是一个统一约定所有 STL 查找算法都以返回 [first, last) 中的某个位置或 last 为标准答案。这样做的逻辑是返回last不但是没找到的哨兵还保持了区间语义的完整性拿到返回值后可以直接判断it last不需要特殊处理。4.3 索引计算与迭代器无效化的注意事项找到了位置有时需要换算成索引用std::distance(first, it)就行。但如果容器是std::list这个计算是 O(n) 的。另外这些算法都是只读操作不修改容器内容。问题往往出在并发场景一边search另一边其他线程往容器里push_back迭代器一旦失效行为就是未定义的。所以要么保证容器不动要么加锁要么直接在拷贝或只读快照上操作。还有一个实际教训search默认用operator也就是区分大小写的。有次同事查日志里的error日志里写的是ERROR结果search一直返回end()查了半天。遇上不区分大小写的需求别犹豫直接用谓词版本自己写个比较函数。5. 近亲算法大对比find、find_end、adjacent_find、contains谁更合适algorithm里跟查找相关的算法有一大家子。选错了也不是不能跑但代码读起来会很拧巴。我整理了一张对比表算法查找目标返回结果find单个元素等于给定值第一个匹配元素的迭代器find_if单个元素满足一元谓词第一个满足条件元素的迭代器search一段指定的子序列子序列第一次出现的起点迭代器search_n连续 count 个相同的值连续段起点的迭代器find_end一段指定的子序列子序列最后一次出现的起点迭代器adjacent_find相邻两个相等或满足条件的元素第一个相邻对中前一个元素的迭代器ends_with/starts_with序列是否以某个子序列结束/开始boolC20contains序列里是否存在某个值boolC235.1 选型经验根据最后一次出现和相邻重复区分场景我实际选型时的判断逻辑很简单只找单个元素看值用find看条件用find_if。要找一整段模式还要第一次出现的位置用search。要找一整段模式但需要最后一次出现的位置用find_end。要找连续重复的相同值用search_n。只是判断两个相邻元素是否满足某种关系不限定具体值用adjacent_find。举个例子字符串abcabcabc里找abcsearch返回开头的位置find_end返回第二个abc结束的位置不对find_end返回最后一次出现的起点也就是索引 6。想验证模式是否出现在末尾或者统计数据里某模式的分布范围时find_end特别有用。还有个实用组合search找到第一次出现然后用这个迭代器继续调用search就能循环找出所有匹配位置实现一个简单的模式统计器。6. 实战三个真实代码场景光讲原理不够我把自己实际写过的三个场景拿出来直接上代码和思路。6.1 日志告警中的连续错误检测这是最典型的一个。假设日志状态码是字符串检测连续 3 个及以上ERROR#include algorithm #include iostream #include string #include vector int main() { std::vectorstd::string log_lines { INFO, ERROR, ERROR, ERROR, WARN, ERROR }; auto it std::search_n(log_lines.begin(), log_lines.end(), 3, std::string(ERROR)); if (it ! log_lines.end()) { std::cout 发现连续 3 个 ERROR从第 std::distance(log_lines.begin(), it) 1 行开始\n; } return 0; }注意这里value参数的类型是std::string(ERROR)必须和容器元素类型一致。输出第 2 行开始。如果日志量几十万行search_n内部会尽量提前终止——找到第一个长度为 3 的连续段就停不会傻傻扫到尾。6.2 二进制特征码的内存扫描做文件分析时有时需要在缓冲区里找一段二进制特征码比如定位某个文件头的魔数#include algorithm #include cstdint #include vector std::vectoruint8_t make_buffer(); std::vectoruint8_t signature {0x89, 0x50, 0x4E, 0x47}; // PNG 头 auto it std::search(buffer.begin(), buffer.end(), signature.begin(), signature.end()); if (it ! buffer.end()) { // 找到特征码it 指向 0x89 }这段代码优雅且容器无关。以后看到手写的for (int i 0; i size; i)配memcmp的二进制匹配代码我都建议先考虑换成search可读性立刻就上来了。6.3 行情数据中的连续上涨判断K 线数据里判断最近有没有连续 3 天上涨可以这样写#include algorithm #include iostream #include vector int main() { std::vectordouble closes {10.0, 10.5, 10.8, 10.4, 11.0, 11.2}; auto it std::search_n(closes.begin(), closes.end(), 3, 0.0, [](double cur, double /*unused*/) { // 这种写法不对见下方说明 return false; }); return 0; }这里我要说清楚search_n的谓词版本比较的是序列里的元素和你传入的固定 value它没法直接表达连续上涨这种元素之间的相对关系。连续上涨的判断需要比较相邻两个元素这个场景更适合用std::adjacent_find来自定义连续上涨条件或者配合std::is_sorted。所以search_n适合连续等于某个基准值或连续接近某个基准值的场景如果是连续满足某个演化规则你要换算法。这个区分想明白能省不少调试时间。7. 底层原理、性能与 C20 ranges 的现代化写法search和search_n的底层实现并不神秘但理解它有助于合理预期性能。7.1 复杂度最坏情况下的朴素匹配标准规定std::search最多进行(last1 - first1) * (last2 - first2)次比较。std::search_n最多进行(last - first) * count次比较。也就是说典型实现就是朴素的滑动窗口匹配从主序列每个位置出发逐一和模式序列比较一旦失配就平移一个位置。如果主序列长度是 N模式长度是 M最坏时间复杂度是 O(N×M)。对于大多数实际场景——文本片段、日志状态码、短线特征值——这个复杂度完全够用因为分布通常比较稀疏匹配很快就能命中或失败。7.2 标准库实现里的小心思现代标准库实现不会傻到每个位置都从头开始比。GCC 的 libstdc 在实现search时有一些优化思路如果模式序列长度为 1直接退化为findO(N) 完成。模式长度大于 1 时会先用快速的单值查找机制在主序列里定位模式首元素的候选位置然后再做完整比较这样能跳过大量明显不匹配的位置。这也是为什么我建议优先用标准库算法而不是手写循环的原因之一你手写的朴素循环没有任何优化标准库的实现则集成了各种工程智慧。7.3 C17 并行策略如果你的主序列很大比如几 GB 的日志文件可以考虑 C17 引入的执行策略#include algorithm #include execution auto it std::search(std::execution::par, buffer.begin(), buffer.end(), signature.begin(), signature.end());加上execution头文件传入std::execution::par就可以在多核上并行查找。不是所有场景都能受益碎片化的模式匹配并行收益有限但值得知道有这个选项。search_n同样支持这种写法。7.4 C20 ranges 版本更直观的调用方式C20 以后std::ranges命名空间提供了更现代的接口#include algorithm #include iostream #include ranges #include vector int main() { std::vectorint text {5, 6, 7, 5, 6, 7}; std::vectorint pattern {6, 7}; auto result std::ranges::search(text, pattern); // 返回的是 subrange不是裸迭代器 if (!result.empty()) { std::cout 找到起点 std::distance(text.begin(), result.begin()) \n; } auto result2 std::ranges::search_n(text, 2, 6); if (!result2.empty()) { std::cout 连续 2 个 6起点 std::distance(text.begin(), result2.begin()) \n; } return 0; }std::ranges::search返回的是一个subrange对象它直接把匹配段的开始和结束都给你了不用像老版本那样自己根据起点推算范围。判断是否找到用result.empty()语义上比it ! end()更清晰。7.5 什么时候不要用它没有哪个算法是全能的。如果你的主序列和模式都非常大比如在几 GB 的文本搜索几百 MB 的模式O(N×M) 的朴素匹配就太慢此时该考虑 KMP、Boyer-Moore或者直接引入现成的字符串搜索库。如果检索对象是 Unicode 文本还涉及规范化比较search的默认行为也不够用。判断标准很简单模式很短而且主搜索是常规文本时标准库算法是最优选择模式很长或者追求极致性能时才有必要专门设计匹配算法。我在实际项目中用过很多次这两个算法说点个人体会。search和search_n的定位看似简单但它们是用算法名表达代码意图的绝佳例子——看到search读者马上明白你在找一段子序列看到search_n读者立刻知道你在查连续重复。相比手写循环这种语义价值完全不输性能优化。我现在的习惯是凡是遇到在序列中找片段或找连续重复的需求第一反应永远是先翻algorithm而不是立刻开 for 循环。这两个算法用熟之后你的 C 代码会干净很多bug 也会少很多。
