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_ABI_ALTERNATE_STRING_LAYOUT
1205
1206 template <class _CharT, size_t = sizeof(_CharT)>
1207 struct __padding
1208 {
1209     unsigned char __xx[sizeof(_CharT)-1];
1210 };
1211
1212 template <class _CharT>
1213 struct __padding<_CharT, 1>
1214 {
1215 };
1216
1217 #endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1218
1219 template<class _CharT, class _Traits, class _Allocator>
1220 class _LIBCPP_TYPE_VIS_ONLY basic_string
1221     : private __basic_string_common<true>
1222 {
1223 public:
1224     typedef basic_string                                 __self;
1225     typedef _Traits                                      traits_type;
1226     typedef typename traits_type::char_type              value_type;
1227     typedef _Allocator                                   allocator_type;
1228     typedef allocator_traits<allocator_type>             __alloc_traits;
1229     typedef typename __alloc_traits::size_type           size_type;
1230     typedef typename __alloc_traits::difference_type     difference_type;
1231     typedef value_type&                                  reference;
1232     typedef const value_type&                            const_reference;
1233     typedef typename __alloc_traits::pointer             pointer;
1234     typedef typename __alloc_traits::const_pointer       const_pointer;
1235
1236     static_assert(is_pod<value_type>::value, "Character type of basic_string must be a POD");
1237     static_assert((is_same<_CharT, value_type>::value),
1238                   "traits_type::char_type must be the same type as CharT");
1239     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1240                   "Allocator::value_type must be same type as value_type");
1241 #if defined(_LIBCPP_RAW_ITERATORS)
1242     typedef pointer                                      iterator;
1243     typedef const_pointer                                const_iterator;
1244 #else  // defined(_LIBCPP_RAW_ITERATORS)
1245     typedef __wrap_iter<pointer>                         iterator;
1246     typedef __wrap_iter<const_pointer>                   const_iterator;
1247 #endif  // defined(_LIBCPP_RAW_ITERATORS)
1248     typedef _VSTD::reverse_iterator<iterator>             reverse_iterator;
1249     typedef _VSTD::reverse_iterator<const_iterator>       const_reverse_iterator;
1250
1251 private:
1252
1253 #ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1254
1255     struct __long
1256     {
1257         pointer   __data_;
1258         size_type __size_;
1259         size_type __cap_;
1260     };
1261
1262 #if _LIBCPP_BIG_ENDIAN
1263     enum {__short_mask = 0x01};
1264     enum {__long_mask  = 0x1ul};
1265 #else  // _LIBCPP_BIG_ENDIAN
1266     enum {__short_mask = 0x80};
1267     enum {__long_mask  = ~(size_type(~0) >> 1)};
1268 #endif  // _LIBCPP_BIG_ENDIAN
1269
1270     enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
1271                       (sizeof(__long) - 1)/sizeof(value_type) : 2};
1272
1273     struct __short
1274     {
1275         value_type __data_[__min_cap];
1276         struct
1277             : __padding<value_type>
1278         {
1279             unsigned char __size_;
1280         };
1281     };
1282
1283 #else
1284
1285     struct __long
1286     {
1287         size_type __cap_;
1288         size_type __size_;
1289         pointer   __data_;
1290     };
1291
1292 #if _LIBCPP_BIG_ENDIAN
1293     enum {__short_mask = 0x80};
1294     enum {__long_mask  = ~(size_type(~0) >> 1)};
1295 #else  // _LIBCPP_BIG_ENDIAN
1296     enum {__short_mask = 0x01};
1297     enum {__long_mask  = 0x1ul};
1298 #endif  // _LIBCPP_BIG_ENDIAN
1299
1300     enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
1301                       (sizeof(__long) - 1)/sizeof(value_type) : 2};
1302
1303     struct __short
1304     {
1305         union
1306         {
1307             unsigned char __size_;
1308             value_type __lx;
1309         };
1310         value_type __data_[__min_cap];
1311     };
1312
1313 #endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1314
1315     union __ulx{__long __lx; __short __lxx;};
1316
1317     enum {__n_words = sizeof(__ulx) / sizeof(size_type)};
1318
1319     struct __raw
1320     {
1321         size_type __words[__n_words];
1322     };
1323
1324     struct __rep
1325     {
1326         union
1327         {
1328             __long  __l;
1329             __short __s;
1330             __raw   __r;
1331         };
1332     };
1333
1334     __compressed_pair<__rep, allocator_type> __r_;
1335
1336 public:
1337     static const size_type npos = -1;
1338
1339     _LIBCPP_INLINE_VISIBILITY basic_string()
1340         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
1341
1342     _LIBCPP_INLINE_VISIBILITY explicit basic_string(const allocator_type& __a)
1343 #if _LIBCPP_STD_VER <= 14
1344         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
1345 #else
1346         _NOEXCEPT;
1347 #endif
1348
1349     basic_string(const basic_string& __str);
1350     basic_string(const basic_string& __str, const allocator_type& __a);
1351
1352 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1353     _LIBCPP_INLINE_VISIBILITY
1354     basic_string(basic_string&& __str)
1355 #if _LIBCPP_STD_VER <= 14
1356         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
1357 #else
1358         _NOEXCEPT;
1359 #endif
1360
1361     _LIBCPP_INLINE_VISIBILITY
1362     basic_string(basic_string&& __str, const allocator_type& __a);
1363 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1364     _LIBCPP_INLINE_VISIBILITY basic_string(const value_type* __s);
1365     _LIBCPP_INLINE_VISIBILITY
1366     basic_string(const value_type* __s, const allocator_type& __a);
1367     _LIBCPP_INLINE_VISIBILITY
1368     basic_string(const value_type* __s, size_type __n);
1369     _LIBCPP_INLINE_VISIBILITY
1370     basic_string(const value_type* __s, size_type __n, const allocator_type& __a);
1371     _LIBCPP_INLINE_VISIBILITY
1372     basic_string(size_type __n, value_type __c);
1373     _LIBCPP_INLINE_VISIBILITY
1374     basic_string(size_type __n, value_type __c, const allocator_type& __a);
1375     basic_string(const basic_string& __str, size_type __pos, size_type __n = npos,
1376                  const allocator_type& __a = allocator_type());
1377     template<class _InputIterator>
1378         _LIBCPP_INLINE_VISIBILITY
1379         basic_string(_InputIterator __first, _InputIterator __last);
1380     template<class _InputIterator>
1381         _LIBCPP_INLINE_VISIBILITY
1382         basic_string(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
1383 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1384     _LIBCPP_INLINE_VISIBILITY
1385     basic_string(initializer_list<value_type> __il);
1386     _LIBCPP_INLINE_VISIBILITY
1387     basic_string(initializer_list<value_type> __il, const allocator_type& __a);
1388 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1389
1390     ~basic_string();
1391
1392     basic_string& operator=(const basic_string& __str);
1393 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1394     _LIBCPP_INLINE_VISIBILITY
1395     basic_string& operator=(basic_string&& __str)
1396         _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
1397 #endif
1398     _LIBCPP_INLINE_VISIBILITY basic_string& operator=(const value_type* __s) {return assign(__s);}
1399     basic_string& operator=(value_type __c);
1400 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1401     _LIBCPP_INLINE_VISIBILITY
1402     basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1403 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1404
1405 #if _LIBCPP_DEBUG_LEVEL >= 2
1406     _LIBCPP_INLINE_VISIBILITY
1407     iterator begin() _NOEXCEPT
1408         {return iterator(this, __get_pointer());}
1409     _LIBCPP_INLINE_VISIBILITY
1410     const_iterator begin() const _NOEXCEPT
1411         {return const_iterator(this, __get_pointer());}
1412     _LIBCPP_INLINE_VISIBILITY
1413     iterator end() _NOEXCEPT
1414         {return iterator(this, __get_pointer() + size());}
1415     _LIBCPP_INLINE_VISIBILITY
1416     const_iterator end() const _NOEXCEPT
1417         {return const_iterator(this, __get_pointer() + size());}
1418 #else
1419     _LIBCPP_INLINE_VISIBILITY
1420     iterator begin() _NOEXCEPT
1421         {return iterator(__get_pointer());}
1422     _LIBCPP_INLINE_VISIBILITY
1423     const_iterator begin() const _NOEXCEPT
1424         {return const_iterator(__get_pointer());}
1425     _LIBCPP_INLINE_VISIBILITY
1426     iterator end() _NOEXCEPT
1427         {return iterator(__get_pointer() + size());}
1428     _LIBCPP_INLINE_VISIBILITY
1429     const_iterator end() const _NOEXCEPT
1430         {return const_iterator(__get_pointer() + size());}
1431 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1432     _LIBCPP_INLINE_VISIBILITY
1433     reverse_iterator rbegin() _NOEXCEPT
1434         {return reverse_iterator(end());}
1435     _LIBCPP_INLINE_VISIBILITY
1436     const_reverse_iterator rbegin() const _NOEXCEPT
1437         {return const_reverse_iterator(end());}
1438     _LIBCPP_INLINE_VISIBILITY
1439     reverse_iterator rend() _NOEXCEPT
1440         {return reverse_iterator(begin());}
1441     _LIBCPP_INLINE_VISIBILITY
1442     const_reverse_iterator rend() const _NOEXCEPT
1443         {return const_reverse_iterator(begin());}
1444
1445     _LIBCPP_INLINE_VISIBILITY
1446     const_iterator cbegin() const _NOEXCEPT
1447         {return begin();}
1448     _LIBCPP_INLINE_VISIBILITY
1449     const_iterator cend() const _NOEXCEPT
1450         {return end();}
1451     _LIBCPP_INLINE_VISIBILITY
1452     const_reverse_iterator crbegin() const _NOEXCEPT
1453         {return rbegin();}
1454     _LIBCPP_INLINE_VISIBILITY
1455     const_reverse_iterator crend() const _NOEXCEPT
1456         {return rend();}
1457
1458     _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT
1459         {return __is_long() ? __get_long_size() : __get_short_size();}
1460     _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}
1461     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT;
1462     _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT
1463         {return (__is_long() ? __get_long_cap()
1464                              : static_cast<size_type>(__min_cap)) - 1;}
1465
1466     void resize(size_type __n, value_type __c);
1467     _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());}
1468
1469     void reserve(size_type res_arg = 0);
1470     _LIBCPP_INLINE_VISIBILITY
1471     void shrink_to_fit() _NOEXCEPT {reserve();}
1472     _LIBCPP_INLINE_VISIBILITY
1473     void clear() _NOEXCEPT;
1474     _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return size() == 0;}
1475
1476     _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const;
1477     _LIBCPP_INLINE_VISIBILITY reference       operator[](size_type __pos);
1478
1479     const_reference at(size_type __n) const;
1480     reference       at(size_type __n);
1481
1482     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const basic_string& __str) {return append(__str);}
1483     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const value_type* __s)         {return append(__s);}
1484     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(value_type __c)            {push_back(__c); return *this;}
1485 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1486     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(initializer_list<value_type> __il) {return append(__il);}
1487 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1488
1489     _LIBCPP_INLINE_VISIBILITY
1490     basic_string& append(const basic_string& __str);
1491     basic_string& append(const basic_string& __str, size_type __pos, size_type __n=npos);
1492     basic_string& append(const value_type* __s, size_type __n);
1493     basic_string& append(const value_type* __s);
1494     basic_string& append(size_type __n, value_type __c);
1495     template<class _InputIterator>
1496         typename enable_if
1497         <
1498              __is_input_iterator  <_InputIterator>::value &&
1499             !__is_forward_iterator<_InputIterator>::value,
1500             basic_string&
1501         >::type
1502         append(_InputIterator __first, _InputIterator __last);
1503     template<class _ForwardIterator>
1504         typename enable_if
1505         <
1506             __is_forward_iterator<_ForwardIterator>::value,
1507             basic_string&
1508         >::type
1509         append(_ForwardIterator __first, _ForwardIterator __last);
1510 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1511     _LIBCPP_INLINE_VISIBILITY
1512     basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());}
1513 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1514
1515     void push_back(value_type __c);
1516     _LIBCPP_INLINE_VISIBILITY
1517     void pop_back();
1518     _LIBCPP_INLINE_VISIBILITY reference       front();
1519     _LIBCPP_INLINE_VISIBILITY const_reference front() const;
1520     _LIBCPP_INLINE_VISIBILITY reference       back();
1521     _LIBCPP_INLINE_VISIBILITY const_reference back() const;
1522
1523     _LIBCPP_INLINE_VISIBILITY
1524     basic_string& assign(const basic_string& __str);
1525 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1526     _LIBCPP_INLINE_VISIBILITY
1527     basic_string& assign(basic_string&& str)
1528         _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
1529         {*this = _VSTD::move(str); return *this;}
1530 #endif
1531     basic_string& assign(const basic_string& __str, size_type __pos, size_type __n=npos);
1532     basic_string& assign(const value_type* __s, size_type __n);
1533     basic_string& assign(const value_type* __s);
1534     basic_string& assign(size_type __n, value_type __c);
1535     template<class _InputIterator>
1536         typename enable_if
1537         <
1538              __is_input_iterator  <_InputIterator>::value &&
1539             !__is_forward_iterator<_InputIterator>::value,
1540             basic_string&
1541         >::type
1542         assign(_InputIterator __first, _InputIterator __last);
1543     template<class _ForwardIterator>
1544         typename enable_if
1545         <
1546             __is_forward_iterator<_ForwardIterator>::value,
1547             basic_string&
1548         >::type
1549         assign(_ForwardIterator __first, _ForwardIterator __last);
1550 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1551     _LIBCPP_INLINE_VISIBILITY
1552     basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1553 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1554
1555     _LIBCPP_INLINE_VISIBILITY
1556     basic_string& insert(size_type __pos1, const basic_string& __str);
1557     basic_string& insert(size_type __pos1, const basic_string& __str, size_type __pos2, size_type __n=npos);
1558     basic_string& insert(size_type __pos, const value_type* __s, size_type __n);
1559     basic_string& insert(size_type __pos, const value_type* __s);
1560     basic_string& insert(size_type __pos, size_type __n, value_type __c);
1561     iterator      insert(const_iterator __pos, value_type __c);
1562     _LIBCPP_INLINE_VISIBILITY
1563     iterator      insert(const_iterator __pos, size_type __n, value_type __c);
1564     template<class _InputIterator>
1565         typename enable_if
1566         <
1567              __is_input_iterator  <_InputIterator>::value &&
1568             !__is_forward_iterator<_InputIterator>::value,
1569             iterator
1570         >::type
1571         insert(const_iterator __pos, _InputIterator __first, _InputIterator __last);
1572     template<class _ForwardIterator>
1573         typename enable_if
1574         <
1575             __is_forward_iterator<_ForwardIterator>::value,
1576             iterator
1577         >::type
1578         insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last);
1579 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1580     _LIBCPP_INLINE_VISIBILITY
1581     iterator insert(const_iterator __pos, initializer_list<value_type> __il)
1582                     {return insert(__pos, __il.begin(), __il.end());}
1583 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1584
1585     basic_string& erase(size_type __pos = 0, size_type __n = npos);
1586     _LIBCPP_INLINE_VISIBILITY
1587     iterator      erase(const_iterator __pos);
1588     _LIBCPP_INLINE_VISIBILITY
1589     iterator      erase(const_iterator __first, const_iterator __last);
1590
1591     _LIBCPP_INLINE_VISIBILITY
1592     basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str);
1593     basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos);
1594     basic_string& replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2);
1595     basic_string& replace(size_type __pos, size_type __n1, const value_type* __s);
1596     basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c);
1597     _LIBCPP_INLINE_VISIBILITY
1598     basic_string& replace(const_iterator __i1, const_iterator __i2, const basic_string& __str);
1599     _LIBCPP_INLINE_VISIBILITY
1600     basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n);
1601     _LIBCPP_INLINE_VISIBILITY
1602     basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s);
1603     _LIBCPP_INLINE_VISIBILITY
1604     basic_string& replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c);
1605     template<class _InputIterator>
1606         typename enable_if
1607         <
1608             __is_input_iterator<_InputIterator>::value,
1609             basic_string&
1610         >::type
1611         replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2);
1612 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1613     _LIBCPP_INLINE_VISIBILITY
1614     basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list<value_type> __il)
1615         {return replace(__i1, __i2, __il.begin(), __il.end());}
1616 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1617
1618     size_type copy(value_type* __s, size_type __n, size_type __pos = 0) const;
1619     _LIBCPP_INLINE_VISIBILITY
1620     basic_string substr(size_type __pos = 0, size_type __n = npos) const;
1621
1622     _LIBCPP_INLINE_VISIBILITY
1623     void swap(basic_string& __str)
1624 #if _LIBCPP_STD_VER >= 14
1625         _NOEXCEPT;
1626 #else
1627         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1628                     __is_nothrow_swappable<allocator_type>::value);
1629 #endif
1630
1631     _LIBCPP_INLINE_VISIBILITY
1632     const value_type* c_str() const _NOEXCEPT {return data();}
1633     _LIBCPP_INLINE_VISIBILITY
1634     const value_type* data() const _NOEXCEPT  {return _VSTD::__to_raw_pointer(__get_pointer());}
1635
1636     _LIBCPP_INLINE_VISIBILITY
1637     allocator_type get_allocator() const _NOEXCEPT {return __alloc();}
1638
1639     _LIBCPP_INLINE_VISIBILITY
1640     size_type find(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1641     size_type find(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1642     _LIBCPP_INLINE_VISIBILITY
1643     size_type find(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1644     size_type find(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1645
1646     _LIBCPP_INLINE_VISIBILITY
1647     size_type rfind(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1648     size_type rfind(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1649     _LIBCPP_INLINE_VISIBILITY
1650     size_type rfind(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1651     size_type rfind(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1652
1653     _LIBCPP_INLINE_VISIBILITY
1654     size_type find_first_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1655     size_type find_first_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1656     _LIBCPP_INLINE_VISIBILITY
1657     size_type find_first_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1658     _LIBCPP_INLINE_VISIBILITY
1659     size_type find_first_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1660
1661     _LIBCPP_INLINE_VISIBILITY
1662     size_type find_last_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1663     size_type find_last_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1664     _LIBCPP_INLINE_VISIBILITY
1665     size_type find_last_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1666     _LIBCPP_INLINE_VISIBILITY
1667     size_type find_last_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1668
1669     _LIBCPP_INLINE_VISIBILITY
1670     size_type find_first_not_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1671     size_type find_first_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1672     _LIBCPP_INLINE_VISIBILITY
1673     size_type find_first_not_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1674     _LIBCPP_INLINE_VISIBILITY
1675     size_type find_first_not_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1676
1677     _LIBCPP_INLINE_VISIBILITY
1678     size_type find_last_not_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1679     size_type find_last_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1680     _LIBCPP_INLINE_VISIBILITY
1681     size_type find_last_not_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1682     _LIBCPP_INLINE_VISIBILITY
1683     size_type find_last_not_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1684
1685     _LIBCPP_INLINE_VISIBILITY
1686     int compare(const basic_string& __str) const _NOEXCEPT;
1687     _LIBCPP_INLINE_VISIBILITY
1688     int compare(size_type __pos1, size_type __n1, const basic_string& __str) const;
1689     int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos) const;
1690     int compare(const value_type* __s) const _NOEXCEPT;
1691     int compare(size_type __pos1, size_type __n1, const value_type* __s) const;
1692     int compare(size_type __pos1, size_type __n1, const value_type* __s, size_type __n2) const;
1693
1694     _LIBCPP_INLINE_VISIBILITY bool __invariants() const;
1695
1696     _LIBCPP_INLINE_VISIBILITY
1697     bool __is_long() const _NOEXCEPT
1698         {return bool(__r_.first().__s.__size_ & __short_mask);}
1699
1700 #if _LIBCPP_DEBUG_LEVEL >= 2
1701
1702     bool __dereferenceable(const const_iterator* __i) const;
1703     bool __decrementable(const const_iterator* __i) const;
1704     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1705     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1706
1707 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1708
1709 private:
1710     _LIBCPP_INLINE_VISIBILITY
1711     allocator_type& __alloc() _NOEXCEPT
1712         {return __r_.second();}
1713     _LIBCPP_INLINE_VISIBILITY
1714     const allocator_type& __alloc() const _NOEXCEPT
1715         {return __r_.second();}
1716
1717 #ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1718
1719     _LIBCPP_INLINE_VISIBILITY
1720     void __set_short_size(size_type __s) _NOEXCEPT
1721 #   if _LIBCPP_BIG_ENDIAN
1722         {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
1723 #   else
1724         {__r_.first().__s.__size_ = (unsigned char)(__s);}
1725 #   endif
1726
1727     _LIBCPP_INLINE_VISIBILITY
1728     size_type __get_short_size() const _NOEXCEPT
1729 #   if _LIBCPP_BIG_ENDIAN
1730         {return __r_.first().__s.__size_ >> 1;}
1731 #   else
1732         {return __r_.first().__s.__size_;}
1733 #   endif
1734
1735 #else  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1736
1737     _LIBCPP_INLINE_VISIBILITY
1738     void __set_short_size(size_type __s) _NOEXCEPT
1739 #   if _LIBCPP_BIG_ENDIAN
1740         {__r_.first().__s.__size_ = (unsigned char)(__s);}
1741 #   else
1742         {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
1743 #   endif
1744
1745     _LIBCPP_INLINE_VISIBILITY
1746     size_type __get_short_size() const _NOEXCEPT
1747 #   if _LIBCPP_BIG_ENDIAN
1748         {return __r_.first().__s.__size_;}
1749 #   else
1750         {return __r_.first().__s.__size_ >> 1;}
1751 #   endif
1752
1753 #endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
1754
1755     _LIBCPP_INLINE_VISIBILITY
1756     void __set_long_size(size_type __s) _NOEXCEPT
1757         {__r_.first().__l.__size_ = __s;}
1758     _LIBCPP_INLINE_VISIBILITY
1759     size_type __get_long_size() const _NOEXCEPT
1760         {return __r_.first().__l.__size_;}
1761     _LIBCPP_INLINE_VISIBILITY
1762     void __set_size(size_type __s) _NOEXCEPT
1763         {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);}
1764
1765     _LIBCPP_INLINE_VISIBILITY
1766     void __set_long_cap(size_type __s) _NOEXCEPT
1767         {__r_.first().__l.__cap_  = __long_mask | __s;}
1768     _LIBCPP_INLINE_VISIBILITY
1769     size_type __get_long_cap() const _NOEXCEPT
1770         {return __r_.first().__l.__cap_ & size_type(~__long_mask);}
1771
1772     _LIBCPP_INLINE_VISIBILITY
1773     void __set_long_pointer(pointer __p) _NOEXCEPT
1774         {__r_.first().__l.__data_ = __p;}
1775     _LIBCPP_INLINE_VISIBILITY
1776     pointer __get_long_pointer() _NOEXCEPT
1777         {return __r_.first().__l.__data_;}
1778     _LIBCPP_INLINE_VISIBILITY
1779     const_pointer __get_long_pointer() const _NOEXCEPT
1780         {return __r_.first().__l.__data_;}
1781     _LIBCPP_INLINE_VISIBILITY
1782     pointer __get_short_pointer() _NOEXCEPT
1783         {return pointer_traits<pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1784     _LIBCPP_INLINE_VISIBILITY
1785     const_pointer __get_short_pointer() const _NOEXCEPT
1786         {return pointer_traits<const_pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1787     _LIBCPP_INLINE_VISIBILITY
1788     pointer __get_pointer() _NOEXCEPT
1789         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1790     _LIBCPP_INLINE_VISIBILITY
1791     const_pointer __get_pointer() const _NOEXCEPT
1792         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1793
1794     _LIBCPP_INLINE_VISIBILITY
1795     void __zero() _NOEXCEPT
1796         {
1797             size_type (&__a)[__n_words] = __r_.first().__r.__words;
1798             for (unsigned __i = 0; __i < __n_words; ++__i)
1799                 __a[__i] = 0;
1800         }
1801
1802     template <size_type __a> static
1803         _LIBCPP_INLINE_VISIBILITY
1804         size_type __align_it(size_type __s) _NOEXCEPT
1805             {return (__s + (__a-1)) & ~(__a-1);}
1806     enum {__alignment = 16};
1807     static _LIBCPP_INLINE_VISIBILITY
1808     size_type __recommend(size_type __s) _NOEXCEPT
1809         {return (__s < __min_cap ? static_cast<size_type>(__min_cap) :
1810                  __align_it<sizeof(value_type) < __alignment ?
1811                             __alignment/sizeof(value_type) : 1 > (__s+1)) - 1;}
1812
1813     void __init(const value_type* __s, size_type __sz, size_type __reserve);
1814     void __init(const value_type* __s, size_type __sz);
1815     void __init(size_type __n, value_type __c);
1816
1817     template <class _InputIterator>
1818     typename enable_if
1819     <
1820          __is_input_iterator  <_InputIterator>::value &&
1821         !__is_forward_iterator<_InputIterator>::value,
1822         void
1823     >::type
1824     __init(_InputIterator __first, _InputIterator __last);
1825
1826     template <class _ForwardIterator>
1827     typename enable_if
1828     <
1829         __is_forward_iterator<_ForwardIterator>::value,
1830         void
1831     >::type
1832     __init(_ForwardIterator __first, _ForwardIterator __last);
1833
1834     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1835                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
1836     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1837                                size_type __n_copy,  size_type __n_del,
1838                                size_type __n_add, const value_type* __p_new_stuff);
1839
1840     _LIBCPP_INLINE_VISIBILITY
1841     void __erase_to_end(size_type __pos);
1842
1843     _LIBCPP_INLINE_VISIBILITY
1844     void __copy_assign_alloc(const basic_string& __str)
1845         {__copy_assign_alloc(__str, integral_constant<bool,
1846                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
1847
1848     _LIBCPP_INLINE_VISIBILITY
1849     void __copy_assign_alloc(const basic_string& __str, true_type)
1850         {
1851             if (__alloc() != __str.__alloc())
1852             {
1853                 clear();
1854                 shrink_to_fit();
1855             }
1856             __alloc() = __str.__alloc();
1857         }
1858
1859     _LIBCPP_INLINE_VISIBILITY
1860     void __copy_assign_alloc(const basic_string&, false_type) _NOEXCEPT
1861         {}
1862
1863 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1864     _LIBCPP_INLINE_VISIBILITY
1865     void __move_assign(basic_string& __str, false_type)
1866         _NOEXCEPT_(__alloc_traits::is_always_equal::value);
1867     _LIBCPP_INLINE_VISIBILITY
1868     void __move_assign(basic_string& __str, true_type)
1869 #if _LIBCPP_STD_VER > 14
1870         _NOEXCEPT;
1871 #else
1872         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1873 #endif
1874 #endif
1875
1876     _LIBCPP_INLINE_VISIBILITY
1877     void
1878     __move_assign_alloc(basic_string& __str)
1879         _NOEXCEPT_(
1880             !__alloc_traits::propagate_on_container_move_assignment::value ||
1881             is_nothrow_move_assignable<allocator_type>::value)
1882     {__move_assign_alloc(__str, integral_constant<bool,
1883                       __alloc_traits::propagate_on_container_move_assignment::value>());}
1884
1885     _LIBCPP_INLINE_VISIBILITY
1886     void __move_assign_alloc(basic_string& __c, true_type)
1887         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1888         {
1889             __alloc() = _VSTD::move(__c.__alloc());
1890         }
1891
1892     _LIBCPP_INLINE_VISIBILITY
1893     void __move_assign_alloc(basic_string&, false_type)
1894         _NOEXCEPT
1895         {}
1896
1897     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
1898     _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type);
1899
1900     friend basic_string operator+<>(const basic_string&, const basic_string&);
1901     friend basic_string operator+<>(const value_type*, const basic_string&);
1902     friend basic_string operator+<>(value_type, const basic_string&);
1903     friend basic_string operator+<>(const basic_string&, const value_type*);
1904     friend basic_string operator+<>(const basic_string&, value_type);
1905 };
1906
1907 template <class _CharT, class _Traits, class _Allocator>
1908 inline _LIBCPP_INLINE_VISIBILITY
1909 void
1910 basic_string<_CharT, _Traits, _Allocator>::__invalidate_all_iterators()
1911 {
1912 #if _LIBCPP_DEBUG_LEVEL >= 2
1913     __get_db()->__invalidate_all(this);
1914 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1915 }
1916
1917 template <class _CharT, class _Traits, class _Allocator>
1918 inline _LIBCPP_INLINE_VISIBILITY
1919 void
1920 basic_string<_CharT, _Traits, _Allocator>::__invalidate_iterators_past(size_type
1921 #if _LIBCPP_DEBUG_LEVEL >= 2
1922                                                                         __pos
1923 #endif
1924                                                                       )
1925 {
1926 #if _LIBCPP_DEBUG_LEVEL >= 2
1927     __c_node* __c = __get_db()->__find_c_and_lock(this);
1928     if (__c)
1929     {
1930         const_pointer __new_last = __get_pointer() + __pos;
1931         for (__i_node** __p = __c->end_; __p != __c->beg_; )
1932         {
1933             --__p;
1934             const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
1935             if (__i->base() > __new_last)
1936             {
1937                 (*__p)->__c_ = nullptr;
1938                 if (--__c->end_ != __p)
1939                     memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1940             }
1941         }
1942         __get_db()->unlock();
1943     }
1944 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1945 }
1946
1947 template <class _CharT, class _Traits, class _Allocator>
1948 inline _LIBCPP_INLINE_VISIBILITY
1949 basic_string<_CharT, _Traits, _Allocator>::basic_string()
1950     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1951 {
1952 #if _LIBCPP_DEBUG_LEVEL >= 2
1953     __get_db()->__insert_c(this);
1954 #endif
1955     __zero();
1956 }
1957
1958 template <class _CharT, class _Traits, class _Allocator>
1959 inline _LIBCPP_INLINE_VISIBILITY
1960 basic_string<_CharT, _Traits, _Allocator>::basic_string(const allocator_type& __a)
1961 #if _LIBCPP_STD_VER <= 14
1962         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
1963 #else
1964         _NOEXCEPT
1965 #endif
1966 : __r_(__a)
1967 {
1968 #if _LIBCPP_DEBUG_LEVEL >= 2
1969     __get_db()->__insert_c(this);
1970 #endif
1971     __zero();
1972 }
1973
1974 template <class _CharT, class _Traits, class _Allocator>
1975 void
1976 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz, size_type __reserve)
1977 {
1978     if (__reserve > max_size())
1979         this->__throw_length_error();
1980     pointer __p;
1981     if (__reserve < __min_cap)
1982     {
1983         __set_short_size(__sz);
1984         __p = __get_short_pointer();
1985     }
1986     else
1987     {
1988         size_type __cap = __recommend(__reserve);
1989         __p = __alloc_traits::allocate(__alloc(), __cap+1);
1990         __set_long_pointer(__p);
1991         __set_long_cap(__cap+1);
1992         __set_long_size(__sz);
1993     }
1994     traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz);
1995     traits_type::assign(__p[__sz], value_type());
1996 }
1997
1998 template <class _CharT, class _Traits, class _Allocator>
1999 void
2000 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
2001 {
2002     if (__sz > max_size())
2003         this->__throw_length_error();
2004     pointer __p;
2005     if (__sz < __min_cap)
2006     {
2007         __set_short_size(__sz);
2008         __p = __get_short_pointer();
2009     }
2010     else
2011     {
2012         size_type __cap = __recommend(__sz);
2013         __p = __alloc_traits::allocate(__alloc(), __cap+1);
2014         __set_long_pointer(__p);
2015         __set_long_cap(__cap+1);
2016         __set_long_size(__sz);
2017     }
2018     traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz);
2019     traits_type::assign(__p[__sz], value_type());
2020 }
2021
2022 template <class _CharT, class _Traits, class _Allocator>
2023 inline _LIBCPP_INLINE_VISIBILITY
2024 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s)
2025 {
2026     _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*) detected nullptr");
2027     __init(__s, traits_type::length(__s));
2028 #if _LIBCPP_DEBUG_LEVEL >= 2
2029     __get_db()->__insert_c(this);
2030 #endif
2031 }
2032
2033 template <class _CharT, class _Traits, class _Allocator>
2034 inline _LIBCPP_INLINE_VISIBILITY
2035 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, const allocator_type& __a)
2036     : __r_(__a)
2037 {
2038     _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*, allocator) detected nullptr");
2039     __init(__s, traits_type::length(__s));
2040 #if _LIBCPP_DEBUG_LEVEL >= 2
2041     __get_db()->__insert_c(this);
2042 #endif
2043 }
2044
2045 template <class _CharT, class _Traits, class _Allocator>
2046 inline _LIBCPP_INLINE_VISIBILITY
2047 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n)
2048 {
2049     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n) detected nullptr");
2050     __init(__s, __n);
2051 #if _LIBCPP_DEBUG_LEVEL >= 2
2052     __get_db()->__insert_c(this);
2053 #endif
2054 }
2055
2056 template <class _CharT, class _Traits, class _Allocator>
2057 inline _LIBCPP_INLINE_VISIBILITY
2058 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n, const allocator_type& __a)
2059     : __r_(__a)
2060 {
2061     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n, allocator) detected nullptr");
2062     __init(__s, __n);
2063 #if _LIBCPP_DEBUG_LEVEL >= 2
2064     __get_db()->__insert_c(this);
2065 #endif
2066 }
2067
2068 template <class _CharT, class _Traits, class _Allocator>
2069 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str)
2070     : __r_(__alloc_traits::select_on_container_copy_construction(__str.__alloc()))
2071 {
2072     if (!__str.__is_long())
2073         __r_.first().__r = __str.__r_.first().__r;
2074     else
2075         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2076 #if _LIBCPP_DEBUG_LEVEL >= 2
2077     __get_db()->__insert_c(this);
2078 #endif
2079 }
2080
2081 template <class _CharT, class _Traits, class _Allocator>
2082 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, const allocator_type& __a)
2083     : __r_(__a)
2084 {
2085     if (!__str.__is_long())
2086         __r_.first().__r = __str.__r_.first().__r;
2087     else
2088         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2089 #if _LIBCPP_DEBUG_LEVEL >= 2
2090     __get_db()->__insert_c(this);
2091 #endif
2092 }
2093
2094 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2095
2096 template <class _CharT, class _Traits, class _Allocator>
2097 inline _LIBCPP_INLINE_VISIBILITY
2098 basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str)
2099 #if _LIBCPP_STD_VER <= 14
2100         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2101 #else
2102         _NOEXCEPT
2103 #endif
2104     : __r_(_VSTD::move(__str.__r_))
2105 {
2106     __str.__zero();
2107 #if _LIBCPP_DEBUG_LEVEL >= 2
2108     __get_db()->__insert_c(this);
2109     if (__is_long())
2110         __get_db()->swap(this, &__str);
2111 #endif
2112 }
2113
2114 template <class _CharT, class _Traits, class _Allocator>
2115 inline _LIBCPP_INLINE_VISIBILITY
2116 basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str, const allocator_type& __a)
2117     : __r_(__a)
2118 {
2119     if (__str.__is_long() && __a != __str.__alloc()) // copy, not move
2120         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2121     else
2122     {
2123         __r_.first().__r = __str.__r_.first().__r;
2124         __str.__zero();
2125     }
2126 #if _LIBCPP_DEBUG_LEVEL >= 2
2127     __get_db()->__insert_c(this);
2128     if (__is_long())
2129         __get_db()->swap(this, &__str);
2130 #endif
2131 }
2132
2133 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2134
2135 template <class _CharT, class _Traits, class _Allocator>
2136 void
2137 basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
2138 {
2139     if (__n > max_size())
2140         this->__throw_length_error();
2141     pointer __p;
2142     if (__n < __min_cap)
2143     {
2144         __set_short_size(__n);
2145         __p = __get_short_pointer();
2146     }
2147     else
2148     {
2149         size_type __cap = __recommend(__n);
2150         __p = __alloc_traits::allocate(__alloc(), __cap+1);
2151         __set_long_pointer(__p);
2152         __set_long_cap(__cap+1);
2153         __set_long_size(__n);
2154     }
2155     traits_type::assign(_VSTD::__to_raw_pointer(__p), __n, __c);
2156     traits_type::assign(__p[__n], value_type());
2157 }
2158
2159 template <class _CharT, class _Traits, class _Allocator>
2160 inline _LIBCPP_INLINE_VISIBILITY
2161 basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c)
2162 {
2163     __init(__n, __c);
2164 #if _LIBCPP_DEBUG_LEVEL >= 2
2165     __get_db()->__insert_c(this);
2166 #endif
2167 }
2168
2169 template <class _CharT, class _Traits, class _Allocator>
2170 inline _LIBCPP_INLINE_VISIBILITY
2171 basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c, const allocator_type& __a)
2172     : __r_(__a)
2173 {
2174     __init(__n, __c);
2175 #if _LIBCPP_DEBUG_LEVEL >= 2
2176     __get_db()->__insert_c(this);
2177 #endif
2178 }
2179
2180 template <class _CharT, class _Traits, class _Allocator>
2181 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, size_type __pos, size_type __n,
2182                                                         const allocator_type& __a)
2183     : __r_(__a)
2184 {
2185     size_type __str_sz = __str.size();
2186     if (__pos > __str_sz)
2187         this->__throw_out_of_range();
2188     __init(__str.data() + __pos, _VSTD::min(__n, __str_sz - __pos));
2189 #if _LIBCPP_DEBUG_LEVEL >= 2
2190     __get_db()->__insert_c(this);
2191 #endif
2192 }
2193
2194 template <class _CharT, class _Traits, class _Allocator>
2195 template <class _InputIterator>
2196 typename enable_if
2197 <
2198      __is_input_iterator  <_InputIterator>::value &&
2199     !__is_forward_iterator<_InputIterator>::value,
2200     void
2201 >::type
2202 basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last)
2203 {
2204     __zero();
2205 #ifndef _LIBCPP_NO_EXCEPTIONS
2206     try
2207     {
2208 #endif  // _LIBCPP_NO_EXCEPTIONS
2209     for (; __first != __last; ++__first)
2210         push_back(*__first);
2211 #ifndef _LIBCPP_NO_EXCEPTIONS
2212     }
2213     catch (...)
2214     {
2215         if (__is_long())
2216             __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2217         throw;
2218     }
2219 #endif  // _LIBCPP_NO_EXCEPTIONS
2220 }
2221
2222 template <class _CharT, class _Traits, class _Allocator>
2223 template <class _ForwardIterator>
2224 typename enable_if
2225 <
2226     __is_forward_iterator<_ForwardIterator>::value,
2227     void
2228 >::type
2229 basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
2230 {
2231     size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last));
2232     if (__sz > max_size())
2233         this->__throw_length_error();
2234     pointer __p;
2235     if (__sz < __min_cap)
2236     {
2237         __set_short_size(__sz);
2238         __p = __get_short_pointer();
2239     }
2240     else
2241     {
2242         size_type __cap = __recommend(__sz);
2243         __p = __alloc_traits::allocate(__alloc(), __cap+1);
2244         __set_long_pointer(__p);
2245         __set_long_cap(__cap+1);
2246         __set_long_size(__sz);
2247     }
2248     for (; __first != __last; ++__first, (void) ++__p)
2249         traits_type::assign(*__p, *__first);
2250     traits_type::assign(*__p, value_type());
2251 }
2252
2253 template <class _CharT, class _Traits, class _Allocator>
2254 template<class _InputIterator>
2255 inline _LIBCPP_INLINE_VISIBILITY
2256 basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last)
2257 {
2258     __init(__first, __last);
2259 #if _LIBCPP_DEBUG_LEVEL >= 2
2260     __get_db()->__insert_c(this);
2261 #endif
2262 }
2263
2264 template <class _CharT, class _Traits, class _Allocator>
2265 template<class _InputIterator>
2266 inline _LIBCPP_INLINE_VISIBILITY
2267 basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last,
2268                                                         const allocator_type& __a)
2269     : __r_(__a)
2270 {
2271     __init(__first, __last);
2272 #if _LIBCPP_DEBUG_LEVEL >= 2
2273     __get_db()->__insert_c(this);
2274 #endif
2275 }
2276
2277 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2278
2279 template <class _CharT, class _Traits, class _Allocator>
2280 inline _LIBCPP_INLINE_VISIBILITY
2281 basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il)
2282 {
2283     __init(__il.begin(), __il.end());
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 inline _LIBCPP_INLINE_VISIBILITY
2291 basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il, const allocator_type& __a)
2292     : __r_(__a)
2293 {
2294     __init(__il.begin(), __il.end());
2295 #if _LIBCPP_DEBUG_LEVEL >= 2
2296     __get_db()->__insert_c(this);
2297 #endif
2298 }
2299
2300 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2301
2302 template <class _CharT, class _Traits, class _Allocator>
2303 basic_string<_CharT, _Traits, _Allocator>::~basic_string()
2304 {
2305 #if _LIBCPP_DEBUG_LEVEL >= 2
2306     __get_db()->__erase_c(this);
2307 #endif
2308     if (__is_long())
2309         __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2310 }
2311
2312 template <class _CharT, class _Traits, class _Allocator>
2313 void
2314 basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
2315     (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2316      size_type __n_copy,  size_type __n_del,     size_type __n_add, const value_type* __p_new_stuff)
2317 {
2318     size_type __ms = max_size();
2319     if (__delta_cap > __ms - __old_cap - 1)
2320         this->__throw_length_error();
2321     pointer __old_p = __get_pointer();
2322     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2323                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2324                           __ms - 1;
2325     pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
2326     __invalidate_all_iterators();
2327     if (__n_copy != 0)
2328         traits_type::copy(_VSTD::__to_raw_pointer(__p),
2329                           _VSTD::__to_raw_pointer(__old_p), __n_copy);
2330     if (__n_add != 0)
2331         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy, __p_new_stuff, __n_add);
2332     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2333     if (__sec_cp_sz != 0)
2334         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
2335                           _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del, __sec_cp_sz);
2336     if (__old_cap+1 != __min_cap)
2337         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
2338     __set_long_pointer(__p);
2339     __set_long_cap(__cap+1);
2340     __old_sz = __n_copy + __n_add + __sec_cp_sz;
2341     __set_long_size(__old_sz);
2342     traits_type::assign(__p[__old_sz], value_type());
2343 }
2344
2345 template <class _CharT, class _Traits, class _Allocator>
2346 void
2347 basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2348                                                      size_type __n_copy,  size_type __n_del,     size_type __n_add)
2349 {
2350     size_type __ms = max_size();
2351     if (__delta_cap > __ms - __old_cap)
2352         this->__throw_length_error();
2353     pointer __old_p = __get_pointer();
2354     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2355                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2356                           __ms - 1;
2357     pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
2358     __invalidate_all_iterators();
2359     if (__n_copy != 0)
2360         traits_type::copy(_VSTD::__to_raw_pointer(__p),
2361                           _VSTD::__to_raw_pointer(__old_p), __n_copy);
2362     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2363     if (__sec_cp_sz != 0)
2364         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
2365                           _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del,
2366                           __sec_cp_sz);
2367     if (__old_cap+1 != __min_cap)
2368         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
2369     __set_long_pointer(__p);
2370     __set_long_cap(__cap+1);
2371 }
2372
2373 // assign
2374
2375 template <class _CharT, class _Traits, class _Allocator>
2376 basic_string<_CharT, _Traits, _Allocator>&
2377 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
2378 {
2379     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr");
2380     size_type __cap = capacity();
2381     if (__cap >= __n)
2382     {
2383         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2384         traits_type::move(__p, __s, __n);
2385         traits_type::assign(__p[__n], value_type());
2386         __set_size(__n);
2387         __invalidate_iterators_past(__n);
2388     }
2389     else
2390     {
2391         size_type __sz = size();
2392         __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
2393     }
2394     return *this;
2395 }
2396
2397 template <class _CharT, class _Traits, class _Allocator>
2398 basic_string<_CharT, _Traits, _Allocator>&
2399 basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
2400 {
2401     size_type __cap = capacity();
2402     if (__cap < __n)
2403     {
2404         size_type __sz = size();
2405         __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2406     }
2407     else
2408         __invalidate_iterators_past(__n);
2409     value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2410     traits_type::assign(__p, __n, __c);
2411     traits_type::assign(__p[__n], value_type());
2412     __set_size(__n);
2413     return *this;
2414 }
2415
2416 template <class _CharT, class _Traits, class _Allocator>
2417 basic_string<_CharT, _Traits, _Allocator>&
2418 basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
2419 {
2420     pointer __p;
2421     if (__is_long())
2422     {
2423         __p = __get_long_pointer();
2424         __set_long_size(1);
2425     }
2426     else
2427     {
2428         __p = __get_short_pointer();
2429         __set_short_size(1);
2430     }
2431     traits_type::assign(*__p, __c);
2432     traits_type::assign(*++__p, value_type());
2433     __invalidate_iterators_past(1);
2434     return *this;
2435 }
2436
2437 template <class _CharT, class _Traits, class _Allocator>
2438 basic_string<_CharT, _Traits, _Allocator>&
2439 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
2440 {
2441     if (this != &__str)
2442     {
2443         __copy_assign_alloc(__str);
2444         assign(__str);
2445     }
2446     return *this;
2447 }
2448
2449 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2450
2451 template <class _CharT, class _Traits, class _Allocator>
2452 inline _LIBCPP_INLINE_VISIBILITY
2453 void
2454 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)
2455     _NOEXCEPT_(__alloc_traits::is_always_equal::value)
2456 {
2457     if (__alloc() != __str.__alloc())
2458         assign(__str);
2459     else
2460         __move_assign(__str, true_type());
2461 }
2462
2463 template <class _CharT, class _Traits, class _Allocator>
2464 inline _LIBCPP_INLINE_VISIBILITY
2465 void
2466 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type)
2467 #if _LIBCPP_STD_VER > 14
2468     _NOEXCEPT
2469 #else
2470     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2471 #endif
2472 {
2473     clear();
2474     shrink_to_fit();
2475     __r_.first() = __str.__r_.first();
2476     __move_assign_alloc(__str);
2477     __str.__zero();
2478 }
2479
2480 template <class _CharT, class _Traits, class _Allocator>
2481 inline _LIBCPP_INLINE_VISIBILITY
2482 basic_string<_CharT, _Traits, _Allocator>&
2483 basic_string<_CharT, _Traits, _Allocator>::operator=(basic_string&& __str)
2484     _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
2485 {
2486     __move_assign(__str, integral_constant<bool,
2487           __alloc_traits::propagate_on_container_move_assignment::value>());
2488     return *this;
2489 }
2490
2491 #endif
2492
2493 template <class _CharT, class _Traits, class _Allocator>
2494 template<class _InputIterator>
2495 typename enable_if
2496 <
2497      __is_input_iterator  <_InputIterator>::value &&
2498     !__is_forward_iterator<_InputIterator>::value,
2499     basic_string<_CharT, _Traits, _Allocator>&
2500 >::type
2501 basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2502 {
2503     clear();
2504     for (; __first != __last; ++__first)
2505         push_back(*__first);
2506     return *this;
2507 }
2508
2509 template <class _CharT, class _Traits, class _Allocator>
2510 template<class _ForwardIterator>
2511 typename enable_if
2512 <
2513     __is_forward_iterator<_ForwardIterator>::value,
2514     basic_string<_CharT, _Traits, _Allocator>&
2515 >::type
2516 basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2517 {
2518     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2519     size_type __cap = capacity();
2520     if (__cap < __n)
2521     {
2522         size_type __sz = size();
2523         __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2524     }
2525     else
2526         __invalidate_iterators_past(__n);
2527     pointer __p = __get_pointer();
2528     for (; __first != __last; ++__first, ++__p)
2529         traits_type::assign(*__p, *__first);
2530     traits_type::assign(*__p, value_type());
2531     __set_size(__n);
2532     return *this;
2533 }
2534
2535 template <class _CharT, class _Traits, class _Allocator>
2536 inline _LIBCPP_INLINE_VISIBILITY
2537 basic_string<_CharT, _Traits, _Allocator>&
2538 basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str)
2539 {
2540     return assign(__str.data(), __str.size());
2541 }
2542
2543 template <class _CharT, class _Traits, class _Allocator>
2544 basic_string<_CharT, _Traits, _Allocator>&
2545 basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n)
2546 {
2547     size_type __sz = __str.size();
2548     if (__pos > __sz)
2549         this->__throw_out_of_range();
2550     return assign(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
2551 }
2552
2553 template <class _CharT, class _Traits, class _Allocator>
2554 basic_string<_CharT, _Traits, _Allocator>&
2555 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s)
2556 {
2557     _LIBCPP_ASSERT(__s != nullptr, "string::assign received nullptr");
2558     return assign(__s, traits_type::length(__s));
2559 }
2560
2561 // append
2562
2563 template <class _CharT, class _Traits, class _Allocator>
2564 basic_string<_CharT, _Traits, _Allocator>&
2565 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n)
2566 {
2567     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::append received nullptr");
2568     size_type __cap = capacity();
2569     size_type __sz = size();
2570     if (__cap - __sz >= __n)
2571     {
2572         if (__n)
2573         {
2574             value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2575             traits_type::copy(__p + __sz, __s, __n);
2576             __sz += __n;
2577             __set_size(__sz);
2578             traits_type::assign(__p[__sz], value_type());
2579         }
2580     }
2581     else
2582         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s);
2583     return *this;
2584 }
2585
2586 template <class _CharT, class _Traits, class _Allocator>
2587 basic_string<_CharT, _Traits, _Allocator>&
2588 basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c)
2589 {
2590     if (__n)
2591     {
2592         size_type __cap = capacity();
2593         size_type __sz = size();
2594         if (__cap - __sz < __n)
2595             __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2596         pointer __p = __get_pointer();
2597         traits_type::assign(_VSTD::__to_raw_pointer(__p) + __sz, __n, __c);
2598         __sz += __n;
2599         __set_size(__sz);
2600         traits_type::assign(__p[__sz], value_type());
2601     }
2602     return *this;
2603 }
2604
2605 template <class _CharT, class _Traits, class _Allocator>
2606 void
2607 basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)
2608 {
2609     bool __is_short = !__is_long();
2610     size_type __cap;
2611     size_type __sz;
2612     if (__is_short)
2613     {
2614         __cap = __min_cap - 1;
2615         __sz = __get_short_size();
2616     }
2617     else
2618     {
2619         __cap = __get_long_cap() - 1;
2620         __sz = __get_long_size();
2621     }
2622     if (__sz == __cap)
2623     {
2624         __grow_by(__cap, 1, __sz, __sz, 0);
2625         __is_short = !__is_long();
2626     }
2627     pointer __p;
2628     if (__is_short)
2629     {
2630         __p = __get_short_pointer() + __sz;
2631         __set_short_size(__sz+1);
2632     }
2633     else
2634     {
2635         __p = __get_long_pointer() + __sz;
2636         __set_long_size(__sz+1);
2637     }
2638     traits_type::assign(*__p, __c);
2639     traits_type::assign(*++__p, value_type());
2640 }
2641
2642 template <class _CharT, class _Traits, class _Allocator>
2643 template<class _InputIterator>
2644 typename enable_if
2645 <
2646      __is_input_iterator  <_InputIterator>::value &&
2647     !__is_forward_iterator<_InputIterator>::value,
2648     basic_string<_CharT, _Traits, _Allocator>&
2649 >::type
2650 basic_string<_CharT, _Traits, _Allocator>::append(_InputIterator __first, _InputIterator __last)
2651 {
2652     for (; __first != __last; ++__first)
2653         push_back(*__first);
2654     return *this;
2655 }
2656
2657 template <class _CharT, class _Traits, class _Allocator>
2658 template<class _ForwardIterator>
2659 typename enable_if
2660 <
2661     __is_forward_iterator<_ForwardIterator>::value,
2662     basic_string<_CharT, _Traits, _Allocator>&
2663 >::type
2664 basic_string<_CharT, _Traits, _Allocator>::append(_ForwardIterator __first, _ForwardIterator __last)
2665 {
2666     size_type __sz = size();
2667     size_type __cap = capacity();
2668     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2669     if (__n)
2670     {
2671         if (__cap - __sz < __n)
2672             __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2673         pointer __p = __get_pointer() + __sz;
2674         for (; __first != __last; ++__p, ++__first)
2675             traits_type::assign(*__p, *__first);
2676         traits_type::assign(*__p, value_type());
2677         __set_size(__sz + __n);
2678     }
2679     return *this;
2680 }
2681
2682 template <class _CharT, class _Traits, class _Allocator>
2683 inline _LIBCPP_INLINE_VISIBILITY
2684 basic_string<_CharT, _Traits, _Allocator>&
2685 basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str)
2686 {
2687     return append(__str.data(), __str.size());
2688 }
2689
2690 template <class _CharT, class _Traits, class _Allocator>
2691 basic_string<_CharT, _Traits, _Allocator>&
2692 basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n)
2693 {
2694     size_type __sz = __str.size();
2695     if (__pos > __sz)
2696         this->__throw_out_of_range();
2697     return append(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
2698 }
2699
2700 template <class _CharT, class _Traits, class _Allocator>
2701 basic_string<_CharT, _Traits, _Allocator>&
2702 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s)
2703 {
2704     _LIBCPP_ASSERT(__s != nullptr, "string::append received nullptr");
2705     return append(__s, traits_type::length(__s));
2706 }
2707
2708 // insert
2709
2710 template <class _CharT, class _Traits, class _Allocator>
2711 basic_string<_CharT, _Traits, _Allocator>&
2712 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s, size_type __n)
2713 {
2714     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::insert received nullptr");
2715     size_type __sz = size();
2716     if (__pos > __sz)
2717         this->__throw_out_of_range();
2718     size_type __cap = capacity();
2719     if (__cap - __sz >= __n)
2720     {
2721         if (__n)
2722         {
2723             value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2724             size_type __n_move = __sz - __pos;
2725             if (__n_move != 0)
2726             {
2727                 if (__p + __pos <= __s && __s < __p + __sz)
2728                     __s += __n;
2729                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2730             }
2731             traits_type::move(__p + __pos, __s, __n);
2732             __sz += __n;
2733             __set_size(__sz);
2734             traits_type::assign(__p[__sz], value_type());
2735         }
2736     }
2737     else
2738         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s);
2739     return *this;
2740 }
2741
2742 template <class _CharT, class _Traits, class _Allocator>
2743 basic_string<_CharT, _Traits, _Allocator>&
2744 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c)
2745 {
2746     size_type __sz = size();
2747     if (__pos > __sz)
2748         this->__throw_out_of_range();
2749     if (__n)
2750     {
2751         size_type __cap = capacity();
2752         value_type* __p;
2753         if (__cap - __sz >= __n)
2754         {
2755             __p = _VSTD::__to_raw_pointer(__get_pointer());
2756             size_type __n_move = __sz - __pos;
2757             if (__n_move != 0)
2758                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2759         }
2760         else
2761         {
2762             __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n);
2763             __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2764         }
2765         traits_type::assign(__p + __pos, __n, __c);
2766         __sz += __n;
2767         __set_size(__sz);
2768         traits_type::assign(__p[__sz], value_type());
2769     }
2770     return *this;
2771 }
2772
2773 template <class _CharT, class _Traits, class _Allocator>
2774 template<class _InputIterator>
2775 typename enable_if
2776 <
2777      __is_input_iterator  <_InputIterator>::value &&
2778     !__is_forward_iterator<_InputIterator>::value,
2779     typename basic_string<_CharT, _Traits, _Allocator>::iterator
2780 >::type
2781 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last)
2782 {
2783 #if _LIBCPP_DEBUG_LEVEL >= 2
2784     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2785         "string::insert(iterator, range) called with an iterator not"
2786         " referring to this string");
2787 #endif
2788     size_type __old_sz = size();
2789     difference_type __ip = __pos - begin();
2790     for (; __first != __last; ++__first)
2791         push_back(*__first);
2792     pointer __p = __get_pointer();
2793     _VSTD::rotate(__p + __ip, __p + __old_sz, __p + size());
2794 #if _LIBCPP_DEBUG_LEVEL >= 2
2795     return iterator(this, __p + __ip);
2796 #else
2797     return iterator(__p + __ip);
2798 #endif
2799 }
2800
2801 template <class _CharT, class _Traits, class _Allocator>
2802 template<class _ForwardIterator>
2803 typename enable_if
2804 <
2805     __is_forward_iterator<_ForwardIterator>::value,
2806     typename basic_string<_CharT, _Traits, _Allocator>::iterator
2807 >::type
2808 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last)
2809 {
2810 #if _LIBCPP_DEBUG_LEVEL >= 2
2811     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2812         "string::insert(iterator, range) called with an iterator not"
2813         " referring to this string");
2814 #endif
2815     size_type __ip = static_cast<size_type>(__pos - begin());
2816     size_type __sz = size();
2817     size_type __cap = capacity();
2818     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2819     if (__n)
2820     {
2821         value_type* __p;
2822         if (__cap - __sz >= __n)
2823         {
2824             __p = _VSTD::__to_raw_pointer(__get_pointer());
2825             size_type __n_move = __sz - __ip;
2826             if (__n_move != 0)
2827                 traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
2828         }
2829         else
2830         {
2831             __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
2832             __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2833         }
2834         __sz += __n;
2835         __set_size(__sz);
2836         traits_type::assign(__p[__sz], value_type());
2837         for (__p += __ip; __first != __last; ++__p, ++__first)
2838             traits_type::assign(*__p, *__first);
2839     }
2840     return begin() + __ip;
2841 }
2842
2843 template <class _CharT, class _Traits, class _Allocator>
2844 inline _LIBCPP_INLINE_VISIBILITY
2845 basic_string<_CharT, _Traits, _Allocator>&
2846 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str)
2847 {
2848     return insert(__pos1, __str.data(), __str.size());
2849 }
2850
2851 template <class _CharT, class _Traits, class _Allocator>
2852 basic_string<_CharT, _Traits, _Allocator>&
2853 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str,
2854                                                   size_type __pos2, size_type __n)
2855 {
2856     size_type __str_sz = __str.size();
2857     if (__pos2 > __str_sz)
2858         this->__throw_out_of_range();
2859     return insert(__pos1, __str.data() + __pos2, _VSTD::min(__n, __str_sz - __pos2));
2860 }
2861
2862 template <class _CharT, class _Traits, class _Allocator>
2863 basic_string<_CharT, _Traits, _Allocator>&
2864 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s)
2865 {
2866     _LIBCPP_ASSERT(__s != nullptr, "string::insert received nullptr");
2867     return insert(__pos, __s, traits_type::length(__s));
2868 }
2869
2870 template <class _CharT, class _Traits, class _Allocator>
2871 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2872 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c)
2873 {
2874     size_type __ip = static_cast<size_type>(__pos - begin());
2875     size_type __sz = size();
2876     size_type __cap = capacity();
2877     value_type* __p;
2878     if (__cap == __sz)
2879     {
2880         __grow_by(__cap, 1, __sz, __ip, 0, 1);
2881         __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2882     }
2883     else
2884     {
2885         __p = _VSTD::__to_raw_pointer(__get_pointer());
2886         size_type __n_move = __sz - __ip;
2887         if (__n_move != 0)
2888             traits_type::move(__p + __ip + 1, __p + __ip, __n_move);
2889     }
2890     traits_type::assign(__p[__ip], __c);
2891     traits_type::assign(__p[++__sz], value_type());
2892     __set_size(__sz);
2893     return begin() + static_cast<difference_type>(__ip);
2894 }
2895
2896 template <class _CharT, class _Traits, class _Allocator>
2897 inline _LIBCPP_INLINE_VISIBILITY
2898 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2899 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, size_type __n, value_type __c)
2900 {
2901 #if _LIBCPP_DEBUG_LEVEL >= 2
2902     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2903         "string::insert(iterator, n, value) called with an iterator not"
2904         " referring to this string");
2905 #endif
2906     difference_type __p = __pos - begin();
2907     insert(static_cast<size_type>(__p), __n, __c);
2908     return begin() + __p;
2909 }
2910
2911 // replace
2912
2913 template <class _CharT, class _Traits, class _Allocator>
2914 basic_string<_CharT, _Traits, _Allocator>&
2915 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2)
2916 {
2917     _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::replace received nullptr");
2918     size_type __sz = size();
2919     if (__pos > __sz)
2920         this->__throw_out_of_range();
2921     __n1 = _VSTD::min(__n1, __sz - __pos);
2922     size_type __cap = capacity();
2923     if (__cap - __sz + __n1 >= __n2)
2924     {
2925         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2926         if (__n1 != __n2)
2927         {
2928             size_type __n_move = __sz - __pos - __n1;
2929             if (__n_move != 0)
2930             {
2931                 if (__n1 > __n2)
2932                 {
2933                     traits_type::move(__p + __pos, __s, __n2);
2934                     traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2935                     goto __finish;
2936                 }
2937                 if (__p + __pos < __s && __s < __p + __sz)
2938                 {
2939                     if (__p + __pos + __n1 <= __s)
2940                         __s += __n2 - __n1;
2941                     else // __p + __pos < __s < __p + __pos + __n1
2942                     {
2943                         traits_type::move(__p + __pos, __s, __n1);
2944                         __pos += __n1;
2945                         __s += __n2;
2946                         __n2 -= __n1;
2947                         __n1 = 0;
2948                     }
2949                 }
2950                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2951             }
2952         }
2953         traits_type::move(__p + __pos, __s, __n2);
2954 __finish:
2955         __sz += __n2 - __n1;
2956         __set_size(__sz);
2957         __invalidate_iterators_past(__sz);
2958         traits_type::assign(__p[__sz], value_type());
2959     }
2960     else
2961         __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s);
2962     return *this;
2963 }
2964
2965 template <class _CharT, class _Traits, class _Allocator>
2966 basic_string<_CharT, _Traits, _Allocator>&
2967 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c)
2968 {
2969     size_type __sz = size();
2970     if (__pos > __sz)
2971         this->__throw_out_of_range();
2972     __n1 = _VSTD::min(__n1, __sz - __pos);
2973     size_type __cap = capacity();
2974     value_type* __p;
2975     if (__cap - __sz + __n1 >= __n2)
2976     {
2977         __p = _VSTD::__to_raw_pointer(__get_pointer());
2978         if (__n1 != __n2)
2979         {
2980             size_type __n_move = __sz - __pos - __n1;
2981             if (__n_move != 0)
2982                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2983         }
2984     }
2985     else
2986     {
2987         __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2);
2988         __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2989     }
2990     traits_type::assign(__p + __pos, __n2, __c);
2991     __sz += __n2 - __n1;
2992     __set_size(__sz);
2993     __invalidate_iterators_past(__sz);
2994     traits_type::assign(__p[__sz], value_type());
2995     return *this;
2996 }
2997
2998 template <class _CharT, class _Traits, class _Allocator>
2999 template<class _InputIterator>
3000 typename enable_if
3001 <
3002     __is_input_iterator<_InputIterator>::value,
3003     basic_string<_CharT, _Traits, _Allocator>&
3004 >::type
3005 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2,
3006                                                    _InputIterator __j1, _InputIterator __j2)
3007 {
3008     for (; true; ++__i1, ++__j1)
3009     {
3010         if (__i1 == __i2)
3011         {
3012             if (__j1 != __j2)
3013                 insert(__i1, __j1, __j2);
3014             break;
3015         }
3016         if (__j1 == __j2)
3017         {
3018             erase(__i1, __i2);
3019             break;
3020         }
3021         traits_type::assign(const_cast<value_type&>(*__i1), *__j1);
3022     }
3023     return *this;
3024 }
3025
3026 template <class _CharT, class _Traits, class _Allocator>
3027 inline _LIBCPP_INLINE_VISIBILITY
3028 basic_string<_CharT, _Traits, _Allocator>&
3029 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str)
3030 {
3031     return replace(__pos1, __n1, __str.data(), __str.size());
3032 }
3033
3034 template <class _CharT, class _Traits, class _Allocator>
3035 basic_string<_CharT, _Traits, _Allocator>&
3036 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str,
3037                                                    size_type __pos2, size_type __n2)
3038 {
3039     size_type __str_sz = __str.size();
3040     if (__pos2 > __str_sz)
3041         this->__throw_out_of_range();
3042     return replace(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, __str_sz - __pos2));
3043 }
3044
3045 template <class _CharT, class _Traits, class _Allocator>
3046 basic_string<_CharT, _Traits, _Allocator>&
3047 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s)
3048 {
3049     _LIBCPP_ASSERT(__s != nullptr, "string::replace received nullptr");
3050     return replace(__pos, __n1, __s, traits_type::length(__s));
3051 }
3052
3053 template <class _CharT, class _Traits, class _Allocator>
3054 inline _LIBCPP_INLINE_VISIBILITY
3055 basic_string<_CharT, _Traits, _Allocator>&
3056 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const basic_string& __str)
3057 {
3058     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1),
3059                    __str.data(), __str.size());
3060 }
3061
3062 template <class _CharT, class _Traits, class _Allocator>
3063 inline _LIBCPP_INLINE_VISIBILITY
3064 basic_string<_CharT, _Traits, _Allocator>&
3065 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n)
3066 {
3067     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n);
3068 }
3069
3070 template <class _CharT, class _Traits, class _Allocator>
3071 inline _LIBCPP_INLINE_VISIBILITY
3072 basic_string<_CharT, _Traits, _Allocator>&
3073 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const value_type* __s)
3074 {
3075     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s);
3076 }
3077
3078 template <class _CharT, class _Traits, class _Allocator>
3079 inline _LIBCPP_INLINE_VISIBILITY
3080 basic_string<_CharT, _Traits, _Allocator>&
3081 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c)
3082 {
3083     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c);
3084 }
3085
3086 // erase
3087
3088 template <class _CharT, class _Traits, class _Allocator>
3089 basic_string<_CharT, _Traits, _Allocator>&
3090 basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos, size_type __n)
3091 {
3092     size_type __sz = size();
3093     if (__pos > __sz)
3094         this->__throw_out_of_range();
3095     if (__n)
3096     {
3097         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
3098         __n = _VSTD::min(__n, __sz - __pos);
3099         size_type __n_move = __sz - __pos - __n;
3100         if (__n_move != 0)
3101             traits_type::move(__p + __pos, __p + __pos + __n, __n_move);
3102         __sz -= __n;
3103         __set_size(__sz);
3104         __invalidate_iterators_past(__sz);
3105         traits_type::assign(__p[__sz], value_type());
3106     }
3107     return *this;
3108 }
3109
3110 template <class _CharT, class _Traits, class _Allocator>
3111 inline _LIBCPP_INLINE_VISIBILITY
3112 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3113 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos)
3114 {
3115 #if _LIBCPP_DEBUG_LEVEL >= 2
3116     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
3117         "string::erase(iterator) called with an iterator not"
3118         " referring to this string");
3119 #endif
3120     _LIBCPP_ASSERT(__pos != end(),
3121         "string::erase(iterator) called with a non-dereferenceable iterator");
3122     iterator __b = begin();
3123     size_type __r = static_cast<size_type>(__pos - __b);
3124     erase(__r, 1);
3125     return __b + static_cast<difference_type>(__r);
3126 }
3127
3128 template <class _CharT, class _Traits, class _Allocator>
3129 inline _LIBCPP_INLINE_VISIBILITY
3130 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3131 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last)
3132 {
3133 #if _LIBCPP_DEBUG_LEVEL >= 2
3134     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
3135         "string::erase(iterator,  iterator) called with an iterator not"
3136         " referring to this string");
3137 #endif
3138     _LIBCPP_ASSERT(__first <= __last, "string::erase(first, last) called with invalid range");
3139     iterator __b = begin();
3140     size_type __r = static_cast<size_type>(__first - __b);
3141     erase(__r, static_cast<size_type>(__last - __first));
3142     return __b + static_cast<difference_type>(__r);
3143 }
3144
3145 template <class _CharT, class _Traits, class _Allocator>
3146 inline _LIBCPP_INLINE_VISIBILITY
3147 void
3148 basic_string<_CharT, _Traits, _Allocator>::pop_back()
3149 {
3150     _LIBCPP_ASSERT(!empty(), "string::pop_back(): string is already empty");
3151     size_type __sz;
3152     if (__is_long())
3153     {
3154         __sz = __get_long_size() - 1;
3155         __set_long_size(__sz);
3156         traits_type::assign(*(__get_long_pointer() + __sz), value_type());
3157     }
3158     else
3159     {
3160         __sz = __get_short_size() - 1;
3161         __set_short_size(__sz);
3162         traits_type::assign(*(__get_short_pointer() + __sz), value_type());
3163     }
3164     __invalidate_iterators_past(__sz);
3165 }
3166
3167 template <class _CharT, class _Traits, class _Allocator>
3168 inline _LIBCPP_INLINE_VISIBILITY
3169 void
3170 basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT
3171 {
3172     __invalidate_all_iterators();
3173     if (__is_long())
3174     {
3175         traits_type::assign(*__get_long_pointer(), value_type());
3176         __set_long_size(0);
3177     }
3178     else
3179     {
3180         traits_type::assign(*__get_short_pointer(), value_type());
3181         __set_short_size(0);
3182     }
3183 }
3184
3185 template <class _CharT, class _Traits, class _Allocator>
3186 inline _LIBCPP_INLINE_VISIBILITY
3187 void
3188 basic_string<_CharT, _Traits, _Allocator>::__erase_to_end(size_type __pos)
3189 {
3190     if (__is_long())
3191     {
3192         traits_type::assign(*(__get_long_pointer() + __pos), value_type());
3193         __set_long_size(__pos);
3194     }
3195     else
3196     {
3197         traits_type::assign(*(__get_short_pointer() + __pos), value_type());
3198         __set_short_size(__pos);
3199     }
3200     __invalidate_iterators_past(__pos);
3201 }
3202
3203 template <class _CharT, class _Traits, class _Allocator>
3204 void
3205 basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
3206 {
3207     size_type __sz = size();
3208     if (__n > __sz)
3209         append(__n - __sz, __c);
3210     else
3211         __erase_to_end(__n);
3212 }
3213
3214 template <class _CharT, class _Traits, class _Allocator>
3215 inline _LIBCPP_INLINE_VISIBILITY
3216 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3217 basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT
3218 {
3219     size_type __m = __alloc_traits::max_size(__alloc());
3220 #if _LIBCPP_BIG_ENDIAN
3221     return (__m <= ~__long_mask ? __m : __m/2) - __alignment;
3222 #else
3223     return __m - __alignment;
3224 #endif
3225 }
3226
3227 template <class _CharT, class _Traits, class _Allocator>
3228 void
3229 basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __res_arg)
3230 {
3231     if (__res_arg > max_size())
3232         this->__throw_length_error();
3233     size_type __cap = capacity();
3234     size_type __sz = size();
3235     __res_arg = _VSTD::max(__res_arg, __sz);
3236     __res_arg = __recommend(__res_arg);
3237     if (__res_arg != __cap)
3238     {
3239         pointer __new_data, __p;
3240         bool __was_long, __now_long;
3241         if (__res_arg == __min_cap - 1)
3242         {
3243             __was_long = true;
3244             __now_long = false;
3245             __new_data = __get_short_pointer();
3246             __p = __get_long_pointer();
3247         }
3248         else
3249         {
3250             if (__res_arg > __cap)
3251                 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
3252             else
3253             {
3254             #ifndef _LIBCPP_NO_EXCEPTIONS
3255                 try
3256                 {
3257             #endif  // _LIBCPP_NO_EXCEPTIONS
3258                     __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
3259             #ifndef _LIBCPP_NO_EXCEPTIONS
3260                 }
3261                 catch (...)
3262                 {
3263                     return;
3264                 }
3265             #else  // _LIBCPP_NO_EXCEPTIONS
3266                 if (__new_data == nullptr)
3267                     return;
3268             #endif  // _LIBCPP_NO_EXCEPTIONS
3269             }
3270             __now_long = true;
3271             __was_long = __is_long();
3272             __p = __get_pointer();
3273         }
3274         traits_type::copy(_VSTD::__to_raw_pointer(__new_data),
3275                           _VSTD::__to_raw_pointer(__p), size()+1);
3276         if (__was_long)
3277             __alloc_traits::deallocate(__alloc(), __p, __cap+1);
3278         if (__now_long)
3279         {
3280             __set_long_cap(__res_arg+1);
3281             __set_long_size(__sz);
3282             __set_long_pointer(__new_data);
3283         }
3284         else
3285             __set_short_size(__sz);
3286         __invalidate_all_iterators();
3287     }
3288 }
3289
3290 template <class _CharT, class _Traits, class _Allocator>
3291 inline _LIBCPP_INLINE_VISIBILITY
3292 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3293 basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) const
3294 {
3295     _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds");
3296     return *(data() + __pos);
3297 }
3298
3299 template <class _CharT, class _Traits, class _Allocator>
3300 inline _LIBCPP_INLINE_VISIBILITY
3301 typename basic_string<_CharT, _Traits, _Allocator>::reference
3302 basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos)
3303 {
3304     _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds");
3305     return *(__get_pointer() + __pos);
3306 }
3307
3308 template <class _CharT, class _Traits, class _Allocator>
3309 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3310 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const
3311 {
3312     if (__n >= size())
3313         this->__throw_out_of_range();
3314     return (*this)[__n];
3315 }
3316
3317 template <class _CharT, class _Traits, class _Allocator>
3318 typename basic_string<_CharT, _Traits, _Allocator>::reference
3319 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n)
3320 {
3321     if (__n >= size())
3322         this->__throw_out_of_range();
3323     return (*this)[__n];
3324 }
3325
3326 template <class _CharT, class _Traits, class _Allocator>
3327 inline _LIBCPP_INLINE_VISIBILITY
3328 typename basic_string<_CharT, _Traits, _Allocator>::reference
3329 basic_string<_CharT, _Traits, _Allocator>::front()
3330 {
3331     _LIBCPP_ASSERT(!empty(), "string::front(): string is empty");
3332     return *__get_pointer();
3333 }
3334
3335 template <class _CharT, class _Traits, class _Allocator>
3336 inline _LIBCPP_INLINE_VISIBILITY
3337 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3338 basic_string<_CharT, _Traits, _Allocator>::front() const
3339 {
3340     _LIBCPP_ASSERT(!empty(), "string::front(): string is empty");
3341     return *data();
3342 }
3343
3344 template <class _CharT, class _Traits, class _Allocator>
3345 inline _LIBCPP_INLINE_VISIBILITY
3346 typename basic_string<_CharT, _Traits, _Allocator>::reference
3347 basic_string<_CharT, _Traits, _Allocator>::back()
3348 {
3349     _LIBCPP_ASSERT(!empty(), "string::back(): string is empty");
3350     return *(__get_pointer() + size() - 1);
3351 }
3352
3353 template <class _CharT, class _Traits, class _Allocator>
3354 inline _LIBCPP_INLINE_VISIBILITY
3355 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3356 basic_string<_CharT, _Traits, _Allocator>::back() const
3357 {
3358     _LIBCPP_ASSERT(!empty(), "string::back(): string is empty");
3359     return *(data() + size() - 1);
3360 }
3361
3362 template <class _CharT, class _Traits, class _Allocator>
3363 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3364 basic_string<_CharT, _Traits, _Allocator>::copy(value_type* __s, size_type __n, size_type __pos) const
3365 {
3366     size_type __sz = size();
3367     if (__pos > __sz)
3368         this->__throw_out_of_range();
3369     size_type __rlen = _VSTD::min(__n, __sz - __pos);
3370     traits_type::copy(__s, data() + __pos, __rlen);
3371     return __rlen;
3372 }
3373
3374 template <class _CharT, class _Traits, class _Allocator>
3375 inline _LIBCPP_INLINE_VISIBILITY
3376 basic_string<_CharT, _Traits, _Allocator>
3377 basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const
3378 {
3379     return basic_string(*this, __pos, __n, __alloc());
3380 }
3381
3382 template <class _CharT, class _Traits, class _Allocator>
3383 inline _LIBCPP_INLINE_VISIBILITY
3384 void
3385 basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str)
3386 #if _LIBCPP_STD_VER >= 14
3387         _NOEXCEPT
3388 #else
3389         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3390                     __is_nothrow_swappable<allocator_type>::value)
3391 #endif
3392 {
3393 #if _LIBCPP_DEBUG_LEVEL >= 2
3394     if (!__is_long())
3395         __get_db()->__invalidate_all(this);
3396     if (!__str.__is_long())
3397         __get_db()->__invalidate_all(&__str);
3398     __get_db()->swap(this, &__str);
3399 #endif
3400     _VSTD::swap(__r_.first(), __str.__r_.first());
3401     __swap_allocator(__alloc(), __str.__alloc());
3402 }
3403
3404 // find
3405
3406 template <class _Traits>
3407 struct _LIBCPP_HIDDEN __traits_eq
3408 {
3409     typedef typename _Traits::char_type char_type;
3410     _LIBCPP_INLINE_VISIBILITY
3411     bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT
3412         {return _Traits::eq(__x, __y);}
3413 };
3414
3415 template<class _CharT, class _Traits, class _Allocator>
3416 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3417 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3418                                                 size_type __pos,
3419                                                 size_type __n) const _NOEXCEPT
3420 {
3421     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find(): received nullptr");
3422     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3423         (data(), size(), __s, __pos, __n);
3424 }
3425
3426 template<class _CharT, class _Traits, class _Allocator>
3427 inline _LIBCPP_INLINE_VISIBILITY
3428 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3429 basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str,
3430                                                 size_type __pos) const _NOEXCEPT
3431 {
3432     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3433         (data(), size(), __str.data(), __pos, __str.size());
3434 }
3435
3436 template<class _CharT, class _Traits, class _Allocator>
3437 inline _LIBCPP_INLINE_VISIBILITY
3438 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3439 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3440                                                 size_type __pos) const _NOEXCEPT
3441 {
3442     _LIBCPP_ASSERT(__s != nullptr, "string::find(): received nullptr");
3443     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3444         (data(), size(), __s, __pos, traits_type::length(__s));
3445 }
3446
3447 template<class _CharT, class _Traits, class _Allocator>
3448 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3449 basic_string<_CharT, _Traits, _Allocator>::find(value_type __c,
3450                                                 size_type __pos) const _NOEXCEPT
3451 {
3452     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3453         (data(), size(), __c, __pos);
3454 }
3455
3456 // rfind
3457
3458 template<class _CharT, class _Traits, class _Allocator>
3459 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3460 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3461                                                  size_type __pos,
3462                                                  size_type __n) const _NOEXCEPT
3463 {
3464     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::rfind(): received nullptr");
3465     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3466         (data(), size(), __s, __pos, __n);
3467 }
3468
3469 template<class _CharT, class _Traits, class _Allocator>
3470 inline _LIBCPP_INLINE_VISIBILITY
3471 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3472 basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str,
3473                                                  size_type __pos) const _NOEXCEPT
3474 {
3475     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3476         (data(), size(), __str.data(), __pos, __str.size());
3477 }
3478
3479 template<class _CharT, class _Traits, class _Allocator>
3480 inline _LIBCPP_INLINE_VISIBILITY
3481 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3482 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3483                                                  size_type __pos) const _NOEXCEPT
3484 {
3485     _LIBCPP_ASSERT(__s != nullptr, "string::rfind(): received nullptr");
3486     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3487         (data(), size(), __s, __pos, traits_type::length(__s));
3488 }
3489
3490 template<class _CharT, class _Traits, class _Allocator>
3491 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3492 basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c,
3493                                                  size_type __pos) const _NOEXCEPT
3494 {
3495     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3496         (data(), size(), __c, __pos);
3497 }
3498
3499 // find_first_of
3500
3501 template<class _CharT, class _Traits, class _Allocator>
3502 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3503 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3504                                                          size_type __pos,
3505                                                          size_type __n) const _NOEXCEPT
3506 {
3507     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_of(): received nullptr");
3508     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3509         (data(), size(), __s, __pos, __n);
3510 }
3511
3512 template<class _CharT, class _Traits, class _Allocator>
3513 inline _LIBCPP_INLINE_VISIBILITY
3514 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3515 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str,
3516                                                          size_type __pos) const _NOEXCEPT
3517 {
3518     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3519         (data(), size(), __str.data(), __pos, __str.size());
3520 }
3521
3522 template<class _CharT, class _Traits, class _Allocator>
3523 inline _LIBCPP_INLINE_VISIBILITY
3524 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3525 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3526                                                          size_type __pos) const _NOEXCEPT
3527 {
3528     _LIBCPP_ASSERT(__s != nullptr, "string::find_first_of(): received nullptr");
3529     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3530         (data(), size(), __s, __pos, traits_type::length(__s));
3531 }
3532
3533 template<class _CharT, class _Traits, class _Allocator>
3534 inline _LIBCPP_INLINE_VISIBILITY
3535 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3536 basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c,
3537                                                          size_type __pos) const _NOEXCEPT
3538 {
3539     return find(__c, __pos);
3540 }
3541
3542 // find_last_of
3543
3544 template<class _CharT, class _Traits, class _Allocator>
3545 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3546 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3547                                                         size_type __pos,
3548                                                         size_type __n) const _NOEXCEPT
3549 {
3550     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_of(): received nullptr");
3551     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3552         (data(), size(), __s, __pos, __n);
3553 }
3554
3555 template<class _CharT, class _Traits, class _Allocator>
3556 inline _LIBCPP_INLINE_VISIBILITY
3557 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3558 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str,
3559                                                         size_type __pos) const _NOEXCEPT
3560 {
3561     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3562         (data(), size(), __str.data(), __pos, __str.size());
3563 }
3564
3565 template<class _CharT, class _Traits, class _Allocator>
3566 inline _LIBCPP_INLINE_VISIBILITY
3567 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3568 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3569                                                         size_type __pos) const _NOEXCEPT
3570 {
3571     _LIBCPP_ASSERT(__s != nullptr, "string::find_last_of(): received nullptr");
3572     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3573         (data(), size(), __s, __pos, traits_type::length(__s));
3574 }
3575
3576 template<class _CharT, class _Traits, class _Allocator>
3577 inline _LIBCPP_INLINE_VISIBILITY
3578 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3579 basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c,
3580                                                         size_type __pos) const _NOEXCEPT
3581 {
3582     return rfind(__c, __pos);
3583 }
3584
3585 // find_first_not_of
3586
3587 template<class _CharT, class _Traits, class _Allocator>
3588 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3589 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3590                                                              size_type __pos,
3591                                                              size_type __n) const _NOEXCEPT
3592 {
3593     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_not_of(): received nullptr");
3594     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3595         (data(), size(), __s, __pos, __n);
3596 }
3597
3598 template<class _CharT, class _Traits, class _Allocator>
3599 inline _LIBCPP_INLINE_VISIBILITY
3600 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3601 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str,
3602                                                              size_type __pos) const _NOEXCEPT
3603 {
3604     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3605         (data(), size(), __str.data(), __pos, __str.size());
3606 }
3607
3608 template<class _CharT, class _Traits, class _Allocator>
3609 inline _LIBCPP_INLINE_VISIBILITY
3610 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3611 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3612                                                              size_type __pos) const _NOEXCEPT
3613 {
3614     _LIBCPP_ASSERT(__s != nullptr, "string::find_first_not_of(): received nullptr");
3615     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3616         (data(), size(), __s, __pos, traits_type::length(__s));
3617 }
3618
3619 template<class _CharT, class _Traits, class _Allocator>
3620 inline _LIBCPP_INLINE_VISIBILITY
3621 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3622 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c,
3623                                                              size_type __pos) const _NOEXCEPT
3624 {
3625     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3626         (data(), size(), __c, __pos);
3627 }
3628
3629 // find_last_not_of
3630
3631 template<class _CharT, class _Traits, class _Allocator>
3632 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3633 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3634                                                             size_type __pos,
3635                                                             size_type __n) const _NOEXCEPT
3636 {
3637     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_not_of(): received nullptr");
3638     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3639         (data(), size(), __s, __pos, __n);
3640 }
3641
3642 template<class _CharT, class _Traits, class _Allocator>
3643 inline _LIBCPP_INLINE_VISIBILITY
3644 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3645 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str,
3646                                                             size_type __pos) const _NOEXCEPT
3647 {
3648     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3649         (data(), size(), __str.data(), __pos, __str.size());
3650 }
3651
3652 template<class _CharT, class _Traits, class _Allocator>
3653 inline _LIBCPP_INLINE_VISIBILITY
3654 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3655 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3656                                                             size_type __pos) const _NOEXCEPT
3657 {
3658     _LIBCPP_ASSERT(__s != nullptr, "string::find_last_not_of(): received nullptr");
3659     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3660         (data(), size(), __s, __pos, traits_type::length(__s));
3661 }
3662
3663 template<class _CharT, class _Traits, class _Allocator>
3664 inline _LIBCPP_INLINE_VISIBILITY
3665 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3666 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c,
3667                                                             size_type __pos) const _NOEXCEPT
3668 {
3669     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3670         (data(), size(), __c, __pos);
3671 }
3672
3673 // compare
3674
3675 template <class _CharT, class _Traits, class _Allocator>
3676 inline _LIBCPP_INLINE_VISIBILITY
3677 int
3678 basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT
3679 {
3680     size_t __lhs_sz = size();
3681     size_t __rhs_sz = __str.size();
3682     int __result = traits_type::compare(data(), __str.data(),
3683                                         _VSTD::min(__lhs_sz, __rhs_sz));
3684     if (__result != 0)
3685         return __result;
3686     if (__lhs_sz < __rhs_sz)
3687         return -1;
3688     if (__lhs_sz > __rhs_sz)
3689         return 1;
3690     return 0;
3691 }
3692
3693 template <class _CharT, class _Traits, class _Allocator>
3694 inline _LIBCPP_INLINE_VISIBILITY
3695 int
3696 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3697                                                    size_type __n1,
3698                                                    const basic_string& __str) const
3699 {
3700     return compare(__pos1, __n1, __str.data(), __str.size());
3701 }
3702
3703 template <class _CharT, class _Traits, class _Allocator>
3704 int
3705 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3706                                                    size_type __n1,
3707                                                    const basic_string& __str,
3708                                                    size_type __pos2,
3709                                                    size_type __n2) const
3710 {
3711     size_type __sz = __str.size();
3712     if (__pos2 > __sz)
3713         this->__throw_out_of_range();
3714     return compare(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2,
3715                                                                   __sz - __pos2));
3716 }
3717
3718 template <class _CharT, class _Traits, class _Allocator>
3719 int
3720 basic_string<_CharT, _Traits, _Allocator>::compare(const value_type* __s) const _NOEXCEPT
3721 {
3722     _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr");
3723     return compare(0, npos, __s, traits_type::length(__s));
3724 }
3725
3726 template <class _CharT, class _Traits, class _Allocator>
3727 int
3728 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3729                                                    size_type __n1,
3730                                                    const value_type* __s) const
3731 {
3732     _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr");
3733     return compare(__pos1, __n1, __s, traits_type::length(__s));
3734 }
3735
3736 template <class _CharT, class _Traits, class _Allocator>
3737 int
3738 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3739                                                    size_type __n1,
3740                                                    const value_type* __s,
3741                                                    size_type __n2) const
3742 {
3743     _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::compare(): received nullptr");
3744     size_type __sz = size();
3745     if (__pos1 > __sz || __n2 == npos)
3746         this->__throw_out_of_range();
3747     size_type __rlen = _VSTD::min(__n1, __sz - __pos1);
3748     int __r = traits_type::compare(data() + __pos1, __s, _VSTD::min(__rlen, __n2));
3749     if (__r == 0)
3750     {
3751         if (__rlen < __n2)
3752             __r = -1;
3753         else if (__rlen > __n2)
3754             __r = 1;
3755     }
3756     return __r;
3757 }
3758
3759 // __invariants
3760
3761 template<class _CharT, class _Traits, class _Allocator>
3762 inline _LIBCPP_INLINE_VISIBILITY
3763 bool
3764 basic_string<_CharT, _Traits, _Allocator>::__invariants() const
3765 {
3766     if (size() > capacity())
3767         return false;
3768     if (capacity() < __min_cap - 1)
3769         return false;
3770     if (data() == 0)
3771         return false;
3772     if (data()[size()] != value_type(0))
3773         return false;
3774     return true;
3775 }
3776
3777 // operator==
3778
3779 template<class _CharT, class _Traits, class _Allocator>
3780 inline _LIBCPP_INLINE_VISIBILITY
3781 bool
3782 operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3783            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3784 {
3785     size_t __lhs_sz = __lhs.size();
3786     return __lhs_sz == __rhs.size() && _Traits::compare(__lhs.data(),
3787                                                         __rhs.data(),
3788                                                         __lhs_sz) == 0;
3789 }
3790
3791 template<class _Allocator>
3792 inline _LIBCPP_INLINE_VISIBILITY
3793 bool
3794 operator==(const basic_string<char, char_traits<char>, _Allocator>& __lhs,
3795            const basic_string<char, char_traits<char>, _Allocator>& __rhs) _NOEXCEPT
3796 {
3797     size_t __lhs_sz = __lhs.size();
3798     if (__lhs_sz != __rhs.size())
3799         return false;
3800     const char* __lp = __lhs.data();
3801     const char* __rp = __rhs.data();
3802     if (__lhs.__is_long())
3803         return char_traits<char>::compare(__lp, __rp, __lhs_sz) == 0;
3804     for (; __lhs_sz != 0; --__lhs_sz, ++__lp, ++__rp)
3805         if (*__lp != *__rp)
3806             return false;
3807     return true;
3808 }
3809
3810 template<class _CharT, class _Traits, class _Allocator>
3811 inline _LIBCPP_INLINE_VISIBILITY
3812 bool
3813 operator==(const _CharT* __lhs,
3814            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3815 {
3816     typedef basic_string<_CharT, _Traits, _Allocator> _String;
3817     _LIBCPP_ASSERT(__lhs != nullptr, "operator==(char*, basic_string): received nullptr");
3818     size_t __lhs_len = _Traits::length(__lhs);
3819     if (__lhs_len != __rhs.size()) return false;
3820     return __rhs.compare(0, _String::npos, __lhs, __lhs_len) == 0;
3821 }
3822
3823 template<class _CharT, class _Traits, class _Allocator>
3824 inline _LIBCPP_INLINE_VISIBILITY
3825 bool
3826 operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3827            const _CharT* __rhs) _NOEXCEPT
3828 {
3829     typedef basic_string<_CharT, _Traits, _Allocator> _String;
3830     _LIBCPP_ASSERT(__rhs != nullptr, "operator==(basic_string, char*): received nullptr");
3831     size_t __rhs_len = _Traits::length(__rhs);
3832     if (__rhs_len != __lhs.size()) return false;
3833     return __lhs.compare(0, _String::npos, __rhs, __rhs_len) == 0;
3834 }
3835
3836 // operator!=
3837
3838 template<class _CharT, class _Traits, class _Allocator>
3839 inline _LIBCPP_INLINE_VISIBILITY
3840 bool
3841 operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3842            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3843 {
3844     return !(__lhs == __rhs);
3845 }
3846
3847 template<class _CharT, class _Traits, class _Allocator>
3848 inline _LIBCPP_INLINE_VISIBILITY
3849 bool
3850 operator!=(const _CharT* __lhs,
3851            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3852 {
3853     return !(__lhs == __rhs);
3854 }
3855
3856 template<class _CharT, class _Traits, class _Allocator>
3857 inline _LIBCPP_INLINE_VISIBILITY
3858 bool
3859 operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3860            const _CharT* __rhs) _NOEXCEPT
3861 {
3862     return !(__lhs == __rhs);
3863 }
3864
3865 // operator<
3866
3867 template<class _CharT, class _Traits, class _Allocator>
3868 inline _LIBCPP_INLINE_VISIBILITY
3869 bool
3870 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3871            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3872 {
3873     return __lhs.compare(__rhs) < 0;
3874 }
3875
3876 template<class _CharT, class _Traits, class _Allocator>
3877 inline _LIBCPP_INLINE_VISIBILITY
3878 bool
3879 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3880            const _CharT* __rhs) _NOEXCEPT
3881 {
3882     return __lhs.compare(__rhs) < 0;
3883 }
3884
3885 template<class _CharT, class _Traits, class _Allocator>
3886 inline _LIBCPP_INLINE_VISIBILITY
3887 bool
3888 operator< (const _CharT* __lhs,
3889            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3890 {
3891     return __rhs.compare(__lhs) > 0;
3892 }
3893
3894 // operator>
3895
3896 template<class _CharT, class _Traits, class _Allocator>
3897 inline _LIBCPP_INLINE_VISIBILITY
3898 bool
3899 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3900            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3901 {
3902     return __rhs < __lhs;
3903 }
3904
3905 template<class _CharT, class _Traits, class _Allocator>
3906 inline _LIBCPP_INLINE_VISIBILITY
3907 bool
3908 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3909            const _CharT* __rhs) _NOEXCEPT
3910 {
3911     return __rhs < __lhs;
3912 }
3913
3914 template<class _CharT, class _Traits, class _Allocator>
3915 inline _LIBCPP_INLINE_VISIBILITY
3916 bool
3917 operator> (const _CharT* __lhs,
3918            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3919 {
3920     return __rhs < __lhs;
3921 }
3922
3923 // operator<=
3924
3925 template<class _CharT, class _Traits, class _Allocator>
3926 inline _LIBCPP_INLINE_VISIBILITY
3927 bool
3928 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3929            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3930 {
3931     return !(__rhs < __lhs);
3932 }
3933
3934 template<class _CharT, class _Traits, class _Allocator>
3935 inline _LIBCPP_INLINE_VISIBILITY
3936 bool
3937 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3938            const _CharT* __rhs) _NOEXCEPT
3939 {
3940     return !(__rhs < __lhs);
3941 }
3942
3943 template<class _CharT, class _Traits, class _Allocator>
3944 inline _LIBCPP_INLINE_VISIBILITY
3945 bool
3946 operator<=(const _CharT* __lhs,
3947            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3948 {
3949     return !(__rhs < __lhs);
3950 }
3951
3952 // operator>=
3953
3954 template<class _CharT, class _Traits, class _Allocator>
3955 inline _LIBCPP_INLINE_VISIBILITY
3956 bool
3957 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3958            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3959 {
3960     return !(__lhs < __rhs);
3961 }
3962
3963 template<class _CharT, class _Traits, class _Allocator>
3964 inline _LIBCPP_INLINE_VISIBILITY
3965 bool
3966 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3967            const _CharT* __rhs) _NOEXCEPT
3968 {
3969     return !(__lhs < __rhs);
3970 }
3971
3972 template<class _CharT, class _Traits, class _Allocator>
3973 inline _LIBCPP_INLINE_VISIBILITY
3974 bool
3975 operator>=(const _CharT* __lhs,
3976            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3977 {
3978     return !(__lhs < __rhs);
3979 }
3980
3981 // operator +
3982
3983 template<class _CharT, class _Traits, class _Allocator>
3984 basic_string<_CharT, _Traits, _Allocator>
3985 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3986           const basic_string<_CharT, _Traits, _Allocator>& __rhs)
3987 {
3988     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3989     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3990     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3991     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
3992     __r.append(__rhs.data(), __rhs_sz);
3993     return __r;
3994 }
3995
3996 template<class _CharT, class _Traits, class _Allocator>
3997 basic_string<_CharT, _Traits, _Allocator>
3998 operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs)
3999 {
4000     basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
4001     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = _Traits::length(__lhs);
4002     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
4003     __r.__init(__lhs, __lhs_sz, __lhs_sz + __rhs_sz);
4004     __r.append(__rhs.data(), __rhs_sz);
4005     return __r;
4006 }
4007
4008 template<class _CharT, class _Traits, class _Allocator>
4009 basic_string<_CharT, _Traits, _Allocator>
4010 operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs)
4011 {
4012     basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
4013     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
4014     __r.__init(&__lhs, 1, 1 + __rhs_sz);
4015     __r.append(__rhs.data(), __rhs_sz);
4016     return __r;
4017 }
4018
4019 template<class _CharT, class _Traits, class _Allocator>
4020 basic_string<_CharT, _Traits, _Allocator>
4021 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs)
4022 {
4023     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
4024     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
4025     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = _Traits::length(__rhs);
4026     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
4027     __r.append(__rhs, __rhs_sz);
4028     return __r;
4029 }
4030
4031 template<class _CharT, class _Traits, class _Allocator>
4032 basic_string<_CharT, _Traits, _Allocator>
4033 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs)
4034 {
4035     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
4036     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
4037     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + 1);
4038     __r.push_back(__rhs);
4039     return __r;
4040 }
4041
4042 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4043
4044 template<class _CharT, class _Traits, class _Allocator>
4045 inline _LIBCPP_INLINE_VISIBILITY
4046 basic_string<_CharT, _Traits, _Allocator>
4047 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs)
4048 {
4049     return _VSTD::move(__lhs.append(__rhs));
4050 }
4051
4052 template<class _CharT, class _Traits, class _Allocator>
4053 inline _LIBCPP_INLINE_VISIBILITY
4054 basic_string<_CharT, _Traits, _Allocator>
4055 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4056 {
4057     return _VSTD::move(__rhs.insert(0, __lhs));
4058 }
4059
4060 template<class _CharT, class _Traits, class _Allocator>
4061 inline _LIBCPP_INLINE_VISIBILITY
4062 basic_string<_CharT, _Traits, _Allocator>
4063 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4064 {
4065     return _VSTD::move(__lhs.append(__rhs));
4066 }
4067
4068 template<class _CharT, class _Traits, class _Allocator>
4069 inline _LIBCPP_INLINE_VISIBILITY
4070 basic_string<_CharT, _Traits, _Allocator>
4071 operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4072 {
4073     return _VSTD::move(__rhs.insert(0, __lhs));
4074 }
4075
4076 template<class _CharT, class _Traits, class _Allocator>
4077 inline _LIBCPP_INLINE_VISIBILITY
4078 basic_string<_CharT, _Traits, _Allocator>
4079 operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4080 {
4081     __rhs.insert(__rhs.begin(), __lhs);
4082     return _VSTD::move(__rhs);
4083 }
4084
4085 template<class _CharT, class _Traits, class _Allocator>
4086 inline _LIBCPP_INLINE_VISIBILITY
4087 basic_string<_CharT, _Traits, _Allocator>
4088 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const _CharT* __rhs)
4089 {
4090     return _VSTD::move(__lhs.append(__rhs));
4091 }
4092
4093 template<class _CharT, class _Traits, class _Allocator>
4094 inline _LIBCPP_INLINE_VISIBILITY
4095 basic_string<_CharT, _Traits, _Allocator>
4096 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs)
4097 {
4098     __lhs.push_back(__rhs);
4099     return _VSTD::move(__lhs);
4100 }
4101
4102 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4103
4104 // swap
4105
4106 template<class _CharT, class _Traits, class _Allocator>
4107 inline _LIBCPP_INLINE_VISIBILITY
4108 void
4109 swap(basic_string<_CharT, _Traits, _Allocator>& __lhs,
4110      basic_string<_CharT, _Traits, _Allocator>& __rhs)
4111      _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs)))
4112 {
4113     __lhs.swap(__rhs);
4114 }
4115
4116 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
4117
4118 typedef basic_string<char16_t> u16string;
4119 typedef basic_string<char32_t> u32string;
4120
4121 #endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
4122
4123 _LIBCPP_FUNC_VIS int                stoi  (const string& __str, size_t* __idx = 0, int __base = 10);
4124 _LIBCPP_FUNC_VIS long               stol  (const string& __str, size_t* __idx = 0, int __base = 10);
4125 _LIBCPP_FUNC_VIS unsigned long      stoul (const string& __str, size_t* __idx = 0, int __base = 10);
4126 _LIBCPP_FUNC_VIS long long          stoll (const string& __str, size_t* __idx = 0, int __base = 10);
4127 _LIBCPP_FUNC_VIS unsigned long long stoull(const string& __str, size_t* __idx = 0, int __base = 10);
4128
4129 _LIBCPP_FUNC_VIS float       stof (const string& __str, size_t* __idx = 0);
4130 _LIBCPP_FUNC_VIS double      stod (const string& __str, size_t* __idx = 0);
4131 _LIBCPP_FUNC_VIS long double stold(const string& __str, size_t* __idx = 0);
4132
4133 _LIBCPP_FUNC_VIS string to_string(int __val);
4134 _LIBCPP_FUNC_VIS string to_string(unsigned __val);
4135 _LIBCPP_FUNC_VIS string to_string(long __val);
4136 _LIBCPP_FUNC_VIS string to_string(unsigned long __val);
4137 _LIBCPP_FUNC_VIS string to_string(long long __val);
4138 _LIBCPP_FUNC_VIS string to_string(unsigned long long __val);
4139 _LIBCPP_FUNC_VIS string to_string(float __val);
4140 _LIBCPP_FUNC_VIS string to_string(double __val);
4141 _LIBCPP_FUNC_VIS string to_string(long double __val);
4142
4143 _LIBCPP_FUNC_VIS int                stoi  (const wstring& __str, size_t* __idx = 0, int __base = 10);
4144 _LIBCPP_FUNC_VIS long               stol  (const wstring& __str, size_t* __idx = 0, int __base = 10);
4145 _LIBCPP_FUNC_VIS unsigned long      stoul (const wstring& __str, size_t* __idx = 0, int __base = 10);
4146 _LIBCPP_FUNC_VIS long long          stoll (const wstring& __str, size_t* __idx = 0, int __base = 10);
4147 _LIBCPP_FUNC_VIS unsigned long long stoull(const wstring& __str, size_t* __idx = 0, int __base = 10);
4148
4149 _LIBCPP_FUNC_VIS float       stof (const wstring& __str, size_t* __idx = 0);
4150 _LIBCPP_FUNC_VIS double      stod (const wstring& __str, size_t* __idx = 0);
4151 _LIBCPP_FUNC_VIS long double stold(const wstring& __str, size_t* __idx = 0);
4152
4153 _LIBCPP_FUNC_VIS wstring to_wstring(int __val);
4154 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned __val);
4155 _LIBCPP_FUNC_VIS wstring to_wstring(long __val);
4156 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned long __val);
4157 _LIBCPP_FUNC_VIS wstring to_wstring(long long __val);
4158 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned long long __val);
4159 _LIBCPP_FUNC_VIS wstring to_wstring(float __val);
4160 _LIBCPP_FUNC_VIS wstring to_wstring(double __val);
4161 _LIBCPP_FUNC_VIS wstring to_wstring(long double __val);
4162
4163 template<class _CharT, class _Traits, class _Allocator>
4164     const typename basic_string<_CharT, _Traits, _Allocator>::size_type
4165                    basic_string<_CharT, _Traits, _Allocator>::npos;
4166
4167 template<class _CharT, class _Traits, class _Allocator>
4168 struct _LIBCPP_TYPE_VIS_ONLY hash<basic_string<_CharT, _Traits, _Allocator> >
4169     : public unary_function<basic_string<_CharT, _Traits, _Allocator>, size_t>
4170 {
4171     size_t
4172         operator()(const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT;
4173 };
4174
4175 template<class _CharT, class _Traits, class _Allocator>
4176 size_t
4177 hash<basic_string<_CharT, _Traits, _Allocator> >::operator()(
4178         const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT
4179 {
4180     return __do_string_hash(__val.data(), __val.data() + __val.size());
4181 }
4182
4183 template<class _CharT, class _Traits, class _Allocator>
4184 basic_ostream<_CharT, _Traits>&
4185 operator<<(basic_ostream<_CharT, _Traits>& __os,
4186            const basic_string<_CharT, _Traits, _Allocator>& __str);
4187
4188 template<class _CharT, class _Traits, class _Allocator>
4189 basic_istream<_CharT, _Traits>&
4190 operator>>(basic_istream<_CharT, _Traits>& __is,
4191            basic_string<_CharT, _Traits, _Allocator>& __str);
4192
4193 template<class _CharT, class _Traits, class _Allocator>
4194 basic_istream<_CharT, _Traits>&
4195 getline(basic_istream<_CharT, _Traits>& __is,
4196         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
4197
4198 template<class _CharT, class _Traits, class _Allocator>
4199 inline _LIBCPP_INLINE_VISIBILITY
4200 basic_istream<_CharT, _Traits>&
4201 getline(basic_istream<_CharT, _Traits>& __is,
4202         basic_string<_CharT, _Traits, _Allocator>& __str);
4203
4204 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4205
4206 template<class _CharT, class _Traits, class _Allocator>
4207 inline _LIBCPP_INLINE_VISIBILITY
4208 basic_istream<_CharT, _Traits>&
4209 getline(basic_istream<_CharT, _Traits>&& __is,
4210         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
4211
4212 template<class _CharT, class _Traits, class _Allocator>
4213 inline _LIBCPP_INLINE_VISIBILITY
4214 basic_istream<_CharT, _Traits>&
4215 getline(basic_istream<_CharT, _Traits>&& __is,
4216         basic_string<_CharT, _Traits, _Allocator>& __str);
4217
4218 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4219
4220 #if _LIBCPP_DEBUG_LEVEL >= 2
4221
4222 template<class _CharT, class _Traits, class _Allocator>
4223 bool
4224 basic_string<_CharT, _Traits, _Allocator>::__dereferenceable(const const_iterator* __i) const
4225 {
4226     return this->data() <= _VSTD::__to_raw_pointer(__i->base()) &&
4227            _VSTD::__to_raw_pointer(__i->base()) < this->data() + this->size();
4228 }
4229
4230 template<class _CharT, class _Traits, class _Allocator>
4231 bool
4232 basic_string<_CharT, _Traits, _Allocator>::__decrementable(const const_iterator* __i) const
4233 {
4234     return this->data() < _VSTD::__to_raw_pointer(__i->base()) &&
4235            _VSTD::__to_raw_pointer(__i->base()) <= this->data() + this->size();
4236 }
4237
4238 template<class _CharT, class _Traits, class _Allocator>
4239 bool
4240 basic_string<_CharT, _Traits, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
4241 {
4242     const value_type* __p = _VSTD::__to_raw_pointer(__i->base()) + __n;
4243     return this->data() <= __p && __p <= this->data() + this->size();
4244 }
4245
4246 template<class _CharT, class _Traits, class _Allocator>
4247 bool
4248 basic_string<_CharT, _Traits, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
4249 {
4250     const value_type* __p = _VSTD::__to_raw_pointer(__i->base()) + __n;
4251     return this->data() <= __p && __p < this->data() + this->size();
4252 }
4253
4254 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
4255
4256 #if _LIBCPP_STD_VER > 11
4257 // Literal suffixes for basic_string [basic.string.literals]
4258 inline namespace literals
4259 {
4260   inline namespace string_literals
4261   {
4262     inline _LIBCPP_INLINE_VISIBILITY
4263     basic_string<char> operator "" s( const char *__str, size_t __len )
4264     {
4265         return basic_string<char> (__str, __len);
4266     }
4267
4268     inline _LIBCPP_INLINE_VISIBILITY
4269     basic_string<wchar_t> operator "" s( const wchar_t *__str, size_t __len )
4270     {
4271         return basic_string<wchar_t> (__str, __len);
4272     }
4273
4274     inline _LIBCPP_INLINE_VISIBILITY
4275     basic_string<char16_t> operator "" s( const char16_t *__str, size_t __len )
4276     {
4277         return basic_string<char16_t> (__str, __len);
4278     }
4279
4280     inline _LIBCPP_INLINE_VISIBILITY
4281     basic_string<char32_t> operator "" s( const char32_t *__str, size_t __len )
4282     {
4283         return basic_string<char32_t> (__str, __len);
4284     }
4285   }
4286 }
4287 #endif
4288
4289 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<char>)
4290 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<wchar_t>)
4291 _LIBCPP_EXTERN_TEMPLATE(string operator+<char, char_traits<char>, allocator<char> >(char const*, string const&))
4292
4293 _LIBCPP_END_NAMESPACE_STD
4294
4295 #endif  // _LIBCPP_STRING