contrib/libc++/include/string

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