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