libcxx/include/string

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