The cppreference says std::string::contains is coming out,
https://en.cppreference.com/w/cpp/string/basic_string/contains
but there is no runtime requirement. Is it guaranteed to run in linear time? (say, using KMP algorithm in implementation) or quadratic time?
I've tried to find it in the current C++ standard draft (http://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf), but I couldn't find the reference.
Going by the most recent draft, contains is:
Equivalent to:
return basic_string_view<charT, traits>(data(), size()).contains(x);
With the string_view function being:
Equivalent to:
return find(x) != npos;
Since equality testing an integer with basic_string_view::npos is a constant-time operation, the time complexity 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.
The proposal (P1679) indicates that contains is equivalent to find(x) != npos.
At worst, the complexity could be O(size() * str.size()). At best the operation can be performed at compile time if both strings are known since both std::string::contains and std::string_view::contains are constexpr methods.
Note, currently (GCC 11) only std::string_view has constexpr functionality in libstdc++.
Trivial constexpr example: https://godbolt.org/z/Ejosx43bM
The commit adding contains() to libstdc++ for GCC 11: https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=f004d6d9fab9fe732b94f0e7d254700795a37f30
