CODEWITHSUNDEEP
c++c++23
frozenca
frozenca

Reputation: 877

What's the time complexity of std::string::contains in C++23?

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.

Upvotes: 3

Views: 1473

Answers (2)

PFee
PFee

Reputation: 273

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

Upvotes: 0

Nicol Bolas
Nicol Bolas

Reputation: 474136

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.

Upvotes: 7

Related Questions