C++23 中 std::string::contains 的时间复杂度是多少？

Question

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）中找到它，但我找不到参考。

Answer 1

通过去最近的草案，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()) 复杂度，尽管实现应该做得更好。