cppreference说std::string::contains
即将问世,https://en.cppreference.com/w/cpp/string/basic_string/contains
但是没有运行时要求。它能保证在线性时间内运行吗?(比如说,在实现中使用KMP算法(还是二次时间?
我试着在当前的C++标准草案中找到它(http://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf),但我找不到推荐人。
根据最新的草案,contains
为:
等价于:
return basic_string_view<charT, traits>(data(), size()).contains(x);
string_view
函数为:
等效于:
return find(x) != npos;
由于用basic_string_view::npos
测试整数的等式是一个恒定的时间运算,因此时间复杂度将是basic_string_view::find
:的时间复杂度
本小节中的成员函数最坏的情况下具有复杂性O(size((*str.size(((,尽管实现应该做得更好。
建议书(P1679(表明contains
等同于find(x) != npos
。
最坏的情况下,复杂度可能是O(size((*str.size(((。如果两个字符串都已知,则最多可以在编译时执行该操作,因为std::string::contains
和std::string_view::contains
都是constexpr
方法。
注意,目前(GCC 11(只有std::string_view
在libstdc++中具有constexpr
功能。
琐碎的constexpr示例:https://godbolt.org/z/Ejosx43bM
提交将contains((添加到GCC 11的libstdc++:https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=f004d6d9fab9fe732b94f0e7d 254700795a37f30