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