c++ - 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

经过 the most recent draft ，包含是:

Equivalent to:

return basic_string_view<charT, traits>(data(), size()).contains(x);

随着string_view function being :

Equivalent to: return find(x) != npos;

由于使用 basic_string_view::npos 对整数进行相等性测试是一个常量时间操作，因此时间复杂度 will be that of basic_string_view::find :

Member functions in this subclause have complexity O(size() * str.size()) at worst, although implementations should do better.