我在写业务代码和刷算法题的时候经常遇到“在一串数据里找连续的一段”这种需求。比如操作日志里出现了一组特定的命令序列或者传感器数据里连续传了几个异常值。最笨的办法是嵌套循环自己写写多了就发现边界条件很容易搞错而且代码又臭又长。C标准库的algorithm头文件里其实已经准备好了search和search_n这两个现成函数专门干这件事。这俩函数名气不如sort、find大但用对了地方代码能简洁不少。这篇内容就把它们的原理、用法、坑一次说清楚适合刚接触STL的C初学者也适合想把手头代码写得更干净的工程开发者。1. 认识search和search_n这对算法到底解决什么问题1.1 谁负责“找”谁负责“数”search和search_n看起来名字就差一个_n解决的问题却不一样。search负责在一段主序列里查找另一段子序列的首次出现位置它做的是“模式匹配”。比如主序列是[1, 3, 5, 7, 9, 11]你想知道[5, 7]这个连续小片段是不是存在于主序列里、出现在哪个位置这就是search的工作。更直白一点你要在主序列里找的不是单个值而是一串连续的值。search_n则是查找“连续 n 个相同值”的首次出现位置。比如一个数组里有[2, 4, 4, 4, 6]你想知道有没有连续三个4从哪个位置开始这就是search_n的工作。它不关心你要找的这串值前后是什么只关心某个值连续出现了多少次。两者和find的区别也很明显find只找一个元素search找一整段连续子区间search_n找连续重复的元素。举个生活里的例子一条传送带上经过各种纸箱find是找一个贴了红色标签的箱子search是找“红标签箱子后面紧接着黄标签箱子”这种组合search_n则是找连续三个贴了红标签的箱子。需求完全不同用的工具也不同。1.2 接口签名与参数行为两个函数的接口很清晰需要重点记住的是它们都返回迭代器而且都支持“值比较”和“自定义谓词”两种用法。#include algorithm #include vector #include iostream int main() { std::vectorint haystack {1, 2, 3, 9, 8, 7, 3, 3, 3, 5}; std::vectorint pattern {9, 8, 7}; // search查找 pattern 是否作为连续子序列出现在 haystack 中 auto it1 std::search(haystack.begin(), haystack.end(), pattern.begin(), pattern.end()); if (it1 ! haystack.end()) { std::cout search 找到子序列起始下标: std::distance(haystack.begin(), it1) \n; } else { std::cout search 未找到子序列\n; } // search_n查找连续 3 个值为 3 的片段 auto it2 std::search_n(haystack.begin(), haystack.end(), 3, 3); if (it2 ! haystack.end()) { std::cout search_n 找到连续三个3起始下标: std::distance(haystack.begin(), it2) \n; } return 0; }这里有几个行为细节值得注意。返回值方面两个函数在找不到目标时都会返回“主序列的末尾迭代器”也就是last所以判断结果时必须拿返回值和haystack.end()比较不能直接解引用。这个习惯能避免一大半越界错误。空序列的行为也有明确约定当search的子序列区间为空时即pattern.begin() pattern.end()按现代标准库的行为函数直接返回first也就是主序列的起始位置同理search_n的count如果小于等于0也直接返回first。这个语义在你写工具函数需要兼容“零次”场景时特别有用。性能上两个函数的时间复杂度在最坏情况下都是O(N*M)N是主序列长度M是子序列长度或count值。标准只规定了谓词比较次数的上限并没有强制要求实现用某种最优算法所以不同编译器对随机访问迭代器的优化程度也不一样。初学者不用纠结这个先把正确性搞明白后面再聊优化。2. 原理剖析源码里到底是怎么一步步找的2.1 朴素匹配的三层循环结构如果打开 GCC 或者 MSVC 的标准库实现看search的内部代码会发现它的核心思想非常朴素从主序列的第一个元素开始把子序列的每个元素依次拿过来比较如果某个位置不匹配就把主序列的起点往后移一位再从子序列的头开始比较。整个过程可以理解成一个外层循环套一个内层循环。主体循环伪代码 对主序列中每个可能作为起点的位置 pos 临时把 pos 复制一份给 p 把子序列起点复制一份给 q 循环比较 *p 与 *q 若相等p、q 同时往后走 若不相等break 退出内层比较 若 q 到头了说明子序列全部匹配成功返回 pos 若主序列遍历完仍无结果返回 last这种实现方式叫朴素匹配也叫暴力匹配。为什么标准库不在这里用KMP这样的高效字符串匹配算法一个重要原因是KMP依赖于“随机访问”和“前缀函数表”而search需要支持任意正向迭代器比如链表list的迭代器。链表只能从前往后走不能像数组那样跳回某个历史位置KMP算法里那种基于下标的跳转根本没法实现。另外模式序列的类型也不一定是string可能是vectorint、deque甚至自定义容器标准库为了通用性选择了一个最稳妥的基础方案。这并不说明C标准库“偷懒”。标准里写的是复杂度上限实现者只要不超过这个上限就行所以不同库的实现细节会有差异。GCC的libstdc里search对随机访问迭代器有一些特殊优化但整体还是围绕“逐个位置尝试匹配”这个思路。理解了这个本质你就明白了为什么search做不了KMP那种线性复杂度的字符串匹配也明白了为什么在超长文本里找短模式时search不一定是性能最优解。2.2 search_n的“连续计数”逻辑search_n的实现思路和search不同它没有子序列可以遍历它的核心逻辑是“从每个位置开始连续比较 count 次”。对主序列中每个位置 pos 把 cur 指向 pos剩余待匹配次数 count_rem count 循环比较 *cur 与 value 若相等cur 后移count_rem 减 1 若 count_rem 减到 0说明连续 count 个都匹配返回 pos 若不相等break 退出 若中途失败移动 pos 时可以直接跳到已经比较过的位置之后而不是只 1注意最后一句这是search_n实现里的一个细节优化。当匹配到某个位置失败时意味着“刚刚已经检查过一段连续的、前面若干个相等但最后一步失败的元素”那这些元素里不可能再有某个位置能作为新的起点产生 count 个连续相等值因为连续相等的长度已经断掉了所以外层可以把起点直接移动到失败位置之后避免重复比较。这也是为什么search_n的复杂度表现看起来还不错的原因之一。search_n的谓词版本同样支持自定义“相等”判断例如把“相等”定义成“绝对值差不超过一个阈值”这样可以在浮点序列里寻找连续接近的值。日常工作里这种需求在传感器数据处理中很常见。2.3 性能边界与现实选择search和search_n是通用容器算法但在特定场景下有更快的替代品。我把常见的选择整理成一个表方便快速对照需求推荐算法复杂度说明找一个值std::findO(N)线性扫描即可找满足条件的单个值std::find_ifO(N)配合自定义谓词在主序列中查找子序列std::searchO(N*M)通用支持任意正向迭代器查找连续 n 个相同值std::search_nO(N*M)通用适合日志、传感器数据在字符串中查找子串std::string::find一般更优针对字符做了专门优化找多个候选值中的任意一个std::find_first_ofO(N*M)候选集合较小的时候合适比较两个区间是否相等std::equal/std::mismatchO(N)不是查找是对齐比较这个表的重点不是让你背结论而是建立一个直觉什么时候用库函数什么时候要手写。工程中绝大多数场景search都够用但如果你的核心业务就是在一个几MB的文本里频繁匹配短模式那std::string::find甚至自己实现KMP才是合理的。通用算法保证的是“正确且不太慢”不是“所有场景最快”。3. 实操在VS Code里把这两个算法跑起来并调试3.1 环境准备一个能跑样例的C工程热搜里经常出现“vscode配置c/c环境”、“函数变量无法跳转”、“visual c redistributable下载”这些问题说明很多初学者卡在了第一步代码写好了但不知道怎么在VS Code里编译调试。我建议的配置路径是这样的先装一个编译器Windows上可以用MinGW-w64或Visual Studio Build Tools然后在VS Code里安装C/C扩展最后在工程目录下配置好.vscode/tasks.json和.vscode/launch.json。这里不贴冗长的JSON配置只提一个最容易踩的坑C/C扩展的IntelliSense找不到标准库头文件时所有函数跳转都失效。解决办法是在.vscode/c_cpp_properties.json里把includePath指向编译器自带的include目录比如MinGW的C:/msys64/mingw64/include或者直接设置compilerPath让扩展自动探测。改完配置重启VS Code跳转和代码补全基本就恢复了。还有不少人在安装Visual Studio时会遇到“microsoft visual c redistributable”的提示这实际上是运行库编译好的程序在别的机器上运行时需要它如果只是为了本地学习装Build Tools时会自动带上一般不用单独处理。真正重要的是把编译和调试打通能跑起来再学算法才有抓手。3.2 三个可以直接抄作业的示例我准备了三个场景示例分别对应子序列匹配、连续阈值检测、子序列出现次数统计。这些代码可以直接建一个.cpp文件测试也是我实际测试过的写法。第一个示例模拟一个操作日志系统。日志里有[登录, 读取, 写入, 登出, 读取]这样的操作码序列业务规则要求检测“登录之后紧接着读取再写入”这个危险操作序列是否出现#include algorithm #include vector #include string #include iostream int main() { std::vectorstd::string log {登录, 读取, 写入, 登出, 读取}; std::vectorstd::string danger {登录, 读取, 写入}; auto it std::search(log.begin(), log.end(), danger.begin(), danger.end()); if (it ! log.end()) { std::cout 检测到危险操作序列起始位置: std::distance(log.begin(), it) \n; } else { std::cout 未检测到危险操作\n; } return 0; }第二个示例处理传感器数据。数据里连续出现3个超过80的数值就触发报警#include algorithm #include vector #include iostream int main() { std::vectorint readings {70, 82, 91, 85, 60, 73}; auto it std::search_n(readings.begin(), readings.end(), 3, 80, [](int a, int b) { return a b; // “相等”的定义当前值 目标值 }); if (it ! readings.end()) { std::cout 出现连续3个超过80的读数起始下标: std::distance(readings.begin(), it) \n; } else { std::cout 没有连续报警\n; } return 0; }第三个示例统计子序列在主序列中出现的次数。库函数只返回第一个出现位置要统计次数需要自己循环推进#include algorithm #include vector #include iostream int main() { std::vectorint data {1, 2, 1, 2, 1, 2, 5, 1, 2}; std::vectorint pat {1, 2}; auto cur data.begin(); int count 0; while (true) { cur std::search(cur, data.end(), pat.begin(), pat.end()); if (cur data.end()) break; count; cur; // 向后移一位避免重复统计同一个起点 } std::cout 子序列出现次数: count \n; return 0; }第三个示例里的“cur”容易被忽略。如果不移动第二次search会永远在同一个位置找到同一个子序列形成死循环。移动一位会漏掉重叠匹配吗会。如果子序列之间可以重叠比如{1,1}在{1,1,1}中应该出现2次上面的写法只会统计1次。对于重叠统计需要每次把cur移动到本次匹配起始位置的下一位而起始位置的下一位置就是从当前下标1开始这等价于cur所以重叠统计恰恰应该这样写。如果你的业务要求不重叠计数把那行改成cur it pat.size();更好。3.3 VS Code里常见的两个坑IntelliSense失效和中文乱码第一个坑是“所有函数变量都没办法跳转”这个前面提到了大概率是includePath配置问题而不是代码问题。第二个坑是程序输出中文乱码常见于Windows终端。解决方案有两个一是源文件保存为UTF-8编码并且在编译参数里加上-finput-charsetUTF-8 -fexec-charsetUTF-8二是在运行前执行chcp 65001把终端切到UTF-8代码页。如果你用MSVC则需要保证源文件是带BOM的UTF-8否则MSVC会按ANSI解析中文字符串。调试的时候我习惯在VS Code的监视窗口里看迭代器的“距离值”比如监视it - haystack.begin()的值而不是打印整个向量。这种做法的好处是能在不破坏容器结构的情况下快速定位到当前迭代器指向的索引位置比逐个检查元素快很多。迭代器本质上是“位置的概念”学会用距离来表达位置调试STL代码会顺畅不少。4. 避坑指南这些边界条件会让你debug到崩溃4.1 空序列、全匹配与找不到的语义search和search_n的边界行为非常容易写错我一一梳理一下。空主序列如果haystack为空即first last那么任何search或search_n调用都应该返回haystack.end()因为根本没有可搜索的位置。这个行为是循环自然终止的结果不需要特殊处理但初学者经常不检查主序列是否为空就解引用返回值此时迭代器指向end解引用是未定义行为程序可能崩也可能不崩排查起来很折磨人。子序列为空search传入的子序列如果为空标准库会直接返回first。这个语义在有些业务里符合直觉有些则不符合。比如“空序列是否存在于任意序列中”数学上通常认为空序列匹配任何位置返回first是合理的设计。search_n的count为0时同理。如果你写代码时发现结果诡异先检查一下是不是传了空模式或者count0。找到的位置就在末尾假设主序列是[1, 2, 3, 4]子序列是[4]search会返回指向4的那个迭代器它和end只差一个位置。这种情况不算找不到必须小心处理。我在实际项目里就摔过一次找到结果后直接it想接着往后搜结果迭代器跳到了end下一次循环里没判断就直接用了程序崩溃。正确做法是每次循环开头重新检查it ! container.end()。4.2 谓词的“相等”语义与副作用陷阱带谓词版本最容易让人误解的地方在于那个二元谓词表达的是“两个元素之间的关系”而不是“元素是否等于某个固定值”。比如search_n(begin, end, 3, 80, [](int a, int b) { return a b; })的意思是找到连续3个满足“自身值 80”的元素。这里的谓词第一个参数是容器里的元素第二个参数是value两个参数的顺序一定不能写反否则结果完全不对。谓词还必须是纯函数性质的不应该有状态也不应该修改被比较的元素。标准库在匹配过程中可能会多次调用同一个谓词如果你在lambda里写了一个计数器每次调用计数加一整个算法结果可能因为求值顺序不同而不稳定。这种问题在单线程下偶尔“碰巧能跑对”一旦换编译器版本或者改优化选项就出怪事非常难查。写谓词时务必保持无状态、无副作用。另一个高频操作是remove_if和erase搭配。很多人误以为remove_if会真正删除元素实际上它只是把保留的元素搬到前面后面的元素还留在容器里。必须配合container.erase(remove_if(...), container.end())才能真正删除。这和search没直接关系但属于同一类“中了标准库语义陷阱”的高发地带顺手提醒一句。4.3 不同容器的验证与自定义类型search和search_n要求迭代器至少是ForwardIterator正向迭代器这意味着vector、deque、list、forward_list都可以用但std::istream_iterator这种单遍迭代器不能用来作为主序列的范围因为它只能前向读取一次无法重复遍历。写泛型代码时如果接到任意迭代器要克制住“传给search试试”的冲动先确认迭代器类别。自定义结构体的比较也要注意。如果不提供operator值版本的search会编译失败因为标准库实现内部默认使用运算符。此时有两个选择一是为你的类型重载operator二是使用谓词版本。工程上我更喜欢谓词版本因为可以按业务语义灵活定义“相等”而且不会污染全局运算符。看一个例子struct Reading { int sensor_id; double value; }; bool sameIdIgnoreValue(const Reading a, const Reading b) { return a.sensor_id b.sensor_id; } // 查找连续三个 sensor_id 相同的记录 auto it std::search_n(readings.begin(), readings.end(), 3, Reading{0, 0.0}, sameIdIgnoreValue);这里我把目标值设成一个{0, 0.0}的占位对象然后谓词里只看sensor_id这样就实现了“连续三个相同传感器”的检测。目标值本身是什么并不重要重要的是谓词怎么定义。这个小技巧能让search_n在自定义类型上非常灵活。5. 经验谈一个成熟的STL使用者如何选“找”的算法5.1 一张表教你快速选择我在实际写代码时会按这样的顺序决策。如果只是找单个值find和find_if是第一选择不需要思考。如果要找一整段连续子序列优先看容器类型如果是std::string直接用find成员函数如果是其他容器用std::search。如果要找连续n个相同或相近值用std::search_n。如果目标不是一段而是多个候选值中的任何一个用std::find_first_of。如果只是想比较两个区间的对应位置是否一致用std::equal或std::mismatch。选型条件第一选择备选方案单个元素存在性findany_of单个元素满足条件find_iffind_if_not连续子序列匹配searchranges::search连续相同值匹配search_n自定义循环子串匹配string::findsearch也可用但性价比低多个候选任意命中find_first_of循环调用find这张表的价值在于帮你建立一个默认倾向绝大多数“查找连续片段”的需求标准库已经覆盖了没必要自己撸起袖子写循环。反过来说如果你发现自己为了完成一个查找写了三层循环加一堆边界判断那大概率是没用对库函数。5.2 从刷题到工程什么时候值得手写刷算法题的时候search和search_n很少被提到因为竞赛更看重手写数据结构而且OJ的评测数据往往故意展示朴素匹配的性能短板。但在工程代码里我看到太多人自己写循环实现search的功能写出来的代码不但冗长边界错误还频发。我个人的经验是工程代码优先用标准库版本只有当性能分析明确指向这里存在瓶颈并且目标场景满足KMP或哈希等高效算法的前提条件时才值得手写。如果编译器支持C20还可以关注std::ranges::search它接收的范围概念更现代调用时能避免“主序列end传错”这类手动错误。ranges::search返回的也是迭代器配合std::span等视图用起来很顺手。不过C20的ranges算法还很新如果项目尚未启用新标准继续用传统版本完全没问题。最后我在实际使用中还有一个小习惯把要匹配的模式提取成命名良好的常量而不是在函数调用里直接写一个字面量。比如const std::vectorstd::string kAuthDangerSequence {登录, 读取, 写入}; auto it std::search(log.begin(), log.end(), kAuthDangerSequence.begin(), kAuthDangerSequence.end());这样代码的自解释性强了很多后来人读代码时一眼就能看懂“模式是什么为什么这么匹配”而不是在一堆魔法数字里猜业务意图。写算法代码的时候可读性往往比节省几行更宝贵。踩过几次坑之后我最大的体会是标准库算法看起来简单但它们对迭代器和边界行为的语义有严格约定稍不小心就会写出“碰巧能跑”的代码。下次你在代码里需要查找连续子序列或连续重复值时不妨先停下来想想search和search_n是不是已经能解决问题。多数时候标准库给你的方案比临时手写的循环可靠得多。