C++23 中 std::string::包含的时间复杂度是多少?



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::containsstd::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

最新更新