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