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、contains 是：

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.

Answer 2

proposal (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

为 GCC 11 添加 contains() 到 libstdc++ 的提交：https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=f004d6d9fab9fe732b94f0e7d254700795a37f30