可能重复：
C++ string::find complex
STL中字符串库自带的查找操作的时间复杂度是多少？
问问题
8764 次
3 回答
3
该标准第 21.4.7.2 节并未就复杂性提供任何保证。
但是，您可以合理地假设std::basic_string::find要搜索的字符串的长度需要线性时间，因为即使是简单的算法（检查每个子字符串是否相等）也具有这种复杂性，并且构造函数不太可能std::string构建一个花哨的索引结构来启用任何东西比那更快。
根据实现的不同，所搜索模式的复杂性可能在线性和常数之间合理变化。
于 2012-12-10T11:36:02.660 回答
0
正如评论中指出的那样，标准没有具体说明。
但是，由于std::string它是一个通用容器，并且它不能对它所包含的字符串的性质做出任何假设，因此您可以合理地假设 O(n)在您搜索单个char.
于 2012-12-10T11:40:20.870 回答
-3
最多执行与 [first,last) 范围内的元素数量一样多的比较。
于 2012-12-10T11:33:28.550 回答