libcxx/include/string

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