include/string

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