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