Какова временная сложность std :: string :: contains в C ++ 23?

Question

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), но мне не удалось найти ссылку.

Answer 1

Исходя из самого последнего черновика , contains является:

Эквивалентно:

       return basic_string_view<charT, traits>(data(), size()).contains(x);

С <tcode id="25720055"></tcode>функция, являющаяся :

Эквивалентно: return find(x) != npos;

Поскольку проверка на равенство целого числа с basic_string_view::nposявляется операцией с постоянным временем, временная сложность будет такой же, как у <tcode id="25720058"></tcode>:

Функции-члены в этом подпункте в худшем случае имеют сложность O (size () * str.size()), хотя реализации должны работать лучше.

Answer 2

Предложение (P1679) указывает на то, что contains эквивалентно find(x) != npos.

В худшем случае сложность может быть O (size() * str.size()). В лучшем случае операция может быть выполнена во время компиляции, если известны обе строки, поскольку обе std::string::contains а также std::string_view::contains методы.

Обратите внимание, что в настоящее время (GCC 11) только std::string_view имеет constexpr функциональность в libstdc++.

Тривиальный пример constexpr: https://godbolt.org/z/Ejosx43bM

Добавление фиксации содержит () в libstdc ++ для GCC 11: https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=f004d6d9fab9fe732b94f0e7d254700795a37f30