contrib/libc++/include/string

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