contrib/libc++/include/string

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