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