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