Search code examples
c++c++23

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.

Solution

  • 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.