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