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