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

Question

首席执行官说std::string::contains要出来了，字符串/包含

但是不需要运行时。能保证在线性时间内运行吗？(例如，在实现中使用KMP算法)还是二次时间？

我试图在当前的C++标准草案(http://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf)中找到它，但是找不到引用。

Answer 1

通过最近的草案，contains是：

相当于： 返回basic_string_view(data()，size()).contains(x)；

与功能存在

相当于：return find(x) != npos;

由于使用basic_string_view::npos对整数进行相等测试是一个常数时间操作，所以时间复杂性basic_string_view::find。

这个子子句中的成员函数在最坏的情况下具有复杂性O(size() * str.size())，尽管实现应该做得更好。

Answer 2

提案(P1679)表示contains等同于find(x) != npos。

最坏的情况是，复杂度可能是O(size() * str.size())。如果知道这两个字符串，则最多可以在编译时执行操作，因为std::string::contains和std::string_view::contains都是constexpr方法。

注意，目前(GCC 11)只有std::string_view在libstdc++中具有constexpr功能。

平凡的常数示例：https://godbolt.org/z/Ejosx43bM

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