string_ref: a non-owning reference to a string, revision 2

Why not change <my-pet-feature>?

I haven't taken every suggestion to change string_ref. This section explains the rationales.

Remove the find*() methods

Many people have asked why we aren't removing all of the find* methods, since they're widely considered a wart on std::string. First, we'd like to make it as easy as possible to convert code to use string_ref, so it's useful to keep the interface as similar as reasonable to std::string. Second, replacing these these methods with uses of the standard algorithms library requires switching from indices to iterators, writing somewhat-complicated conversion code, and/or passing custom lambdas to find_if. Let's look at the replacement code for each of the remaining methods:

haystack.find(needle)

Replaced by:

auto iter = std::search(haystack.begin(), haystack.end(),
                        needle.begin(), needle.end());
return iter == haystack.end() ? std::string::npos : iter - haystack.begin();

haystack.rfind(needle)

Replaced by:

auto iter = std::find_end(haystack.begin(), haystack.end(),
                          needle.begin(), needle.end());
return iter == haystack.end() ? std::string::npos : iter - haystack.begin();

haystack.find_first_of(needles)

Replaced by:

auto iter = std::find_first_of(haystack.begin(), haystack.end(),
                               needles.begin(), needles.end());
return iter == haystack.end() ? std::string::npos : iter - haystack.begin();

haystack.find_last_of(needles)

Replaced by:

auto iter = std::find_first_of(haystack.rbegin(), haystack.rend(),
                               needles.begin(), needles.end());
return iter == haystack.rend() ? std::string::npos : iter.base() - 1 - haystack.begin();

haystack.find_first_not_of(straw)

Replaced by:

auto iter = std::find_if(haystack.begin(), haystack.end(), [&](char c) {
  return std::find(straw.begin(), straw.end(), c) == straw.end();
});
return iter == haystack.end() ? std::string::npos : iter - haystack.begin();

haystack.find_last_not_of(straw)

Replaced by:

auto iter = std::find_if(haystack.rbegin(), haystack.rend(), [&](char c) {
  return std::find(straw.begin(), straw.end(), c) == straw.end();
});
return iter == haystack.rend() ? std::string::npos : iter.base() - 1 - haystack.begin();

find, rfind, and find_first_of are straightforward, although the conversion from indices to iterators would prevent many users from switching even to them. find_last_of, find_first_not_of, and find_last_not_of get progressively worse to handle even in an iterator-based function.

Make `basic_string_ref<char>` mutable

… and use basic_string_ref<const char> for the constant case. The constant case is enough more common than the mutable case that it needs to be the default. Making the mutable case the default would prevent passing string literals into string_ref parameters, which would defeat a significant use case for string_ref. In a somewhat analogous sitation, LLVM defined an ArrayRef class in Feb 2011, and didn't find a need for the matching MutableArrayRef until Jan 2012. They still haven't needed a mutable version of StringRef. One possible reason for this is that most uses that need to modify a string also need to be able to change its length, and that's impossible through even a mutable version of string_ref.

We could use typedef basic_string_ref<const char> string_ref to make the immutable case the default while still supporting the mutable case using the same template. I haven't gone this way because it would complicate the template's definition without significantly helping users.

Add an `explicit operator bool`

This would be an abbreviation for !empty(), usable for initialization in if statements. I didn't add this because it would be inconsistent with the rest of the containers library, but if another proposal adds it to the rest of the containers, that proposal should also add it to string_ref.

Avoid `strlen("string literal")`

With a constructor of the form:

template<size_t N>
basic_string_ref(const charT (&str)[N]);

we could avoid a strlen() call when a basic_string_ref is constructed from a string literal. Unfortunately, this constructor does completely the wrong thing when called like:

char space[PATH_MAX];
snprintf(space, sizeof(space), "some string");
string_ref str(space);

I don't know any way to distinguish string literals from local arrays, so the only way to be safe is to call strlen() on array arguments. Some people have suggested a string_ref::from_literal method, but I consider that too verbose.

Even the original worry is obsolete given modern optimizers: both gcc and clang optimize strlen("Literal") into a constant, making the safe code as efficient as the template. Other implementations should provide the same optimization as a QoI issue.

Define comparison on `begin`/`end` instead of the elements

Operations on string_ref apply to the characters in the string, and not the pointers that refer to the characters. This introduces the possibility that the underlying characters might change while a string_ref referring to them is in an associative container, which would break the container, but we believe this risk is worthwhile because it matches existing practice and matches user intentions more often.

Wait for `contiguous_range<charT>`

contiguous_range<T> along with an is_contiguous<IteratorOrRange> trait would be useful for many purposes. However, a reference class that's specifically for strings provides a couple extra benefits:

string_ref can have an implicit conversion from const char*, while it would be a surprising special case to provide that on contiguous_range<const char*>.
We can provide a subset of basic_string's interface to ease transitions to and from ownership, while such methods would be very strange on contiguous_range.
basic_string_ref takes a char_traits argument allowing customization of comparison. contiguous_range likely wouldn't.
We compare and hash string_refs using the elements they refer to. There's a stronger argument to compare a contiguous_range using the pointers inside it, meaning two contiguous_range<char>s of the same characters might compare unequal.
The notion of a "string" is different from the notion of a range of characters, which is one reason we have std::string in addition to std::vector<char>. Users benefit from saying which they mean in interfaces.

Make `string_ref` null-terminated

Doing this naively makes substr impossible to implement without a copy. We could imagine inventing a more complex interface that records whether the input string was null-terminated, giving the user the option to use that string when trying to pass a string_ref to a legacy or C function expecting a null-terminated const char*. This proposal doesn't include such an interface because it would make string_ref bigger or more expensive, and because there's no existing practice to guide us toward the right interface.

Another option would be to define a separate zstring_ref class to represent null-terminated strings and let it decay to string_ref when necessary. That's plausible but not part of this proposal.

s/remove_prefix/pop_front/, etc.

In Kona 2012, I proposed a range<> class with pop_front, etc. members that adjusted the bounds of the range. Discussion there indicated that committee members were uncomfortable using the same names for lightweight range operations as container operations. Existing practice doesn't agree on a name for this operation, so I've kept the name used by Google's StringPiece.

Allow implicit conversion from more types.

Beman Dawes suggested defining std::string_ref_{begin,end} and allowing users to add overloads within std. Using ADL is a slight variant. We could also allow conversion from any type with .data() and .size() members returning the right types.

Ultimately, I think we want to allow this conversion based on detecting contiguous ranges. Any constructor we add to work around that is going to look like a wart in a couple years. I think we'll be better off making users explicitly convert when they can't add an appropriate conversion operator, and then we can add the optimal constructor when contiguous iterators make it into the library.

Wording

Wording changes are being maintained at https://github.com/google/cxx-std-draft/compare/string-ref and a snapshot of the changes is copied below. A very early implementation is at https://github.com/google/libcxx/compare/string-ref. Patches and pull requests are welcome against both.

Clause 17, Library introduction

Modify the note in [defns.component]

For example, the class ~~template~~ templates basic_string and basic_string_ref and the non-member function templates that operate on strings are referred to as the string component.

Clause 20, General utilities library

Add a constructor to class bitset in [template.bitset]

template<class charT, class traits>
  explicit bitset(
    basic_string_ref<charT,traits> str,
    charT zero = charT(’0’), charT one = charT(’1’));

Modify the constructor definitions in [bitset.cons]

template <class charT, class traits, class Allocator>
explicit
bitset(const basic_string<charT, traits, Allocator>& str,
       typename basic_string<charT, traits, Allocator>::size_type pos = 0,
       typename basic_string<charT, traits, Allocator>::size_type n =
         basic_string<charT, traits, Allocator>::npos,
       charT zero = charT(’0’), charT one = charT(’1’));

Effects: Equivalent to bitset(basic_string_ref<charT, traits>(str).substr(pos, n), zero, one)

template <class charT, class traits>
explicit
bitset(basic_string_ref<charT, traits> str,
       charT zero = charT(’0’), charT one = charT(’1’));

Requires: pos <= str.size().

Throws: out_of_range if pos > str.size().

Effects: Determines the effective length rlen of the initializing string as the smaller of n and str.size() - pos.

~~The function then throws~~ Throws: invalid_argument if any of the ~~rlen~~ characters in str ~~beginning at position pos~~ is other than zero or one. The function uses traits::eq() to compare the character values.

~~Otherwise, the~~ Effects: function constructs an object of class bitset<N>, initializing the first M bit positions to values determined from the corresponding characters in the string str. M is the smaller of N and rlenstr.size().

An element of the constructed string has value zero if the corresponding character in str, ~~beginning at position pos,~~ is 0 zero. Otherwise, the element has the value 1. Character position pos + M - 1 corresponds to bit position zero. Subsequent decreasing character positions correspond to increasing bit positions.

If M < N, remaining bit positions are initialized to zero.

template <class charT>
  explicit bitset(
    const charT* str,
    typename basic_string<charT>::size_type n = basic_string<charT>::npos,
    charT zero = charT(’0’), charT one = charT(’1’));

Effects: Constructs an object of class bitset<N> as if by

bitset(
  n == basic_string<charT>::npos
    ? basic_string_ref<charT>(str)
    : basic_string_ref<charT>(str, n),
  0, n, zero, one)

Clause 21, Strings library

Modify [char.traits.specializations.char], [char.traits.specializations.char16_t], [char.traits.specializations.char32_t], and [char.traits.specializations.wchar.t]

This implements the proposed resolution of LWG issue ####. I could take it out at the cost of making basic_string_ref(const charT*) and all of the comparison operators and methods non-constexpr.

static constexpr int compare(const char_type* s1, const char_type* s2, size_t n);
static constexpr size_t length(const char_type* s);
static constexpr const char_type* find(const char_type* s, size_t n,
                                       const char_type& a);

The header <string> defines the basic_string class template for manipulating varying-length sequences of char-like objects and four typedefs, string, u16string, u32string, and wstring, that name the specializations basic_string<char>, basic_string<char16_t>, basic_string<char32_t>, and basic_string<wchar_t>, respectively.

<string> also defines the basic_string_ref class template for referring to constant sequences of char-like objects and four typedefs, string_ref, u16string_ref, u32string_ref, and wstring_ref, that name the specializations basic_string_ref<char>, basic_string_ref<char16_t>, basic_string_ref<char32_t>, and basic_string_ref<wchar_t>, respectively.

Add to the appropriate places within "Header <string> synopsis"

  // [basic.string.ref], basic_string_ref:
  template<class charT, class traits = char_traits<charT>>
      class basic_string_ref;

  // [string.ref.comparison], non-member basic_string_ref comparison functions
  template<typename charT, typename traits>
  bool operator==(basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  template<typename charT, typename traits>
  bool operator!=(basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  template<typename charT, typename traits>
  bool operator< (basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  template<typename charT, typename traits>
  bool operator> (basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  template<typename charT, typename traits>
  bool operator<=(basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  template<typename charT, typename traits>
  bool operator>=(basic_string_ref<charT, traits> x, basic_string_ref<charT, traits> y);
  // Sufficient additional overloads to allow mixed comparisons with any type
  // that has an implicit conversion to basic_string_ref<charT, traits>.

  // [string.ref.nonmem], other non-member basic_string_ref functions
  template<class charT, class traits = char_traits<charT>,
           class Allocator = allocator<charT> >
    basic_string<charT, traits, Allocator> to_string(
      basic_string_ref<charT, traits>,
      const Allocator& a = Allocator());

  template<class charT, class traits>
    basic_ostream<charT, traits>&
      operator<<(basic_ostream<charT, traits>& os,
                 basic_string_ref<charT,traits> str);

  // basic_string_ref typedef names
  typedef basic_string_ref<char> string_ref;
  typedef basic_string_ref<char16_t> u16string_ref;
  typedef basic_string_ref<char32_t> u32string_ref;
  typedef basic_string_ref<wchar_t> wstring_ref;

It would be nice to remove the string overloads for the numeric conversion functions, but that could break code that relies on an implicit conversion to string. Instead, we need to add const char* overloads to avoid ambiguity.

I'd also like to add optional<T> stox_consume(string_ref&, int base=10) if/when optional becomes available.

  int stoi(string_ref str, size_t* idx = 0, int base = 10);
  int stoi(const char* str, size_t* idx = 0, int base = 10);
  long stol(string_ref str, size_t* idx = 0, int base = 10);
  long stol(const char* str, size_t* idx = 0, int base = 10);
  unsigned long stoul(string_ref str, size_t* idx = 0, int base = 10);
  unsigned long stoul(const char* str, size_t* idx = 0, int base = 10);
  long long stoll(string_ref str, size_t* idx = 0, int base = 10);
  long long stoll(const char* str, size_t* idx = 0, int base = 10);
  unsigned long long stoull(string_ref str, size_t* idx = 0, int base = 10);
  unsigned long long stoull(const char* str, size_t* idx = 0, int base = 10);
  float stof(string_ref str, size_t* idx = 0);
  float stof(const char* str, size_t* idx = 0);
  double stod(string_ref str, size_t* idx = 0);
  double stod(const char* str, size_t* idx = 0);
  long double stold(string_ref str, size_t* idx = 0);
  long double stold(const char* str, size_t* idx = 0);

  int stoi(wstring_ref str, size_t* idx = 0, int base = 10);
  int stoi(const wchar_t* str, size_t* idx = 0, int base = 10);
  long stol(wstring_ref str, size_t* idx = 0, int base = 10);
  long stol(const wchar_t* str, size_t* idx = 0, int base = 10);
  unsigned long stoul(wstring_ref str, size_t* idx = 0, int base = 10);
  unsigned long stoul(const wchar_t* str, size_t* idx = 0, int base = 10);
  long long stoll(wstring_ref str, size_t* idx = 0, int base = 10);
  long long stoll(const wchar_t* str, size_t* idx = 0, int base = 10);
  unsigned long long stoull(wstring_ref str, size_t* idx = 0, int base = 10);
  unsigned long long stoull(const wchar_t* str, size_t* idx = 0, int base = 10);
  float stof(wstring_ref str, size_t* idx = 0);
  float stof(const wchar_t* str, size_t* idx = 0);
  double stod(wstring_ref str, size_t* idx = 0);
  double stod(const wchar_t* str, size_t* idx = 0);
  long double stold(wstring_ref str, size_t* idx = 0);
  long double stold(const wchar_t* str, size_t* idx = 0);

  template <> struct hash<string_ref>;
  template <> struct hash<u16string_ref>;
  template <> struct hash<u32string_ref>;
  template <> struct hash<wstring_ref>;

Add a subclause "x.y Class template basic_string_ref [basic.string.ref]"

The class template basic_string_ref describes objects that can refer to a constant sequence of arbitrary char-like objects with the first element of the sequence at position zero. In the rest of this Clause, the type of the char-like objects held in a basic_string_ref object is designated by charT.

[Note: The library provides implicit conversions from const charT* and std::basic_string<charT, ...> to std::basic_string_ref<charT, ...> so that user code can accept just std::basic_string_ref<charT> as a parameter wherever a sequence of characters is expected. User-defined types should define their own implicit conversions to std::basic_string_ref in order to interoperate with these functions. — end note ]

The complexity of member functions is O(1) unless otherwise specified.

namespace std {
  template<typename charT, typename traits = char_traits<charT>>
  class basic_string_ref {
    public:
    // types
    typedef charT value_type;
    typedef const charT* pointer;
    typedef const charT* const_pointer;
    typedef const charT& reference;
    typedef const charT& const_reference;
    typedef implementation-defined const_iterator; // See [string.ref.iterators]
    typedef const_iterator iterator;  // [Footnote: Because basic_string_ref refers to a constant sequence, iterator and const_iterator are the same type. --end footnote]
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef const_reverse_iterator reverse_iterator;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    static constexpr size_type npos = size_type(-1);

    // [string.ref.cons], construct/copy
    constexpr basic_string_ref() noexcept;
    constexpr basic_string_ref(const basic_string_ref&) noexcept = default;
    basic_string_ref& operator=(const basic_string_ref&) noexcept = default;
    constexpr basic_string_ref(const charT* str);
    constexpr basic_string_ref(const charT* str, size_type len);

No initializer_list constructor because [dcl.init.list]p6 says it would likely store a dangling reference into the string_ref.

    // [string.ref.iterators], iterators
    constexpr const_iterator begin() const noexcept;
    constexpr const_iterator end() const noexcept;
    constexpr const_iterator cbegin() const noexcept;
    constexpr const_iterator cend() const noexcept;

reverse_iterator methods aren’t constexpr because reverse_iterator isn’t a literal type. See LWG Issue 2208.

    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    const_reverse_iterator crend() const noexcept;

    // [string.ref.capacity], capacity
    constexpr size_type size() const noexcept;
    constexpr size_type length() const noexcept;
    constexpr size_type max_size() const noexcept;
    constexpr bool empty() const noexcept;

    // [string.ref.access], element access
    constexpr const charT& operator[](size_type pos) const;
    const charT& at(size_t pos) const;
    constexpr const charT& front() const;
    constexpr const charT& back() const;
    constexpr const charT* data() const noexcept;

    // [string.ref.modifiers], modifiers:
    void clear() noexcept;
    void remove_prefix(size_type n);
    void remove_suffix(size_type n);

    // [string.ref.ops], string operations:
    constexpr basic_string_ref substr(size_type pos, size_type n=npos) const;
    constexpr int compare(basic_string_ref s) const noexcept;
    constexpr int compare(const charT* s) const noexcept;
    constexpr bool starts_with(basic_string_ref s) const noexcept;
    constexpr bool starts_with(charT c) const noexcept;
    constexpr bool starts_with(const charT* s) const noexcept;
    constexpr bool ends_with(basic_string_ref s) const noexcept;
    constexpr bool ends_with(charT c) const noexcept;
    constexpr bool ends_with(const charT* s) const noexcept;
    size_type find(basic_string_ref s) const noexcept;
    size_type find(charT c) const noexcept;
    size_type find(const charT* s) const noexcept;
    size_type rfind(basic_string_ref s) const noexcept;
    size_type rfind(charT c) const noexcept;
    size_type rfind(const charT* s) const noexcept;
    size_type find_first_of(basic_string_ref s) const noexcept;
    size_type find_first_of(charT c) const noexcept;
    size_type find_first_of(const charT* s) const noexcept;
    size_type find_last_of(basic_string_ref s) const noexcept;
    size_type find_last_of(charT c) const noexcept;
    size_type find_last_of(const charT* s) const noexcept;
    size_type find_first_not_of(basic_string_ref s) const noexcept;
    size_type find_first_not_of(charT c) const noexcept;
    size_type find_first_not_of(const charT* s) const noexcept;
    size_type find_last_not_of(basic_string_ref s) const noexcept;
    size_type find_last_not_of(charT c) const noexcept;
    size_type find_last_not_of(const charT* s) const noexcept;
};

Each member function of the form

rt fx1(const charT* s); // such as compare(), find()

is equivalent to fx1(basic_string_ref(s)).

Each member function of the form

rt fx2(charT c); // such as starts_with(), find()

is equivalent to fx2(basic_string_ref(&c, 1)).

Add a sub-subclause "x.y.1 basic_string_ref constructors and assignment operators [string.ref.cons]"

constexpr basic_string_ref();

Effects: Constructs an empty basic_string_ref.

Postcondition: empty() == true and [data(),data()) is a valid range.

basic_string_ref(const charT* str);

Requires: [str,str + traits::length(str)) is a valid range.

Effects: Constructs a basic_string_ref referring to the same string as str, with the postconditions in Table [tab:string.ref.ctr.1]

Table [tab:string.ref.ctr.1] — basic_string_ref(const charT*) effects
Element	Value
data()	str
size()	traits::length(str)

Complexity: O(size())

constexpr basic_string_ref(const charT* str, size_type len);

Requires: str is not a null pointer and [str,str + len) is a valid range.

Effects: Constructs a basic_string_ref, with the postconditions in Table [tab:string.ref.ctr.2]

Table [tab:string.ref.ctr.2] — basic_string_ref(const charT*, size_type) effects
Element	Value
data()	str
size()	len

Add a sub-subclause "x.y.2 basic_string_ref iterator support [string.ref.iterators]"

typedef implementation-defined const_iterator;

A random-access, contiguous iterator type.

For a basic_string_ref str, any operation that invalidates a pointer in the range [str.data(), str.data()+str.size()) invalidates pointers and iterators returned from str’s methods.

constexpr const_iterator begin() const noexcept;
constexpr const_iterator cbegin() const noexcept;

Returns: An iterator referring to the first character in the string.

constexpr const_iterator end() const noexcept;
constexpr const_iterator cend() const noexcept;

Returns: An iterator which is the past-the-end value.

const_reverse_iterator rbegin() const noexcept;
const_reverse_iterator crbegin() const noexcept;

Returns: An iterator which is semantically equivalent to reverse_iterator(end()).

const_reverse_iterator rend() const noexcept;
const_reverse_iterator crend() const noexcept;

Returns: An iterator which is semantically equivalent to reverse_iterator(begin()).

Add a sub-subclause "x.y.3 basic_string_ref capacity [string.ref.capacity]"

size_type size() const noexcept;

Returns: A count of the number of char-like objects referred to by the string_ref.

Complexity: constant time.

size_type length() const noexcept;

Returns: size().

size_type max_size() const noexcept;

Returns: The size of the largest possible string_ref.

bool empty() const noexcept;

Returns: size() == 0.

Add a sub-subclause "x.y.4 basic_string_ref element access [string.ref.access]"

constexpr const_reference operator[](size_type pos) const;

Requires: pos < size().

Returns: *(begin() + pos)

Throws: Nothing.

[ Note: Unlike basic_string::operator[], basic_string_ref::operator[](size()) has undefined behavior instead of returning charT(). — end note ]

constexpr const_reference at(size_type pos) const;

Throws: out_of_range if pos >= size().

Returns: operator[](pos).

constexpr const charT& front() const;

Requires: !empty()

Effects: Equivalent to operator[](0).

constexpr const charT& back() const;

Requires: !empty()

Effects: Equivalent to operator[](size() - 1).

const charT* data() const noexcept;

Returns: A non-null pointer p such that p + i == &operator[](i) for each i in [0,size()).

[ Note: Unlike std::string::data() and string literals, data() may return a pointer to a buffer that is not null-terminated. Therefore it is typically a mistake to pass data() to a routine that takes just a const charT* and expects a null-terminated string. — end note ]

Add a sub-subclause "x.y.5 basic_string_ref modifiers [string.ref.modifiers]"

void clear() noexcept;

Effects: Equivalent to *this = basic_string_ref()

void remove_prefix(size_type n);

Requires: n <= size()

Effects: Equivalent to *this = substr(n, npos)

void remove_suffix(size_type n);

Requires: n <= size()

Effects: Equivalent to *this = substr(0, size() - n)

Add a sub-subclause "x.y.6 basic_string_ref string operations [string.ref.ops]"

[ Note: Unlike std::basic_string, std::basic_string_ref provides no whole-string methods with posi- tion or length parameters. Instead, users should use the substr() method to create the character sequence they’re actually interested in, and use that. — end note ]

basic_string_ref substr(size_type pos, size_type n = npos) const;

Throws: out_of_range if pos > size().

Effects: Determines the effective length rlen of the string to reference as the smaller of n and size() - pos.

Returns: basic_string_ref(data()+pos, rlen).

int compare(const basic_string_ref& str) const noexcept;

Effects: Determines the effective length rlen of the strings to compare as the smallest of size() and str.size(). The function then compares the two strings by calling traits::compare(data(), str.data(), rlen).

Complexity: O(rlen)

Returns: The nonzero result if the result of the comparison is nonzero. Otherwise, returns a value as indicated in Table [tab:string.ref.compare].

Table [tab:string.ref.compare] — compare() results
Condition	Return Value
size() < str.size()	< 0
size() == str.size()	0
size() > str.size()	> 0

bool starts_with(const basic_string_ref& prefix) const noexcept;

Complexity: O(min(size(), prefix.size()))

Returns: size() >= prefix.size() && substr(0, prefix.size()) == prefix

bool ends_with(const basic_string_ref& suffix) const noexcept;

Complexity: O(min(size(), suffix.size()))

Returns: size() >= suffix.size() && substr(size() - suffix.size(), npos) == suffix

Add a sub³clause "x.y.6.1 Searching basic_string_ref [string.ref.find]"

Member functions in this section have complexity O(size() * argument.size()) at worst, although implementations are encouraged to do better.

size_type find(const basic_string_ref& str) const noexcept;

Effects: Determines the lowest position xpos, if possible, such that both of the following conditions obtain:

xpos + str.size() <= size();
traits::eq(at(xpos+I), str.at(I)) for all elements I of the string referenced by str.