libcxx/include/string

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