libcxx/include/string

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_STRING
  11 #define _LIBCPP_STRING
  12
  13 /*
  14     string synopsis
  15
  16 #include <compare>
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 template <class stateT>
  23 class fpos
  24 {
  25 private:
  26     stateT st;
  27 public:
  28     fpos(streamoff = streamoff());
  29
  30     operator streamoff() const;
  31
  32     stateT state() const;
  33     void state(stateT);
  34
  35     fpos& operator+=(streamoff);
  36     fpos  operator+ (streamoff) const;
  37     fpos& operator-=(streamoff);
  38     fpos  operator- (streamoff) const;
  39 };
  40
  41 template <class stateT> streamoff operator-(const fpos<stateT>& x, const fpos<stateT>& y);
  42
  43 template <class stateT> bool operator==(const fpos<stateT>& x, const fpos<stateT>& y);
  44 template <class stateT> bool operator!=(const fpos<stateT>& x, const fpos<stateT>& y);
  45
  46 template <class charT>
  47 struct char_traits
  48 {
  49     using char_type           = charT;
  50     using int_type            = ...;
  51     using off_type            = streamoff;
  52     using pos_type            = streampos;
  53     using state_type          = mbstate_t;
  54     using comparison_category = strong_ordering; // Since C++20 only for the specializations
  55                                                  // char, wchar_t, char8_t, char16_t, and char32_t.
  56
  57     static void assign(char_type& c1, const char_type& c2) noexcept;
  58     static constexpr bool eq(char_type c1, char_type c2) noexcept;
  59     static constexpr bool lt(char_type c1, char_type c2) noexcept;
  60
  61     static int              compare(const char_type* s1, const char_type* s2, size_t n);
  62     static size_t           length(const char_type* s);
  63     static const char_type* find(const char_type* s, size_t n, const char_type& a);
  64     static char_type*       move(char_type* s1, const char_type* s2, size_t n);
  65     static char_type*       copy(char_type* s1, const char_type* s2, size_t n);
  66     static char_type*       assign(char_type* s, size_t n, char_type a);
  67
  68     static constexpr int_type  not_eof(int_type c) noexcept;
  69     static constexpr char_type to_char_type(int_type c) noexcept;
  70     static constexpr int_type  to_int_type(char_type c) noexcept;
  71     static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;
  72     static constexpr int_type  eof() noexcept;
  73 };
  74
  75 template <> struct char_traits<char>;
  76 template <> struct char_traits<wchar_t>;
  77 template <> struct char_traits<char8_t>;  // C++20
  78 template <> struct char_traits<char16_t>;
  79 template <> struct char_traits<char32_t>;
  80
  81 template<class charT, class traits = char_traits<charT>, class Allocator = allocator<charT> >
  82 class basic_string
  83 {
  84 public:
  85 // types:
  86     typedef traits traits_type;
  87     typedef typename traits_type::char_type value_type;
  88     typedef Allocator allocator_type;
  89     typedef typename allocator_type::size_type size_type;
  90     typedef typename allocator_type::difference_type difference_type;
  91     typedef typename allocator_type::reference reference;
  92     typedef typename allocator_type::const_reference const_reference;
  93     typedef typename allocator_type::pointer pointer;
  94     typedef typename allocator_type::const_pointer const_pointer;
  95     typedef implementation-defined iterator;
  96     typedef implementation-defined const_iterator;
  97     typedef std::reverse_iterator<iterator> reverse_iterator;
  98     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  99
 100     static const size_type npos = -1;
 101
 102     basic_string()
 103         noexcept(is_nothrow_default_constructible<allocator_type>::value);                      // constexpr since C++20
 104     explicit basic_string(const allocator_type& a);                                             // constexpr since C++20
 105     basic_string(const basic_string& str);                                                      // constexpr since C++20
 106     basic_string(basic_string&& str)
 107         noexcept(is_nothrow_move_constructible<allocator_type>::value);                         // constexpr since C++20
 108     basic_string(const basic_string& str, size_type pos,
 109                  const allocator_type& a = allocator_type());                                   // constexpr since C++20
 110     basic_string(const basic_string& str, size_type pos, size_type n,
 111                  const Allocator& a = Allocator());                                             // constexpr since C++20
 112     constexpr basic_string(
 113         basic_string&& str, size_type pos, const Allocator& a = Allocator());                   // since C++23
 114     constexpr basic_string(
 115         basic_string&& str, size_type pos, size_type n, const Allocator& a = Allocator());      // since C++23
 116     template<class T>
 117         basic_string(const T& t, size_type pos, size_type n, const Allocator& a = Allocator()); // C++17, constexpr since C++20
 118     template <class T>
 119         explicit basic_string(const T& t, const Allocator& a = Allocator());                    // C++17, constexpr since C++20
 120     basic_string(const value_type* s, const allocator_type& a = allocator_type());              // constexpr since C++20
 121     basic_string(const value_type* s, size_type n, const allocator_type& a = allocator_type()); // constexpr since C++20
 122     basic_string(nullptr_t) = delete; // C++23
 123     basic_string(size_type n, value_type c, const allocator_type& a = allocator_type());        // constexpr since C++20
 124     template<class InputIterator>
 125         basic_string(InputIterator begin, InputIterator end,
 126                      const allocator_type& a = allocator_type());                               // constexpr since C++20
 127     template<container-compatible-range<charT> R>
 128       constexpr basic_string(from_range_t, R&& rg, const Allocator& a = Allocator());           // since C++23
 129     basic_string(initializer_list<value_type>, const Allocator& = Allocator());                 // constexpr since C++20
 130     basic_string(const basic_string&, const Allocator&);                                        // constexpr since C++20
 131     basic_string(basic_string&&, const Allocator&);                                             // constexpr since C++20
 132
 133     ~basic_string();                                                                            // constexpr since C++20
 134
 135     operator basic_string_view<charT, traits>() const noexcept;                                 // constexpr since C++20
 136
 137     basic_string& operator=(const basic_string& str);                                           // constexpr since C++20
 138     template <class T>
 139         basic_string& operator=(const T& t);                                                    // C++17, constexpr since C++20
 140     basic_string& operator=(basic_string&& str)
 141         noexcept(
 142              allocator_type::propagate_on_container_move_assignment::value ||
 143              allocator_type::is_always_equal::value );                                          // C++17, constexpr since C++20
 144     basic_string& operator=(const value_type* s);                                               // constexpr since C++20
 145     basic_string& operator=(nullptr_t) = delete; // C++23
 146     basic_string& operator=(value_type c);                                                      // constexpr since C++20
 147     basic_string& operator=(initializer_list<value_type>);                                      // constexpr since C++20
 148
 149     iterator       begin() noexcept;                                                            // constexpr since C++20
 150     const_iterator begin() const noexcept;                                                      // constexpr since C++20
 151     iterator       end() noexcept;                                                              // constexpr since C++20
 152     const_iterator end() const noexcept;                                                        // constexpr since C++20
 153
 154     reverse_iterator       rbegin() noexcept;                                                   // constexpr since C++20
 155     const_reverse_iterator rbegin() const noexcept;                                             // constexpr since C++20
 156     reverse_iterator       rend() noexcept;                                                     // constexpr since C++20
 157     const_reverse_iterator rend() const noexcept;                                               // constexpr since C++20
 158
 159     const_iterator         cbegin() const noexcept;                                             // constexpr since C++20
 160     const_iterator         cend() const noexcept;                                               // constexpr since C++20
 161     const_reverse_iterator crbegin() const noexcept;                                            // constexpr since C++20
 162     const_reverse_iterator crend() const noexcept;                                              // constexpr since C++20
 163
 164     size_type size() const noexcept;                                                            // constexpr since C++20
 165     size_type length() const noexcept;                                                          // constexpr since C++20
 166     size_type max_size() const noexcept;                                                        // constexpr since C++20
 167     size_type capacity() const noexcept;                                                        // constexpr since C++20
 168
 169     void resize(size_type n, value_type c);                                                     // constexpr since C++20
 170     void resize(size_type n);                                                                   // constexpr since C++20
 171
 172     template<class Operation>
 173     constexpr void resize_and_overwrite(size_type n, Operation op); // since C++23
 174
 175     void reserve(size_type res_arg);                                                            // constexpr since C++20
 176     void reserve(); // deprecated in C++20
 177     void shrink_to_fit();                                                                       // constexpr since C++20
 178     void clear() noexcept;                                                                      // constexpr since C++20
 179     bool empty() const noexcept;                                                                // constexpr since C++20
 180
 181     const_reference operator[](size_type pos) const;                                            // constexpr since C++20
 182     reference       operator[](size_type pos);                                                  // constexpr since C++20
 183
 184     const_reference at(size_type n) const;                                                      // constexpr since C++20
 185     reference       at(size_type n);                                                            // constexpr since C++20
 186
 187     basic_string& operator+=(const basic_string& str);                                          // constexpr since C++20
 188     template <class T>
 189         basic_string& operator+=(const T& t);                                                   // C++17, constexpr since C++20
 190     basic_string& operator+=(const value_type* s);                                              // constexpr since C++20
 191     basic_string& operator+=(value_type c);                                                     // constexpr since C++20
 192     basic_string& operator+=(initializer_list<value_type>);                                     // constexpr since C++20
 193
 194     basic_string& append(const basic_string& str);                                              // constexpr since C++20
 195     template <class T>
 196         basic_string& append(const T& t);                                                       // C++17, constexpr since C++20
 197     basic_string& append(const basic_string& str, size_type pos, size_type n=npos);             // C++14, constexpr since C++20
 198     template <class T>
 199         basic_string& append(const T& t, size_type pos, size_type n=npos);                      // C++17, constexpr since C++20
 200     basic_string& append(const value_type* s, size_type n);                                     // constexpr since C++20
 201     basic_string& append(const value_type* s);                                                  // constexpr since C++20
 202     basic_string& append(size_type n, value_type c);                                            // constexpr since C++20
 203     template<class InputIterator>
 204         basic_string& append(InputIterator first, InputIterator last);                          // constexpr since C++20
 205     template<container-compatible-range<charT> R>
 206       constexpr basic_string& append_range(R&& rg);                                             // C++23
 207     basic_string& append(initializer_list<value_type>);                                         // constexpr since C++20
 208
 209     void push_back(value_type c);                                                               // constexpr since C++20
 210     void pop_back();                                                                            // constexpr since C++20
 211     reference       front();                                                                    // constexpr since C++20
 212     const_reference front() const;                                                              // constexpr since C++20
 213     reference       back();                                                                     // constexpr since C++20
 214     const_reference back() const;                                                               // constexpr since C++20
 215
 216     basic_string& assign(const basic_string& str);                                              // constexpr since C++20
 217     template <class T>
 218         basic_string& assign(const T& t);                                                       // C++17, constexpr since C++20
 219     basic_string& assign(basic_string&& str);                                                   // constexpr since C++20
 220     basic_string& assign(const basic_string& str, size_type pos, size_type n=npos);             // C++14, constexpr since C++20
 221     template <class T>
 222         basic_string& assign(const T& t, size_type pos, size_type n=npos);                      // C++17, constexpr since C++20
 223     basic_string& assign(const value_type* s, size_type n);                                     // constexpr since C++20
 224     basic_string& assign(const value_type* s);                                                  // constexpr since C++20
 225     basic_string& assign(size_type n, value_type c);                                            // constexpr since C++20
 226     template<class InputIterator>
 227         basic_string& assign(InputIterator first, InputIterator last);                          // constexpr since C++20
 228     template<container-compatible-range<charT> R>
 229       constexpr basic_string& assign_range(R&& rg);                                             // C++23
 230     basic_string& assign(initializer_list<value_type>);                                         // constexpr since C++20
 231
 232     basic_string& insert(size_type pos1, const basic_string& str);                              // constexpr since C++20
 233     template <class T>
 234         basic_string& insert(size_type pos1, const T& t);                                       // constexpr since C++20
 235     basic_string& insert(size_type pos1, const basic_string& str,
 236                          size_type pos2, size_type n);                                          // constexpr since C++20
 237     template <class T>
 238         basic_string& insert(size_type pos1, const T& t, size_type pos2, size_type n);          // C++17, constexpr since C++20
 239     basic_string& insert(size_type pos, const value_type* s, size_type n=npos);                 // C++14, constexpr since C++20
 240     basic_string& insert(size_type pos, const value_type* s);                                   // constexpr since C++20
 241     basic_string& insert(size_type pos, size_type n, value_type c);                             // constexpr since C++20
 242     iterator      insert(const_iterator p, value_type c);                                       // constexpr since C++20
 243     iterator      insert(const_iterator p, size_type n, value_type c);                          // constexpr since C++20
 244     template<class InputIterator>
 245         iterator insert(const_iterator p, InputIterator first, InputIterator last);             // constexpr since C++20
 246     template<container-compatible-range<charT> R>
 247       constexpr iterator insert_range(const_iterator p, R&& rg);                                // C++23
 248     iterator      insert(const_iterator p, initializer_list<value_type>);                       // constexpr since C++20
 249
 250     basic_string& erase(size_type pos = 0, size_type n = npos);                                 // constexpr since C++20
 251     iterator      erase(const_iterator position);                                               // constexpr since C++20
 252     iterator      erase(const_iterator first, const_iterator last);                             // constexpr since C++20
 253
 254     basic_string& replace(size_type pos1, size_type n1, const basic_string& str);               // constexpr since C++20
 255     template <class T>
 256     basic_string& replace(size_type pos1, size_type n1, const T& t);                            // C++17, constexpr since C++20
 257     basic_string& replace(size_type pos1, size_type n1, const basic_string& str,
 258                           size_type pos2, size_type n2=npos);                                   // C++14, constexpr since C++20
 259     template <class T>
 260         basic_string& replace(size_type pos1, size_type n1, const T& t,
 261                               size_type pos2, size_type n);                                     // C++17, constexpr since C++20
 262     basic_string& replace(size_type pos, size_type n1, const value_type* s, size_type n2);      // constexpr since C++20
 263     basic_string& replace(size_type pos, size_type n1, const value_type* s);                    // constexpr since C++20
 264     basic_string& replace(size_type pos, size_type n1, size_type n2, value_type c);             // constexpr since C++20
 265     basic_string& replace(const_iterator i1, const_iterator i2, const basic_string& str);       // constexpr since C++20
 266     template <class T>
 267         basic_string& replace(const_iterator i1, const_iterator i2, const T& t);                // C++17, constexpr since C++20
 268     basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s, size_type n); // constexpr since C++20
 269     basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s);           // constexpr since C++20
 270     basic_string& replace(const_iterator i1, const_iterator i2, size_type n, value_type c);     // constexpr since C++20
 271     template<class InputIterator>
 272         basic_string& replace(const_iterator i1, const_iterator i2, InputIterator j1, InputIterator j2); // constexpr since C++20
 273     template<container-compatible-range<charT> R>
 274       constexpr basic_string& replace_with_range(const_iterator i1, const_iterator i2, R&& rg); // C++23
 275     basic_string& replace(const_iterator i1, const_iterator i2, initializer_list<value_type>);  // constexpr since C++20
 276
 277     size_type copy(value_type* s, size_type n, size_type pos = 0) const;                        // constexpr since C++20
 278     basic_string substr(size_type pos = 0, size_type n = npos) const;                           // constexpr in C++20, removed in C++23
 279     basic_string substr(size_type pos = 0, size_type n = npos) const&;                          // since C++23
 280     constexpr basic_string substr(size_type pos = 0, size_type n = npos) &&;                    // since C++23
 281     void swap(basic_string& str)
 282         noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
 283                  allocator_traits<allocator_type>::is_always_equal::value);                     // C++17, constexpr since C++20
 284
 285     const value_type* c_str() const noexcept;                                                   // constexpr since C++20
 286     const value_type* data() const noexcept;                                                    // constexpr since C++20
 287           value_type* data()       noexcept;                                                    // C++17, constexpr since C++20
 288
 289     allocator_type get_allocator() const noexcept;                                              // constexpr since C++20
 290
 291     size_type find(const basic_string& str, size_type pos = 0) const noexcept;                  // constexpr since C++20
 292     template <class T>
 293         size_type find(const T& t, size_type pos = 0) const noexcept;                           // C++17, noexcept as an extension, constexpr since C++20
 294     size_type find(const value_type* s, size_type pos, size_type n) const noexcept;             // constexpr since C++20
 295     size_type find(const value_type* s, size_type pos = 0) const noexcept;                      // constexpr since C++20
 296     size_type find(value_type c, size_type pos = 0) const noexcept;                             // constexpr since C++20
 297
 298     size_type rfind(const basic_string& str, size_type pos = npos) const noexcept;              // constexpr since C++20
 299     template <class T>
 300         size_type rfind(const T& t, size_type pos = npos) const noexcept;                       // C++17, noexcept as an extension, constexpr since C++20
 301     size_type rfind(const value_type* s, size_type pos, size_type n) const noexcept;            // constexpr since C++20
 302     size_type rfind(const value_type* s, size_type pos = npos) const noexcept;                  // constexpr since C++20
 303     size_type rfind(value_type c, size_type pos = npos) const noexcept;                         // constexpr since C++20
 304
 305     size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept;         // constexpr since C++20
 306     template <class T>
 307         size_type find_first_of(const T& t, size_type pos = 0) const noexcept;                  // C++17, noexcept as an extension, constexpr since C++20
 308     size_type find_first_of(const value_type* s, size_type pos, size_type n) const noexcept;    // constexpr since C++20
 309     size_type find_first_of(const value_type* s, size_type pos = 0) const noexcept;             // constexpr since C++20
 310     size_type find_first_of(value_type c, size_type pos = 0) const noexcept;                    // constexpr since C++20
 311
 312     size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept;       // constexpr since C++20
 313     template <class T>
 314         size_type find_last_of(const T& t, size_type pos = npos) const noexcept noexcept;       // C++17, noexcept as an extension, constexpr since C++20
 315     size_type find_last_of(const value_type* s, size_type pos, size_type n) const noexcept;     // constexpr since C++20
 316     size_type find_last_of(const value_type* s, size_type pos = npos) const noexcept;           // constexpr since C++20
 317     size_type find_last_of(value_type c, size_type pos = npos) const noexcept;                  // constexpr since C++20
 318
 319     size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept;     // constexpr since C++20
 320     template <class T>
 321         size_type find_first_not_of(const T& t, size_type pos = 0) const noexcept;              // C++17, noexcept as an extension, constexpr since C++20
 322     size_type find_first_not_of(const value_type* s, size_type pos, size_type n) const noexcept; // constexpr since C++20
 323     size_type find_first_not_of(const value_type* s, size_type pos = 0) const noexcept;         // constexpr since C++20
 324     size_type find_first_not_of(value_type c, size_type pos = 0) const noexcept;                // constexpr since C++20
 325
 326     size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept;   // constexpr since C++20
 327     template <class T>
 328         size_type find_last_not_of(const T& t, size_type pos = npos) const noexcept;            // C++17, noexcept as an extension, constexpr since C++20
 329     size_type find_last_not_of(const value_type* s, size_type pos, size_type n) const noexcept; // constexpr since C++20
 330     size_type find_last_not_of(const value_type* s, size_type pos = npos) const noexcept;       // constexpr since C++20
 331     size_type find_last_not_of(value_type c, size_type pos = npos) const noexcept;              // constexpr since C++20
 332
 333     int compare(const basic_string& str) const noexcept;                                        // constexpr since C++20
 334     template <class T>
 335         int compare(const T& t) const noexcept;                                                 // C++17, noexcept as an extension, constexpr since C++20
 336     int compare(size_type pos1, size_type n1, const basic_string& str) const;                   // constexpr since C++20
 337     template <class T>
 338         int compare(size_type pos1, size_type n1, const T& t) const;                            // C++17, constexpr since C++20
 339     int compare(size_type pos1, size_type n1, const basic_string& str,
 340                 size_type pos2, size_type n2=npos) const;                                       // C++14, constexpr since C++20
 341     template <class T>
 342         int compare(size_type pos1, size_type n1, const T& t,
 343                     size_type pos2, size_type n2=npos) const;                                   // C++17, constexpr since C++20
 344     int compare(const value_type* s) const noexcept;                                            // constexpr since C++20
 345     int compare(size_type pos1, size_type n1, const value_type* s) const;                       // constexpr since C++20
 346     int compare(size_type pos1, size_type n1, const value_type* s, size_type n2) const;         // constexpr since C++20
 347
 348     constexpr bool starts_with(basic_string_view<charT, traits> sv) const noexcept;             // C++20
 349     constexpr bool starts_with(charT c) const noexcept;                                         // C++20
 350     constexpr bool starts_with(const charT* s) const;                                           // C++20
 351     constexpr bool ends_with(basic_string_view<charT, traits> sv) const noexcept;               // C++20
 352     constexpr bool ends_with(charT c) const noexcept;                                           // C++20
 353     constexpr bool ends_with(const charT* s) const;                                             // C++20
 354
 355     constexpr bool contains(basic_string_view<charT, traits> sv) const noexcept;                // C++23
 356     constexpr bool contains(charT c) const noexcept;                                            // C++23
 357     constexpr bool contains(const charT* s) const;                                              // C++23
 358 };
 359
 360 template<class InputIterator,
 361          class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 362 basic_string(InputIterator, InputIterator, Allocator = Allocator())
 363    -> basic_string<typename iterator_traits<InputIterator>::value_type,
 364                   char_traits<typename iterator_traits<InputIterator>::value_type>,
 365                   Allocator>;   // C++17
 366
 367 template<ranges::input_range R,
 368          class Allocator = allocator<ranges::range_value_t<R>>>
 369   basic_string(from_range_t, R&&, Allocator = Allocator())
 370     -> basic_string<ranges::range_value_t<R>, char_traits<ranges::range_value_t<R>>,
 371                     Allocator>; // C++23
 372
 373 template<class charT,
 374          class traits,
 375          class Allocator = allocator<charT>>
 376   explicit basic_string(basic_string_view<charT, traits>, const Allocator& = Allocator())
 377     -> basic_string<charT, traits, Allocator>; // C++17
 378
 379 template<class charT,
 380          class traits,
 381          class Allocator = allocator<charT>>
 382   basic_string(basic_string_view<charT, traits>,
 383                 typename see below::size_type, typename see below::size_type,
 384                 const Allocator& = Allocator())
 385     -> basic_string<charT, traits, Allocator>; // C++17
 386
 387 template<class charT, class traits, class Allocator>
 388 basic_string<charT, traits, Allocator>
 389 operator+(const basic_string<charT, traits, Allocator>& lhs,
 390           const basic_string<charT, traits, Allocator>& rhs);                                   // constexpr since C++20
 391
 392 template<class charT, class traits, class Allocator>
 393 basic_string<charT, traits, Allocator>
 394 operator+(const charT* lhs , const basic_string<charT,traits,Allocator>&rhs);                   // constexpr since C++20
 395
 396 template<class charT, class traits, class Allocator>
 397 basic_string<charT, traits, Allocator>
 398 operator+(charT lhs, const basic_string<charT,traits,Allocator>& rhs);                          // constexpr since C++20
 399
 400 template<class charT, class traits, class Allocator>
 401 basic_string<charT, traits, Allocator>
 402 operator+(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs);                 // constexpr since C++20
 403
 404 template<class charT, class traits, class Allocator>
 405 basic_string<charT, traits, Allocator>
 406 operator+(const basic_string<charT, traits, Allocator>& lhs, charT rhs);                        // constexpr since C++20
 407
 408 template<class charT, class traits, class Allocator>
 409 bool operator==(const basic_string<charT, traits, Allocator>& lhs,
 410                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // constexpr since C++20
 411
 412 template<class charT, class traits, class Allocator>
 413 bool operator==(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 414
 415 template<class charT, class traits, class Allocator>
 416 bool operator==(const basic_string<charT,traits,Allocator>& lhs, const charT* rhs) noexcept;    // constexpr since C++20
 417
 418 template<class charT, class traits, class Allocator>
 419 bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
 420                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // removed in C++20
 421
 422 template<class charT, class traits, class Allocator>
 423 bool operator!=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 424
 425 template<class charT, class traits, class Allocator>
 426 bool operator!=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;  // removed in C++20
 427
 428 template<class charT, class traits, class Allocator>
 429 bool operator< (const basic_string<charT, traits, Allocator>& lhs,
 430                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // removed in C++20
 431
 432 template<class charT, class traits, class Allocator>
 433 bool operator< (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;  // removed in C++20
 434
 435 template<class charT, class traits, class Allocator>
 436 bool operator< (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 437
 438 template<class charT, class traits, class Allocator>
 439 bool operator> (const basic_string<charT, traits, Allocator>& lhs,
 440                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // removed in C++20
 441
 442 template<class charT, class traits, class Allocator>
 443 bool operator> (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;  // removed in C++20
 444
 445 template<class charT, class traits, class Allocator>
 446 bool operator> (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 447
 448 template<class charT, class traits, class Allocator>
 449 bool operator<=(const basic_string<charT, traits, Allocator>& lhs,
 450                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // removed in C++20
 451
 452 template<class charT, class traits, class Allocator>
 453 bool operator<=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;  // removed in C++20
 454
 455 template<class charT, class traits, class Allocator>
 456 bool operator<=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 457
 458 template<class charT, class traits, class Allocator>
 459 bool operator>=(const basic_string<charT, traits, Allocator>& lhs,
 460                 const basic_string<charT, traits, Allocator>& rhs) noexcept;                    // removed in C++20
 461
 462 template<class charT, class traits, class Allocator>
 463 bool operator>=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;  // removed in C++20
 464
 465 template<class charT, class traits, class Allocator>
 466 bool operator>=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;  // removed in C++20
 467
 468 template<class charT, class traits, class Allocator>                                            // since C++20
 469 constexpr see below operator<=>(const basic_string<charT, traits, Allocator>& lhs,
 470                                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 471
 472 template<class charT, class traits, class Allocator>                                            // since C++20
 473 constexpr see below operator<=>(const basic_string<charT, traits, Allocator>& lhs,
 474                                 const charT* rhs) noexcept;
 475
 476 template<class charT, class traits, class Allocator>
 477 void swap(basic_string<charT, traits, Allocator>& lhs,
 478           basic_string<charT, traits, Allocator>& rhs)
 479             noexcept(noexcept(lhs.swap(rhs)));                                                  // constexpr since C++20
 480
 481 template<class charT, class traits, class Allocator>
 482 basic_istream<charT, traits>&
 483 operator>>(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
 484
 485 template<class charT, class traits, class Allocator>
 486 basic_ostream<charT, traits>&
 487 operator<<(basic_ostream<charT, traits>& os, const basic_string<charT, traits, Allocator>& str);
 488
 489 template<class charT, class traits, class Allocator>
 490 basic_istream<charT, traits>&
 491 getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str,
 492         charT delim);
 493
 494 template<class charT, class traits, class Allocator>
 495 basic_istream<charT, traits>&
 496 getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
 497
 498 template<class charT, class traits, class Allocator, class U>
 499 typename basic_string<charT, traits, Allocator>::size_type
 500 erase(basic_string<charT, traits, Allocator>& c, const U& value);    // C++20
 501 template<class charT, class traits, class Allocator, class Predicate>
 502 typename basic_string<charT, traits, Allocator>::size_type
 503 erase_if(basic_string<charT, traits, Allocator>& c, Predicate pred); // C++20
 504
 505 typedef basic_string<char>    string;
 506 typedef basic_string<wchar_t> wstring;
 507 typedef basic_string<char8_t> u8string; // C++20
 508 typedef basic_string<char16_t> u16string;
 509 typedef basic_string<char32_t> u32string;
 510
 511 int                stoi  (const string& str, size_t* idx = nullptr, int base = 10);
 512 long               stol  (const string& str, size_t* idx = nullptr, int base = 10);
 513 unsigned long      stoul (const string& str, size_t* idx = nullptr, int base = 10);
 514 long long          stoll (const string& str, size_t* idx = nullptr, int base = 10);
 515 unsigned long long stoull(const string& str, size_t* idx = nullptr, int base = 10);
 516
 517 float       stof (const string& str, size_t* idx = nullptr);
 518 double      stod (const string& str, size_t* idx = nullptr);
 519 long double stold(const string& str, size_t* idx = nullptr);
 520
 521 string to_string(int val);
 522 string to_string(unsigned val);
 523 string to_string(long val);
 524 string to_string(unsigned long val);
 525 string to_string(long long val);
 526 string to_string(unsigned long long val);
 527 string to_string(float val);
 528 string to_string(double val);
 529 string to_string(long double val);
 530
 531 int                stoi  (const wstring& str, size_t* idx = nullptr, int base = 10);
 532 long               stol  (const wstring& str, size_t* idx = nullptr, int base = 10);
 533 unsigned long      stoul (const wstring& str, size_t* idx = nullptr, int base = 10);
 534 long long          stoll (const wstring& str, size_t* idx = nullptr, int base = 10);
 535 unsigned long long stoull(const wstring& str, size_t* idx = nullptr, int base = 10);
 536
 537 float       stof (const wstring& str, size_t* idx = nullptr);
 538 double      stod (const wstring& str, size_t* idx = nullptr);
 539 long double stold(const wstring& str, size_t* idx = nullptr);
 540
 541 wstring to_wstring(int val);
 542 wstring to_wstring(unsigned val);
 543 wstring to_wstring(long val);
 544 wstring to_wstring(unsigned long val);
 545 wstring to_wstring(long long val);
 546 wstring to_wstring(unsigned long long val);
 547 wstring to_wstring(float val);
 548 wstring to_wstring(double val);
 549 wstring to_wstring(long double val);
 550
 551 template <> struct hash<string>;
 552 template <> struct hash<u8string>; // C++20
 553 template <> struct hash<u16string>;
 554 template <> struct hash<u32string>;
 555 template <> struct hash<wstring>;
 556
 557 basic_string<char>     operator""s( const char *str,     size_t len );           // C++14, constexpr since C++20
 558 basic_string<wchar_t>  operator""s( const wchar_t *str,  size_t len );           // C++14, constexpr since C++20
 559 constexpr basic_string<char8_t>  operator""s( const char8_t *str,  size_t len ); // C++20
 560 basic_string<char16_t> operator""s( const char16_t *str, size_t len );           // C++14, constexpr since C++20
 561 basic_string<char32_t> operator""s( const char32_t *str, size_t len );           // C++14, constexpr since C++20
 562
 563 }  // std
 564
 565 */
 566
 567 #include <__algorithm/max.h>
 568 #include <__algorithm/min.h>
 569 #include <__algorithm/remove.h>
 570 #include <__algorithm/remove_if.h>
 571 #include <__assert> // all public C++ headers provide the assertion handler
 572 #include <__config>
 573 #include <__format/enable_insertable.h>
 574 #include <__functional/hash.h>
 575 #include <__functional/unary_function.h>
 576 #include <__fwd/string.h>
 577 #include <__ios/fpos.h>
 578 #include <__iterator/distance.h>
 579 #include <__iterator/iterator_traits.h>
 580 #include <__iterator/reverse_iterator.h>
 581 #include <__iterator/wrap_iter.h>
 582 #include <__memory/addressof.h>
 583 #include <__memory/allocate_at_least.h>
 584 #include <__memory/allocator.h>
 585 #include <__memory/allocator_traits.h>
 586 #include <__memory/compressed_pair.h>
 587 #include <__memory/construct_at.h>
 588 #include <__memory/pointer_traits.h>
 589 #include <__memory/swap_allocator.h>
 590 #include <__memory_resource/polymorphic_allocator.h>
 591 #include <__ranges/access.h>
 592 #include <__ranges/concepts.h>
 593 #include <__ranges/container_compatible_range.h>
 594 #include <__ranges/from_range.h>
 595 #include <__ranges/size.h>
 596 #include <__string/char_traits.h>
 597 #include <__string/extern_template_lists.h>
 598 #include <__type_traits/is_allocator.h>
 599 #include <__type_traits/is_array.h>
 600 #include <__type_traits/is_convertible.h>
 601 #include <__type_traits/is_nothrow_default_constructible.h>
 602 #include <__type_traits/is_nothrow_move_assignable.h>
 603 #include <__type_traits/is_same.h>
 604 #include <__type_traits/is_standard_layout.h>
 605 #include <__type_traits/is_trivial.h>
 606 #include <__type_traits/noexcept_move_assign_container.h>
 607 #include <__type_traits/remove_cvref.h>
 608 #include <__type_traits/void_t.h>
 609 #include <__utility/auto_cast.h>
 610 #include <__utility/declval.h>
 611 #include <__utility/forward.h>
 612 #include <__utility/is_pointer_in_range.h>
 613 #include <__utility/move.h>
 614 #include <__utility/swap.h>
 615 #include <__utility/unreachable.h>
 616 #include <climits>
 617 #include <cstdio>  // EOF
 618 #include <cstring>
 619 #include <limits>
 620 #include <stdexcept>
 621 #include <string_view>
 622 #include <version>
 623
 624 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 625 #  include <cwchar>
 626 #endif
 627
 628 // standard-mandated includes
 629
 630 // [iterator.range]
 631 #include <__iterator/access.h>
 632 #include <__iterator/data.h>
 633 #include <__iterator/empty.h>
 634 #include <__iterator/reverse_access.h>
 635 #include <__iterator/size.h>
 636
 637 // [string.syn]
 638 #include <compare>
 639 #include <initializer_list>
 640
 641 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 642 #  pragma GCC system_header
 643 #endif
 644
 645 _LIBCPP_PUSH_MACROS
 646 #include <__undef_macros>
 647
 648
 649 _LIBCPP_BEGIN_NAMESPACE_STD
 650
 651 // basic_string
 652
 653 template<class _CharT, class _Traits, class _Allocator>
 654 basic_string<_CharT, _Traits, _Allocator>
 655 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 656 operator+(const basic_string<_CharT, _Traits, _Allocator>& __x,
 657           const basic_string<_CharT, _Traits, _Allocator>& __y);
 658
 659 template<class _CharT, class _Traits, class _Allocator>
 660 _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR_SINCE_CXX20
 661 basic_string<_CharT, _Traits, _Allocator>
 662 operator+(const _CharT* __x, const basic_string<_CharT,_Traits,_Allocator>& __y);
 663
 664 template<class _CharT, class _Traits, class _Allocator>
 665 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 666 basic_string<_CharT, _Traits, _Allocator>
 667 operator+(_CharT __x, const basic_string<_CharT,_Traits,_Allocator>& __y);
 668
 669 template<class _CharT, class _Traits, class _Allocator>
 670 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 671 basic_string<_CharT, _Traits, _Allocator>
 672 operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, const _CharT* __y);
 673
 674 template<class _CharT, class _Traits, class _Allocator>
 675 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 676 basic_string<_CharT, _Traits, _Allocator>
 677 operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, _CharT __y);
 678
 679 extern template _LIBCPP_EXPORTED_FROM_ABI string operator+
 680     <char, char_traits<char>, allocator<char> >(char const*, string const&);
 681
 682 template <class _Iter>
 683 struct __string_is_trivial_iterator : public false_type {};
 684
 685 template <class _Tp>
 686 struct __string_is_trivial_iterator<_Tp*>
 687     : public is_arithmetic<_Tp> {};
 688
 689 template <class _Iter>
 690 struct __string_is_trivial_iterator<__wrap_iter<_Iter> >
 691     : public __string_is_trivial_iterator<_Iter> {};
 692
 693 template <class _CharT, class _Traits, class _Tp>
 694 struct __can_be_converted_to_string_view : public _BoolConstant<
 695       is_convertible<const _Tp&, basic_string_view<_CharT, _Traits> >::value &&
 696      !is_convertible<const _Tp&, const _CharT*>::value
 697     > {};
 698
 699 struct __uninitialized_size_tag {};
 700 struct __init_with_sentinel_tag {};
 701
 702 template<class _CharT, class _Traits, class _Allocator>
 703 class basic_string
 704 {
 705 public:
 706     typedef basic_string                                 __self;
 707     typedef basic_string_view<_CharT, _Traits>           __self_view;
 708     typedef _Traits                                      traits_type;
 709     typedef _CharT                                       value_type;
 710     typedef _Allocator                                   allocator_type;
 711     typedef allocator_traits<allocator_type>             __alloc_traits;
 712     typedef typename __alloc_traits::size_type           size_type;
 713     typedef typename __alloc_traits::difference_type     difference_type;
 714     typedef value_type&                                  reference;
 715     typedef const value_type&                            const_reference;
 716     typedef typename __alloc_traits::pointer             pointer;
 717     typedef typename __alloc_traits::const_pointer       const_pointer;
 718
 719     static_assert((!is_array<value_type>::value), "Character type of basic_string must not be an array");
 720     static_assert(( is_standard_layout<value_type>::value), "Character type of basic_string must be standard-layout");
 721     static_assert(( is_trivial<value_type>::value), "Character type of basic_string must be trivial");
 722     static_assert(( is_same<_CharT, typename traits_type::char_type>::value),
 723                   "traits_type::char_type must be the same type as CharT");
 724     static_assert(( is_same<typename allocator_type::value_type, value_type>::value),
 725                   "Allocator::value_type must be same type as value_type");
 726
 727     static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
 728                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
 729                   "original allocator");
 730
 731     // TODO: Implement iterator bounds checking without requiring the global database.
 732     typedef __wrap_iter<pointer>                         iterator;
 733     typedef __wrap_iter<const_pointer>                   const_iterator;
 734     typedef std::reverse_iterator<iterator>              reverse_iterator;
 735     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
 736
 737 private:
 738     static_assert(CHAR_BIT == 8, "This implementation assumes that one byte contains 8 bits");
 739
 740 #ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 741
 742     struct __long
 743     {
 744         pointer   __data_;
 745         size_type __size_;
 746         size_type __cap_ : sizeof(size_type) * CHAR_BIT - 1;
 747         size_type __is_long_ : 1;
 748     };
 749
 750     enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
 751                       (sizeof(__long) - 1)/sizeof(value_type) : 2};
 752
 753     struct __short
 754     {
 755         value_type __data_[__min_cap];
 756         unsigned char __padding_[sizeof(value_type) - 1];
 757         unsigned char __size_ : 7;
 758         unsigned char __is_long_ : 1;
 759     };
 760
 761 // The __endian_factor is required because the field we use to store the size
 762 // has one fewer bit than it would if it were not a bitfield.
 763 //
 764 // If the LSB is used to store the short-flag in the short string representation,
 765 // we have to multiply the size by two when it is stored and divide it by two when
 766 // it is loaded to make sure that we always store an even number. In the long string
 767 // representation, we can ignore this because we can assume that we always allocate
 768 // an even amount of value_types.
 769 //
 770 // If the MSB is used for the short-flag, the max_size() is numeric_limits<size_type>::max() / 2.
 771 // This does not impact the short string representation, since we never need the MSB
 772 // for representing the size of a short string anyway.
 773
 774 #ifdef _LIBCPP_BIG_ENDIAN
 775     static const size_type __endian_factor = 2;
 776 #else
 777     static const size_type __endian_factor = 1;
 778 #endif
 779
 780 #else // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 781
 782 #ifdef _LIBCPP_BIG_ENDIAN
 783     static const size_type __endian_factor = 1;
 784 #else
 785     static const size_type __endian_factor = 2;
 786 #endif
 787
 788     // Attribute 'packed' is used to keep the layout compatible with the
 789     // previous definition that did not use bit fields. This is because on
 790     // some platforms bit fields have a default size rather than the actual
 791     // size used, e.g., it is 4 bytes on AIX. See D128285 for details.
 792     struct __long
 793     {
 794         struct _LIBCPP_PACKED {
 795             size_type __is_long_ : 1;
 796             size_type __cap_ : sizeof(size_type) * CHAR_BIT - 1;
 797         };
 798         size_type __size_;
 799         pointer   __data_;
 800     };
 801
 802     enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
 803                       (sizeof(__long) - 1)/sizeof(value_type) : 2};
 804
 805     struct __short
 806     {
 807         struct _LIBCPP_PACKED {
 808             unsigned char __is_long_ : 1;
 809             unsigned char __size_ : 7;
 810         };
 811         char __padding_[sizeof(value_type) - 1];
 812         value_type __data_[__min_cap];
 813     };
 814
 815 #endif // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 816
 817     static_assert(sizeof(__short) == (sizeof(value_type) * (__min_cap + 1)), "__short has an unexpected size.");
 818
 819     union __ulx{__long __lx; __short __lxx;};
 820
 821     enum {__n_words = sizeof(__ulx) / sizeof(size_type)};
 822
 823     struct __raw
 824     {
 825         size_type __words[__n_words];
 826     };
 827
 828     struct __rep
 829     {
 830         union
 831         {
 832             __short __s;
 833             __long  __l;
 834             __raw   __r;
 835         };
 836     };
 837
 838     __compressed_pair<__rep, allocator_type> __r_;
 839
 840     // Construct a string with the given allocator and enough storage to hold `__size` characters, but
 841     // don't initialize the characters. The contents of the string, including the null terminator, must be
 842     // initialized separately.
 843     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 844     explicit basic_string(__uninitialized_size_tag, size_type __size, const allocator_type& __a)
 845             : __r_(__default_init_tag(), __a) {
 846         if (__size > max_size())
 847             __throw_length_error();
 848         if (__fits_in_sso(__size)) {
 849             __r_.first() = __rep();
 850             __set_short_size(__size);
 851         } else {
 852             auto __capacity = __recommend(__size) + 1;
 853             auto __allocation = __alloc_traits::allocate(__alloc(), __capacity);
 854             __begin_lifetime(__allocation, __capacity);
 855             __set_long_cap(__capacity);
 856             __set_long_pointer(__allocation);
 857             __set_long_size(__size);
 858         }
 859     }
 860
 861     template <class _Iter, class _Sent>
 862     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 863     basic_string(__init_with_sentinel_tag, _Iter __first, _Sent __last, const allocator_type& __a)
 864         : __r_(__default_init_tag(), __a) {
 865       __init_with_sentinel(std::move(__first), std::move(__last));
 866     }
 867
 868     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iterator(pointer __p) {
 869         return iterator(__p);
 870     }
 871
 872     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_const_iterator(const_pointer __p) const {
 873         return const_iterator(__p);
 874     }
 875
 876 public:
 877   _LIBCPP_TEMPLATE_DATA_VIS static const size_type npos = -1;
 878
 879   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string()
 880       _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 881       : __r_(__value_init_tag(), __default_init_tag()) {}
 882
 883   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit basic_string(const allocator_type& __a)
 884 #if _LIBCPP_STD_VER <= 14
 885       _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 886 #else
 887       _NOEXCEPT
 888 #endif
 889       : __r_(__value_init_tag(), __a) {}
 890
 891   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(const basic_string& __str)
 892       : __r_(__default_init_tag(), __alloc_traits::select_on_container_copy_construction(__str.__alloc())) {
 893     if (!__str.__is_long())
 894       __r_.first() = __str.__r_.first();
 895     else
 896       __init_copy_ctor_external(std::__to_address(__str.__get_long_pointer()), __str.__get_long_size());
 897   }
 898
 899   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(const basic_string& __str, const allocator_type& __a)
 900       : __r_(__default_init_tag(), __a) {
 901     if (!__str.__is_long())
 902       __r_.first() = __str.__r_.first();
 903     else
 904       __init_copy_ctor_external(std::__to_address(__str.__get_long_pointer()), __str.__get_long_size());
 905   }
 906
 907 #ifndef _LIBCPP_CXX03_LANG
 908   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(basic_string&& __str)
 909 #  if _LIBCPP_STD_VER <= 14
 910       _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 911 #  else
 912       _NOEXCEPT
 913 #  endif
 914       : __r_(std::move(__str.__r_)) {
 915     __str.__r_.first() = __rep();
 916   }
 917
 918   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(basic_string&& __str, const allocator_type& __a)
 919       : __r_(__default_init_tag(), __a) {
 920     if (__str.__is_long() && __a != __str.__alloc()) // copy, not move
 921       __init(std::__to_address(__str.__get_long_pointer()), __str.__get_long_size());
 922     else {
 923       if (__libcpp_is_constant_evaluated())
 924         __r_.first() = __rep();
 925       __r_.first() = __str.__r_.first();
 926       __str.__r_.first() = __rep();
 927     }
 928   }
 929 #endif // _LIBCPP_CXX03_LANG
 930
 931   template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>
 932   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(const _CharT* __s)
 933       : __r_(__default_init_tag(), __default_init_tag()) {
 934     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "basic_string(const char*) detected nullptr");
 935     __init(__s, traits_type::length(__s));
 936   }
 937
 938   template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>
 939   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(const _CharT* __s, const _Allocator& __a)
 940       : __r_(__default_init_tag(), __a) {
 941     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "basic_string(const char*, allocator) detected nullptr");
 942     __init(__s, traits_type::length(__s));
 943   }
 944
 945 #if _LIBCPP_STD_VER >= 23
 946   basic_string(nullptr_t) = delete;
 947 #endif
 948
 949   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(const _CharT* __s, size_type __n)
 950       : __r_(__default_init_tag(), __default_init_tag()) {
 951     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "basic_string(const char*, n) detected nullptr");
 952     __init(__s, __n);
 953   }
 954
 955   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 956   basic_string(const _CharT* __s, size_type __n, const _Allocator& __a)
 957       : __r_(__default_init_tag(), __a) {
 958     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr,
 959                                  "basic_string(const char*, n, allocator) detected nullptr");
 960     __init(__s, __n);
 961   }
 962
 963   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(size_type __n, _CharT __c)
 964       : __r_(__default_init_tag(), __default_init_tag()) {
 965     __init(__n, __c);
 966   }
 967
 968 #if _LIBCPP_STD_VER >= 23
 969   _LIBCPP_HIDE_FROM_ABI constexpr
 970   basic_string(basic_string&& __str, size_type __pos, const _Allocator& __alloc = _Allocator())
 971       : basic_string(std::move(__str), __pos, npos, __alloc) {}
 972
 973   _LIBCPP_HIDE_FROM_ABI constexpr
 974   basic_string(basic_string&& __str, size_type __pos, size_type __n, const _Allocator& __alloc = _Allocator())
 975       : __r_(__default_init_tag(), __alloc) {
 976     if (__pos > __str.size())
 977       __throw_out_of_range();
 978
 979     auto __len = std::min<size_type>(__n, __str.size() - __pos);
 980     if (__alloc_traits::is_always_equal::value || __alloc == __str.__alloc()) {
 981       __move_assign(std::move(__str), __pos, __len);
 982     } else {
 983       // Perform a copy because the allocators are not compatible.
 984       __init(__str.data() + __pos, __len);
 985     }
 986   }
 987 #endif
 988
 989   template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>
 990   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(size_type __n, _CharT __c, const _Allocator& __a)
 991       : __r_(__default_init_tag(), __a) {
 992     __init(__n, __c);
 993   }
 994
 995   _LIBCPP_CONSTEXPR_SINCE_CXX20
 996   basic_string(const basic_string& __str, size_type __pos, size_type __n, const _Allocator& __a = _Allocator())
 997       : __r_(__default_init_tag(), __a) {
 998     size_type __str_sz = __str.size();
 999     if (__pos > __str_sz)
1000       __throw_out_of_range();
1001     __init(__str.data() + __pos, std::min(__n, __str_sz - __pos));
1002   }
1003
1004   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1005   basic_string(const basic_string& __str, size_type __pos, const _Allocator& __a = _Allocator())
1006       : __r_(__default_init_tag(), __a) {
1007     size_type __str_sz = __str.size();
1008     if (__pos > __str_sz)
1009       __throw_out_of_range();
1010     __init(__str.data() + __pos, __str_sz - __pos);
1011   }
1012
1013   template <class _Tp,
1014             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1015                               !__is_same_uncvref<_Tp, basic_string>::value,
1016                           int> = 0>
1017   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20
1018   basic_string(const _Tp& __t, size_type __pos, size_type __n, const allocator_type& __a = allocator_type())
1019       : __r_(__default_init_tag(), __a) {
1020     __self_view __sv0 = __t;
1021     __self_view __sv  = __sv0.substr(__pos, __n);
1022     __init(__sv.data(), __sv.size());
1023   }
1024
1025   template <class _Tp,
1026             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1027                               !__is_same_uncvref<_Tp, basic_string>::value,
1028                           int> = 0>
1029   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit basic_string(const _Tp& __t)
1030       : __r_(__default_init_tag(), __default_init_tag()) {
1031     __self_view __sv = __t;
1032     __init(__sv.data(), __sv.size());
1033   }
1034
1035   template <class _Tp,
1036             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1037                               !__is_same_uncvref<_Tp, basic_string>::value,
1038                           int> = 0>
1039   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit basic_string(
1040       const _Tp& __t, const allocator_type& __a)
1041       : __r_(__default_init_tag(), __a) {
1042     __self_view __sv = __t;
1043     __init(__sv.data(), __sv.size());
1044   }
1045
1046   template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
1047   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(_InputIterator __first, _InputIterator __last)
1048       : __r_(__default_init_tag(), __default_init_tag()) {
1049     __init(__first, __last);
1050   }
1051
1052   template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
1053   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1054   basic_string(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
1055       : __r_(__default_init_tag(), __a) {
1056     __init(__first, __last);
1057   }
1058
1059 #if _LIBCPP_STD_VER >= 23
1060   template <_ContainerCompatibleRange<_CharT> _Range>
1061   _LIBCPP_HIDE_FROM_ABI constexpr
1062   basic_string(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
1063       : __r_(__default_init_tag(), __a) {
1064     if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
1065       __init_with_size(ranges::begin(__range), ranges::end(__range), ranges::distance(__range));
1066     } else {
1067       __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
1068     }
1069   }
1070 #endif
1071
1072 #ifndef _LIBCPP_CXX03_LANG
1073   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(initializer_list<_CharT> __il)
1074       : __r_(__default_init_tag(), __default_init_tag()) {
1075     __init(__il.begin(), __il.end());
1076   }
1077
1078   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string(initializer_list<_CharT> __il, const _Allocator& __a)
1079       : __r_(__default_init_tag(), __a) {
1080     __init(__il.begin(), __il.end());
1081   }
1082 #endif // _LIBCPP_CXX03_LANG
1083
1084   inline _LIBCPP_CONSTEXPR_SINCE_CXX20 ~basic_string() {
1085     if (__is_long())
1086       __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
1087   }
1088
1089     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1090     operator __self_view() const _NOEXCEPT { return __self_view(data(), size()); }
1091
1092     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator=(const basic_string& __str);
1093
1094     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1095                                            !__is_same_uncvref<_Tp, basic_string>::value, int> = 0>
1096     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator=(const _Tp& __t) {
1097       __self_view __sv = __t;
1098       return assign(__sv);
1099     }
1100
1101 #ifndef _LIBCPP_CXX03_LANG
1102   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator=(basic_string&& __str)
1103       _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) {
1104     __move_assign(__str, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
1105     return *this;
1106   }
1107
1108      _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1109     basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1110 #endif
1111     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1112     basic_string& operator=(const value_type* __s) {return assign(__s);}
1113 #if _LIBCPP_STD_VER >= 23
1114     basic_string& operator=(nullptr_t) = delete;
1115 #endif
1116     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator=(value_type __c);
1117
1118     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1119     iterator begin() _NOEXCEPT
1120         {return __make_iterator(__get_pointer());}
1121     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1122     const_iterator begin() const _NOEXCEPT
1123         {return __make_const_iterator(__get_pointer());}
1124     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1125     iterator end() _NOEXCEPT
1126         {return __make_iterator(__get_pointer() + size());}
1127     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1128     const_iterator end() const _NOEXCEPT
1129         {return __make_const_iterator(__get_pointer() + size());}
1130
1131     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1132     reverse_iterator rbegin() _NOEXCEPT
1133         {return reverse_iterator(end());}
1134     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1135     const_reverse_iterator rbegin() const _NOEXCEPT
1136         {return const_reverse_iterator(end());}
1137     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1138     reverse_iterator rend() _NOEXCEPT
1139         {return reverse_iterator(begin());}
1140     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1141     const_reverse_iterator rend() const _NOEXCEPT
1142         {return const_reverse_iterator(begin());}
1143
1144     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1145     const_iterator cbegin() const _NOEXCEPT
1146         {return begin();}
1147     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1148     const_iterator cend() const _NOEXCEPT
1149         {return end();}
1150     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1151     const_reverse_iterator crbegin() const _NOEXCEPT
1152         {return rbegin();}
1153     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1154     const_reverse_iterator crend() const _NOEXCEPT
1155         {return rend();}
1156
1157     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT
1158         {return __is_long() ? __get_long_size() : __get_short_size();}
1159     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type length() const _NOEXCEPT {return size();}
1160
1161   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT {
1162     size_type __m = __alloc_traits::max_size(__alloc());
1163     if (__m <= std::numeric_limits<size_type>::max() / 2) {
1164       return __m - __alignment;
1165     } else {
1166     bool __uses_lsb = __endian_factor == 2;
1167       return __uses_lsb ? __m - __alignment : (__m / 2) - __alignment;
1168     }
1169   }
1170
1171     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
1172         return (__is_long() ? __get_long_cap() : static_cast<size_type>(__min_cap)) - 1;
1173     }
1174
1175     _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __n, value_type __c);
1176     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __n) { resize(__n, value_type()); }
1177
1178     _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __requested_capacity);
1179
1180 #if _LIBCPP_STD_VER >= 23
1181     template <class _Op>
1182     _LIBCPP_HIDE_FROM_ABI constexpr
1183     void resize_and_overwrite(size_type __n, _Op __op) {
1184       __resize_default_init(__n);
1185       __erase_to_end(std::move(__op)(data(), _LIBCPP_AUTO_CAST(__n)));
1186     }
1187 #endif
1188
1189     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __resize_default_init(size_type __n);
1190
1191     _LIBCPP_DEPRECATED_IN_CXX20 _LIBCPP_HIDE_FROM_ABI void reserve() _NOEXCEPT { shrink_to_fit(); }
1192     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;
1193     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT;
1194
1195     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1196     bool empty() const _NOEXCEPT {return size() == 0;}
1197
1198   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference operator[](size_type __pos) const _NOEXCEPT {
1199     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__pos <= size(), "string index out of bounds");
1200     if (__builtin_constant_p(__pos) && !__fits_in_sso(__pos)) {
1201       return *(__get_long_pointer() + __pos);
1202     }
1203     return *(data() + __pos);
1204   }
1205
1206   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __pos) _NOEXCEPT {
1207     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__pos <= size(), "string index out of bounds");
1208     if (__builtin_constant_p(__pos) && !__fits_in_sso(__pos)) {
1209       return *(__get_long_pointer() + __pos);
1210     }
1211     return *(__get_pointer() + __pos);
1212   }
1213
1214     _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference at(size_type __n) const;
1215     _LIBCPP_CONSTEXPR_SINCE_CXX20 reference       at(size_type __n);
1216
1217     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator+=(const basic_string& __str) {
1218         return append(__str);
1219     }
1220
1221     template <class _Tp,
1222               __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1223                                 !__is_same_uncvref<_Tp, basic_string >::value,
1224                             int> = 0>
1225     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1226     operator+=(const _Tp& __t) {
1227         __self_view __sv = __t; return append(__sv);
1228     }
1229
1230     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator+=(const value_type* __s) {
1231         return append(__s);
1232     }
1233
1234     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& operator+=(value_type __c) {
1235         push_back(__c);
1236         return *this;
1237     }
1238
1239 #ifndef _LIBCPP_CXX03_LANG
1240     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1241     basic_string& operator+=(initializer_list<value_type> __il) { return append(__il); }
1242 #endif // _LIBCPP_CXX03_LANG
1243
1244   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(const basic_string& __str) {
1245         return append(__str.data(), __str.size());
1246   }
1247
1248   template <class _Tp,
1249             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1250                               !__is_same_uncvref<_Tp, basic_string>::value,
1251                           int> = 0>
1252   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1253   append(const _Tp& __t) {
1254         __self_view __sv = __t;
1255         return append(__sv.data(), __sv.size());
1256   }
1257
1258     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(const basic_string& __str, size_type __pos, size_type __n=npos);
1259
1260     template <class _Tp,
1261               __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1262                                 !__is_same_uncvref<_Tp, basic_string>::value,
1263                             int> = 0>
1264     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20
1265
1266         basic_string&
1267         append(const _Tp& __t, size_type __pos, size_type __n = npos);
1268
1269     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(const value_type* __s, size_type __n);
1270     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(const value_type* __s);
1271     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(size_type __n, value_type __c);
1272
1273     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1274     void __append_default_init(size_type __n);
1275
1276     template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1277     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1278     append(_InputIterator __first, _InputIterator __last) {
1279         const basic_string __temp(__first, __last, __alloc());
1280         append(__temp.data(), __temp.size());
1281         return *this;
1282     }
1283
1284     template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1285     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1286     append(_ForwardIterator __first, _ForwardIterator __last);
1287
1288 #if _LIBCPP_STD_VER >= 23
1289     template <_ContainerCompatibleRange<_CharT> _Range>
1290     _LIBCPP_HIDE_FROM_ABI
1291     constexpr basic_string& append_range(_Range&& __range) {
1292       insert_range(end(), std::forward<_Range>(__range));
1293       return *this;
1294     }
1295 #endif
1296
1297 #ifndef _LIBCPP_CXX03_LANG
1298     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1299     basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());}
1300 #endif // _LIBCPP_CXX03_LANG
1301
1302     _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(value_type __c);
1303     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back();
1304
1305   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() _NOEXCEPT {
1306     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "string::front(): string is empty");
1307     return *__get_pointer();
1308   }
1309
1310   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const _NOEXCEPT {
1311     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "string::front(): string is empty");
1312     return *data();
1313   }
1314
1315   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() _NOEXCEPT {
1316     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "string::back(): string is empty");
1317     return *(__get_pointer() + size() - 1);
1318   }
1319
1320   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const _NOEXCEPT {
1321     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "string::back(): string is empty");
1322     return *(data() + size() - 1);
1323   }
1324
1325   template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1326   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1327   assign(const _Tp& __t) {
1328     __self_view __sv = __t;
1329     return assign(__sv.data(), __sv.size());
1330   }
1331
1332 #if _LIBCPP_STD_VER >= 20
1333   _LIBCPP_HIDE_FROM_ABI constexpr
1334   void __move_assign(basic_string&& __str, size_type __pos, size_type __len) {
1335     // Pilfer the allocation from __str.
1336     _LIBCPP_ASSERT_INTERNAL(__alloc() == __str.__alloc(), "__move_assign called with wrong allocator");
1337     __r_.first() = __str.__r_.first();
1338     __str.__r_.first() = __rep();
1339
1340     _Traits::move(data(), data() + __pos, __len);
1341     __set_size(__len);
1342     _Traits::assign(data()[__len], value_type());
1343   }
1344 #endif
1345
1346     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1347     basic_string& assign(const basic_string& __str) { return *this = __str; }
1348 #ifndef _LIBCPP_CXX03_LANG
1349     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1350     basic_string& assign(basic_string&& __str)
1351         _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
1352         {*this = std::move(__str); return *this;}
1353 #endif
1354     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(const basic_string& __str, size_type __pos, size_type __n=npos);
1355
1356     template <class _Tp,
1357               __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1358                                 !__is_same_uncvref<_Tp, basic_string>::value,
1359                             int> = 0>
1360     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1361     assign(const _Tp& __t, size_type __pos, size_type __n = npos);
1362
1363     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(const value_type* __s, size_type __n);
1364     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(const value_type* __s);
1365     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(size_type __n, value_type __c);
1366     template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1367     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1368     assign(_InputIterator __first, _InputIterator __last);
1369
1370     template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1371     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1372     assign(_ForwardIterator __first, _ForwardIterator __last);
1373
1374 #if _LIBCPP_STD_VER >= 23
1375     template <_ContainerCompatibleRange<_CharT> _Range>
1376     _LIBCPP_HIDE_FROM_ABI
1377     constexpr basic_string& assign_range(_Range&& __range) {
1378       if constexpr (__string_is_trivial_iterator<ranges::iterator_t<_Range>>::value &&
1379           (ranges::forward_range<_Range> || ranges::sized_range<_Range>)) {
1380         size_type __n = static_cast<size_type>(ranges::distance(__range));
1381         __assign_trivial(ranges::begin(__range), ranges::end(__range), __n);
1382
1383       } else {
1384         __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
1385       }
1386
1387       return *this;
1388     }
1389 #endif
1390
1391 #ifndef _LIBCPP_CXX03_LANG
1392     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1393     basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1394 #endif // _LIBCPP_CXX03_LANG
1395
1396   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1397   insert(size_type __pos1, const basic_string& __str) {
1398     return insert(__pos1, __str.data(), __str.size());
1399   }
1400
1401   template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1402   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1403   insert(size_type __pos1, const _Tp& __t) {
1404     __self_view __sv = __t;
1405     return insert(__pos1, __sv.data(), __sv.size());
1406   }
1407
1408   template <class _Tp,
1409             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1410                               !__is_same_uncvref<_Tp, basic_string>::value,
1411                           int> = 0>
1412   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1413   insert(size_type __pos1, const _Tp& __t, size_type __pos2, size_type __n = npos);
1414
1415   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1416   insert(size_type __pos1, const basic_string& __str, size_type __pos2, size_type __n = npos);
1417   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& insert(size_type __pos, const value_type* __s, size_type __n);
1418   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& insert(size_type __pos, const value_type* __s);
1419   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& insert(size_type __pos, size_type __n, value_type __c);
1420   _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __pos, value_type __c);
1421
1422 #if _LIBCPP_STD_VER >= 23
1423     template <_ContainerCompatibleRange<_CharT> _Range>
1424     _LIBCPP_HIDE_FROM_ABI
1425     constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
1426       if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
1427         auto __n = static_cast<size_type>(ranges::distance(__range));
1428         return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
1429
1430       } else {
1431         basic_string __temp(from_range, std::forward<_Range>(__range), __alloc());
1432         return insert(__position, __temp.data(), __temp.data() + __temp.size());
1433       }
1434     }
1435 #endif
1436
1437   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
1438   insert(const_iterator __pos, size_type __n, value_type __c) {
1439     difference_type __p = __pos - begin();
1440     insert(static_cast<size_type>(__p), __n, __c);
1441     return begin() + __p;
1442   }
1443
1444   template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1445   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
1446   insert(const_iterator __pos, _InputIterator __first, _InputIterator __last);
1447
1448   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1449   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
1450   insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last);
1451
1452 #ifndef _LIBCPP_CXX03_LANG
1453     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1454     iterator insert(const_iterator __pos, initializer_list<value_type> __il)
1455                     {return insert(__pos, __il.begin(), __il.end());}
1456 #endif // _LIBCPP_CXX03_LANG
1457
1458     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& erase(size_type __pos = 0, size_type __n = npos);
1459     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1460     iterator      erase(const_iterator __pos);
1461     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1462     iterator      erase(const_iterator __first, const_iterator __last);
1463
1464   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1465   replace(size_type __pos1, size_type __n1, const basic_string& __str) {
1466     return replace(__pos1, __n1, __str.data(), __str.size());
1467   }
1468
1469   template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1470   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1471   replace(size_type __pos1, size_type __n1, const _Tp& __t) {
1472     __self_view __sv = __t;
1473     return replace(__pos1, __n1, __sv.data(), __sv.size());
1474   }
1475
1476   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1477   replace(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2 = npos);
1478
1479   template <class _Tp,
1480             __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1481                               !__is_same_uncvref<_Tp, basic_string>::value,
1482                           int> = 0>
1483   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1484   replace(size_type __pos1, size_type __n1, const _Tp& __t, size_type __pos2, size_type __n2 = npos);
1485
1486   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1487   replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2);
1488   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& replace(size_type __pos, size_type __n1, const value_type* __s);
1489   _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c);
1490
1491   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1492   replace(const_iterator __i1, const_iterator __i2, const basic_string& __str) {
1493     return replace(
1494         static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __str.data(), __str.size());
1495   }
1496
1497   template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1498   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1499   replace(const_iterator __i1, const_iterator __i2, const _Tp& __t) {
1500     __self_view __sv = __t;
1501     return replace(__i1 - begin(), __i2 - __i1, __sv);
1502   }
1503
1504   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1505   replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n) {
1506     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n);
1507   }
1508
1509   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1510   replace(const_iterator __i1, const_iterator __i2, const value_type* __s) {
1511     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s);
1512   }
1513
1514   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1515   replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c) {
1516     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c);
1517   }
1518
1519   template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
1520   _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string&
1521   replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2);
1522
1523 #if _LIBCPP_STD_VER >= 23
1524   template <_ContainerCompatibleRange<_CharT> _Range>
1525   _LIBCPP_HIDE_FROM_ABI
1526   constexpr basic_string& replace_with_range(const_iterator __i1, const_iterator __i2, _Range&& __range) {
1527     basic_string __temp(from_range, std::forward<_Range>(__range), __alloc());
1528     return replace(__i1, __i2, __temp);
1529   }
1530 #endif
1531
1532 #ifndef _LIBCPP_CXX03_LANG
1533     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1534     basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list<value_type> __il)
1535         {return replace(__i1, __i2, __il.begin(), __il.end());}
1536 #endif // _LIBCPP_CXX03_LANG
1537
1538     _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type copy(value_type* __s, size_type __n, size_type __pos = 0) const;
1539
1540 #if _LIBCPP_STD_VER <= 20
1541     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1542     basic_string substr(size_type __pos = 0, size_type __n = npos) const {
1543       return basic_string(*this, __pos, __n);
1544     }
1545 #else
1546     _LIBCPP_HIDE_FROM_ABI constexpr
1547     basic_string substr(size_type __pos = 0, size_type __n = npos) const& {
1548       return basic_string(*this, __pos, __n);
1549     }
1550
1551     _LIBCPP_HIDE_FROM_ABI constexpr
1552     basic_string substr(size_type __pos = 0, size_type __n = npos) && {
1553       return basic_string(std::move(*this), __pos, __n);
1554     }
1555 #endif
1556
1557     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1558     void swap(basic_string& __str)
1559 #if _LIBCPP_STD_VER >= 14
1560         _NOEXCEPT;
1561 #else
1562         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1563                     __is_nothrow_swappable<allocator_type>::value);
1564 #endif
1565
1566     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1567     const value_type* c_str() const _NOEXCEPT {return data();}
1568     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1569     const value_type* data() const _NOEXCEPT  {return std::__to_address(__get_pointer());}
1570 #if _LIBCPP_STD_VER >= 17
1571     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1572     value_type* data()             _NOEXCEPT  {return std::__to_address(__get_pointer());}
1573 #endif
1574
1575     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1576     allocator_type get_allocator() const _NOEXCEPT {return __alloc();}
1577
1578     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1579     size_type find(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1580
1581     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1582     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1583     find(const _Tp& __t, size_type __pos = 0) const _NOEXCEPT;
1584
1585     _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type find(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1586     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1587     size_type find(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1588     _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type find(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1589
1590     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1591     size_type rfind(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1592
1593     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1594     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1595     rfind(const _Tp& __t, size_type __pos = npos) const _NOEXCEPT;
1596
1597     _LIBCPP_CONSTEXPR_SINCE_CXX20
1598     size_type rfind(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1599     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1600     size_type rfind(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1601     _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type rfind(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1602
1603     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1604     size_type find_first_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1605
1606     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1607     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1608     find_first_of(const _Tp& __t, size_type __pos = 0) const _NOEXCEPT;
1609
1610     _LIBCPP_CONSTEXPR_SINCE_CXX20
1611     size_type find_first_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1612     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1613     size_type find_first_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1614     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1615     size_type find_first_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1616
1617     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1618     size_type find_last_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1619
1620     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1621     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1622     find_last_of(const _Tp& __t, size_type __pos = npos) const _NOEXCEPT;
1623
1624     _LIBCPP_CONSTEXPR_SINCE_CXX20
1625     size_type find_last_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1626     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1627     size_type find_last_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1628     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1629     size_type find_last_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1630
1631     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1632     size_type find_first_not_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1633
1634     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1635     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1636     find_first_not_of(const _Tp& __t, size_type __pos = 0) const _NOEXCEPT;
1637
1638     _LIBCPP_CONSTEXPR_SINCE_CXX20
1639     size_type find_first_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1640     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1641     size_type find_first_not_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1642     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1643     size_type find_first_not_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1644
1645     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1646     size_type find_last_not_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1647
1648     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1649     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type
1650     find_last_not_of(const _Tp& __t, size_type __pos = npos) const _NOEXCEPT;
1651
1652     _LIBCPP_CONSTEXPR_SINCE_CXX20
1653     size_type find_last_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1654     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1655     size_type find_last_not_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1656     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1657     size_type find_last_not_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1658
1659     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1660     int compare(const basic_string& __str) const _NOEXCEPT;
1661
1662     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1663     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 int
1664     compare(const _Tp& __t) const _NOEXCEPT;
1665
1666     template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> = 0>
1667     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 int
1668     compare(size_type __pos1, size_type __n1, const _Tp& __t) const;
1669
1670     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1671     int compare(size_type __pos1, size_type __n1, const basic_string& __str) const;
1672     _LIBCPP_CONSTEXPR_SINCE_CXX20
1673     int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2,
1674                 size_type __n2 = npos) const;
1675
1676     template <class _Tp,
1677               __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
1678                                 !__is_same_uncvref<_Tp, basic_string>::value,
1679                             int> = 0>
1680     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 int
1681     compare(size_type __pos1, size_type __n1, const _Tp& __t, size_type __pos2, size_type __n2 = npos) const;
1682
1683     _LIBCPP_CONSTEXPR_SINCE_CXX20 int compare(const value_type* __s) const _NOEXCEPT;
1684     _LIBCPP_CONSTEXPR_SINCE_CXX20 int compare(size_type __pos1, size_type __n1, const value_type* __s) const;
1685     _LIBCPP_CONSTEXPR_SINCE_CXX20
1686     int compare(size_type __pos1, size_type __n1, const value_type* __s, size_type __n2) const;
1687
1688 #if _LIBCPP_STD_VER >= 20
1689     constexpr _LIBCPP_HIDE_FROM_ABI
1690     bool starts_with(__self_view __sv) const noexcept
1691     { return __self_view(data(), size()).starts_with(__sv); }
1692
1693     constexpr _LIBCPP_HIDE_FROM_ABI
1694     bool starts_with(value_type __c) const noexcept
1695     { return !empty() && _Traits::eq(front(), __c); }
1696
1697     constexpr _LIBCPP_HIDE_FROM_ABI
1698     bool starts_with(const value_type* __s) const noexcept
1699     { return starts_with(__self_view(__s)); }
1700
1701     constexpr _LIBCPP_HIDE_FROM_ABI
1702     bool ends_with(__self_view __sv) const noexcept
1703     { return __self_view(data(), size()).ends_with( __sv); }
1704
1705     constexpr _LIBCPP_HIDE_FROM_ABI
1706     bool ends_with(value_type __c) const noexcept
1707     { return !empty() && _Traits::eq(back(), __c); }
1708
1709     constexpr _LIBCPP_HIDE_FROM_ABI
1710     bool ends_with(const value_type* __s) const noexcept
1711     { return ends_with(__self_view(__s)); }
1712 #endif
1713
1714 #if _LIBCPP_STD_VER >= 23
1715     constexpr _LIBCPP_HIDE_FROM_ABI
1716     bool contains(__self_view __sv) const noexcept
1717     { return __self_view(data(), size()).contains(__sv); }
1718
1719     constexpr _LIBCPP_HIDE_FROM_ABI
1720     bool contains(value_type __c) const noexcept
1721     { return __self_view(data(), size()).contains(__c); }
1722
1723     constexpr _LIBCPP_HIDE_FROM_ABI
1724     bool contains(const value_type* __s) const
1725     { return __self_view(data(), size()).contains(__s); }
1726 #endif
1727
1728     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;
1729
1730     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __clear_and_shrink() _NOEXCEPT;
1731
1732 private:
1733     template<class _Alloc>
1734     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1735     bool friend operator==(const basic_string<char, char_traits<char>, _Alloc>& __lhs,
1736                            const basic_string<char, char_traits<char>, _Alloc>& __rhs) _NOEXCEPT;
1737
1738     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __shrink_or_extend(size_type __target_capacity);
1739
1740     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1741     bool __is_long() const _NOEXCEPT {
1742         if (__libcpp_is_constant_evaluated() && __builtin_constant_p(__r_.first().__l.__is_long_)) {
1743             return __r_.first().__l.__is_long_;
1744         }
1745         return __r_.first().__s.__is_long_;
1746     }
1747
1748     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __begin_lifetime(pointer __begin, size_type __n) {
1749 #if _LIBCPP_STD_VER >= 20
1750         if (__libcpp_is_constant_evaluated()) {
1751             for (size_type __i = 0; __i != __n; ++__i)
1752                 std::construct_at(std::addressof(__begin[__i]));
1753         }
1754 #else
1755         (void)__begin;
1756         (void)__n;
1757 #endif // _LIBCPP_STD_VER >= 20
1758     }
1759
1760     _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI static bool __fits_in_sso(size_type __sz) {
1761         return __sz < __min_cap;
1762     }
1763
1764     template <class _Iterator, class _Sentinel>
1765     _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
1766     void __assign_trivial(_Iterator __first, _Sentinel __last, size_type __n);
1767
1768     template <class _Iterator, class _Sentinel>
1769     _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
1770     void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
1771
1772     template <class _ForwardIterator, class _Sentinel>
1773     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
1774     iterator __insert_from_safe_copy(size_type __n, size_type __ip, _ForwardIterator __first, _Sentinel __last) {
1775         size_type __sz = size();
1776         size_type __cap = capacity();
1777         value_type* __p;
1778         if (__cap - __sz >= __n)
1779         {
1780             __p = std::__to_address(__get_pointer());
1781             size_type __n_move = __sz - __ip;
1782             if (__n_move != 0)
1783                 traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
1784         }
1785         else
1786         {
1787             __grow_by_without_replace(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
1788             __p = std::__to_address(__get_long_pointer());
1789         }
1790         __sz += __n;
1791         __set_size(__sz);
1792         traits_type::assign(__p[__sz], value_type());
1793         for (__p += __ip; __first != __last; ++__p, ++__first)
1794             traits_type::assign(*__p, *__first);
1795
1796         return begin() + __ip;
1797     }
1798
1799     template<class _Iterator, class _Sentinel>
1800     _LIBCPP_CONSTEXPR_SINCE_CXX20
1801     iterator __insert_with_size(const_iterator __pos, _Iterator __first, _Sentinel __last, size_type __n);
1802
1803     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 allocator_type& __alloc() _NOEXCEPT { return __r_.second(); }
1804     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR const allocator_type& __alloc() const _NOEXCEPT { return __r_.second(); }
1805
1806     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1807     void __set_short_size(size_type __s) _NOEXCEPT {
1808         _LIBCPP_ASSERT_INTERNAL(
1809             __s < __min_cap, "__s should never be greater than or equal to the short string capacity");
1810         __r_.first().__s.__size_ = __s;
1811         __r_.first().__s.__is_long_ = false;
1812     }
1813
1814     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1815     size_type __get_short_size() const _NOEXCEPT {
1816         _LIBCPP_ASSERT_INTERNAL(
1817             !__r_.first().__s.__is_long_, "String has to be short when trying to get the short size");
1818         return __r_.first().__s.__size_;
1819     }
1820
1821     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1822     void __set_long_size(size_type __s) _NOEXCEPT
1823         {__r_.first().__l.__size_ = __s;}
1824     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1825     size_type __get_long_size() const _NOEXCEPT
1826         {return __r_.first().__l.__size_;}
1827     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1828     void __set_size(size_type __s) _NOEXCEPT
1829         {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);}
1830
1831     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1832     void __set_long_cap(size_type __s) _NOEXCEPT {
1833         __r_.first().__l.__cap_ = __s / __endian_factor;
1834         __r_.first().__l.__is_long_ = true;
1835     }
1836
1837     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1838     size_type __get_long_cap() const _NOEXCEPT {
1839         return __r_.first().__l.__cap_ * __endian_factor;
1840     }
1841
1842     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1843     void __set_long_pointer(pointer __p) _NOEXCEPT
1844         {__r_.first().__l.__data_ = __p;}
1845     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1846     pointer __get_long_pointer() _NOEXCEPT
1847         {return __r_.first().__l.__data_;}
1848     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1849     const_pointer __get_long_pointer() const _NOEXCEPT
1850         {return __r_.first().__l.__data_;}
1851     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1852     pointer __get_short_pointer() _NOEXCEPT
1853         {return pointer_traits<pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1854     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1855     const_pointer __get_short_pointer() const _NOEXCEPT
1856         {return pointer_traits<const_pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1857     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1858     pointer __get_pointer() _NOEXCEPT
1859         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1860     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1861     const_pointer __get_pointer() const _NOEXCEPT
1862         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1863
1864     template <size_type __a> static
1865         _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1866         size_type __align_it(size_type __s) _NOEXCEPT
1867             {return (__s + (__a-1)) & ~(__a-1);}
1868     enum {
1869       __alignment =
1870 #ifdef _LIBCPP_ABI_STRING_8_BYTE_ALIGNMENT
1871       8
1872 #else
1873       16
1874 #endif
1875     };
1876     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1877     size_type __recommend(size_type __s) _NOEXCEPT
1878     {
1879         if (__s < __min_cap) {
1880             return static_cast<size_type>(__min_cap) - 1;
1881         }
1882         size_type __guess = __align_it<sizeof(value_type) < __alignment ?
1883                      __alignment/sizeof(value_type) : 1 > (__s+1) - 1;
1884         if (__guess == __min_cap) ++__guess;
1885         return __guess;
1886     }
1887
1888     inline _LIBCPP_CONSTEXPR_SINCE_CXX20
1889     void __init(const value_type* __s, size_type __sz, size_type __reserve);
1890     inline _LIBCPP_CONSTEXPR_SINCE_CXX20
1891     void __init(const value_type* __s, size_type __sz);
1892     inline _LIBCPP_CONSTEXPR_SINCE_CXX20
1893     void __init(size_type __n, value_type __c);
1894
1895     // Slow path for the (inlined) copy constructor for 'long' strings.
1896     // Always externally instantiated and not inlined.
1897     // Requires that __s is zero terminated.
1898     // The main reason for this function to exist is because for unstable, we
1899     // want to allow inlining of the copy constructor. However, we don't want
1900     // to call the __init() functions as those are marked as inline which may
1901     // result in over-aggressive inlining by the compiler, where our aim is
1902     // to only inline the fast path code directly in the ctor.
1903     _LIBCPP_CONSTEXPR_SINCE_CXX20 void __init_copy_ctor_external(const value_type* __s, size_type __sz);
1904
1905     template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1906     inline _LIBCPP_CONSTEXPR_SINCE_CXX20 void __init(_InputIterator __first, _InputIterator __last);
1907
1908     template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1909     inline _LIBCPP_CONSTEXPR_SINCE_CXX20 void __init(_ForwardIterator __first, _ForwardIterator __last);
1910
1911     template <class _InputIterator, class _Sentinel>
1912     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1913     void __init_with_sentinel(_InputIterator __first, _Sentinel __last);
1914     template <class _InputIterator, class _Sentinel>
1915     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1916     void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __sz);
1917
1918     _LIBCPP_CONSTEXPR_SINCE_CXX20
1919 #if _LIBCPP_ABI_VERSION >= 2 //  We want to use the function in the dylib in ABIv1
1920     _LIBCPP_HIDE_FROM_ABI
1921 #endif
1922     _LIBCPP_DEPRECATED_("use __grow_by_without_replace")
1923     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1924                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
1925     _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
1926     void __grow_by_without_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1927                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
1928     _LIBCPP_CONSTEXPR_SINCE_CXX20
1929     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1930                                size_type __n_copy,  size_type __n_del,
1931                                size_type __n_add, const value_type* __p_new_stuff);
1932
1933     // __assign_no_alias is invoked for assignment operations where we
1934     // have proof that the input does not alias the current instance.
1935     // For example, operator=(basic_string) performs a 'self' check.
1936     template <bool __is_short>
1937     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& __assign_no_alias(const value_type* __s, size_type __n);
1938
1939   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __erase_to_end(size_type __pos) {
1940     __null_terminate_at(std::__to_address(__get_pointer()), __pos);
1941   }
1942
1943     // __erase_external_with_move is invoked for erase() invocations where
1944     // `n ~= npos`, likely requiring memory moves on the string data.
1945     _LIBCPP_CONSTEXPR_SINCE_CXX20 void __erase_external_with_move(size_type __pos, size_type __n);
1946
1947     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1948     void __copy_assign_alloc(const basic_string& __str)
1949         {__copy_assign_alloc(__str, integral_constant<bool,
1950                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
1951
1952     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1953     void __copy_assign_alloc(const basic_string& __str, true_type)
1954         {
1955             if (__alloc() == __str.__alloc())
1956                 __alloc() = __str.__alloc();
1957             else
1958             {
1959                 if (!__str.__is_long())
1960                 {
1961                     __clear_and_shrink();
1962                     __alloc() = __str.__alloc();
1963                 }
1964                 else
1965                 {
1966                     allocator_type __a = __str.__alloc();
1967                     auto __allocation = std::__allocate_at_least(__a, __str.__get_long_cap());
1968                     __begin_lifetime(__allocation.ptr, __allocation.count);
1969                     if (__is_long())
1970                         __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
1971                     __alloc() = std::move(__a);
1972                     __set_long_pointer(__allocation.ptr);
1973                     __set_long_cap(__allocation.count);
1974                     __set_long_size(__str.size());
1975                 }
1976             }
1977         }
1978
1979     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1980     void __copy_assign_alloc(const basic_string&, false_type) _NOEXCEPT
1981         {}
1982
1983 #ifndef _LIBCPP_CXX03_LANG
1984     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1985     void __move_assign(basic_string& __str, false_type)
1986         _NOEXCEPT_(__alloc_traits::is_always_equal::value);
1987     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1988     void __move_assign(basic_string& __str, true_type)
1989 #if _LIBCPP_STD_VER >= 17
1990         _NOEXCEPT;
1991 #else
1992         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1993 #endif
1994 #endif
1995
1996     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1997     void
1998     __move_assign_alloc(basic_string& __str)
1999         _NOEXCEPT_(
2000             !__alloc_traits::propagate_on_container_move_assignment::value ||
2001             is_nothrow_move_assignable<allocator_type>::value)
2002     {__move_assign_alloc(__str, integral_constant<bool,
2003                       __alloc_traits::propagate_on_container_move_assignment::value>());}
2004
2005     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2006     void __move_assign_alloc(basic_string& __c, true_type)
2007         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2008         {
2009             __alloc() = std::move(__c.__alloc());
2010         }
2011
2012     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2013     void __move_assign_alloc(basic_string&, false_type)
2014         _NOEXCEPT
2015         {}
2016
2017     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& __assign_external(const value_type* __s);
2018     _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& __assign_external(const value_type* __s, size_type __n);
2019
2020     // Assigns the value in __s, guaranteed to be __n < __min_cap in length.
2021     inline _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& __assign_short(const value_type* __s, size_type __n) {
2022       pointer __p = __is_long()
2023                         ? (__set_long_size(__n), __get_long_pointer())
2024                         : (__set_short_size(__n), __get_short_pointer());
2025       traits_type::move(std::__to_address(__p), __s, __n);
2026       traits_type::assign(__p[__n], value_type());
2027       return *this;
2028     }
2029
2030     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2031     basic_string& __null_terminate_at(value_type* __p, size_type __newsz) {
2032       __set_size(__newsz);
2033       traits_type::assign(__p[__newsz], value_type());
2034       return *this;
2035     }
2036
2037     template <class _Tp>
2038     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __addr_in_range(const _Tp& __v) const {
2039       return std::__is_pointer_in_range(data(), data() + size() + 1, std::addressof(__v));
2040     }
2041
2042     _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
2043     void __throw_length_error() const {
2044         std::__throw_length_error("basic_string");
2045     }
2046
2047     _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
2048     void __throw_out_of_range() const {
2049         std::__throw_out_of_range("basic_string");
2050     }
2051
2052     friend _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string operator+<>(const basic_string&, const basic_string&);
2053     friend _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string operator+<>(const value_type*, const basic_string&);
2054     friend _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string operator+<>(value_type, const basic_string&);
2055     friend _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string operator+<>(const basic_string&, const value_type*);
2056     friend _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string operator+<>(const basic_string&, value_type);
2057 };
2058
2059 // These declarations must appear before any functions are implicitly used
2060 // so that they have the correct visibility specifier.
2061 #define _LIBCPP_DECLARE(...) extern template __VA_ARGS__;
2062 #ifdef _LIBCPP_ABI_STRING_OPTIMIZED_EXTERNAL_INSTANTIATION
2063     _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, char)
2064 #   ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2065         _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, wchar_t)
2066 #   endif
2067 #else
2068     _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, char)
2069 #   ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2070         _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, wchar_t)
2071 #   endif
2072 #endif
2073 #undef _LIBCPP_DECLARE
2074
2075
2076 #if _LIBCPP_STD_VER >= 17
2077 template<class _InputIterator,
2078          class _CharT = __iter_value_type<_InputIterator>,
2079          class _Allocator = allocator<_CharT>,
2080          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2081          class = enable_if_t<__is_allocator<_Allocator>::value>
2082          >
2083 basic_string(_InputIterator, _InputIterator, _Allocator = _Allocator())
2084   -> basic_string<_CharT, char_traits<_CharT>, _Allocator>;
2085
2086 template<class _CharT,
2087          class _Traits,
2088          class _Allocator = allocator<_CharT>,
2089          class = enable_if_t<__is_allocator<_Allocator>::value>
2090          >
2091 explicit basic_string(basic_string_view<_CharT, _Traits>, const _Allocator& = _Allocator())
2092   -> basic_string<_CharT, _Traits, _Allocator>;
2093
2094 template<class _CharT,
2095          class _Traits,
2096          class _Allocator = allocator<_CharT>,
2097          class = enable_if_t<__is_allocator<_Allocator>::value>,
2098          class _Sz = typename allocator_traits<_Allocator>::size_type
2099          >
2100 basic_string(basic_string_view<_CharT, _Traits>, _Sz, _Sz, const _Allocator& = _Allocator())
2101   -> basic_string<_CharT, _Traits, _Allocator>;
2102 #endif
2103
2104 #if _LIBCPP_STD_VER >= 23
2105 template <ranges::input_range _Range,
2106           class _Allocator = allocator<ranges::range_value_t<_Range>>,
2107           class = enable_if_t<__is_allocator<_Allocator>::value>
2108           >
2109 basic_string(from_range_t, _Range&&, _Allocator = _Allocator())
2110   -> basic_string<ranges::range_value_t<_Range>, char_traits<ranges::range_value_t<_Range>>, _Allocator>;
2111 #endif
2112
2113 template <class _CharT, class _Traits, class _Allocator>
2114 _LIBCPP_CONSTEXPR_SINCE_CXX20
2115 void basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s,
2116                                                        size_type __sz,
2117                                                        size_type __reserve)
2118 {
2119     if (__libcpp_is_constant_evaluated())
2120         __r_.first() = __rep();
2121     if (__reserve > max_size())
2122         __throw_length_error();
2123     pointer __p;
2124     if (__fits_in_sso(__reserve))
2125     {
2126         __set_short_size(__sz);
2127         __p = __get_short_pointer();
2128     }
2129     else
2130     {
2131         auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__reserve) + 1);
2132         __p = __allocation.ptr;
2133         __begin_lifetime(__p, __allocation.count);
2134         __set_long_pointer(__p);
2135         __set_long_cap(__allocation.count);
2136         __set_long_size(__sz);
2137     }
2138     traits_type::copy(std::__to_address(__p), __s, __sz);
2139     traits_type::assign(__p[__sz], value_type());
2140 }
2141
2142 template <class _CharT, class _Traits, class _Allocator>
2143 _LIBCPP_CONSTEXPR_SINCE_CXX20
2144 void
2145 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
2146 {
2147     if (__libcpp_is_constant_evaluated())
2148         __r_.first() = __rep();
2149     if (__sz > max_size())
2150         __throw_length_error();
2151     pointer __p;
2152     if (__fits_in_sso(__sz))
2153     {
2154         __set_short_size(__sz);
2155         __p = __get_short_pointer();
2156     }
2157     else
2158     {
2159         auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
2160         __p = __allocation.ptr;
2161         __begin_lifetime(__p, __allocation.count);
2162         __set_long_pointer(__p);
2163         __set_long_cap(__allocation.count);
2164         __set_long_size(__sz);
2165     }
2166     traits_type::copy(std::__to_address(__p), __s, __sz);
2167     traits_type::assign(__p[__sz], value_type());
2168 }
2169
2170 template <class _CharT, class _Traits, class _Allocator>
2171 _LIBCPP_CONSTEXPR_SINCE_CXX20
2172 void basic_string<_CharT, _Traits, _Allocator>::__init_copy_ctor_external(
2173     const value_type* __s, size_type __sz) {
2174   if (__libcpp_is_constant_evaluated())
2175     __r_.first() = __rep();
2176
2177   pointer __p;
2178   if (__fits_in_sso(__sz)) {
2179     __p = __get_short_pointer();
2180     __set_short_size(__sz);
2181   } else {
2182     if (__sz > max_size())
2183       __throw_length_error();
2184     auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
2185     __p = __allocation.ptr;
2186     __begin_lifetime(__p, __allocation.count);
2187     __set_long_pointer(__p);
2188     __set_long_cap(__allocation.count);
2189     __set_long_size(__sz);
2190   }
2191   traits_type::copy(std::__to_address(__p), __s, __sz + 1);
2192 }
2193
2194 template <class _CharT, class _Traits, class _Allocator>
2195 _LIBCPP_CONSTEXPR_SINCE_CXX20
2196 void
2197 basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
2198 {
2199     if (__libcpp_is_constant_evaluated())
2200         __r_.first() = __rep();
2201
2202     if (__n > max_size())
2203         __throw_length_error();
2204     pointer __p;
2205     if (__fits_in_sso(__n))
2206     {
2207         __set_short_size(__n);
2208         __p = __get_short_pointer();
2209     }
2210     else
2211     {
2212         auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__n) + 1);
2213         __p = __allocation.ptr;
2214         __begin_lifetime(__p, __allocation.count);
2215         __set_long_pointer(__p);
2216         __set_long_cap(__allocation.count);
2217         __set_long_size(__n);
2218     }
2219     traits_type::assign(std::__to_address(__p), __n, __c);
2220     traits_type::assign(__p[__n], value_type());
2221 }
2222
2223 template <class _CharT, class _Traits, class _Allocator>
2224 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2225 _LIBCPP_CONSTEXPR_SINCE_CXX20
2226 void basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last)
2227 {
2228   __init_with_sentinel(std::move(__first), std::move(__last));
2229 }
2230
2231 template <class _CharT, class _Traits, class _Allocator>
2232 template <class _InputIterator, class _Sentinel>
2233 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2234 void basic_string<_CharT, _Traits, _Allocator>::__init_with_sentinel(_InputIterator __first, _Sentinel __last) {
2235     __r_.first() = __rep();
2236
2237 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2238     try
2239     {
2240 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2241     for (; __first != __last; ++__first)
2242         push_back(*__first);
2243 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2244     }
2245     catch (...)
2246     {
2247         if (__is_long())
2248             __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2249         throw;
2250     }
2251 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2252 }
2253
2254 template <class _CharT, class _Traits, class _Allocator>
2255 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2256 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2257 basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
2258 {
2259   size_type __sz = static_cast<size_type>(std::distance(__first, __last));
2260   __init_with_size(__first, __last, __sz);
2261 }
2262
2263 template <class _CharT, class _Traits, class _Allocator>
2264 template <class _InputIterator, class _Sentinel>
2265 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2266 void basic_string<_CharT, _Traits, _Allocator>::__init_with_size(
2267     _InputIterator __first, _Sentinel __last, size_type __sz) {
2268     if (__libcpp_is_constant_evaluated())
2269         __r_.first() = __rep();
2270
2271     if (__sz > max_size())
2272         __throw_length_error();
2273
2274     pointer __p;
2275     if (__fits_in_sso(__sz))
2276     {
2277         __set_short_size(__sz);
2278         __p = __get_short_pointer();
2279
2280     }
2281     else
2282     {
2283         auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
2284         __p = __allocation.ptr;
2285         __begin_lifetime(__p, __allocation.count);
2286         __set_long_pointer(__p);
2287         __set_long_cap(__allocation.count);
2288         __set_long_size(__sz);
2289     }
2290
2291 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2292     try
2293     {
2294 #endif  // _LIBCPP_HAS_NO_EXCEPTIONS
2295     for (; __first != __last; ++__first, (void) ++__p)
2296         traits_type::assign(*__p, *__first);
2297     traits_type::assign(*__p, value_type());
2298 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2299     }
2300     catch (...)
2301     {
2302         if (__is_long())
2303             __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2304         throw;
2305     }
2306 #endif  // _LIBCPP_HAS_NO_EXCEPTIONS
2307 }
2308
2309 template <class _CharT, class _Traits, class _Allocator>
2310 _LIBCPP_CONSTEXPR_SINCE_CXX20
2311 void
2312 basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
2313     (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2314      size_type __n_copy,  size_type __n_del,     size_type __n_add, const value_type* __p_new_stuff)
2315 {
2316     size_type __ms = max_size();
2317     if (__delta_cap > __ms - __old_cap - 1)
2318         __throw_length_error();
2319     pointer __old_p = __get_pointer();
2320     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2321                           __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2322                           __ms - 1;
2323     auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
2324     pointer __p = __allocation.ptr;
2325     __begin_lifetime(__p, __allocation.count);
2326     if (__n_copy != 0)
2327         traits_type::copy(std::__to_address(__p),
2328                           std::__to_address(__old_p), __n_copy);
2329     if (__n_add != 0)
2330         traits_type::copy(std::__to_address(__p) + __n_copy, __p_new_stuff, __n_add);
2331     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2332     if (__sec_cp_sz != 0)
2333         traits_type::copy(std::__to_address(__p) + __n_copy + __n_add,
2334                           std::__to_address(__old_p) + __n_copy + __n_del, __sec_cp_sz);
2335     if (__old_cap+1 != __min_cap)
2336         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
2337     __set_long_pointer(__p);
2338     __set_long_cap(__allocation.count);
2339     __old_sz = __n_copy + __n_add + __sec_cp_sz;
2340     __set_long_size(__old_sz);
2341     traits_type::assign(__p[__old_sz], value_type());
2342 }
2343
2344 // __grow_by is deprecated because it does not set the size. It may not update the size when the size is changed, and it
2345 // may also not set the size at all when the string was short initially. This leads to unpredictable size value. It is
2346 // not removed or changed to avoid breaking the ABI.
2347 template <class _CharT, class _Traits, class _Allocator>
2348 void
2349 _LIBCPP_CONSTEXPR_SINCE_CXX20
2350 #if _LIBCPP_ABI_VERSION >= 2 // We want to use the function in the dylib in ABIv1
2351     _LIBCPP_HIDE_FROM_ABI
2352 #endif
2353     _LIBCPP_DEPRECATED_("use __grow_by_without_replace")
2354 basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2355                                                      size_type __n_copy,  size_type __n_del,     size_type __n_add)
2356 {
2357     size_type __ms = max_size();
2358     if (__delta_cap > __ms - __old_cap)
2359         __throw_length_error();
2360     pointer __old_p = __get_pointer();
2361     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2362                           __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2363                           __ms - 1;
2364     auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
2365     pointer __p = __allocation.ptr;
2366     __begin_lifetime(__p, __allocation.count);
2367     if (__n_copy != 0)
2368         traits_type::copy(std::__to_address(__p),
2369                           std::__to_address(__old_p), __n_copy);
2370     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2371     if (__sec_cp_sz != 0)
2372         traits_type::copy(std::__to_address(__p) + __n_copy + __n_add,
2373                           std::__to_address(__old_p) + __n_copy + __n_del,
2374                           __sec_cp_sz);
2375     if (__old_cap + 1 != __min_cap)
2376         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap + 1);
2377     __set_long_pointer(__p);
2378     __set_long_cap(__allocation.count);
2379 }
2380
2381 template <class _CharT, class _Traits, class _Allocator>
2382 void _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
2383 basic_string<_CharT, _Traits, _Allocator>::__grow_by_without_replace(
2384     size_type __old_cap,
2385     size_type __delta_cap,
2386     size_type __old_sz,
2387     size_type __n_copy,
2388     size_type __n_del,
2389     size_type __n_add) {
2390     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
2391     __grow_by(__old_cap, __delta_cap, __old_sz, __n_copy, __n_del, __n_add);
2392     _LIBCPP_SUPPRESS_DEPRECATED_POP
2393     __set_long_size(__old_sz - __n_del + __n_add);
2394 }
2395
2396 // assign
2397
2398 template <class _CharT, class _Traits, class _Allocator>
2399 template <bool __is_short>
2400 _LIBCPP_CONSTEXPR_SINCE_CXX20
2401 basic_string<_CharT, _Traits, _Allocator>&
2402 basic_string<_CharT, _Traits, _Allocator>::__assign_no_alias(
2403     const value_type* __s, size_type __n) {
2404   size_type __cap = __is_short ? static_cast<size_type>(__min_cap) : __get_long_cap();
2405   if (__n < __cap) {
2406     pointer __p = __is_short ? __get_short_pointer() : __get_long_pointer();
2407     __is_short ? __set_short_size(__n) : __set_long_size(__n);
2408     traits_type::copy(std::__to_address(__p), __s, __n);
2409     traits_type::assign(__p[__n], value_type());
2410   } else {
2411     size_type __sz = __is_short ? __get_short_size() : __get_long_size();
2412     __grow_by_and_replace(__cap - 1, __n - __cap + 1, __sz, 0, __sz, __n, __s);
2413   }
2414   return *this;
2415 }
2416
2417 template <class _CharT, class _Traits, class _Allocator>
2418 _LIBCPP_CONSTEXPR_SINCE_CXX20
2419 basic_string<_CharT, _Traits, _Allocator>&
2420 basic_string<_CharT, _Traits, _Allocator>::__assign_external(
2421     const value_type* __s, size_type __n) {
2422   size_type __cap = capacity();
2423   if (__cap >= __n) {
2424     value_type* __p = std::__to_address(__get_pointer());
2425     traits_type::move(__p, __s, __n);
2426     return __null_terminate_at(__p, __n);
2427   } else {
2428     size_type __sz = size();
2429     __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
2430     return *this;
2431   }
2432 }
2433
2434 template <class _CharT, class _Traits, class _Allocator>
2435 _LIBCPP_CONSTEXPR_SINCE_CXX20
2436 basic_string<_CharT, _Traits, _Allocator>&
2437 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
2438 {
2439     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::assign received nullptr");
2440     return (__builtin_constant_p(__n) && __fits_in_sso(__n))
2441                ? __assign_short(__s, __n)
2442                : __assign_external(__s, __n);
2443 }
2444
2445 template <class _CharT, class _Traits, class _Allocator>
2446 _LIBCPP_CONSTEXPR_SINCE_CXX20
2447 basic_string<_CharT, _Traits, _Allocator>&
2448 basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
2449 {
2450     size_type __cap = capacity();
2451     if (__cap < __n)
2452     {
2453         size_type __sz = size();
2454         __grow_by_without_replace(__cap, __n - __cap, __sz, 0, __sz);
2455     }
2456     value_type* __p = std::__to_address(__get_pointer());
2457     traits_type::assign(__p, __n, __c);
2458     return __null_terminate_at(__p, __n);
2459 }
2460
2461 template <class _CharT, class _Traits, class _Allocator>
2462 _LIBCPP_CONSTEXPR_SINCE_CXX20
2463 basic_string<_CharT, _Traits, _Allocator>&
2464 basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
2465 {
2466     pointer __p;
2467     if (__is_long())
2468     {
2469         __p = __get_long_pointer();
2470         __set_long_size(1);
2471     }
2472     else
2473     {
2474         __p = __get_short_pointer();
2475         __set_short_size(1);
2476     }
2477     traits_type::assign(*__p, __c);
2478     traits_type::assign(*++__p, value_type());
2479     return *this;
2480 }
2481
2482 template <class _CharT, class _Traits, class _Allocator>
2483 _LIBCPP_CONSTEXPR_SINCE_CXX20
2484 basic_string<_CharT, _Traits, _Allocator>&
2485 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
2486 {
2487   if (this != std::addressof(__str)) {
2488     __copy_assign_alloc(__str);
2489     if (!__is_long()) {
2490       if (!__str.__is_long()) {
2491         __r_.first() = __str.__r_.first();
2492       } else {
2493         return __assign_no_alias<true>(__str.data(), __str.size());
2494       }
2495     } else {
2496       return __assign_no_alias<false>(__str.data(), __str.size());
2497     }
2498   }
2499   return *this;
2500 }
2501
2502 #ifndef _LIBCPP_CXX03_LANG
2503
2504 template <class _CharT, class _Traits, class _Allocator>
2505 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
2506 void
2507 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)
2508     _NOEXCEPT_(__alloc_traits::is_always_equal::value)
2509 {
2510     if (__alloc() != __str.__alloc())
2511         assign(__str);
2512     else
2513         __move_assign(__str, true_type());
2514 }
2515
2516 template <class _CharT, class _Traits, class _Allocator>
2517 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
2518 void
2519 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type)
2520 #if _LIBCPP_STD_VER >= 17
2521     _NOEXCEPT
2522 #else
2523     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2524 #endif
2525 {
2526   if (__is_long()) {
2527     __alloc_traits::deallocate(__alloc(), __get_long_pointer(),
2528                                __get_long_cap());
2529 #if _LIBCPP_STD_VER <= 14
2530     if (!is_nothrow_move_assignable<allocator_type>::value) {
2531       __set_short_size(0);
2532       traits_type::assign(__get_short_pointer()[0], value_type());
2533     }
2534 #endif
2535   }
2536   __move_assign_alloc(__str);
2537   __r_.first() = __str.__r_.first();
2538   __str.__set_short_size(0);
2539   traits_type::assign(__str.__get_short_pointer()[0], value_type());
2540 }
2541
2542 #endif
2543
2544 template <class _CharT, class _Traits, class _Allocator>
2545 template<class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2546 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2547 basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2548 {
2549   __assign_with_sentinel(__first, __last);
2550   return *this;
2551 }
2552
2553 template <class _CharT, class _Traits, class _Allocator>
2554 template <class _InputIterator, class _Sentinel>
2555 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2556 void
2557 basic_string<_CharT, _Traits, _Allocator>::__assign_with_sentinel(_InputIterator __first, _Sentinel __last) {
2558   const basic_string __temp(__init_with_sentinel_tag(), std::move(__first), std::move(__last), __alloc());
2559   assign(__temp.data(), __temp.size());
2560 }
2561
2562 template <class _CharT, class _Traits, class _Allocator>
2563 template<class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2564 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2565 basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2566 {
2567   if (__string_is_trivial_iterator<_ForwardIterator>::value) {
2568     size_type __n = static_cast<size_type>(std::distance(__first, __last));
2569     __assign_trivial(__first, __last, __n);
2570   } else {
2571     __assign_with_sentinel(__first, __last);
2572   }
2573
2574   return *this;
2575 }
2576
2577 template <class _CharT, class _Traits, class _Allocator>
2578 template <class _Iterator, class _Sentinel>
2579 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
2580 void
2581 basic_string<_CharT, _Traits, _Allocator>::__assign_trivial(_Iterator __first, _Sentinel __last, size_type __n) {
2582   _LIBCPP_ASSERT_INTERNAL(
2583       __string_is_trivial_iterator<_Iterator>::value, "The iterator type given to `__assign_trivial` must be trivial");
2584
2585   size_type __cap = capacity();
2586   if (__cap < __n) {
2587     // Unlike `append` functions, if the input range points into the string itself, there is no case that the input
2588     // range could get invalidated by reallocation:
2589     // 1. If the input range is a subset of the string itself, its size cannot exceed the capacity of the string,
2590     //    thus no reallocation would happen.
2591     // 2. In the exotic case where the input range is the byte representation of the string itself, the string
2592     //    object itself stays valid even if reallocation happens.
2593     size_type __sz = size();
2594     __grow_by_without_replace(__cap, __n - __cap, __sz, 0, __sz);
2595     }
2596     pointer __p = __get_pointer();
2597     for (; __first != __last; ++__p, (void) ++__first)
2598         traits_type::assign(*__p, *__first);
2599     traits_type::assign(*__p, value_type());
2600     __set_size(__n);
2601 }
2602
2603 template <class _CharT, class _Traits, class _Allocator>
2604 _LIBCPP_CONSTEXPR_SINCE_CXX20
2605 basic_string<_CharT, _Traits, _Allocator>&
2606 basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n)
2607 {
2608     size_type __sz = __str.size();
2609     if (__pos > __sz)
2610         __throw_out_of_range();
2611     return assign(__str.data() + __pos, std::min(__n, __sz - __pos));
2612 }
2613
2614 template <class _CharT, class _Traits, class _Allocator>
2615 template <class _Tp,
2616           __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
2617                             !__is_same_uncvref<_Tp, basic_string<_CharT, _Traits, _Allocator> >::value,
2618                         int> >
2619 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2620 basic_string<_CharT, _Traits, _Allocator>::assign(const _Tp& __t, size_type __pos, size_type __n) {
2621     __self_view __sv = __t;
2622     size_type __sz = __sv.size();
2623     if (__pos > __sz)
2624         __throw_out_of_range();
2625     return assign(__sv.data() + __pos, std::min(__n, __sz - __pos));
2626 }
2627
2628 template <class _CharT, class _Traits, class _Allocator>
2629 _LIBCPP_CONSTEXPR_SINCE_CXX20
2630 basic_string<_CharT, _Traits, _Allocator>&
2631 basic_string<_CharT, _Traits, _Allocator>::__assign_external(const value_type* __s) {
2632   return __assign_external(__s, traits_type::length(__s));
2633 }
2634
2635 template <class _CharT, class _Traits, class _Allocator>
2636 _LIBCPP_CONSTEXPR_SINCE_CXX20
2637 basic_string<_CharT, _Traits, _Allocator>&
2638 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s)
2639 {
2640     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::assign received nullptr");
2641     return __builtin_constant_p(*__s)
2642                ? (__fits_in_sso(traits_type::length(__s))
2643                       ? __assign_short(__s, traits_type::length(__s))
2644                       : __assign_external(__s, traits_type::length(__s)))
2645                : __assign_external(__s);
2646 }
2647 // append
2648
2649 template <class _CharT, class _Traits, class _Allocator>
2650 _LIBCPP_CONSTEXPR_SINCE_CXX20
2651 basic_string<_CharT, _Traits, _Allocator>&
2652 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n)
2653 {
2654     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::append received nullptr");
2655     size_type __cap = capacity();
2656     size_type __sz = size();
2657     if (__cap - __sz >= __n)
2658     {
2659         if (__n)
2660         {
2661             value_type* __p = std::__to_address(__get_pointer());
2662             traits_type::copy(__p + __sz, __s, __n);
2663             __sz += __n;
2664             __set_size(__sz);
2665             traits_type::assign(__p[__sz], value_type());
2666         }
2667     }
2668     else
2669         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s);
2670     return *this;
2671 }
2672
2673 template <class _CharT, class _Traits, class _Allocator>
2674 _LIBCPP_CONSTEXPR_SINCE_CXX20
2675 basic_string<_CharT, _Traits, _Allocator>&
2676 basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c)
2677 {
2678     if (__n)
2679     {
2680         size_type __cap = capacity();
2681         size_type __sz = size();
2682         if (__cap - __sz < __n)
2683             __grow_by_without_replace(__cap, __sz + __n - __cap, __sz, __sz, 0);
2684         pointer __p = __get_pointer();
2685         traits_type::assign(std::__to_address(__p) + __sz, __n, __c);
2686         __sz += __n;
2687         __set_size(__sz);
2688         traits_type::assign(__p[__sz], value_type());
2689     }
2690     return *this;
2691 }
2692
2693 template <class _CharT, class _Traits, class _Allocator>
2694 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
2695 basic_string<_CharT, _Traits, _Allocator>::__append_default_init(size_type __n)
2696 {
2697     if (__n)
2698     {
2699         size_type __cap = capacity();
2700         size_type __sz = size();
2701         if (__cap - __sz < __n)
2702             __grow_by_without_replace(__cap, __sz + __n - __cap, __sz, __sz, 0);
2703         pointer __p = __get_pointer();
2704         __sz += __n;
2705         __set_size(__sz);
2706         traits_type::assign(__p[__sz], value_type());
2707     }
2708 }
2709
2710 template <class _CharT, class _Traits, class _Allocator>
2711 _LIBCPP_CONSTEXPR_SINCE_CXX20
2712 void
2713 basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)
2714 {
2715     bool __is_short = !__is_long();
2716     size_type __cap;
2717     size_type __sz;
2718     if (__is_short)
2719     {
2720         __cap = __min_cap - 1;
2721         __sz = __get_short_size();
2722     }
2723     else
2724     {
2725         __cap = __get_long_cap() - 1;
2726         __sz = __get_long_size();
2727     }
2728     if (__sz == __cap)
2729     {
2730         __grow_by_without_replace(__cap, 1, __sz, __sz, 0);
2731         __is_short = false; // the string is always long after __grow_by
2732     }
2733     pointer __p = __get_pointer();
2734     if (__is_short)
2735     {
2736         __p = __get_short_pointer() + __sz;
2737         __set_short_size(__sz+1);
2738     }
2739     else
2740     {
2741         __p = __get_long_pointer() + __sz;
2742         __set_long_size(__sz+1);
2743     }
2744     traits_type::assign(*__p, __c);
2745     traits_type::assign(*++__p, value_type());
2746 }
2747
2748 template <class _CharT, class _Traits, class _Allocator>
2749 template<class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2750 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2751 basic_string<_CharT, _Traits, _Allocator>::append(
2752     _ForwardIterator __first, _ForwardIterator __last)
2753 {
2754     size_type __sz = size();
2755     size_type __cap = capacity();
2756     size_type __n = static_cast<size_type>(std::distance(__first, __last));
2757     if (__n)
2758     {
2759         if (__string_is_trivial_iterator<_ForwardIterator>::value &&
2760             !__addr_in_range(*__first))
2761         {
2762             if (__cap - __sz < __n)
2763               __grow_by_without_replace(__cap, __sz + __n - __cap, __sz, __sz, 0);
2764             pointer __p = __get_pointer() + __sz;
2765             for (; __first != __last; ++__p, (void) ++__first)
2766                 traits_type::assign(*__p, *__first);
2767             traits_type::assign(*__p, value_type());
2768             __set_size(__sz + __n);
2769         }
2770         else
2771         {
2772             const basic_string __temp(__first, __last, __alloc());
2773             append(__temp.data(), __temp.size());
2774         }
2775     }
2776     return *this;
2777 }
2778
2779 template <class _CharT, class _Traits, class _Allocator>
2780 _LIBCPP_CONSTEXPR_SINCE_CXX20
2781 basic_string<_CharT, _Traits, _Allocator>&
2782 basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n)
2783 {
2784     size_type __sz = __str.size();
2785     if (__pos > __sz)
2786         __throw_out_of_range();
2787     return append(__str.data() + __pos, std::min(__n, __sz - __pos));
2788 }
2789
2790 template <class _CharT, class _Traits, class _Allocator>
2791 template <class _Tp,
2792           __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
2793                             !__is_same_uncvref<_Tp, basic_string<_CharT, _Traits, _Allocator> >::value,
2794                         int> >
2795 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2796 basic_string<_CharT, _Traits, _Allocator>::append(const _Tp& __t, size_type __pos, size_type __n) {
2797     __self_view __sv = __t;
2798     size_type __sz = __sv.size();
2799     if (__pos > __sz)
2800         __throw_out_of_range();
2801     return append(__sv.data() + __pos, std::min(__n, __sz - __pos));
2802 }
2803
2804 template <class _CharT, class _Traits, class _Allocator>
2805 _LIBCPP_CONSTEXPR_SINCE_CXX20
2806 basic_string<_CharT, _Traits, _Allocator>&
2807 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s)
2808 {
2809     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::append received nullptr");
2810     return append(__s, traits_type::length(__s));
2811 }
2812
2813 // insert
2814
2815 template <class _CharT, class _Traits, class _Allocator>
2816 _LIBCPP_CONSTEXPR_SINCE_CXX20
2817 basic_string<_CharT, _Traits, _Allocator>&
2818 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s, size_type __n)
2819 {
2820     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::insert received nullptr");
2821     size_type __sz = size();
2822     if (__pos > __sz)
2823         __throw_out_of_range();
2824     size_type __cap = capacity();
2825     if (__cap - __sz >= __n)
2826     {
2827         if (__n)
2828         {
2829             value_type* __p = std::__to_address(__get_pointer());
2830             size_type __n_move = __sz - __pos;
2831             if (__n_move != 0)
2832             {
2833                 if (std::__is_pointer_in_range(__p + __pos, __p + __sz, __s))
2834                     __s += __n;
2835                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2836             }
2837             traits_type::move(__p + __pos, __s, __n);
2838             __sz += __n;
2839             __set_size(__sz);
2840             traits_type::assign(__p[__sz], value_type());
2841         }
2842     }
2843     else
2844         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s);
2845     return *this;
2846 }
2847
2848 template <class _CharT, class _Traits, class _Allocator>
2849 _LIBCPP_CONSTEXPR_SINCE_CXX20
2850 basic_string<_CharT, _Traits, _Allocator>&
2851 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c)
2852 {
2853     size_type __sz = size();
2854     if (__pos > __sz)
2855         __throw_out_of_range();
2856     if (__n)
2857     {
2858         size_type __cap = capacity();
2859         value_type* __p;
2860         if (__cap - __sz >= __n)
2861         {
2862             __p = std::__to_address(__get_pointer());
2863             size_type __n_move = __sz - __pos;
2864             if (__n_move != 0)
2865                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2866         }
2867         else
2868         {
2869             __grow_by_without_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n);
2870             __p = std::__to_address(__get_long_pointer());
2871         }
2872         traits_type::assign(__p + __pos, __n, __c);
2873         __sz += __n;
2874         __set_size(__sz);
2875         traits_type::assign(__p[__sz], value_type());
2876     }
2877     return *this;
2878 }
2879
2880 template <class _CharT, class _Traits, class _Allocator>
2881 template<class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2882 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2883 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last)
2884 {
2885   const basic_string __temp(__first, __last, __alloc());
2886   return insert(__pos, __temp.data(), __temp.data() + __temp.size());
2887 }
2888
2889 template <class _CharT, class _Traits, class _Allocator>
2890 template<class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2891 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2892 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last)
2893 {
2894     auto __n = static_cast<size_type>(std::distance(__first, __last));
2895     return __insert_with_size(__pos, __first, __last, __n);
2896 }
2897
2898 template <class _CharT, class _Traits, class _Allocator>
2899 template<class _Iterator, class _Sentinel>
2900 _LIBCPP_CONSTEXPR_SINCE_CXX20
2901 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2902 basic_string<_CharT, _Traits, _Allocator>::__insert_with_size(
2903     const_iterator __pos, _Iterator __first, _Sentinel __last, size_type __n) {
2904     size_type __ip = static_cast<size_type>(__pos - begin());
2905     if (__n == 0)
2906         return begin() + __ip;
2907
2908     if (__string_is_trivial_iterator<_Iterator>::value && !__addr_in_range(*__first))
2909     {
2910         return __insert_from_safe_copy(__n, __ip, __first, __last);
2911     }
2912     else
2913     {
2914         const basic_string __temp(__init_with_sentinel_tag(), __first, __last, __alloc());
2915         return __insert_from_safe_copy(__n, __ip, __temp.begin(), __temp.end());
2916     }
2917 }
2918
2919 template <class _CharT, class _Traits, class _Allocator>
2920 _LIBCPP_CONSTEXPR_SINCE_CXX20
2921 basic_string<_CharT, _Traits, _Allocator>&
2922 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str,
2923                                                   size_type __pos2, size_type __n)
2924 {
2925     size_type __str_sz = __str.size();
2926     if (__pos2 > __str_sz)
2927         __throw_out_of_range();
2928     return insert(__pos1, __str.data() + __pos2, std::min(__n, __str_sz - __pos2));
2929 }
2930
2931 template <class _CharT, class _Traits, class _Allocator>
2932 template <class _Tp,
2933           __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
2934                             !__is_same_uncvref<_Tp, basic_string<_CharT, _Traits, _Allocator> >::value,
2935                         int> >
2936 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
2937 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const _Tp& __t, size_type __pos2, size_type __n) {
2938     __self_view __sv = __t;
2939     size_type __str_sz = __sv.size();
2940     if (__pos2 > __str_sz)
2941         __throw_out_of_range();
2942     return insert(__pos1, __sv.data() + __pos2, std::min(__n, __str_sz - __pos2));
2943 }
2944
2945 template <class _CharT, class _Traits, class _Allocator>
2946 _LIBCPP_CONSTEXPR_SINCE_CXX20
2947 basic_string<_CharT, _Traits, _Allocator>&
2948 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s)
2949 {
2950     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::insert received nullptr");
2951     return insert(__pos, __s, traits_type::length(__s));
2952 }
2953
2954 template <class _CharT, class _Traits, class _Allocator>
2955 _LIBCPP_CONSTEXPR_SINCE_CXX20
2956 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2957 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c)
2958 {
2959     size_type __ip = static_cast<size_type>(__pos - begin());
2960     size_type __sz = size();
2961     size_type __cap = capacity();
2962     value_type* __p;
2963     if (__cap == __sz)
2964     {
2965         __grow_by_without_replace(__cap, 1, __sz, __ip, 0, 1);
2966         __p = std::__to_address(__get_long_pointer());
2967     }
2968     else
2969     {
2970         __p = std::__to_address(__get_pointer());
2971         size_type __n_move = __sz - __ip;
2972         if (__n_move != 0)
2973             traits_type::move(__p + __ip + 1, __p + __ip, __n_move);
2974     }
2975     traits_type::assign(__p[__ip], __c);
2976     traits_type::assign(__p[++__sz], value_type());
2977     __set_size(__sz);
2978     return begin() + static_cast<difference_type>(__ip);
2979 }
2980
2981 // replace
2982
2983 template <class _CharT, class _Traits, class _Allocator>
2984 _LIBCPP_CONSTEXPR_SINCE_CXX20
2985 basic_string<_CharT, _Traits, _Allocator>&
2986 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2)
2987     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2988 {
2989     _LIBCPP_ASSERT_UNCATEGORIZED(__n2 == 0 || __s != nullptr, "string::replace received nullptr");
2990     size_type __sz = size();
2991     if (__pos > __sz)
2992         __throw_out_of_range();
2993     __n1 = std::min(__n1, __sz - __pos);
2994     size_type __cap = capacity();
2995     if (__cap - __sz + __n1 >= __n2)
2996     {
2997         value_type* __p = std::__to_address(__get_pointer());
2998         if (__n1 != __n2)
2999         {
3000             size_type __n_move = __sz - __pos - __n1;
3001             if (__n_move != 0)
3002             {
3003                 if (__n1 > __n2)
3004                 {
3005                     traits_type::move(__p + __pos, __s, __n2);
3006                     traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
3007                     return __null_terminate_at(__p, __sz + (__n2 - __n1));
3008                 }
3009                 if (std::__is_pointer_in_range(__p + __pos + 1, __p + __sz, __s))
3010                 {
3011                     if (__p + __pos + __n1 <= __s)
3012                         __s += __n2 - __n1;
3013                     else // __p + __pos < __s < __p + __pos + __n1
3014                     {
3015                         traits_type::move(__p + __pos, __s, __n1);
3016                         __pos += __n1;
3017                         __s += __n2;
3018                         __n2 -= __n1;
3019                         __n1 = 0;
3020                     }
3021                 }
3022                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
3023             }
3024         }
3025         traits_type::move(__p + __pos, __s, __n2);
3026         return __null_terminate_at(__p, __sz + (__n2 - __n1));
3027     }
3028     else
3029         __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s);
3030     return *this;
3031 }
3032
3033 template <class _CharT, class _Traits, class _Allocator>
3034 _LIBCPP_CONSTEXPR_SINCE_CXX20
3035 basic_string<_CharT, _Traits, _Allocator>&
3036 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c)
3037 {
3038     size_type __sz = size();
3039     if (__pos > __sz)
3040         __throw_out_of_range();
3041     __n1 = std::min(__n1, __sz - __pos);
3042     size_type __cap = capacity();
3043     value_type* __p;
3044     if (__cap - __sz + __n1 >= __n2)
3045     {
3046         __p = std::__to_address(__get_pointer());
3047         if (__n1 != __n2)
3048         {
3049             size_type __n_move = __sz - __pos - __n1;
3050             if (__n_move != 0)
3051                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
3052         }
3053     }
3054     else
3055     {
3056         __grow_by_without_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2);
3057         __p = std::__to_address(__get_long_pointer());
3058     }
3059     traits_type::assign(__p + __pos, __n2, __c);
3060     return __null_terminate_at(__p, __sz - (__n1 - __n2));
3061 }
3062
3063 template <class _CharT, class _Traits, class _Allocator>
3064 template<class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
3065 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
3066 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2,
3067                                                    _InputIterator __j1, _InputIterator __j2)
3068 {
3069     const basic_string __temp(__j1, __j2, __alloc());
3070     return replace(__i1, __i2, __temp);
3071 }
3072
3073 template <class _CharT, class _Traits, class _Allocator>
3074 _LIBCPP_CONSTEXPR_SINCE_CXX20
3075 basic_string<_CharT, _Traits, _Allocator>&
3076 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str,
3077                                                    size_type __pos2, size_type __n2)
3078 {
3079     size_type __str_sz = __str.size();
3080     if (__pos2 > __str_sz)
3081         __throw_out_of_range();
3082     return replace(__pos1, __n1, __str.data() + __pos2, std::min(__n2, __str_sz - __pos2));
3083 }
3084
3085 template <class _CharT, class _Traits, class _Allocator>
3086 template <class _Tp,
3087           __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
3088                             !__is_same_uncvref<_Tp, basic_string<_CharT, _Traits, _Allocator> >::value,
3089                         int> >
3090 _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>&
3091 basic_string<_CharT, _Traits, _Allocator>::replace(
3092     size_type __pos1, size_type __n1, const _Tp& __t, size_type __pos2, size_type __n2) {
3093     __self_view __sv = __t;
3094     size_type __str_sz = __sv.size();
3095     if (__pos2 > __str_sz)
3096         __throw_out_of_range();
3097     return replace(__pos1, __n1, __sv.data() + __pos2, std::min(__n2, __str_sz - __pos2));
3098 }
3099
3100 template <class _CharT, class _Traits, class _Allocator>
3101 _LIBCPP_CONSTEXPR_SINCE_CXX20
3102 basic_string<_CharT, _Traits, _Allocator>&
3103 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s)
3104 {
3105     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::replace received nullptr");
3106     return replace(__pos, __n1, __s, traits_type::length(__s));
3107 }
3108
3109 // erase
3110
3111 // 'externally instantiated' erase() implementation, called when __n != npos.
3112 // Does not check __pos against size()
3113 template <class _CharT, class _Traits, class _Allocator>
3114 _LIBCPP_CONSTEXPR_SINCE_CXX20
3115 void
3116 basic_string<_CharT, _Traits, _Allocator>::__erase_external_with_move(
3117     size_type __pos, size_type __n)
3118 {
3119     if (__n)
3120     {
3121         size_type __sz = size();
3122         value_type* __p = std::__to_address(__get_pointer());
3123         __n = std::min(__n, __sz - __pos);
3124         size_type __n_move = __sz - __pos - __n;
3125         if (__n_move != 0)
3126             traits_type::move(__p + __pos, __p + __pos + __n, __n_move);
3127         __null_terminate_at(__p, __sz - __n);
3128     }
3129 }
3130
3131 template <class _CharT, class _Traits, class _Allocator>
3132 _LIBCPP_CONSTEXPR_SINCE_CXX20
3133 basic_string<_CharT, _Traits, _Allocator>&
3134 basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos,
3135                                                  size_type __n) {
3136   if (__pos > size())
3137     __throw_out_of_range();
3138   if (__n == npos) {
3139     __erase_to_end(__pos);
3140   } else {
3141     __erase_external_with_move(__pos, __n);
3142   }
3143   return *this;
3144 }
3145
3146 template <class _CharT, class _Traits, class _Allocator>
3147 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3148 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3149 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos)
3150 {
3151   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
3152       __pos != end(), "string::erase(iterator) called with a non-dereferenceable iterator");
3153   iterator __b = begin();
3154   size_type __r = static_cast<size_type>(__pos - __b);
3155   erase(__r, 1);
3156   return __b + static_cast<difference_type>(__r);
3157 }
3158
3159 template <class _CharT, class _Traits, class _Allocator>
3160 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3161 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3162 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last)
3163 {
3164   _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "string::erase(first, last) called with invalid range");
3165   iterator __b = begin();
3166   size_type __r = static_cast<size_type>(__first - __b);
3167   erase(__r, static_cast<size_type>(__last - __first));
3168   return __b + static_cast<difference_type>(__r);
3169 }
3170
3171 template <class _CharT, class _Traits, class _Allocator>
3172 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3173 void
3174 basic_string<_CharT, _Traits, _Allocator>::pop_back()
3175 {
3176     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "string::pop_back(): string is already empty");
3177     __erase_to_end(size() - 1);
3178 }
3179
3180 template <class _CharT, class _Traits, class _Allocator>
3181 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3182 void
3183 basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT
3184 {
3185     if (__is_long())
3186     {
3187         traits_type::assign(*__get_long_pointer(), value_type());
3188         __set_long_size(0);
3189     }
3190     else
3191     {
3192         traits_type::assign(*__get_short_pointer(), value_type());
3193         __set_short_size(0);
3194     }
3195 }
3196
3197 template <class _CharT, class _Traits, class _Allocator>
3198 _LIBCPP_CONSTEXPR_SINCE_CXX20
3199 void
3200 basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
3201 {
3202     size_type __sz = size();
3203     if (__n > __sz)
3204         append(__n - __sz, __c);
3205     else
3206         __erase_to_end(__n);
3207 }
3208
3209 template <class _CharT, class _Traits, class _Allocator>
3210 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
3211 basic_string<_CharT, _Traits, _Allocator>::__resize_default_init(size_type __n)
3212 {
3213     size_type __sz = size();
3214     if (__n > __sz) {
3215        __append_default_init(__n - __sz);
3216     } else
3217         __erase_to_end(__n);
3218 }
3219
3220 template <class _CharT, class _Traits, class _Allocator>
3221 _LIBCPP_CONSTEXPR_SINCE_CXX20
3222 void
3223 basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __requested_capacity)
3224 {
3225     if (__requested_capacity > max_size())
3226         __throw_length_error();
3227
3228     // Make sure reserve(n) never shrinks. This is technically only required in C++20
3229     // and later (since P0966R1), however we provide consistent behavior in all Standard
3230     // modes because this function is instantiated in the shared library.
3231     if (__requested_capacity <= capacity())
3232         return;
3233
3234     size_type __target_capacity = std::max(__requested_capacity, size());
3235     __target_capacity = __recommend(__target_capacity);
3236     if (__target_capacity == capacity()) return;
3237
3238     __shrink_or_extend(__target_capacity);
3239 }
3240
3241 template <class _CharT, class _Traits, class _Allocator>
3242 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3243 void
3244 basic_string<_CharT, _Traits, _Allocator>::shrink_to_fit() _NOEXCEPT
3245 {
3246     size_type __target_capacity = __recommend(size());
3247     if (__target_capacity == capacity()) return;
3248
3249     __shrink_or_extend(__target_capacity);
3250 }
3251
3252 template <class _CharT, class _Traits, class _Allocator>
3253 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3254 void
3255 basic_string<_CharT, _Traits, _Allocator>::__shrink_or_extend(size_type __target_capacity)
3256 {
3257     size_type __cap = capacity();
3258     size_type __sz = size();
3259
3260     pointer __new_data, __p;
3261     bool __was_long, __now_long;
3262     if (__fits_in_sso(__target_capacity))
3263     {
3264         __was_long = true;
3265         __now_long = false;
3266         __new_data = __get_short_pointer();
3267         __p = __get_long_pointer();
3268     }
3269     else
3270     {
3271         if (__target_capacity > __cap) {
3272             auto __allocation = std::__allocate_at_least(__alloc(), __target_capacity + 1);
3273             __new_data = __allocation.ptr;
3274             __target_capacity = __allocation.count - 1;
3275         }
3276         else
3277         {
3278         #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
3279             try
3280             {
3281         #endif // _LIBCPP_HAS_NO_EXCEPTIONS
3282                 auto __allocation = std::__allocate_at_least(__alloc(), __target_capacity + 1);
3283                 __new_data = __allocation.ptr;
3284                 __target_capacity = __allocation.count - 1;
3285         #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
3286             }
3287             catch (...)
3288             {
3289                 return;
3290             }
3291         #else  // _LIBCPP_HAS_NO_EXCEPTIONS
3292             if (__new_data == nullptr)
3293                 return;
3294         #endif // _LIBCPP_HAS_NO_EXCEPTIONS
3295         }
3296         __begin_lifetime(__new_data, __target_capacity + 1);
3297         __now_long = true;
3298         __was_long = __is_long();
3299         __p = __get_pointer();
3300     }
3301     traits_type::copy(std::__to_address(__new_data),
3302                       std::__to_address(__p), size()+1);
3303     if (__was_long)
3304         __alloc_traits::deallocate(__alloc(), __p, __cap+1);
3305     if (__now_long)
3306     {
3307         __set_long_cap(__target_capacity+1);
3308         __set_long_size(__sz);
3309         __set_long_pointer(__new_data);
3310     }
3311     else
3312         __set_short_size(__sz);
3313 }
3314
3315 template <class _CharT, class _Traits, class _Allocator>
3316 _LIBCPP_CONSTEXPR_SINCE_CXX20
3317 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3318 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const
3319 {
3320     if (__n >= size())
3321         __throw_out_of_range();
3322     return (*this)[__n];
3323 }
3324
3325 template <class _CharT, class _Traits, class _Allocator>
3326 _LIBCPP_CONSTEXPR_SINCE_CXX20
3327 typename basic_string<_CharT, _Traits, _Allocator>::reference
3328 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n)
3329 {
3330     if (__n >= size())
3331         __throw_out_of_range();
3332     return (*this)[__n];
3333 }
3334
3335 template <class _CharT, class _Traits, class _Allocator>
3336 _LIBCPP_CONSTEXPR_SINCE_CXX20
3337 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3338 basic_string<_CharT, _Traits, _Allocator>::copy(value_type* __s, size_type __n, size_type __pos) const
3339 {
3340     size_type __sz = size();
3341     if (__pos > __sz)
3342         __throw_out_of_range();
3343     size_type __rlen = std::min(__n, __sz - __pos);
3344     traits_type::copy(__s, data() + __pos, __rlen);
3345     return __rlen;
3346 }
3347
3348 template <class _CharT, class _Traits, class _Allocator>
3349 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3350 void
3351 basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str)
3352 #if _LIBCPP_STD_VER >= 14
3353         _NOEXCEPT
3354 #else
3355         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3356                     __is_nothrow_swappable<allocator_type>::value)
3357 #endif
3358 {
3359     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
3360         __alloc_traits::propagate_on_container_swap::value ||
3361         __alloc_traits::is_always_equal::value ||
3362         __alloc() == __str.__alloc(), "swapping non-equal allocators");
3363     std::swap(__r_.first(), __str.__r_.first());
3364     std::__swap_allocator(__alloc(), __str.__alloc());
3365 }
3366
3367 // find
3368
3369 template <class _Traits>
3370 struct _LIBCPP_HIDDEN __traits_eq
3371 {
3372     typedef typename _Traits::char_type char_type;
3373     _LIBCPP_HIDE_FROM_ABI
3374     bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT
3375         {return _Traits::eq(__x, __y);}
3376 };
3377
3378 template<class _CharT, class _Traits, class _Allocator>
3379 _LIBCPP_CONSTEXPR_SINCE_CXX20
3380 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3381 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3382                                                 size_type __pos,
3383                                                 size_type __n) const _NOEXCEPT
3384 {
3385     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::find(): received nullptr");
3386     return std::__str_find<value_type, size_type, traits_type, npos>
3387         (data(), size(), __s, __pos, __n);
3388 }
3389
3390 template<class _CharT, class _Traits, class _Allocator>
3391 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3392 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3393 basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str,
3394                                                 size_type __pos) const _NOEXCEPT
3395 {
3396     return std::__str_find<value_type, size_type, traits_type, npos>
3397         (data(), size(), __str.data(), __pos, __str.size());
3398 }
3399
3400 template<class _CharT, class _Traits, class _Allocator>
3401 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3402 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3403 basic_string<_CharT, _Traits, _Allocator>::find(const _Tp &__t,
3404                                                 size_type __pos) const _NOEXCEPT
3405 {
3406     __self_view __sv = __t;
3407     return std::__str_find<value_type, size_type, traits_type, npos>
3408         (data(), size(), __sv.data(), __pos, __sv.size());
3409 }
3410
3411 template<class _CharT, class _Traits, class _Allocator>
3412 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3413 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3414 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3415                                                 size_type __pos) const _NOEXCEPT
3416 {
3417     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::find(): received nullptr");
3418     return std::__str_find<value_type, size_type, traits_type, npos>
3419         (data(), size(), __s, __pos, traits_type::length(__s));
3420 }
3421
3422 template<class _CharT, class _Traits, class _Allocator>
3423 _LIBCPP_CONSTEXPR_SINCE_CXX20
3424 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3425 basic_string<_CharT, _Traits, _Allocator>::find(value_type __c,
3426                                                 size_type __pos) const _NOEXCEPT
3427 {
3428     return std::__str_find<value_type, size_type, traits_type, npos>
3429         (data(), size(), __c, __pos);
3430 }
3431
3432 // rfind
3433
3434 template<class _CharT, class _Traits, class _Allocator>
3435 _LIBCPP_CONSTEXPR_SINCE_CXX20
3436 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3437 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3438                                                  size_type __pos,
3439                                                  size_type __n) const _NOEXCEPT
3440 {
3441     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::rfind(): received nullptr");
3442     return std::__str_rfind<value_type, size_type, traits_type, npos>
3443         (data(), size(), __s, __pos, __n);
3444 }
3445
3446 template<class _CharT, class _Traits, class _Allocator>
3447 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3448 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3449 basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str,
3450                                                  size_type __pos) const _NOEXCEPT
3451 {
3452     return std::__str_rfind<value_type, size_type, traits_type, npos>
3453         (data(), size(), __str.data(), __pos, __str.size());
3454 }
3455
3456 template<class _CharT, class _Traits, class _Allocator>
3457 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3458 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3459 basic_string<_CharT, _Traits, _Allocator>::rfind(const _Tp& __t,
3460                                                 size_type __pos) const _NOEXCEPT
3461 {
3462     __self_view __sv = __t;
3463     return std::__str_rfind<value_type, size_type, traits_type, npos>
3464         (data(), size(), __sv.data(), __pos, __sv.size());
3465 }
3466
3467 template<class _CharT, class _Traits, class _Allocator>
3468 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3469 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3470 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3471                                                  size_type __pos) const _NOEXCEPT
3472 {
3473     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::rfind(): received nullptr");
3474     return std::__str_rfind<value_type, size_type, traits_type, npos>
3475         (data(), size(), __s, __pos, traits_type::length(__s));
3476 }
3477
3478 template<class _CharT, class _Traits, class _Allocator>
3479 _LIBCPP_CONSTEXPR_SINCE_CXX20
3480 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3481 basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c,
3482                                                  size_type __pos) const _NOEXCEPT
3483 {
3484     return std::__str_rfind<value_type, size_type, traits_type, npos>
3485         (data(), size(), __c, __pos);
3486 }
3487
3488 // find_first_of
3489
3490 template<class _CharT, class _Traits, class _Allocator>
3491 _LIBCPP_CONSTEXPR_SINCE_CXX20
3492 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3493 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3494                                                          size_type __pos,
3495                                                          size_type __n) const _NOEXCEPT
3496 {
3497     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::find_first_of(): received nullptr");
3498     return std::__str_find_first_of<value_type, size_type, traits_type, npos>
3499         (data(), size(), __s, __pos, __n);
3500 }
3501
3502 template<class _CharT, class _Traits, class _Allocator>
3503 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3504 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3505 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str,
3506                                                          size_type __pos) const _NOEXCEPT
3507 {
3508     return std::__str_find_first_of<value_type, size_type, traits_type, npos>
3509         (data(), size(), __str.data(), __pos, __str.size());
3510 }
3511
3512 template<class _CharT, class _Traits, class _Allocator>
3513 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3514 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3515 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const _Tp& __t,
3516                                                 size_type __pos) const _NOEXCEPT
3517 {
3518     __self_view __sv = __t;
3519     return std::__str_find_first_of<value_type, size_type, traits_type, npos>
3520         (data(), size(), __sv.data(), __pos, __sv.size());
3521 }
3522
3523 template<class _CharT, class _Traits, class _Allocator>
3524 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3525 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3526 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3527                                                          size_type __pos) const _NOEXCEPT
3528 {
3529     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::find_first_of(): received nullptr");
3530     return std::__str_find_first_of<value_type, size_type, traits_type, npos>
3531         (data(), size(), __s, __pos, traits_type::length(__s));
3532 }
3533
3534 template<class _CharT, class _Traits, class _Allocator>
3535 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3536 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3537 basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c,
3538                                                          size_type __pos) const _NOEXCEPT
3539 {
3540     return find(__c, __pos);
3541 }
3542
3543 // find_last_of
3544
3545 template<class _CharT, class _Traits, class _Allocator>
3546 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3547 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3548 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3549                                                         size_type __pos,
3550                                                         size_type __n) const _NOEXCEPT
3551 {
3552     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::find_last_of(): received nullptr");
3553     return std::__str_find_last_of<value_type, size_type, traits_type, npos>
3554         (data(), size(), __s, __pos, __n);
3555 }
3556
3557 template<class _CharT, class _Traits, class _Allocator>
3558 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3559 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3560 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str,
3561                                                         size_type __pos) const _NOEXCEPT
3562 {
3563     return std::__str_find_last_of<value_type, size_type, traits_type, npos>
3564         (data(), size(), __str.data(), __pos, __str.size());
3565 }
3566
3567 template<class _CharT, class _Traits, class _Allocator>
3568 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3569 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3570 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const _Tp& __t,
3571                                                 size_type __pos) const _NOEXCEPT
3572 {
3573     __self_view __sv = __t;
3574     return std::__str_find_last_of<value_type, size_type, traits_type, npos>
3575         (data(), size(), __sv.data(), __pos, __sv.size());
3576 }
3577
3578 template<class _CharT, class _Traits, class _Allocator>
3579 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3580 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3581 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3582                                                         size_type __pos) const _NOEXCEPT
3583 {
3584     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::find_last_of(): received nullptr");
3585     return std::__str_find_last_of<value_type, size_type, traits_type, npos>
3586         (data(), size(), __s, __pos, traits_type::length(__s));
3587 }
3588
3589 template<class _CharT, class _Traits, class _Allocator>
3590 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3591 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3592 basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c,
3593                                                         size_type __pos) const _NOEXCEPT
3594 {
3595     return rfind(__c, __pos);
3596 }
3597
3598 // find_first_not_of
3599
3600 template<class _CharT, class _Traits, class _Allocator>
3601 _LIBCPP_CONSTEXPR_SINCE_CXX20
3602 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3603 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3604                                                              size_type __pos,
3605                                                              size_type __n) const _NOEXCEPT
3606 {
3607     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::find_first_not_of(): received nullptr");
3608     return std::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3609         (data(), size(), __s, __pos, __n);
3610 }
3611
3612 template<class _CharT, class _Traits, class _Allocator>
3613 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3614 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3615 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str,
3616                                                              size_type __pos) const _NOEXCEPT
3617 {
3618     return std::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3619         (data(), size(), __str.data(), __pos, __str.size());
3620 }
3621
3622 template<class _CharT, class _Traits, class _Allocator>
3623 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3624 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3625 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const _Tp& __t,
3626                                                 size_type __pos) const _NOEXCEPT
3627 {
3628     __self_view __sv = __t;
3629     return std::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3630         (data(), size(), __sv.data(), __pos, __sv.size());
3631 }
3632
3633 template<class _CharT, class _Traits, class _Allocator>
3634 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3635 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3636 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3637                                                              size_type __pos) const _NOEXCEPT
3638 {
3639     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::find_first_not_of(): received nullptr");
3640     return std::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3641         (data(), size(), __s, __pos, traits_type::length(__s));
3642 }
3643
3644 template<class _CharT, class _Traits, class _Allocator>
3645 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3646 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3647 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c,
3648                                                              size_type __pos) const _NOEXCEPT
3649 {
3650     return std::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3651         (data(), size(), __c, __pos);
3652 }
3653
3654 // find_last_not_of
3655
3656 template<class _CharT, class _Traits, class _Allocator>
3657 _LIBCPP_CONSTEXPR_SINCE_CXX20
3658 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3659 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3660                                                             size_type __pos,
3661                                                             size_type __n) const _NOEXCEPT
3662 {
3663     _LIBCPP_ASSERT_UNCATEGORIZED(__n == 0 || __s != nullptr, "string::find_last_not_of(): received nullptr");
3664     return std::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3665         (data(), size(), __s, __pos, __n);
3666 }
3667
3668 template<class _CharT, class _Traits, class _Allocator>
3669 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3670 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3671 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str,
3672                                                             size_type __pos) const _NOEXCEPT
3673 {
3674     return std::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3675         (data(), size(), __str.data(), __pos, __str.size());
3676 }
3677
3678 template<class _CharT, class _Traits, class _Allocator>
3679 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3680 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3681 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const _Tp& __t,
3682                                                 size_type __pos) const _NOEXCEPT
3683 {
3684     __self_view __sv = __t;
3685     return std::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3686         (data(), size(), __sv.data(), __pos, __sv.size());
3687 }
3688
3689 template<class _CharT, class _Traits, class _Allocator>
3690 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3691 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3692 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3693                                                             size_type __pos) const _NOEXCEPT
3694 {
3695     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::find_last_not_of(): received nullptr");
3696     return std::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3697         (data(), size(), __s, __pos, traits_type::length(__s));
3698 }
3699
3700 template<class _CharT, class _Traits, class _Allocator>
3701 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3702 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3703 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c,
3704                                                             size_type __pos) const _NOEXCEPT
3705 {
3706     return std::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3707         (data(), size(), __c, __pos);
3708 }
3709
3710 // compare
3711
3712 template <class _CharT, class _Traits, class _Allocator>
3713 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3714 _LIBCPP_CONSTEXPR_SINCE_CXX20 int
3715 basic_string<_CharT, _Traits, _Allocator>::compare(const _Tp& __t) const _NOEXCEPT
3716 {
3717     __self_view __sv = __t;
3718     size_t __lhs_sz = size();
3719     size_t __rhs_sz = __sv.size();
3720     int __result = traits_type::compare(data(), __sv.data(),
3721                                         std::min(__lhs_sz, __rhs_sz));
3722     if (__result != 0)
3723         return __result;
3724     if (__lhs_sz < __rhs_sz)
3725         return -1;
3726     if (__lhs_sz > __rhs_sz)
3727         return 1;
3728     return 0;
3729 }
3730
3731 template <class _CharT, class _Traits, class _Allocator>
3732 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3733 int
3734 basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT
3735 {
3736     return compare(__self_view(__str));
3737 }
3738
3739 template <class _CharT, class _Traits, class _Allocator>
3740 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3741 int
3742 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3743                                                    size_type __n1,
3744                                                    const value_type* __s,
3745                                                    size_type __n2) const
3746 {
3747     _LIBCPP_ASSERT_UNCATEGORIZED(__n2 == 0 || __s != nullptr, "string::compare(): received nullptr");
3748     size_type __sz = size();
3749     if (__pos1 > __sz || __n2 == npos)
3750         __throw_out_of_range();
3751     size_type __rlen = std::min(__n1, __sz - __pos1);
3752     int __r = traits_type::compare(data() + __pos1, __s, std::min(__rlen, __n2));
3753     if (__r == 0)
3754     {
3755         if (__rlen < __n2)
3756             __r = -1;
3757         else if (__rlen > __n2)
3758             __r = 1;
3759     }
3760     return __r;
3761 }
3762
3763 template <class _CharT, class _Traits, class _Allocator>
3764 template <class _Tp, __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value, int> >
3765 _LIBCPP_CONSTEXPR_SINCE_CXX20 int
3766 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3767                                                    size_type __n1,
3768                                                    const _Tp& __t) const
3769 {
3770     __self_view __sv = __t;
3771     return compare(__pos1, __n1, __sv.data(), __sv.size());
3772 }
3773
3774 template <class _CharT, class _Traits, class _Allocator>
3775 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3776 int
3777 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3778                                                    size_type __n1,
3779                                                    const basic_string& __str) const
3780 {
3781     return compare(__pos1, __n1, __str.data(), __str.size());
3782 }
3783
3784 template <class _CharT, class _Traits, class _Allocator>
3785 template <class _Tp,
3786           __enable_if_t<__can_be_converted_to_string_view<_CharT, _Traits, _Tp>::value &&
3787                             !__is_same_uncvref<_Tp, basic_string<_CharT, _Traits, _Allocator> >::value,
3788                         int> >
3789 _LIBCPP_CONSTEXPR_SINCE_CXX20 int basic_string<_CharT, _Traits, _Allocator>::compare(
3790     size_type __pos1, size_type __n1, const _Tp& __t, size_type __pos2, size_type __n2) const {
3791     __self_view __sv = __t;
3792     return __self_view(*this).substr(__pos1, __n1).compare(__sv.substr(__pos2, __n2));
3793 }
3794
3795 template <class _CharT, class _Traits, class _Allocator>
3796 _LIBCPP_CONSTEXPR_SINCE_CXX20
3797 int
3798 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3799                                                    size_type __n1,
3800                                                    const basic_string& __str,
3801                                                    size_type __pos2,
3802                                                    size_type __n2) const
3803 {
3804     return compare(__pos1, __n1, __self_view(__str), __pos2, __n2);
3805 }
3806
3807 template <class _CharT, class _Traits, class _Allocator>
3808 _LIBCPP_CONSTEXPR_SINCE_CXX20
3809 int
3810 basic_string<_CharT, _Traits, _Allocator>::compare(const value_type* __s) const _NOEXCEPT
3811 {
3812     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::compare(): received nullptr");
3813     return compare(0, npos, __s, traits_type::length(__s));
3814 }
3815
3816 template <class _CharT, class _Traits, class _Allocator>
3817 _LIBCPP_CONSTEXPR_SINCE_CXX20
3818 int
3819 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3820                                                    size_type __n1,
3821                                                    const value_type* __s) const
3822 {
3823     _LIBCPP_ASSERT_UNCATEGORIZED(__s != nullptr, "string::compare(): received nullptr");
3824     return compare(__pos1, __n1, __s, traits_type::length(__s));
3825 }
3826
3827 // __invariants
3828
3829 template<class _CharT, class _Traits, class _Allocator>
3830 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3831 bool
3832 basic_string<_CharT, _Traits, _Allocator>::__invariants() const
3833 {
3834     if (size() > capacity())
3835         return false;
3836     if (capacity() < __min_cap - 1)
3837         return false;
3838     if (data() == nullptr)
3839         return false;
3840     if (!_Traits::eq(data()[size()], value_type()))
3841         return false;
3842     return true;
3843 }
3844
3845 // __clear_and_shrink
3846
3847 template<class _CharT, class _Traits, class _Allocator>
3848 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
3849 void
3850 basic_string<_CharT, _Traits, _Allocator>::__clear_and_shrink() _NOEXCEPT
3851 {
3852     clear();
3853     if(__is_long())
3854     {
3855         __alloc_traits::deallocate(__alloc(), __get_long_pointer(), capacity() + 1);
3856         __r_.first() = __rep();
3857     }
3858 }
3859
3860 // operator==
3861
3862 template<class _CharT, class _Traits, class _Allocator>
3863 inline _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
3864 bool
3865 operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3866            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3867 {
3868 #if _LIBCPP_STD_VER >= 20
3869     return basic_string_view<_CharT, _Traits>(__lhs) == basic_string_view<_CharT, _Traits>(__rhs);
3870 #else
3871     size_t __lhs_sz = __lhs.size();
3872     return __lhs_sz == __rhs.size() && _Traits::compare(__lhs.data(),
3873                                                         __rhs.data(),
3874                                                         __lhs_sz) == 0;
3875 #endif
3876 }
3877
3878 template<class _Allocator>
3879 inline _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
3880 bool
3881 operator==(const basic_string<char, char_traits<char>, _Allocator>& __lhs,
3882            const basic_string<char, char_traits<char>, _Allocator>& __rhs) _NOEXCEPT
3883 {
3884     size_t __lhs_sz = __lhs.size();
3885     if (__lhs_sz != __rhs.size())
3886         return false;
3887     const char* __lp = __lhs.data();
3888     const char* __rp = __rhs.data();
3889     if (__lhs.__is_long())
3890         return char_traits<char>::compare(__lp, __rp, __lhs_sz) == 0;
3891     for (; __lhs_sz != 0; --__lhs_sz, ++__lp, ++__rp)
3892         if (*__lp != *__rp)
3893             return false;
3894     return true;
3895 }
3896
3897 #if _LIBCPP_STD_VER <= 17
3898 template<class _CharT, class _Traits, class _Allocator>
3899 inline _LIBCPP_HIDE_FROM_ABI
3900 bool
3901 operator==(const _CharT* __lhs,
3902            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3903 {
3904     typedef basic_string<_CharT, _Traits, _Allocator> _String;
3905     _LIBCPP_ASSERT_UNCATEGORIZED(__lhs != nullptr, "operator==(char*, basic_string): received nullptr");
3906     size_t __lhs_len = _Traits::length(__lhs);
3907     if (__lhs_len != __rhs.size()) return false;
3908     return __rhs.compare(0, _String::npos, __lhs, __lhs_len) == 0;
3909 }
3910 #endif // _LIBCPP_STD_VER <= 17
3911
3912 template<class _CharT, class _Traits, class _Allocator>
3913 inline _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
3914 bool
3915 operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3916            const _CharT* __rhs) _NOEXCEPT
3917 {
3918 #if _LIBCPP_STD_VER >= 20
3919     return basic_string_view<_CharT, _Traits>(__lhs) == basic_string_view<_CharT, _Traits>(__rhs);
3920 #else
3921     typedef basic_string<_CharT, _Traits, _Allocator> _String;
3922     _LIBCPP_ASSERT_UNCATEGORIZED(__rhs != nullptr, "operator==(basic_string, char*): received nullptr");
3923     size_t __rhs_len = _Traits::length(__rhs);
3924     if (__rhs_len != __lhs.size()) return false;
3925     return __lhs.compare(0, _String::npos, __rhs, __rhs_len) == 0;
3926 #endif
3927 }
3928
3929 #if _LIBCPP_STD_VER >= 20
3930
3931 template <class _CharT, class _Traits, class _Allocator>
3932 _LIBCPP_HIDE_FROM_ABI constexpr auto operator<=>(
3933     const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3934     const basic_string<_CharT, _Traits, _Allocator>& __rhs) noexcept {
3935     return basic_string_view<_CharT, _Traits>(__lhs) <=> basic_string_view<_CharT, _Traits>(__rhs);
3936 }
3937
3938 template <class _CharT, class _Traits, class _Allocator>
3939 _LIBCPP_HIDE_FROM_ABI constexpr auto
3940 operator<=>(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs) {
3941     return basic_string_view<_CharT, _Traits>(__lhs) <=> basic_string_view<_CharT, _Traits>(__rhs);
3942 }
3943
3944 #else // _LIBCPP_STD_VER >= 20
3945
3946 template<class _CharT, class _Traits, class _Allocator>
3947 inline _LIBCPP_HIDE_FROM_ABI
3948 bool
3949 operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3950            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3951 {
3952     return !(__lhs == __rhs);
3953 }
3954
3955 template<class _CharT, class _Traits, class _Allocator>
3956 inline _LIBCPP_HIDE_FROM_ABI
3957 bool
3958 operator!=(const _CharT* __lhs,
3959            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3960 {
3961     return !(__lhs == __rhs);
3962 }
3963
3964 template<class _CharT, class _Traits, class _Allocator>
3965 inline _LIBCPP_HIDE_FROM_ABI
3966 bool
3967 operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3968            const _CharT* __rhs) _NOEXCEPT
3969 {
3970     return !(__lhs == __rhs);
3971 }
3972
3973 // operator<
3974
3975 template<class _CharT, class _Traits, class _Allocator>
3976 inline _LIBCPP_HIDE_FROM_ABI
3977 bool
3978 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3979            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3980 {
3981     return __lhs.compare(__rhs) < 0;
3982 }
3983
3984 template<class _CharT, class _Traits, class _Allocator>
3985 inline _LIBCPP_HIDE_FROM_ABI
3986 bool
3987 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3988            const _CharT* __rhs) _NOEXCEPT
3989 {
3990     return __lhs.compare(__rhs) < 0;
3991 }
3992
3993 template<class _CharT, class _Traits, class _Allocator>
3994 inline _LIBCPP_HIDE_FROM_ABI
3995 bool
3996 operator< (const _CharT* __lhs,
3997            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3998 {
3999     return __rhs.compare(__lhs) > 0;
4000 }
4001
4002 // operator>
4003
4004 template<class _CharT, class _Traits, class _Allocator>
4005 inline _LIBCPP_HIDE_FROM_ABI
4006 bool
4007 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4008            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4009 {
4010     return __rhs < __lhs;
4011 }
4012
4013 template<class _CharT, class _Traits, class _Allocator>
4014 inline _LIBCPP_HIDE_FROM_ABI
4015 bool
4016 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4017            const _CharT* __rhs) _NOEXCEPT
4018 {
4019     return __rhs < __lhs;
4020 }
4021
4022 template<class _CharT, class _Traits, class _Allocator>
4023 inline _LIBCPP_HIDE_FROM_ABI
4024 bool
4025 operator> (const _CharT* __lhs,
4026            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4027 {
4028     return __rhs < __lhs;
4029 }
4030
4031 // operator<=
4032
4033 template<class _CharT, class _Traits, class _Allocator>
4034 inline _LIBCPP_HIDE_FROM_ABI
4035 bool
4036 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4037            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4038 {
4039     return !(__rhs < __lhs);
4040 }
4041
4042 template<class _CharT, class _Traits, class _Allocator>
4043 inline _LIBCPP_HIDE_FROM_ABI
4044 bool
4045 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4046            const _CharT* __rhs) _NOEXCEPT
4047 {
4048     return !(__rhs < __lhs);
4049 }
4050
4051 template<class _CharT, class _Traits, class _Allocator>
4052 inline _LIBCPP_HIDE_FROM_ABI
4053 bool
4054 operator<=(const _CharT* __lhs,
4055            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4056 {
4057     return !(__rhs < __lhs);
4058 }
4059
4060 // operator>=
4061
4062 template<class _CharT, class _Traits, class _Allocator>
4063 inline _LIBCPP_HIDE_FROM_ABI
4064 bool
4065 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4066            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4067 {
4068     return !(__lhs < __rhs);
4069 }
4070
4071 template<class _CharT, class _Traits, class _Allocator>
4072 inline _LIBCPP_HIDE_FROM_ABI
4073 bool
4074 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4075            const _CharT* __rhs) _NOEXCEPT
4076 {
4077     return !(__lhs < __rhs);
4078 }
4079
4080 template<class _CharT, class _Traits, class _Allocator>
4081 inline _LIBCPP_HIDE_FROM_ABI
4082 bool
4083 operator>=(const _CharT* __lhs,
4084            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
4085 {
4086     return !(__lhs < __rhs);
4087 }
4088 #endif // _LIBCPP_STD_VER >= 20
4089
4090 // operator +
4091
4092 template<class _CharT, class _Traits, class _Allocator>
4093 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4094 basic_string<_CharT, _Traits, _Allocator>
4095 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
4096           const basic_string<_CharT, _Traits, _Allocator>& __rhs)
4097 {
4098     using _String = basic_string<_CharT, _Traits, _Allocator>;
4099     auto __lhs_sz = __lhs.size();
4100     auto __rhs_sz = __rhs.size();
4101     _String __r(__uninitialized_size_tag(),
4102                 __lhs_sz + __rhs_sz,
4103                 _String::__alloc_traits::select_on_container_copy_construction(__lhs.get_allocator()));
4104     auto __ptr = std::__to_address(__r.__get_pointer());
4105     _Traits::copy(__ptr, __lhs.data(), __lhs_sz);
4106     _Traits::copy(__ptr + __lhs_sz, __rhs.data(), __rhs_sz);
4107     _Traits::assign(__ptr + __lhs_sz + __rhs_sz, 1, _CharT());
4108     return __r;
4109 }
4110
4111 template<class _CharT, class _Traits, class _Allocator>
4112 _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR_SINCE_CXX20
4113 basic_string<_CharT, _Traits, _Allocator>
4114 operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs)
4115 {
4116     using _String = basic_string<_CharT, _Traits, _Allocator>;
4117     auto __lhs_sz = _Traits::length(__lhs);
4118     auto __rhs_sz = __rhs.size();
4119     _String __r(__uninitialized_size_tag(),
4120                 __lhs_sz + __rhs_sz,
4121                 _String::__alloc_traits::select_on_container_copy_construction(__rhs.get_allocator()));
4122     auto __ptr = std::__to_address(__r.__get_pointer());
4123     _Traits::copy(__ptr, __lhs, __lhs_sz);
4124     _Traits::copy(__ptr + __lhs_sz, __rhs.data(), __rhs_sz);
4125     _Traits::assign(__ptr + __lhs_sz + __rhs_sz, 1, _CharT());
4126     return __r;
4127 }
4128
4129 template<class _CharT, class _Traits, class _Allocator>
4130 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4131 basic_string<_CharT, _Traits, _Allocator>
4132 operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs)
4133 {
4134     using _String = basic_string<_CharT, _Traits, _Allocator>;
4135     typename _String::size_type __rhs_sz = __rhs.size();
4136     _String __r(__uninitialized_size_tag(),
4137                 __rhs_sz + 1,
4138                 _String::__alloc_traits::select_on_container_copy_construction(__rhs.get_allocator()));
4139     auto __ptr = std::__to_address(__r.__get_pointer());
4140     _Traits::assign(__ptr, 1, __lhs);
4141     _Traits::copy(__ptr + 1, __rhs.data(), __rhs_sz);
4142     _Traits::assign(__ptr + 1 + __rhs_sz, 1, _CharT());
4143     return __r;
4144 }
4145
4146 template<class _CharT, class _Traits, class _Allocator>
4147 inline _LIBCPP_CONSTEXPR_SINCE_CXX20
4148 basic_string<_CharT, _Traits, _Allocator>
4149 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs)
4150 {
4151     using _String = basic_string<_CharT, _Traits, _Allocator>;
4152     typename _String::size_type __lhs_sz = __lhs.size();
4153     typename _String::size_type __rhs_sz = _Traits::length(__rhs);
4154     _String __r(__uninitialized_size_tag(),
4155                 __lhs_sz + __rhs_sz,
4156                 _String::__alloc_traits::select_on_container_copy_construction(__lhs.get_allocator()));
4157     auto __ptr = std::__to_address(__r.__get_pointer());
4158     _Traits::copy(__ptr, __lhs.data(), __lhs_sz);
4159     _Traits::copy(__ptr + __lhs_sz, __rhs, __rhs_sz);
4160     _Traits::assign(__ptr + __lhs_sz + __rhs_sz, 1, _CharT());
4161     return __r;
4162 }
4163
4164 template<class _CharT, class _Traits, class _Allocator>
4165 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4166 basic_string<_CharT, _Traits, _Allocator>
4167 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs)
4168 {
4169     using _String = basic_string<_CharT, _Traits, _Allocator>;
4170     typename _String::size_type __lhs_sz = __lhs.size();
4171     _String __r(__uninitialized_size_tag(),
4172                 __lhs_sz + 1,
4173                 _String::__alloc_traits::select_on_container_copy_construction(__lhs.get_allocator()));
4174     auto __ptr = std::__to_address(__r.__get_pointer());
4175     _Traits::copy(__ptr, __lhs.data(), __lhs_sz);
4176     _Traits::assign(__ptr + __lhs_sz, 1, __rhs);
4177     _Traits::assign(__ptr + 1 + __lhs_sz, 1, _CharT());
4178     return __r;
4179 }
4180
4181 #ifndef _LIBCPP_CXX03_LANG
4182
4183 template<class _CharT, class _Traits, class _Allocator>
4184 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4185 basic_string<_CharT, _Traits, _Allocator>
4186 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs)
4187 {
4188     return std::move(__lhs.append(__rhs));
4189 }
4190
4191 template<class _CharT, class _Traits, class _Allocator>
4192 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4193 basic_string<_CharT, _Traits, _Allocator>
4194 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4195 {
4196     return std::move(__rhs.insert(0, __lhs));
4197 }
4198
4199 template<class _CharT, class _Traits, class _Allocator>
4200 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4201 basic_string<_CharT, _Traits, _Allocator>
4202 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4203 {
4204     return std::move(__lhs.append(__rhs));
4205 }
4206
4207 template<class _CharT, class _Traits, class _Allocator>
4208 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4209 basic_string<_CharT, _Traits, _Allocator>
4210 operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4211 {
4212     return std::move(__rhs.insert(0, __lhs));
4213 }
4214
4215 template<class _CharT, class _Traits, class _Allocator>
4216 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4217 basic_string<_CharT, _Traits, _Allocator>
4218 operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4219 {
4220     __rhs.insert(__rhs.begin(), __lhs);
4221     return std::move(__rhs);
4222 }
4223
4224 template<class _CharT, class _Traits, class _Allocator>
4225 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4226 basic_string<_CharT, _Traits, _Allocator>
4227 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const _CharT* __rhs)
4228 {
4229     return std::move(__lhs.append(__rhs));
4230 }
4231
4232 template<class _CharT, class _Traits, class _Allocator>
4233 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4234 basic_string<_CharT, _Traits, _Allocator>
4235 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs)
4236 {
4237     __lhs.push_back(__rhs);
4238     return std::move(__lhs);
4239 }
4240
4241 #endif // _LIBCPP_CXX03_LANG
4242
4243 // swap
4244
4245 template<class _CharT, class _Traits, class _Allocator>
4246 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4247 void
4248 swap(basic_string<_CharT, _Traits, _Allocator>& __lhs,
4249      basic_string<_CharT, _Traits, _Allocator>& __rhs)
4250      _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs)))
4251 {
4252     __lhs.swap(__rhs);
4253 }
4254
4255 _LIBCPP_EXPORTED_FROM_ABI int                stoi  (const string& __str, size_t* __idx = nullptr, int __base = 10);
4256 _LIBCPP_EXPORTED_FROM_ABI long               stol  (const string& __str, size_t* __idx = nullptr, int __base = 10);
4257 _LIBCPP_EXPORTED_FROM_ABI unsigned long      stoul (const string& __str, size_t* __idx = nullptr, int __base = 10);
4258 _LIBCPP_EXPORTED_FROM_ABI long long          stoll (const string& __str, size_t* __idx = nullptr, int __base = 10);
4259 _LIBCPP_EXPORTED_FROM_ABI unsigned long long stoull(const string& __str, size_t* __idx = nullptr, int __base = 10);
4260
4261 _LIBCPP_EXPORTED_FROM_ABI float       stof (const string& __str, size_t* __idx = nullptr);
4262 _LIBCPP_EXPORTED_FROM_ABI double      stod (const string& __str, size_t* __idx = nullptr);
4263 _LIBCPP_EXPORTED_FROM_ABI long double stold(const string& __str, size_t* __idx = nullptr);
4264
4265 _LIBCPP_EXPORTED_FROM_ABI string to_string(int __val);
4266 _LIBCPP_EXPORTED_FROM_ABI string to_string(unsigned __val);
4267 _LIBCPP_EXPORTED_FROM_ABI string to_string(long __val);
4268 _LIBCPP_EXPORTED_FROM_ABI string to_string(unsigned long __val);
4269 _LIBCPP_EXPORTED_FROM_ABI string to_string(long long __val);
4270 _LIBCPP_EXPORTED_FROM_ABI string to_string(unsigned long long __val);
4271 _LIBCPP_EXPORTED_FROM_ABI string to_string(float __val);
4272 _LIBCPP_EXPORTED_FROM_ABI string to_string(double __val);
4273 _LIBCPP_EXPORTED_FROM_ABI string to_string(long double __val);
4274
4275 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
4276 _LIBCPP_EXPORTED_FROM_ABI int                stoi  (const wstring& __str, size_t* __idx = nullptr, int __base = 10);
4277 _LIBCPP_EXPORTED_FROM_ABI long               stol  (const wstring& __str, size_t* __idx = nullptr, int __base = 10);
4278 _LIBCPP_EXPORTED_FROM_ABI unsigned long      stoul (const wstring& __str, size_t* __idx = nullptr, int __base = 10);
4279 _LIBCPP_EXPORTED_FROM_ABI long long          stoll (const wstring& __str, size_t* __idx = nullptr, int __base = 10);
4280 _LIBCPP_EXPORTED_FROM_ABI unsigned long long stoull(const wstring& __str, size_t* __idx = nullptr, int __base = 10);
4281
4282 _LIBCPP_EXPORTED_FROM_ABI float       stof (const wstring& __str, size_t* __idx = nullptr);
4283 _LIBCPP_EXPORTED_FROM_ABI double      stod (const wstring& __str, size_t* __idx = nullptr);
4284 _LIBCPP_EXPORTED_FROM_ABI long double stold(const wstring& __str, size_t* __idx = nullptr);
4285
4286 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(int __val);
4287 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(unsigned __val);
4288 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(long __val);
4289 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(unsigned long __val);
4290 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(long long __val);
4291 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(unsigned long long __val);
4292 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(float __val);
4293 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(double __val);
4294 _LIBCPP_EXPORTED_FROM_ABI wstring to_wstring(long double __val);
4295 #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
4296
4297 template<class _CharT, class _Traits, class _Allocator>
4298 _LIBCPP_TEMPLATE_DATA_VIS
4299 const typename basic_string<_CharT, _Traits, _Allocator>::size_type
4300                basic_string<_CharT, _Traits, _Allocator>::npos;
4301
4302 template <class _CharT, class _Allocator>
4303 struct __string_hash : public __unary_function<basic_string<_CharT, char_traits<_CharT>, _Allocator>, size_t> {
4304     _LIBCPP_HIDE_FROM_ABI size_t
4305     operator()(const basic_string<_CharT, char_traits<_CharT>, _Allocator>& __val) const _NOEXCEPT {
4306         return std::__do_string_hash(__val.data(), __val.data() + __val.size());
4307     }
4308 };
4309
4310 template <class _Allocator>
4311 struct hash<basic_string<char, char_traits<char>, _Allocator> > : __string_hash<char, _Allocator> {};
4312
4313 #ifndef _LIBCPP_HAS_NO_CHAR8_T
4314 template <class _Allocator>
4315 struct hash<basic_string<char8_t, char_traits<char8_t>, _Allocator> > : __string_hash<char8_t, _Allocator> {};
4316 #endif
4317
4318 template <class _Allocator>
4319 struct hash<basic_string<char16_t, char_traits<char16_t>, _Allocator> > : __string_hash<char16_t, _Allocator> {};
4320
4321 template <class _Allocator>
4322 struct hash<basic_string<char32_t, char_traits<char32_t>, _Allocator> > : __string_hash<char32_t, _Allocator> {};
4323
4324 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
4325 template <class _Allocator>
4326 struct hash<basic_string<wchar_t, char_traits<wchar_t>, _Allocator> > : __string_hash<wchar_t, _Allocator> {};
4327 #endif
4328
4329 template<class _CharT, class _Traits, class _Allocator>
4330 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
4331 operator<<(basic_ostream<_CharT, _Traits>& __os,
4332            const basic_string<_CharT, _Traits, _Allocator>& __str);
4333
4334 template<class _CharT, class _Traits, class _Allocator>
4335 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
4336 operator>>(basic_istream<_CharT, _Traits>& __is,
4337            basic_string<_CharT, _Traits, _Allocator>& __str);
4338
4339 template<class _CharT, class _Traits, class _Allocator>
4340 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
4341 getline(basic_istream<_CharT, _Traits>& __is,
4342         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
4343
4344 template<class _CharT, class _Traits, class _Allocator>
4345 inline _LIBCPP_HIDE_FROM_ABI
4346 basic_istream<_CharT, _Traits>&
4347 getline(basic_istream<_CharT, _Traits>& __is,
4348         basic_string<_CharT, _Traits, _Allocator>& __str);
4349
4350 template<class _CharT, class _Traits, class _Allocator>
4351 inline _LIBCPP_HIDE_FROM_ABI
4352 basic_istream<_CharT, _Traits>&
4353 getline(basic_istream<_CharT, _Traits>&& __is,
4354         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
4355
4356 template<class _CharT, class _Traits, class _Allocator>
4357 inline _LIBCPP_HIDE_FROM_ABI
4358 basic_istream<_CharT, _Traits>&
4359 getline(basic_istream<_CharT, _Traits>&& __is,
4360         basic_string<_CharT, _Traits, _Allocator>& __str);
4361
4362 #if _LIBCPP_STD_VER >= 20
4363 template <class _CharT, class _Traits, class _Allocator, class _Up>
4364 inline _LIBCPP_HIDE_FROM_ABI
4365     typename basic_string<_CharT, _Traits, _Allocator>::size_type
4366     erase(basic_string<_CharT, _Traits, _Allocator>& __str, const _Up& __v) {
4367   auto __old_size = __str.size();
4368   __str.erase(std::remove(__str.begin(), __str.end(), __v), __str.end());
4369   return __old_size - __str.size();
4370 }
4371
4372 template <class _CharT, class _Traits, class _Allocator, class _Predicate>
4373 inline _LIBCPP_HIDE_FROM_ABI
4374     typename basic_string<_CharT, _Traits, _Allocator>::size_type
4375     erase_if(basic_string<_CharT, _Traits, _Allocator>& __str,
4376              _Predicate __pred) {
4377   auto __old_size = __str.size();
4378   __str.erase(std::remove_if(__str.begin(), __str.end(), __pred),
4379               __str.end());
4380   return __old_size - __str.size();
4381 }
4382 #endif
4383
4384 #if _LIBCPP_STD_VER >= 14
4385 // Literal suffixes for basic_string [basic.string.literals]
4386 inline namespace literals
4387 {
4388   inline namespace string_literals
4389   {
4390     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4391     basic_string<char> operator""s( const char *__str, size_t __len )
4392     {
4393         return basic_string<char> (__str, __len);
4394     }
4395
4396 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
4397     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4398     basic_string<wchar_t> operator""s( const wchar_t *__str, size_t __len )
4399     {
4400         return basic_string<wchar_t> (__str, __len);
4401     }
4402 #endif
4403
4404 #ifndef _LIBCPP_HAS_NO_CHAR8_T
4405     inline _LIBCPP_HIDE_FROM_ABI constexpr
4406     basic_string<char8_t> operator""s(const char8_t *__str, size_t __len)
4407     {
4408         return basic_string<char8_t> (__str, __len);
4409     }
4410 #endif
4411
4412     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4413     basic_string<char16_t> operator""s( const char16_t *__str, size_t __len )
4414     {
4415         return basic_string<char16_t> (__str, __len);
4416     }
4417
4418     inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
4419     basic_string<char32_t> operator""s( const char32_t *__str, size_t __len )
4420     {
4421         return basic_string<char32_t> (__str, __len);
4422     }
4423   } // namespace string_literals
4424 } // namespace literals
4425
4426 #if _LIBCPP_STD_VER >= 20
4427 template <>
4428 inline constexpr bool __format::__enable_insertable<std::basic_string<char>> = true;
4429 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
4430 template <>
4431 inline constexpr bool __format::__enable_insertable<std::basic_string<wchar_t>> = true;
4432 #endif
4433 #endif
4434
4435 #endif
4436
4437 _LIBCPP_END_NAMESPACE_STD
4438
4439 _LIBCPP_POP_MACROS
4440
4441 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
4442 #  include <algorithm>
4443 #  include <concepts>
4444 #  include <cstdlib>
4445 #  include <iterator>
4446 #  include <new>
4447 #  include <type_traits>
4448 #  include <typeinfo>
4449 #  include <utility>
4450 #endif
4451
4452 #endif // _LIBCPP_STRING