contrib/libc++/include/string

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