external/bsd/libc++/dist/libcxx/include/string

   1 // -*- C++ -*-
   2 //===--------------------------- string -----------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_STRING
  12 #define _LIBCPP_STRING
  13
  14 /*
  15     string synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class stateT>
  21 class fpos
  22 {
  23 private:
  24     stateT st;
  25 public:
  26     fpos(streamoff = streamoff());
  27
  28     operator streamoff() const;
  29
  30     stateT state() const;
  31     void state(stateT);
  32
  33     fpos& operator+=(streamoff);
  34     fpos  operator+ (streamoff) const;
  35     fpos& operator-=(streamoff);
  36     fpos  operator- (streamoff) const;
  37 };
  38
  39 template <class stateT> streamoff operator-(const fpos<stateT>& x, const fpos<stateT>& y);
  40
  41 template <class stateT> bool operator==(const fpos<stateT>& x, const fpos<stateT>& y);
  42 template <class stateT> bool operator!=(const fpos<stateT>& x, const fpos<stateT>& y);
  43
  44 template <class charT>
  45 struct char_traits
  46 {
  47     typedef charT     char_type;
  48     typedef ...       int_type;
  49     typedef streamoff off_type;
  50     typedef streampos pos_type;
  51     typedef mbstate_t state_type;
  52
  53     static void assign(char_type& c1, const char_type& c2) noexcept;
  54     static constexpr bool eq(char_type c1, char_type c2) noexcept;
  55     static constexpr bool lt(char_type c1, char_type c2) noexcept;
  56
  57     static int              compare(const char_type* s1, const char_type* s2, size_t n);
  58     static size_t           length(const char_type* s);
  59     static const char_type* find(const char_type* s, size_t n, const char_type& a);
  60     static char_type*       move(char_type* s1, const char_type* s2, size_t n);
  61     static char_type*       copy(char_type* s1, const char_type* s2, size_t n);
  62     static char_type*       assign(char_type* s, size_t n, char_type a);
  63
  64     static constexpr int_type  not_eof(int_type c) noexcept;
  65     static constexpr char_type to_char_type(int_type c) noexcept;
  66     static constexpr int_type  to_int_type(char_type c) noexcept;
  67     static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;
  68     static constexpr int_type  eof() noexcept;
  69 };
  70
  71 template <> struct char_traits<char>;
  72 template <> struct char_traits<wchar_t>;
  73
  74 template<class charT, class traits = char_traits<charT>, class Allocator = allocator<charT> >
  75 class basic_string
  76 {
  77 public:
  78 // types:
  79     typedef traits traits_type;
  80     typedef typename traits_type::char_type value_type;
  81     typedef Allocator allocator_type;
  82     typedef typename allocator_type::size_type size_type;
  83     typedef typename allocator_type::difference_type difference_type;
  84     typedef typename allocator_type::reference reference;
  85     typedef typename allocator_type::const_reference const_reference;
  86     typedef typename allocator_type::pointer pointer;
  87     typedef typename allocator_type::const_pointer const_pointer;
  88     typedef implementation-defined iterator;
  89     typedef implementation-defined const_iterator;
  90     typedef std::reverse_iterator<iterator> reverse_iterator;
  91     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  92
  93     static const size_type npos = -1;
  94
  95     basic_string()
  96         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  97     explicit basic_string(const allocator_type& a);
  98     basic_string(const basic_string& str);
  99     basic_string(basic_string&& str)
 100         noexcept(is_nothrow_move_constructible<allocator_type>::value);
 101     basic_string(const basic_string& str, size_type pos, size_type n = npos,
 102                  const allocator_type& a = allocator_type());
 103     basic_string(const value_type* s, const allocator_type& a = allocator_type());
 104     basic_string(const value_type* s, size_type n, const allocator_type& a = allocator_type());
 105     basic_string(size_type n, value_type c, const allocator_type& a = allocator_type());
 106     template<class InputIterator>
 107         basic_string(InputIterator begin, InputIterator end,
 108                      const allocator_type& a = allocator_type());
 109     basic_string(initializer_list<value_type>, const Allocator& = Allocator());
 110     basic_string(const basic_string&, const Allocator&);
 111     basic_string(basic_string&&, const Allocator&);
 112
 113     ~basic_string();
 114
 115     basic_string& operator=(const basic_string& str);
 116     basic_string& operator=(basic_string&& str)
 117         noexcept(
 118              allocator_type::propagate_on_container_move_assignment::value ||
 119              allocator_type::is_always_equal::value ); // C++17
 120     basic_string& operator=(const value_type* s);
 121     basic_string& operator=(value_type c);
 122     basic_string& operator=(initializer_list<value_type>);
 123
 124     iterator       begin() noexcept;
 125     const_iterator begin() const noexcept;
 126     iterator       end() noexcept;
 127     const_iterator end() const noexcept;
 128
 129     reverse_iterator       rbegin() noexcept;
 130     const_reverse_iterator rbegin() const noexcept;
 131     reverse_iterator       rend() noexcept;
 132     const_reverse_iterator rend() const noexcept;
 133
 134     const_iterator         cbegin() const noexcept;
 135     const_iterator         cend() const noexcept;
 136     const_reverse_iterator crbegin() const noexcept;
 137     const_reverse_iterator crend() const noexcept;
 138
 139     size_type size() const noexcept;
 140     size_type length() const noexcept;
 141     size_type max_size() const noexcept;
 142     size_type capacity() const noexcept;
 143
 144     void resize(size_type n, value_type c);
 145     void resize(size_type n);
 146
 147     void reserve(size_type res_arg = 0);
 148     void shrink_to_fit();
 149     void clear() noexcept;
 150     bool empty() const noexcept;
 151
 152     const_reference operator[](size_type pos) const;
 153     reference       operator[](size_type pos);
 154
 155     const_reference at(size_type n) const;
 156     reference       at(size_type n);
 157
 158     basic_string& operator+=(const basic_string& str);
 159     basic_string& operator+=(const value_type* s);
 160     basic_string& operator+=(value_type c);
 161     basic_string& operator+=(initializer_list<value_type>);
 162
 163     basic_string& append(const basic_string& str);
 164     basic_string& append(const basic_string& str, size_type pos, size_type n=npos); //C++14
 165     basic_string& append(const value_type* s, size_type n);
 166     basic_string& append(const value_type* s);
 167     basic_string& append(size_type n, value_type c);
 168     template<class InputIterator>
 169         basic_string& append(InputIterator first, InputIterator last);
 170     basic_string& append(initializer_list<value_type>);
 171
 172     void push_back(value_type c);
 173     void pop_back();
 174     reference       front();
 175     const_reference front() const;
 176     reference       back();
 177     const_reference back() const;
 178
 179     basic_string& assign(const basic_string& str);
 180     basic_string& assign(basic_string&& str);
 181     basic_string& assign(const basic_string& str, size_type pos, size_type n=npos); // C++14
 182     basic_string& assign(const value_type* s, size_type n);
 183     basic_string& assign(const value_type* s);
 184     basic_string& assign(size_type n, value_type c);
 185     template<class InputIterator>
 186         basic_string& assign(InputIterator first, InputIterator last);
 187     basic_string& assign(initializer_list<value_type>);
 188
 189     basic_string& insert(size_type pos1, const basic_string& str);
 190     basic_string& insert(size_type pos1, const basic_string& str,
 191                          size_type pos2, size_type n);
 192     basic_string& insert(size_type pos, const value_type* s, size_type n=npos); //C++14
 193     basic_string& insert(size_type pos, const value_type* s);
 194     basic_string& insert(size_type pos, size_type n, value_type c);
 195     iterator      insert(const_iterator p, value_type c);
 196     iterator      insert(const_iterator p, size_type n, value_type c);
 197     template<class InputIterator>
 198         iterator insert(const_iterator p, InputIterator first, InputIterator last);
 199     iterator      insert(const_iterator p, initializer_list<value_type>);
 200
 201     basic_string& erase(size_type pos = 0, size_type n = npos);
 202     iterator      erase(const_iterator position);
 203     iterator      erase(const_iterator first, const_iterator last);
 204
 205     basic_string& replace(size_type pos1, size_type n1, const basic_string& str);
 206     basic_string& replace(size_type pos1, size_type n1, const basic_string& str,
 207                           size_type pos2, size_type n2=npos); // C++14
 208     basic_string& replace(size_type pos, size_type n1, const value_type* s, size_type n2);
 209     basic_string& replace(size_type pos, size_type n1, const value_type* s);
 210     basic_string& replace(size_type pos, size_type n1, size_type n2, value_type c);
 211     basic_string& replace(const_iterator i1, const_iterator i2, const basic_string& str);
 212     basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s, size_type n);
 213     basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s);
 214     basic_string& replace(const_iterator i1, const_iterator i2, size_type n, value_type c);
 215     template<class InputIterator>
 216         basic_string& replace(const_iterator i1, const_iterator i2, InputIterator j1, InputIterator j2);
 217     basic_string& replace(const_iterator i1, const_iterator i2, initializer_list<value_type>);
 218
 219     size_type copy(value_type* s, size_type n, size_type pos = 0) const;
 220     basic_string substr(size_type pos = 0, size_type n = npos) const;
 221
 222     void swap(basic_string& str)
 223         noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
 224                  allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 225
 226     const value_type* c_str() const noexcept;
 227     const value_type* data() const noexcept;
 228
 229     allocator_type get_allocator() const noexcept;
 230
 231     size_type find(const basic_string& str, size_type pos = 0) const noexcept;
 232     size_type find(const value_type* s, size_type pos, size_type n) const noexcept;
 233     size_type find(const value_type* s, size_type pos = 0) const noexcept;
 234     size_type find(value_type c, size_type pos = 0) const noexcept;
 235
 236     size_type rfind(const basic_string& str, size_type pos = npos) const noexcept;
 237     size_type rfind(const value_type* s, size_type pos, size_type n) const noexcept;
 238     size_type rfind(const value_type* s, size_type pos = npos) const noexcept;
 239     size_type rfind(value_type c, size_type pos = npos) const noexcept;
 240
 241     size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept;
 242     size_type find_first_of(const value_type* s, size_type pos, size_type n) const noexcept;
 243     size_type find_first_of(const value_type* s, size_type pos = 0) const noexcept;
 244     size_type find_first_of(value_type c, size_type pos = 0) const noexcept;
 245
 246     size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept;
 247     size_type find_last_of(const value_type* s, size_type pos, size_type n) const noexcept;
 248     size_type find_last_of(const value_type* s, size_type pos = npos) const noexcept;
 249     size_type find_last_of(value_type c, size_type pos = npos) const noexcept;
 250
 251     size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept;
 252     size_type find_first_not_of(const value_type* s, size_type pos, size_type n) const noexcept;
 253     size_type find_first_not_of(const value_type* s, size_type pos = 0) const noexcept;
 254     size_type find_first_not_of(value_type c, size_type pos = 0) const noexcept;
 255
 256     size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept;
 257     size_type find_last_not_of(const value_type* s, size_type pos, size_type n) const noexcept;
 258     size_type find_last_not_of(const value_type* s, size_type pos = npos) const noexcept;
 259     size_type find_last_not_of(value_type c, size_type pos = npos) const noexcept;
 260
 261     int compare(const basic_string& str) const noexcept;
 262     int compare(size_type pos1, size_type n1, const basic_string& str) const;
 263     int compare(size_type pos1, size_type n1, const basic_string& str,
 264                 size_type pos2, size_type n2=npos) const; // C++14
 265     int compare(const value_type* s) const noexcept;
 266     int compare(size_type pos1, size_type n1, const value_type* s) const;
 267     int compare(size_type pos1, size_type n1, const value_type* s, size_type n2) const;
 268
 269     bool __invariants() const;
 270 };
 271
 272 template<class charT, class traits, class Allocator>
 273 basic_string<charT, traits, Allocator>
 274 operator+(const basic_string<charT, traits, Allocator>& lhs,
 275           const basic_string<charT, traits, Allocator>& rhs);
 276
 277 template<class charT, class traits, class Allocator>
 278 basic_string<charT, traits, Allocator>
 279 operator+(const charT* lhs , const basic_string<charT,traits,Allocator>&rhs);
 280
 281 template<class charT, class traits, class Allocator>
 282 basic_string<charT, traits, Allocator>
 283 operator+(charT lhs, const basic_string<charT,traits,Allocator>& rhs);
 284
 285 template<class charT, class traits, class Allocator>
 286 basic_string<charT, traits, Allocator>
 287 operator+(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs);
 288
 289 template<class charT, class traits, class Allocator>
 290 basic_string<charT, traits, Allocator>
 291 operator+(const basic_string<charT, traits, Allocator>& lhs, charT rhs);
 292
 293 template<class charT, class traits, class Allocator>
 294 bool operator==(const basic_string<charT, traits, Allocator>& lhs,
 295                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 296
 297 template<class charT, class traits, class Allocator>
 298 bool operator==(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 299
 300 template<class charT, class traits, class Allocator>
 301 bool operator==(const basic_string<charT,traits,Allocator>& lhs, const charT* rhs) noexcept;
 302
 303 template<class charT, class traits, class Allocator>
 304 bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
 305                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 306
 307 template<class charT, class traits, class Allocator>
 308 bool operator!=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 309
 310 template<class charT, class traits, class Allocator>
 311 bool operator!=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
 312
 313 template<class charT, class traits, class Allocator>
 314 bool operator< (const basic_string<charT, traits, Allocator>& lhs,
 315                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 316
 317 template<class charT, class traits, class Allocator>
 318 bool operator< (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
 319
 320 template<class charT, class traits, class Allocator>
 321 bool operator< (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 322
 323 template<class charT, class traits, class Allocator>
 324 bool operator> (const basic_string<charT, traits, Allocator>& lhs,
 325                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 326
 327 template<class charT, class traits, class Allocator>
 328 bool operator> (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
 329
 330 template<class charT, class traits, class Allocator>
 331 bool operator> (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 332
 333 template<class charT, class traits, class Allocator>
 334 bool operator<=(const basic_string<charT, traits, Allocator>& lhs,
 335                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 336
 337 template<class charT, class traits, class Allocator>
 338 bool operator<=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
 339
 340 template<class charT, class traits, class Allocator>
 341 bool operator<=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 342
 343 template<class charT, class traits, class Allocator>
 344 bool operator>=(const basic_string<charT, traits, Allocator>& lhs,
 345                 const basic_string<charT, traits, Allocator>& rhs) noexcept;
 346
 347 template<class charT, class traits, class Allocator>
 348 bool operator>=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
 349
 350 template<class charT, class traits, class Allocator>
 351 bool operator>=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
 352
 353 template<class charT, class traits, class Allocator>
 354 void swap(basic_string<charT, traits, Allocator>& lhs,
 355           basic_string<charT, traits, Allocator>& rhs)
 356             noexcept(noexcept(lhs.swap(rhs)));
 357
 358 template<class charT, class traits, class Allocator>
 359 basic_istream<charT, traits>&
 360 operator>>(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
 361
 362 template<class charT, class traits, class Allocator>
 363 basic_ostream<charT, traits>&
 364 operator<<(basic_ostream<charT, traits>& os, const basic_string<charT, traits, Allocator>& str);
 365
 366 template<class charT, class traits, class Allocator>
 367 basic_istream<charT, traits>&
 368 getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str,
 369         charT delim);
 370
 371 template<class charT, class traits, class Allocator>
 372 basic_istream<charT, traits>&
 373 getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
 374
 375 typedef basic_string<char>    string;
 376 typedef basic_string<wchar_t> wstring;
 377 typedef basic_string<char16_t> u16string;
 378 typedef basic_string<char32_t> u32string;
 379
 380 int                stoi  (const string& str, size_t* idx = 0, int base = 10);
 381 long               stol  (const string& str, size_t* idx = 0, int base = 10);
 382 unsigned long      stoul (const string& str, size_t* idx = 0, int base = 10);
 383 long long          stoll (const string& str, size_t* idx = 0, int base = 10);
 384 unsigned long long stoull(const string& str, size_t* idx = 0, int base = 10);
 385
 386 float       stof (const string& str, size_t* idx = 0);
 387 double      stod (const string& str, size_t* idx = 0);
 388 long double stold(const string& str, size_t* idx = 0);
 389
 390 string to_string(int val);
 391 string to_string(unsigned val);
 392 string to_string(long val);
 393 string to_string(unsigned long val);
 394 string to_string(long long val);
 395 string to_string(unsigned long long val);
 396 string to_string(float val);
 397 string to_string(double val);
 398 string to_string(long double val);
 399
 400 int                stoi  (const wstring& str, size_t* idx = 0, int base = 10);
 401 long               stol  (const wstring& str, size_t* idx = 0, int base = 10);
 402 unsigned long      stoul (const wstring& str, size_t* idx = 0, int base = 10);
 403 long long          stoll (const wstring& str, size_t* idx = 0, int base = 10);
 404 unsigned long long stoull(const wstring& str, size_t* idx = 0, int base = 10);
 405
 406 float       stof (const wstring& str, size_t* idx = 0);
 407 double      stod (const wstring& str, size_t* idx = 0);
 408 long double stold(const wstring& str, size_t* idx = 0);
 409
 410 wstring to_wstring(int val);
 411 wstring to_wstring(unsigned val);
 412 wstring to_wstring(long val);
 413 wstring to_wstring(unsigned long val);
 414 wstring to_wstring(long long val);
 415 wstring to_wstring(unsigned long long val);
 416 wstring to_wstring(float val);
 417 wstring to_wstring(double val);
 418 wstring to_wstring(long double val);
 419
 420 template <> struct hash<string>;
 421 template <> struct hash<u16string>;
 422 template <> struct hash<u32string>;
 423 template <> struct hash<wstring>;
 424
 425 basic_string<char>     operator "" s( const char *str,     size_t len ); // C++14
 426 basic_string<wchar_t>  operator "" s( const wchar_t *str,  size_t len ); // C++14
 427 basic_string<char16_t> operator "" s( const char16_t *str, size_t len ); // C++14
 428 basic_string<char32_t> operator "" s( const char32_t *str, size_t len ); // C++14
 429
 430 }  // std
 431
 432 */
 433
 434 #include <__config>
 435 #include <iosfwd>
 436 #include <cstring>
 437 #include <cstdio>  // For EOF.
 438 #include <cwchar>
 439 #include <algorithm>
 440 #include <iterator>
 441 #include <utility>
 442 #include <memory>
 443 #include <stdexcept>
 444 #include <type_traits>
 445 #include <initializer_list>
 446 #include <__functional_base>
 447 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
 448 #include <cstdint>
 449 #endif
 450 #if defined(_LIBCPP_NO_EXCEPTIONS)
 451 #include <cassert>
 452 #endif
 453
 454 #include <__undef_min_max>
 455
 456 #include <__debug>
 457
 458 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 459 #pragma GCC system_header
 460 #endif
 461
 462 _LIBCPP_BEGIN_NAMESPACE_STD
 463
 464 // fpos
 465
 466 template <class _StateT>
 467 class _LIBCPP_TYPE_VIS_ONLY fpos
 468 {
 469 private:
 470     _StateT __st_;
 471     streamoff __off_;
 472 public:
 473     _LIBCPP_INLINE_VISIBILITY fpos(streamoff __off = streamoff()) : __st_(), __off_(__off) {}
 474
 475     _LIBCPP_INLINE_VISIBILITY operator streamoff() const {return __off_;}
 476
 477     _LIBCPP_INLINE_VISIBILITY _StateT state() const {return __st_;}
 478     _LIBCPP_INLINE_VISIBILITY void state(_StateT __st) {__st_ = __st;}
 479
 480     _LIBCPP_INLINE_VISIBILITY fpos& operator+=(streamoff __off) {__off_ += __off; return *this;}
 481     _LIBCPP_INLINE_VISIBILITY fpos  operator+ (streamoff __off) const {fpos __t(*this); __t += __off; return __t;}
 482     _LIBCPP_INLINE_VISIBILITY fpos& operator-=(streamoff __off) {__off_ -= __off; return *this;}
 483     _LIBCPP_INLINE_VISIBILITY fpos  operator- (streamoff __off) const {fpos __t(*this); __t -= __off; return __t;}
 484 };
 485
 486 template <class _StateT>
 487 inline _LIBCPP_INLINE_VISIBILITY
 488 streamoff operator-(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
 489     {return streamoff(__x) - streamoff(__y);}
 490
 491 template <class _StateT>
 492 inline _LIBCPP_INLINE_VISIBILITY
 493 bool operator==(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
 494     {return streamoff(__x) == streamoff(__y);}
 495
 496 template <class _StateT>
 497 inline _LIBCPP_INLINE_VISIBILITY
 498 bool operator!=(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
 499     {return streamoff(__x) != streamoff(__y);}
 500
 501 // char_traits
 502
 503 template <class _CharT>
 504 struct _LIBCPP_TYPE_VIS_ONLY char_traits
 505 {
 506     typedef _CharT    char_type;
 507     typedef int       int_type;
 508     typedef streamoff off_type;
 509     typedef streampos pos_type;
 510     typedef mbstate_t state_type;
 511
 512     static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
 513         {__c1 = __c2;}
 514     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 515         {return __c1 == __c2;}
 516     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 517         {return __c1 < __c2;}
 518
 519     static int              compare(const char_type* __s1, const char_type* __s2, size_t __n);
 520     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(0xFFFF);}
 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_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
1381 #endif
1382     _LIBCPP_INLINE_VISIBILITY basic_string& operator=(const value_type* __s) {return assign(__s);}
1383     basic_string& operator=(value_type __c);
1384 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1385     _LIBCPP_INLINE_VISIBILITY
1386     basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1387 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1388
1389 #if _LIBCPP_DEBUG_LEVEL >= 2
1390     _LIBCPP_INLINE_VISIBILITY
1391     iterator begin() _NOEXCEPT
1392         {return iterator(this, __get_pointer());}
1393     _LIBCPP_INLINE_VISIBILITY
1394     const_iterator begin() const _NOEXCEPT
1395         {return const_iterator(this, __get_pointer());}
1396     _LIBCPP_INLINE_VISIBILITY
1397     iterator end() _NOEXCEPT
1398         {return iterator(this, __get_pointer() + size());}
1399     _LIBCPP_INLINE_VISIBILITY
1400     const_iterator end() const _NOEXCEPT
1401         {return const_iterator(this, __get_pointer() + size());}
1402 #else
1403     _LIBCPP_INLINE_VISIBILITY
1404     iterator begin() _NOEXCEPT
1405         {return iterator(__get_pointer());}
1406     _LIBCPP_INLINE_VISIBILITY
1407     const_iterator begin() const _NOEXCEPT
1408         {return const_iterator(__get_pointer());}
1409     _LIBCPP_INLINE_VISIBILITY
1410     iterator end() _NOEXCEPT
1411         {return iterator(__get_pointer() + size());}
1412     _LIBCPP_INLINE_VISIBILITY
1413     const_iterator end() const _NOEXCEPT
1414         {return const_iterator(__get_pointer() + size());}
1415 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1416     _LIBCPP_INLINE_VISIBILITY
1417     reverse_iterator rbegin() _NOEXCEPT
1418         {return reverse_iterator(end());}
1419     _LIBCPP_INLINE_VISIBILITY
1420     const_reverse_iterator rbegin() const _NOEXCEPT
1421         {return const_reverse_iterator(end());}
1422     _LIBCPP_INLINE_VISIBILITY
1423     reverse_iterator rend() _NOEXCEPT
1424         {return reverse_iterator(begin());}
1425     _LIBCPP_INLINE_VISIBILITY
1426     const_reverse_iterator rend() const _NOEXCEPT
1427         {return const_reverse_iterator(begin());}
1428
1429     _LIBCPP_INLINE_VISIBILITY
1430     const_iterator cbegin() const _NOEXCEPT
1431         {return begin();}
1432     _LIBCPP_INLINE_VISIBILITY
1433     const_iterator cend() const _NOEXCEPT
1434         {return end();}
1435     _LIBCPP_INLINE_VISIBILITY
1436     const_reverse_iterator crbegin() const _NOEXCEPT
1437         {return rbegin();}
1438     _LIBCPP_INLINE_VISIBILITY
1439     const_reverse_iterator crend() const _NOEXCEPT
1440         {return rend();}
1441
1442     _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT
1443         {return __is_long() ? __get_long_size() : __get_short_size();}
1444     _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}
1445     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT;
1446     _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT
1447         {return (__is_long() ? __get_long_cap() : __min_cap) - 1;}
1448
1449     void resize(size_type __n, value_type __c);
1450     _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());}
1451
1452     void reserve(size_type res_arg = 0);
1453     _LIBCPP_INLINE_VISIBILITY
1454     void shrink_to_fit() _NOEXCEPT {reserve();}
1455     _LIBCPP_INLINE_VISIBILITY
1456     void clear() _NOEXCEPT;
1457     _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return size() == 0;}
1458
1459     _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const;
1460     _LIBCPP_INLINE_VISIBILITY reference       operator[](size_type __pos);
1461
1462     const_reference at(size_type __n) const;
1463     reference       at(size_type __n);
1464
1465     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const basic_string& __str) {return append(__str);}
1466     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const value_type* __s)         {return append(__s);}
1467     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(value_type __c)            {push_back(__c); return *this;}
1468 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1469     _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(initializer_list<value_type> __il) {return append(__il);}
1470 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1471
1472     _LIBCPP_INLINE_VISIBILITY
1473     basic_string& append(const basic_string& __str);
1474     basic_string& append(const basic_string& __str, size_type __pos, size_type __n=npos);
1475     basic_string& append(const value_type* __s, size_type __n);
1476     basic_string& append(const value_type* __s);
1477     basic_string& append(size_type __n, value_type __c);
1478     template<class _InputIterator>
1479         typename enable_if
1480         <
1481              __is_input_iterator  <_InputIterator>::value &&
1482             !__is_forward_iterator<_InputIterator>::value,
1483             basic_string&
1484         >::type
1485         append(_InputIterator __first, _InputIterator __last);
1486     template<class _ForwardIterator>
1487         typename enable_if
1488         <
1489             __is_forward_iterator<_ForwardIterator>::value,
1490             basic_string&
1491         >::type
1492         append(_ForwardIterator __first, _ForwardIterator __last);
1493 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1494     _LIBCPP_INLINE_VISIBILITY
1495     basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());}
1496 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1497
1498     void push_back(value_type __c);
1499     _LIBCPP_INLINE_VISIBILITY
1500     void pop_back();
1501     _LIBCPP_INLINE_VISIBILITY reference       front();
1502     _LIBCPP_INLINE_VISIBILITY const_reference front() const;
1503     _LIBCPP_INLINE_VISIBILITY reference       back();
1504     _LIBCPP_INLINE_VISIBILITY const_reference back() const;
1505
1506     _LIBCPP_INLINE_VISIBILITY
1507     basic_string& assign(const basic_string& __str);
1508 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1509     _LIBCPP_INLINE_VISIBILITY
1510     basic_string& assign(basic_string&& str)
1511         {*this = _VSTD::move(str); return *this;}
1512 #endif
1513     basic_string& assign(const basic_string& __str, size_type __pos, size_type __n=npos);
1514     basic_string& assign(const value_type* __s, size_type __n);
1515     basic_string& assign(const value_type* __s);
1516     basic_string& assign(size_type __n, value_type __c);
1517     template<class _InputIterator>
1518         typename enable_if
1519         <
1520              __is_input_iterator  <_InputIterator>::value &&
1521             !__is_forward_iterator<_InputIterator>::value,
1522             basic_string&
1523         >::type
1524         assign(_InputIterator __first, _InputIterator __last);
1525     template<class _ForwardIterator>
1526         typename enable_if
1527         <
1528             __is_forward_iterator<_ForwardIterator>::value,
1529             basic_string&
1530         >::type
1531         assign(_ForwardIterator __first, _ForwardIterator __last);
1532 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1533     _LIBCPP_INLINE_VISIBILITY
1534     basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1535 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1536
1537     _LIBCPP_INLINE_VISIBILITY
1538     basic_string& insert(size_type __pos1, const basic_string& __str);
1539     basic_string& insert(size_type __pos1, const basic_string& __str, size_type __pos2, size_type __n=npos);
1540     basic_string& insert(size_type __pos, const value_type* __s, size_type __n);
1541     basic_string& insert(size_type __pos, const value_type* __s);
1542     basic_string& insert(size_type __pos, size_type __n, value_type __c);
1543     iterator      insert(const_iterator __pos, value_type __c);
1544     _LIBCPP_INLINE_VISIBILITY
1545     iterator      insert(const_iterator __pos, size_type __n, value_type __c);
1546     template<class _InputIterator>
1547         typename enable_if
1548         <
1549              __is_input_iterator  <_InputIterator>::value &&
1550             !__is_forward_iterator<_InputIterator>::value,
1551             iterator
1552         >::type
1553         insert(const_iterator __pos, _InputIterator __first, _InputIterator __last);
1554     template<class _ForwardIterator>
1555         typename enable_if
1556         <
1557             __is_forward_iterator<_ForwardIterator>::value,
1558             iterator
1559         >::type
1560         insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last);
1561 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1562     _LIBCPP_INLINE_VISIBILITY
1563     iterator insert(const_iterator __pos, initializer_list<value_type> __il)
1564                     {return insert(__pos, __il.begin(), __il.end());}
1565 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1566
1567     basic_string& erase(size_type __pos = 0, size_type __n = npos);
1568     _LIBCPP_INLINE_VISIBILITY
1569     iterator      erase(const_iterator __pos);
1570     _LIBCPP_INLINE_VISIBILITY
1571     iterator      erase(const_iterator __first, const_iterator __last);
1572
1573     _LIBCPP_INLINE_VISIBILITY
1574     basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str);
1575     basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos);
1576     basic_string& replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2);
1577     basic_string& replace(size_type __pos, size_type __n1, const value_type* __s);
1578     basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c);
1579     _LIBCPP_INLINE_VISIBILITY
1580     basic_string& replace(const_iterator __i1, const_iterator __i2, const basic_string& __str);
1581     _LIBCPP_INLINE_VISIBILITY
1582     basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n);
1583     _LIBCPP_INLINE_VISIBILITY
1584     basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s);
1585     _LIBCPP_INLINE_VISIBILITY
1586     basic_string& replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c);
1587     template<class _InputIterator>
1588         typename enable_if
1589         <
1590             __is_input_iterator<_InputIterator>::value,
1591             basic_string&
1592         >::type
1593         replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2);
1594 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1595     _LIBCPP_INLINE_VISIBILITY
1596     basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list<value_type> __il)
1597         {return replace(__i1, __i2, __il.begin(), __il.end());}
1598 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1599
1600     size_type copy(value_type* __s, size_type __n, size_type __pos = 0) const;
1601     _LIBCPP_INLINE_VISIBILITY
1602     basic_string substr(size_type __pos = 0, size_type __n = npos) const;
1603
1604     _LIBCPP_INLINE_VISIBILITY
1605     void swap(basic_string& __str)
1606 #if _LIBCPP_STD_VER >= 14
1607         _NOEXCEPT;
1608 #else
1609         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1610                     __is_nothrow_swappable<allocator_type>::value);
1611 #endif
1612
1613     _LIBCPP_INLINE_VISIBILITY
1614     const value_type* c_str() const _NOEXCEPT {return data();}
1615     _LIBCPP_INLINE_VISIBILITY
1616     const value_type* data() const _NOEXCEPT  {return _VSTD::__to_raw_pointer(__get_pointer());}
1617
1618     _LIBCPP_INLINE_VISIBILITY
1619     allocator_type get_allocator() const _NOEXCEPT {return __alloc();}
1620
1621     _LIBCPP_INLINE_VISIBILITY
1622     size_type find(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1623     size_type find(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1624     _LIBCPP_INLINE_VISIBILITY
1625     size_type find(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1626     size_type find(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1627
1628     _LIBCPP_INLINE_VISIBILITY
1629     size_type rfind(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1630     size_type rfind(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1631     _LIBCPP_INLINE_VISIBILITY
1632     size_type rfind(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1633     size_type rfind(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1634
1635     _LIBCPP_INLINE_VISIBILITY
1636     size_type find_first_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1637     size_type find_first_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1638     _LIBCPP_INLINE_VISIBILITY
1639     size_type find_first_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1640     _LIBCPP_INLINE_VISIBILITY
1641     size_type find_first_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1642
1643     _LIBCPP_INLINE_VISIBILITY
1644     size_type find_last_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1645     size_type find_last_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1646     _LIBCPP_INLINE_VISIBILITY
1647     size_type find_last_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1648     _LIBCPP_INLINE_VISIBILITY
1649     size_type find_last_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1650
1651     _LIBCPP_INLINE_VISIBILITY
1652     size_type find_first_not_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1653     size_type find_first_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1654     _LIBCPP_INLINE_VISIBILITY
1655     size_type find_first_not_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT;
1656     _LIBCPP_INLINE_VISIBILITY
1657     size_type find_first_not_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1658
1659     _LIBCPP_INLINE_VISIBILITY
1660     size_type find_last_not_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1661     size_type find_last_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT;
1662     _LIBCPP_INLINE_VISIBILITY
1663     size_type find_last_not_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT;
1664     _LIBCPP_INLINE_VISIBILITY
1665     size_type find_last_not_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1666
1667     _LIBCPP_INLINE_VISIBILITY
1668     int compare(const basic_string& __str) const _NOEXCEPT;
1669     _LIBCPP_INLINE_VISIBILITY
1670     int compare(size_type __pos1, size_type __n1, const basic_string& __str) const;
1671     int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos) const;
1672     int compare(const value_type* __s) const _NOEXCEPT;
1673     int compare(size_type __pos1, size_type __n1, const value_type* __s) const;
1674     int compare(size_type __pos1, size_type __n1, const value_type* __s, size_type __n2) const;
1675
1676     _LIBCPP_INLINE_VISIBILITY bool __invariants() const;
1677
1678     _LIBCPP_INLINE_VISIBILITY
1679     bool __is_long() const _NOEXCEPT
1680         {return bool(__r_.first().__s.__size_ & __short_mask);}
1681
1682 #if _LIBCPP_DEBUG_LEVEL >= 2
1683
1684     bool __dereferenceable(const const_iterator* __i) const;
1685     bool __decrementable(const const_iterator* __i) const;
1686     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1687     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1688
1689 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1690
1691 private:
1692     _LIBCPP_INLINE_VISIBILITY
1693     allocator_type& __alloc() _NOEXCEPT
1694         {return __r_.second();}
1695     _LIBCPP_INLINE_VISIBILITY
1696     const allocator_type& __alloc() const _NOEXCEPT
1697         {return __r_.second();}
1698
1699 #ifdef _LIBCPP_ALTERNATE_STRING_LAYOUT
1700
1701     _LIBCPP_INLINE_VISIBILITY
1702     void __set_short_size(size_type __s) _NOEXCEPT
1703 #   if _LIBCPP_BIG_ENDIAN
1704         {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
1705 #   else
1706         {__r_.first().__s.__size_ = (unsigned char)(__s);}
1707 #   endif
1708
1709     _LIBCPP_INLINE_VISIBILITY
1710     size_type __get_short_size() const _NOEXCEPT
1711 #   if _LIBCPP_BIG_ENDIAN
1712         {return __r_.first().__s.__size_ >> 1;}
1713 #   else
1714         {return __r_.first().__s.__size_;}
1715 #   endif
1716
1717 #else  // _LIBCPP_ALTERNATE_STRING_LAYOUT
1718
1719     _LIBCPP_INLINE_VISIBILITY
1720     void __set_short_size(size_type __s) _NOEXCEPT
1721 #   if _LIBCPP_BIG_ENDIAN
1722         {__r_.first().__s.__size_ = (unsigned char)(__s);}
1723 #   else
1724         {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
1725 #   endif
1726
1727     _LIBCPP_INLINE_VISIBILITY
1728     size_type __get_short_size() const _NOEXCEPT
1729 #   if _LIBCPP_BIG_ENDIAN
1730         {return __r_.first().__s.__size_;}
1731 #   else
1732         {return __r_.first().__s.__size_ >> 1;}
1733 #   endif
1734
1735 #endif  // _LIBCPP_ALTERNATE_STRING_LAYOUT
1736
1737     _LIBCPP_INLINE_VISIBILITY
1738     void __set_long_size(size_type __s) _NOEXCEPT
1739         {__r_.first().__l.__size_ = __s;}
1740     _LIBCPP_INLINE_VISIBILITY
1741     size_type __get_long_size() const _NOEXCEPT
1742         {return __r_.first().__l.__size_;}
1743     _LIBCPP_INLINE_VISIBILITY
1744     void __set_size(size_type __s) _NOEXCEPT
1745         {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);}
1746
1747     _LIBCPP_INLINE_VISIBILITY
1748     void __set_long_cap(size_type __s) _NOEXCEPT
1749         {__r_.first().__l.__cap_  = __long_mask | __s;}
1750     _LIBCPP_INLINE_VISIBILITY
1751     size_type __get_long_cap() const _NOEXCEPT
1752         {return __r_.first().__l.__cap_ & size_type(~__long_mask);}
1753
1754     _LIBCPP_INLINE_VISIBILITY
1755     void __set_long_pointer(pointer __p) _NOEXCEPT
1756         {__r_.first().__l.__data_ = __p;}
1757     _LIBCPP_INLINE_VISIBILITY
1758     pointer __get_long_pointer() _NOEXCEPT
1759         {return __r_.first().__l.__data_;}
1760     _LIBCPP_INLINE_VISIBILITY
1761     const_pointer __get_long_pointer() const _NOEXCEPT
1762         {return __r_.first().__l.__data_;}
1763     _LIBCPP_INLINE_VISIBILITY
1764     pointer __get_short_pointer() _NOEXCEPT
1765         {return pointer_traits<pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1766     _LIBCPP_INLINE_VISIBILITY
1767     const_pointer __get_short_pointer() const _NOEXCEPT
1768         {return pointer_traits<const_pointer>::pointer_to(__r_.first().__s.__data_[0]);}
1769     _LIBCPP_INLINE_VISIBILITY
1770     pointer __get_pointer() _NOEXCEPT
1771         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1772     _LIBCPP_INLINE_VISIBILITY
1773     const_pointer __get_pointer() const _NOEXCEPT
1774         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1775
1776     _LIBCPP_INLINE_VISIBILITY
1777     void __zero() _NOEXCEPT
1778         {
1779             size_type (&__a)[__n_words] = __r_.first().__r.__words;
1780             for (unsigned __i = 0; __i < __n_words; ++__i)
1781                 __a[__i] = 0;
1782         }
1783
1784     template <size_type __a> static
1785         _LIBCPP_INLINE_VISIBILITY
1786         size_type __align_it(size_type __s) _NOEXCEPT
1787             {return __s + (__a-1) & ~(__a-1);}
1788     enum {__alignment = 16};
1789     static _LIBCPP_INLINE_VISIBILITY
1790     size_type __recommend(size_type __s) _NOEXCEPT
1791         {return (__s < __min_cap ? __min_cap :
1792                  __align_it<sizeof(value_type) < __alignment ?
1793                             __alignment/sizeof(value_type) : 1 > (__s+1)) - 1;}
1794
1795     void __init(const value_type* __s, size_type __sz, size_type __reserve);
1796     void __init(const value_type* __s, size_type __sz);
1797     void __init(size_type __n, value_type __c);
1798
1799     template <class _InputIterator>
1800     typename enable_if
1801     <
1802          __is_input_iterator  <_InputIterator>::value &&
1803         !__is_forward_iterator<_InputIterator>::value,
1804         void
1805     >::type
1806     __init(_InputIterator __first, _InputIterator __last);
1807
1808     template <class _ForwardIterator>
1809     typename enable_if
1810     <
1811         __is_forward_iterator<_ForwardIterator>::value,
1812         void
1813     >::type
1814     __init(_ForwardIterator __first, _ForwardIterator __last);
1815
1816     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1817                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
1818     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1819                                size_type __n_copy,  size_type __n_del,
1820                                size_type __n_add, const value_type* __p_new_stuff);
1821
1822     _LIBCPP_INLINE_VISIBILITY
1823     void __erase_to_end(size_type __pos);
1824
1825     _LIBCPP_INLINE_VISIBILITY
1826     void __copy_assign_alloc(const basic_string& __str)
1827         {__copy_assign_alloc(__str, integral_constant<bool,
1828                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
1829
1830     _LIBCPP_INLINE_VISIBILITY
1831     void __copy_assign_alloc(const basic_string& __str, true_type)
1832         {
1833             if (__alloc() != __str.__alloc())
1834             {
1835                 clear();
1836                 shrink_to_fit();
1837             }
1838             __alloc() = __str.__alloc();
1839         }
1840
1841     _LIBCPP_INLINE_VISIBILITY
1842     void __copy_assign_alloc(const basic_string&, false_type) _NOEXCEPT
1843         {}
1844
1845 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1846     _LIBCPP_INLINE_VISIBILITY
1847     void __move_assign(basic_string& __str, false_type)
1848         _NOEXCEPT_(__alloc_traits::is_always_equal::value);
1849     _LIBCPP_INLINE_VISIBILITY
1850     void __move_assign(basic_string& __str, true_type)
1851 #if _LIBCPP_STD_VER > 14
1852         _NOEXCEPT;
1853 #else
1854         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1855 #endif
1856 #endif
1857
1858     _LIBCPP_INLINE_VISIBILITY
1859     void
1860     __move_assign_alloc(basic_string& __str)
1861         _NOEXCEPT_(
1862             !__alloc_traits::propagate_on_container_move_assignment::value ||
1863             is_nothrow_move_assignable<allocator_type>::value)
1864     {__move_assign_alloc(__str, integral_constant<bool,
1865                       __alloc_traits::propagate_on_container_move_assignment::value>());}
1866
1867     _LIBCPP_INLINE_VISIBILITY
1868     void __move_assign_alloc(basic_string& __c, true_type)
1869         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1870         {
1871             __alloc() = _VSTD::move(__c.__alloc());
1872         }
1873
1874     _LIBCPP_INLINE_VISIBILITY
1875     void __move_assign_alloc(basic_string&, false_type)
1876         _NOEXCEPT
1877         {}
1878
1879     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
1880     _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type);
1881
1882     friend basic_string operator+<>(const basic_string&, const basic_string&);
1883     friend basic_string operator+<>(const value_type*, const basic_string&);
1884     friend basic_string operator+<>(value_type, const basic_string&);
1885     friend basic_string operator+<>(const basic_string&, const value_type*);
1886     friend basic_string operator+<>(const basic_string&, value_type);
1887 };
1888
1889 template <class _CharT, class _Traits, class _Allocator>
1890 inline _LIBCPP_INLINE_VISIBILITY
1891 void
1892 basic_string<_CharT, _Traits, _Allocator>::__invalidate_all_iterators()
1893 {
1894 #if _LIBCPP_DEBUG_LEVEL >= 2
1895     __get_db()->__invalidate_all(this);
1896 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1897 }
1898
1899 template <class _CharT, class _Traits, class _Allocator>
1900 inline _LIBCPP_INLINE_VISIBILITY
1901 void
1902 basic_string<_CharT, _Traits, _Allocator>::__invalidate_iterators_past(size_type
1903 #if _LIBCPP_DEBUG_LEVEL >= 2
1904                                                                         __pos
1905 #endif
1906                                                                       )
1907 {
1908 #if _LIBCPP_DEBUG_LEVEL >= 2
1909     __c_node* __c = __get_db()->__find_c_and_lock(this);
1910     if (__c)
1911     {
1912         const_pointer __new_last = __get_pointer() + __pos;
1913         for (__i_node** __p = __c->end_; __p != __c->beg_; )
1914         {
1915             --__p;
1916             const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
1917             if (__i->base() > __new_last)
1918             {
1919                 (*__p)->__c_ = nullptr;
1920                 if (--__c->end_ != __p)
1921                     memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1922             }
1923         }
1924         __get_db()->unlock();
1925     }
1926 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1927 }
1928
1929 template <class _CharT, class _Traits, class _Allocator>
1930 inline _LIBCPP_INLINE_VISIBILITY
1931 basic_string<_CharT, _Traits, _Allocator>::basic_string()
1932     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1933 {
1934 #if _LIBCPP_DEBUG_LEVEL >= 2
1935     __get_db()->__insert_c(this);
1936 #endif
1937     __zero();
1938 }
1939
1940 template <class _CharT, class _Traits, class _Allocator>
1941 inline _LIBCPP_INLINE_VISIBILITY
1942 basic_string<_CharT, _Traits, _Allocator>::basic_string(const allocator_type& __a)
1943 #if _LIBCPP_STD_VER <= 14
1944         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
1945 #else
1946         _NOEXCEPT
1947 #endif
1948 : __r_(__a)
1949 {
1950 #if _LIBCPP_DEBUG_LEVEL >= 2
1951     __get_db()->__insert_c(this);
1952 #endif
1953     __zero();
1954 }
1955
1956 template <class _CharT, class _Traits, class _Allocator>
1957 void
1958 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz, size_type __reserve)
1959 {
1960     if (__reserve > max_size())
1961         this->__throw_length_error();
1962     pointer __p;
1963     if (__reserve < __min_cap)
1964     {
1965         __set_short_size(__sz);
1966         __p = __get_short_pointer();
1967     }
1968     else
1969     {
1970         size_type __cap = __recommend(__reserve);
1971         __p = __alloc_traits::allocate(__alloc(), __cap+1);
1972         __set_long_pointer(__p);
1973         __set_long_cap(__cap+1);
1974         __set_long_size(__sz);
1975     }
1976     traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz);
1977     traits_type::assign(__p[__sz], value_type());
1978 }
1979
1980 template <class _CharT, class _Traits, class _Allocator>
1981 void
1982 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
1983 {
1984     if (__sz > max_size())
1985         this->__throw_length_error();
1986     pointer __p;
1987     if (__sz < __min_cap)
1988     {
1989         __set_short_size(__sz);
1990         __p = __get_short_pointer();
1991     }
1992     else
1993     {
1994         size_type __cap = __recommend(__sz);
1995         __p = __alloc_traits::allocate(__alloc(), __cap+1);
1996         __set_long_pointer(__p);
1997         __set_long_cap(__cap+1);
1998         __set_long_size(__sz);
1999     }
2000     traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz);
2001     traits_type::assign(__p[__sz], value_type());
2002 }
2003
2004 template <class _CharT, class _Traits, class _Allocator>
2005 inline _LIBCPP_INLINE_VISIBILITY
2006 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s)
2007 {
2008     _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*) detected nullptr");
2009     __init(__s, traits_type::length(__s));
2010 #if _LIBCPP_DEBUG_LEVEL >= 2
2011     __get_db()->__insert_c(this);
2012 #endif
2013 }
2014
2015 template <class _CharT, class _Traits, class _Allocator>
2016 inline _LIBCPP_INLINE_VISIBILITY
2017 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, const allocator_type& __a)
2018     : __r_(__a)
2019 {
2020     _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*, allocator) detected nullptr");
2021     __init(__s, traits_type::length(__s));
2022 #if _LIBCPP_DEBUG_LEVEL >= 2
2023     __get_db()->__insert_c(this);
2024 #endif
2025 }
2026
2027 template <class _CharT, class _Traits, class _Allocator>
2028 inline _LIBCPP_INLINE_VISIBILITY
2029 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n)
2030 {
2031     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n) detected nullptr");
2032     __init(__s, __n);
2033 #if _LIBCPP_DEBUG_LEVEL >= 2
2034     __get_db()->__insert_c(this);
2035 #endif
2036 }
2037
2038 template <class _CharT, class _Traits, class _Allocator>
2039 inline _LIBCPP_INLINE_VISIBILITY
2040 basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n, const allocator_type& __a)
2041     : __r_(__a)
2042 {
2043     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n, allocator) detected nullptr");
2044     __init(__s, __n);
2045 #if _LIBCPP_DEBUG_LEVEL >= 2
2046     __get_db()->__insert_c(this);
2047 #endif
2048 }
2049
2050 template <class _CharT, class _Traits, class _Allocator>
2051 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str)
2052     : __r_(__alloc_traits::select_on_container_copy_construction(__str.__alloc()))
2053 {
2054     if (!__str.__is_long())
2055         __r_.first().__r = __str.__r_.first().__r;
2056     else
2057         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2058 #if _LIBCPP_DEBUG_LEVEL >= 2
2059     __get_db()->__insert_c(this);
2060 #endif
2061 }
2062
2063 template <class _CharT, class _Traits, class _Allocator>
2064 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, const allocator_type& __a)
2065     : __r_(__a)
2066 {
2067     if (!__str.__is_long())
2068         __r_.first().__r = __str.__r_.first().__r;
2069     else
2070         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2071 #if _LIBCPP_DEBUG_LEVEL >= 2
2072     __get_db()->__insert_c(this);
2073 #endif
2074 }
2075
2076 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2077
2078 template <class _CharT, class _Traits, class _Allocator>
2079 inline _LIBCPP_INLINE_VISIBILITY
2080 basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str)
2081 #if _LIBCPP_STD_VER <= 14
2082         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2083 #else
2084         _NOEXCEPT
2085 #endif
2086     : __r_(_VSTD::move(__str.__r_))
2087 {
2088     __str.__zero();
2089 #if _LIBCPP_DEBUG_LEVEL >= 2
2090     __get_db()->__insert_c(this);
2091     if (__is_long())
2092         __get_db()->swap(this, &__str);
2093 #endif
2094 }
2095
2096 template <class _CharT, class _Traits, class _Allocator>
2097 inline _LIBCPP_INLINE_VISIBILITY
2098 basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str, const allocator_type& __a)
2099     : __r_(__a)
2100 {
2101     if (__str.__is_long() && __a != __str.__alloc()) // copy, not move
2102         __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size());
2103     else
2104     {
2105         __r_.first().__r = __str.__r_.first().__r;
2106         __str.__zero();
2107     }
2108 #if _LIBCPP_DEBUG_LEVEL >= 2
2109     __get_db()->__insert_c(this);
2110     if (__is_long())
2111         __get_db()->swap(this, &__str);
2112 #endif
2113 }
2114
2115 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2116
2117 template <class _CharT, class _Traits, class _Allocator>
2118 void
2119 basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
2120 {
2121     if (__n > max_size())
2122         this->__throw_length_error();
2123     pointer __p;
2124     if (__n < __min_cap)
2125     {
2126         __set_short_size(__n);
2127         __p = __get_short_pointer();
2128     }
2129     else
2130     {
2131         size_type __cap = __recommend(__n);
2132         __p = __alloc_traits::allocate(__alloc(), __cap+1);
2133         __set_long_pointer(__p);
2134         __set_long_cap(__cap+1);
2135         __set_long_size(__n);
2136     }
2137     traits_type::assign(_VSTD::__to_raw_pointer(__p), __n, __c);
2138     traits_type::assign(__p[__n], value_type());
2139 }
2140
2141 template <class _CharT, class _Traits, class _Allocator>
2142 inline _LIBCPP_INLINE_VISIBILITY
2143 basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c)
2144 {
2145     __init(__n, __c);
2146 #if _LIBCPP_DEBUG_LEVEL >= 2
2147     __get_db()->__insert_c(this);
2148 #endif
2149 }
2150
2151 template <class _CharT, class _Traits, class _Allocator>
2152 inline _LIBCPP_INLINE_VISIBILITY
2153 basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c, const allocator_type& __a)
2154     : __r_(__a)
2155 {
2156     __init(__n, __c);
2157 #if _LIBCPP_DEBUG_LEVEL >= 2
2158     __get_db()->__insert_c(this);
2159 #endif
2160 }
2161
2162 template <class _CharT, class _Traits, class _Allocator>
2163 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, size_type __pos, size_type __n,
2164                                                         const allocator_type& __a)
2165     : __r_(__a)
2166 {
2167     size_type __str_sz = __str.size();
2168     if (__pos > __str_sz)
2169         this->__throw_out_of_range();
2170     __init(__str.data() + __pos, _VSTD::min(__n, __str_sz - __pos));
2171 #if _LIBCPP_DEBUG_LEVEL >= 2
2172     __get_db()->__insert_c(this);
2173 #endif
2174 }
2175
2176 template <class _CharT, class _Traits, class _Allocator>
2177 template <class _InputIterator>
2178 typename enable_if
2179 <
2180      __is_input_iterator  <_InputIterator>::value &&
2181     !__is_forward_iterator<_InputIterator>::value,
2182     void
2183 >::type
2184 basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last)
2185 {
2186     __zero();
2187 #ifndef _LIBCPP_NO_EXCEPTIONS
2188     try
2189     {
2190 #endif  // _LIBCPP_NO_EXCEPTIONS
2191     for (; __first != __last; ++__first)
2192         push_back(*__first);
2193 #ifndef _LIBCPP_NO_EXCEPTIONS
2194     }
2195     catch (...)
2196     {
2197         if (__is_long())
2198             __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2199         throw;
2200     }
2201 #endif  // _LIBCPP_NO_EXCEPTIONS
2202 }
2203
2204 template <class _CharT, class _Traits, class _Allocator>
2205 template <class _ForwardIterator>
2206 typename enable_if
2207 <
2208     __is_forward_iterator<_ForwardIterator>::value,
2209     void
2210 >::type
2211 basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
2212 {
2213     size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last));
2214     if (__sz > max_size())
2215         this->__throw_length_error();
2216     pointer __p;
2217     if (__sz < __min_cap)
2218     {
2219         __set_short_size(__sz);
2220         __p = __get_short_pointer();
2221     }
2222     else
2223     {
2224         size_type __cap = __recommend(__sz);
2225         __p = __alloc_traits::allocate(__alloc(), __cap+1);
2226         __set_long_pointer(__p);
2227         __set_long_cap(__cap+1);
2228         __set_long_size(__sz);
2229     }
2230     for (; __first != __last; ++__first, (void) ++__p)
2231         traits_type::assign(*__p, *__first);
2232     traits_type::assign(*__p, value_type());
2233 }
2234
2235 template <class _CharT, class _Traits, class _Allocator>
2236 template<class _InputIterator>
2237 inline _LIBCPP_INLINE_VISIBILITY
2238 basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last)
2239 {
2240     __init(__first, __last);
2241 #if _LIBCPP_DEBUG_LEVEL >= 2
2242     __get_db()->__insert_c(this);
2243 #endif
2244 }
2245
2246 template <class _CharT, class _Traits, class _Allocator>
2247 template<class _InputIterator>
2248 inline _LIBCPP_INLINE_VISIBILITY
2249 basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last,
2250                                                         const allocator_type& __a)
2251     : __r_(__a)
2252 {
2253     __init(__first, __last);
2254 #if _LIBCPP_DEBUG_LEVEL >= 2
2255     __get_db()->__insert_c(this);
2256 #endif
2257 }
2258
2259 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2260
2261 template <class _CharT, class _Traits, class _Allocator>
2262 inline _LIBCPP_INLINE_VISIBILITY
2263 basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il)
2264 {
2265     __init(__il.begin(), __il.end());
2266 #if _LIBCPP_DEBUG_LEVEL >= 2
2267     __get_db()->__insert_c(this);
2268 #endif
2269 }
2270
2271 template <class _CharT, class _Traits, class _Allocator>
2272 inline _LIBCPP_INLINE_VISIBILITY
2273 basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il, const allocator_type& __a)
2274     : __r_(__a)
2275 {
2276     __init(__il.begin(), __il.end());
2277 #if _LIBCPP_DEBUG_LEVEL >= 2
2278     __get_db()->__insert_c(this);
2279 #endif
2280 }
2281
2282 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2283
2284 template <class _CharT, class _Traits, class _Allocator>
2285 basic_string<_CharT, _Traits, _Allocator>::~basic_string()
2286 {
2287 #if _LIBCPP_DEBUG_LEVEL >= 2
2288     __get_db()->__erase_c(this);
2289 #endif
2290     if (__is_long())
2291         __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
2292 }
2293
2294 template <class _CharT, class _Traits, class _Allocator>
2295 void
2296 basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
2297     (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2298      size_type __n_copy,  size_type __n_del,     size_type __n_add, const value_type* __p_new_stuff)
2299 {
2300     size_type __ms = max_size();
2301     if (__delta_cap > __ms - __old_cap - 1)
2302         this->__throw_length_error();
2303     pointer __old_p = __get_pointer();
2304     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2305                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2306                           __ms - 1;
2307     pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
2308     __invalidate_all_iterators();
2309     if (__n_copy != 0)
2310         traits_type::copy(_VSTD::__to_raw_pointer(__p),
2311                           _VSTD::__to_raw_pointer(__old_p), __n_copy);
2312     if (__n_add != 0)
2313         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy, __p_new_stuff, __n_add);
2314     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2315     if (__sec_cp_sz != 0)
2316         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
2317                           _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del, __sec_cp_sz);
2318     if (__old_cap+1 != __min_cap)
2319         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
2320     __set_long_pointer(__p);
2321     __set_long_cap(__cap+1);
2322     __old_sz = __n_copy + __n_add + __sec_cp_sz;
2323     __set_long_size(__old_sz);
2324     traits_type::assign(__p[__old_sz], value_type());
2325 }
2326
2327 template <class _CharT, class _Traits, class _Allocator>
2328 void
2329 basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2330                                                      size_type __n_copy,  size_type __n_del,     size_type __n_add)
2331 {
2332     size_type __ms = max_size();
2333     if (__delta_cap > __ms - __old_cap)
2334         this->__throw_length_error();
2335     pointer __old_p = __get_pointer();
2336     size_type __cap = __old_cap < __ms / 2 - __alignment ?
2337                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
2338                           __ms - 1;
2339     pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
2340     __invalidate_all_iterators();
2341     if (__n_copy != 0)
2342         traits_type::copy(_VSTD::__to_raw_pointer(__p),
2343                           _VSTD::__to_raw_pointer(__old_p), __n_copy);
2344     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2345     if (__sec_cp_sz != 0)
2346         traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
2347                           _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del,
2348                           __sec_cp_sz);
2349     if (__old_cap+1 != __min_cap)
2350         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
2351     __set_long_pointer(__p);
2352     __set_long_cap(__cap+1);
2353 }
2354
2355 // assign
2356
2357 template <class _CharT, class _Traits, class _Allocator>
2358 basic_string<_CharT, _Traits, _Allocator>&
2359 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
2360 {
2361     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr");
2362     size_type __cap = capacity();
2363     if (__cap >= __n)
2364     {
2365         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2366         traits_type::move(__p, __s, __n);
2367         traits_type::assign(__p[__n], value_type());
2368         __set_size(__n);
2369         __invalidate_iterators_past(__n);
2370     }
2371     else
2372     {
2373         size_type __sz = size();
2374         __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
2375     }
2376     return *this;
2377 }
2378
2379 template <class _CharT, class _Traits, class _Allocator>
2380 basic_string<_CharT, _Traits, _Allocator>&
2381 basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
2382 {
2383     size_type __cap = capacity();
2384     if (__cap < __n)
2385     {
2386         size_type __sz = size();
2387         __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2388     }
2389     else
2390         __invalidate_iterators_past(__n);
2391     value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2392     traits_type::assign(__p, __n, __c);
2393     traits_type::assign(__p[__n], value_type());
2394     __set_size(__n);
2395     return *this;
2396 }
2397
2398 template <class _CharT, class _Traits, class _Allocator>
2399 basic_string<_CharT, _Traits, _Allocator>&
2400 basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
2401 {
2402     pointer __p;
2403     if (__is_long())
2404     {
2405         __p = __get_long_pointer();
2406         __set_long_size(1);
2407     }
2408     else
2409     {
2410         __p = __get_short_pointer();
2411         __set_short_size(1);
2412     }
2413     traits_type::assign(*__p, __c);
2414     traits_type::assign(*++__p, value_type());
2415     __invalidate_iterators_past(1);
2416     return *this;
2417 }
2418
2419 template <class _CharT, class _Traits, class _Allocator>
2420 basic_string<_CharT, _Traits, _Allocator>&
2421 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
2422 {
2423     if (this != &__str)
2424     {
2425         __copy_assign_alloc(__str);
2426         assign(__str);
2427     }
2428     return *this;
2429 }
2430
2431 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2432
2433 template <class _CharT, class _Traits, class _Allocator>
2434 inline _LIBCPP_INLINE_VISIBILITY
2435 void
2436 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)
2437     _NOEXCEPT_(__alloc_traits::is_always_equal::value)
2438 {
2439     if (__alloc() != __str.__alloc())
2440         assign(__str);
2441     else
2442         __move_assign(__str, true_type());
2443 }
2444
2445 template <class _CharT, class _Traits, class _Allocator>
2446 inline _LIBCPP_INLINE_VISIBILITY
2447 void
2448 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type)
2449 #if _LIBCPP_STD_VER > 14
2450     _NOEXCEPT
2451 #else
2452     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2453 #endif
2454 {
2455     clear();
2456     shrink_to_fit();
2457     __r_.first() = __str.__r_.first();
2458     __move_assign_alloc(__str);
2459     __str.__zero();
2460 }
2461
2462 template <class _CharT, class _Traits, class _Allocator>
2463 inline _LIBCPP_INLINE_VISIBILITY
2464 basic_string<_CharT, _Traits, _Allocator>&
2465 basic_string<_CharT, _Traits, _Allocator>::operator=(basic_string&& __str)
2466     _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
2467 {
2468     __move_assign(__str, integral_constant<bool,
2469           __alloc_traits::propagate_on_container_move_assignment::value>());
2470     return *this;
2471 }
2472
2473 #endif
2474
2475 template <class _CharT, class _Traits, class _Allocator>
2476 template<class _InputIterator>
2477 typename enable_if
2478 <
2479      __is_input_iterator  <_InputIterator>::value &&
2480     !__is_forward_iterator<_InputIterator>::value,
2481     basic_string<_CharT, _Traits, _Allocator>&
2482 >::type
2483 basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2484 {
2485     clear();
2486     for (; __first != __last; ++__first)
2487         push_back(*__first);
2488     return *this;
2489 }
2490
2491 template <class _CharT, class _Traits, class _Allocator>
2492 template<class _ForwardIterator>
2493 typename enable_if
2494 <
2495     __is_forward_iterator<_ForwardIterator>::value,
2496     basic_string<_CharT, _Traits, _Allocator>&
2497 >::type
2498 basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2499 {
2500     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2501     size_type __cap = capacity();
2502     if (__cap < __n)
2503     {
2504         size_type __sz = size();
2505         __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2506     }
2507     else
2508         __invalidate_iterators_past(__n);
2509     pointer __p = __get_pointer();
2510     for (; __first != __last; ++__first, ++__p)
2511         traits_type::assign(*__p, *__first);
2512     traits_type::assign(*__p, value_type());
2513     __set_size(__n);
2514     return *this;
2515 }
2516
2517 template <class _CharT, class _Traits, class _Allocator>
2518 inline _LIBCPP_INLINE_VISIBILITY
2519 basic_string<_CharT, _Traits, _Allocator>&
2520 basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str)
2521 {
2522     return assign(__str.data(), __str.size());
2523 }
2524
2525 template <class _CharT, class _Traits, class _Allocator>
2526 basic_string<_CharT, _Traits, _Allocator>&
2527 basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n)
2528 {
2529     size_type __sz = __str.size();
2530     if (__pos > __sz)
2531         this->__throw_out_of_range();
2532     return assign(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
2533 }
2534
2535 template <class _CharT, class _Traits, class _Allocator>
2536 basic_string<_CharT, _Traits, _Allocator>&
2537 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s)
2538 {
2539     _LIBCPP_ASSERT(__s != nullptr, "string::assign received nullptr");
2540     return assign(__s, traits_type::length(__s));
2541 }
2542
2543 // append
2544
2545 template <class _CharT, class _Traits, class _Allocator>
2546 basic_string<_CharT, _Traits, _Allocator>&
2547 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n)
2548 {
2549     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::append received nullptr");
2550     size_type __cap = capacity();
2551     size_type __sz = size();
2552     if (__cap - __sz >= __n)
2553     {
2554         if (__n)
2555         {
2556             value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2557             traits_type::copy(__p + __sz, __s, __n);
2558             __sz += __n;
2559             __set_size(__sz);
2560             traits_type::assign(__p[__sz], value_type());
2561         }
2562     }
2563     else
2564         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s);
2565     return *this;
2566 }
2567
2568 template <class _CharT, class _Traits, class _Allocator>
2569 basic_string<_CharT, _Traits, _Allocator>&
2570 basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c)
2571 {
2572     if (__n)
2573     {
2574         size_type __cap = capacity();
2575         size_type __sz = size();
2576         if (__cap - __sz < __n)
2577             __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2578         pointer __p = __get_pointer();
2579         traits_type::assign(_VSTD::__to_raw_pointer(__p) + __sz, __n, __c);
2580         __sz += __n;
2581         __set_size(__sz);
2582         traits_type::assign(__p[__sz], value_type());
2583     }
2584     return *this;
2585 }
2586
2587 template <class _CharT, class _Traits, class _Allocator>
2588 void
2589 basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)
2590 {
2591     bool __is_short = !__is_long();
2592     size_type __cap;
2593     size_type __sz;
2594     if (__is_short)
2595     {
2596         __cap = __min_cap - 1;
2597         __sz = __get_short_size();
2598     }
2599     else
2600     {
2601         __cap = __get_long_cap() - 1;
2602         __sz = __get_long_size();
2603     }
2604     if (__sz == __cap)
2605     {
2606         __grow_by(__cap, 1, __sz, __sz, 0);
2607         __is_short = !__is_long();
2608     }
2609     pointer __p;
2610     if (__is_short)
2611     {
2612         __p = __get_short_pointer() + __sz;
2613         __set_short_size(__sz+1);
2614     }
2615     else
2616     {
2617         __p = __get_long_pointer() + __sz;
2618         __set_long_size(__sz+1);
2619     }
2620     traits_type::assign(*__p, __c);
2621     traits_type::assign(*++__p, value_type());
2622 }
2623
2624 template <class _CharT, class _Traits, class _Allocator>
2625 template<class _InputIterator>
2626 typename enable_if
2627 <
2628      __is_input_iterator  <_InputIterator>::value &&
2629     !__is_forward_iterator<_InputIterator>::value,
2630     basic_string<_CharT, _Traits, _Allocator>&
2631 >::type
2632 basic_string<_CharT, _Traits, _Allocator>::append(_InputIterator __first, _InputIterator __last)
2633 {
2634     for (; __first != __last; ++__first)
2635         push_back(*__first);
2636     return *this;
2637 }
2638
2639 template <class _CharT, class _Traits, class _Allocator>
2640 template<class _ForwardIterator>
2641 typename enable_if
2642 <
2643     __is_forward_iterator<_ForwardIterator>::value,
2644     basic_string<_CharT, _Traits, _Allocator>&
2645 >::type
2646 basic_string<_CharT, _Traits, _Allocator>::append(_ForwardIterator __first, _ForwardIterator __last)
2647 {
2648     size_type __sz = size();
2649     size_type __cap = capacity();
2650     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2651     if (__n)
2652     {
2653         if (__cap - __sz < __n)
2654             __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2655         pointer __p = __get_pointer() + __sz;
2656         for (; __first != __last; ++__p, ++__first)
2657             traits_type::assign(*__p, *__first);
2658         traits_type::assign(*__p, value_type());
2659         __set_size(__sz + __n);
2660     }
2661     return *this;
2662 }
2663
2664 template <class _CharT, class _Traits, class _Allocator>
2665 inline _LIBCPP_INLINE_VISIBILITY
2666 basic_string<_CharT, _Traits, _Allocator>&
2667 basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str)
2668 {
2669     return append(__str.data(), __str.size());
2670 }
2671
2672 template <class _CharT, class _Traits, class _Allocator>
2673 basic_string<_CharT, _Traits, _Allocator>&
2674 basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n)
2675 {
2676     size_type __sz = __str.size();
2677     if (__pos > __sz)
2678         this->__throw_out_of_range();
2679     return append(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
2680 }
2681
2682 template <class _CharT, class _Traits, class _Allocator>
2683 basic_string<_CharT, _Traits, _Allocator>&
2684 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s)
2685 {
2686     _LIBCPP_ASSERT(__s != nullptr, "string::append received nullptr");
2687     return append(__s, traits_type::length(__s));
2688 }
2689
2690 // insert
2691
2692 template <class _CharT, class _Traits, class _Allocator>
2693 basic_string<_CharT, _Traits, _Allocator>&
2694 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s, size_type __n)
2695 {
2696     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::insert received nullptr");
2697     size_type __sz = size();
2698     if (__pos > __sz)
2699         this->__throw_out_of_range();
2700     size_type __cap = capacity();
2701     if (__cap - __sz >= __n)
2702     {
2703         if (__n)
2704         {
2705             value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2706             size_type __n_move = __sz - __pos;
2707             if (__n_move != 0)
2708             {
2709                 if (__p + __pos <= __s && __s < __p + __sz)
2710                     __s += __n;
2711                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2712             }
2713             traits_type::move(__p + __pos, __s, __n);
2714             __sz += __n;
2715             __set_size(__sz);
2716             traits_type::assign(__p[__sz], value_type());
2717         }
2718     }
2719     else
2720         __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s);
2721     return *this;
2722 }
2723
2724 template <class _CharT, class _Traits, class _Allocator>
2725 basic_string<_CharT, _Traits, _Allocator>&
2726 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c)
2727 {
2728     size_type __sz = size();
2729     if (__pos > __sz)
2730         this->__throw_out_of_range();
2731     if (__n)
2732     {
2733         size_type __cap = capacity();
2734         value_type* __p;
2735         if (__cap - __sz >= __n)
2736         {
2737             __p = _VSTD::__to_raw_pointer(__get_pointer());
2738             size_type __n_move = __sz - __pos;
2739             if (__n_move != 0)
2740                 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2741         }
2742         else
2743         {
2744             __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n);
2745             __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2746         }
2747         traits_type::assign(__p + __pos, __n, __c);
2748         __sz += __n;
2749         __set_size(__sz);
2750         traits_type::assign(__p[__sz], value_type());
2751     }
2752     return *this;
2753 }
2754
2755 template <class _CharT, class _Traits, class _Allocator>
2756 template<class _InputIterator>
2757 typename enable_if
2758 <
2759      __is_input_iterator  <_InputIterator>::value &&
2760     !__is_forward_iterator<_InputIterator>::value,
2761     typename basic_string<_CharT, _Traits, _Allocator>::iterator
2762 >::type
2763 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last)
2764 {
2765 #if _LIBCPP_DEBUG_LEVEL >= 2
2766     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2767         "string::insert(iterator, range) called with an iterator not"
2768         " referring to this string");
2769 #endif
2770     size_type __old_sz = size();
2771     difference_type __ip = __pos - begin();
2772     for (; __first != __last; ++__first)
2773         push_back(*__first);
2774     pointer __p = __get_pointer();
2775     _VSTD::rotate(__p + __ip, __p + __old_sz, __p + size());
2776 #if _LIBCPP_DEBUG_LEVEL >= 2
2777     return iterator(this, __p + __ip);
2778 #else
2779     return iterator(__p + __ip);
2780 #endif
2781 }
2782
2783 template <class _CharT, class _Traits, class _Allocator>
2784 template<class _ForwardIterator>
2785 typename enable_if
2786 <
2787     __is_forward_iterator<_ForwardIterator>::value,
2788     typename basic_string<_CharT, _Traits, _Allocator>::iterator
2789 >::type
2790 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last)
2791 {
2792 #if _LIBCPP_DEBUG_LEVEL >= 2
2793     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2794         "string::insert(iterator, range) called with an iterator not"
2795         " referring to this string");
2796 #endif
2797     size_type __ip = static_cast<size_type>(__pos - begin());
2798     size_type __sz = size();
2799     size_type __cap = capacity();
2800     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2801     if (__n)
2802     {
2803         value_type* __p;
2804         if (__cap - __sz >= __n)
2805         {
2806             __p = _VSTD::__to_raw_pointer(__get_pointer());
2807             size_type __n_move = __sz - __ip;
2808             if (__n_move != 0)
2809                 traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
2810         }
2811         else
2812         {
2813             __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
2814             __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2815         }
2816         __sz += __n;
2817         __set_size(__sz);
2818         traits_type::assign(__p[__sz], value_type());
2819         for (__p += __ip; __first != __last; ++__p, ++__first)
2820             traits_type::assign(*__p, *__first);
2821     }
2822     return begin() + __ip;
2823 }
2824
2825 template <class _CharT, class _Traits, class _Allocator>
2826 inline _LIBCPP_INLINE_VISIBILITY
2827 basic_string<_CharT, _Traits, _Allocator>&
2828 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str)
2829 {
2830     return insert(__pos1, __str.data(), __str.size());
2831 }
2832
2833 template <class _CharT, class _Traits, class _Allocator>
2834 basic_string<_CharT, _Traits, _Allocator>&
2835 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str,
2836                                                   size_type __pos2, size_type __n)
2837 {
2838     size_type __str_sz = __str.size();
2839     if (__pos2 > __str_sz)
2840         this->__throw_out_of_range();
2841     return insert(__pos1, __str.data() + __pos2, _VSTD::min(__n, __str_sz - __pos2));
2842 }
2843
2844 template <class _CharT, class _Traits, class _Allocator>
2845 basic_string<_CharT, _Traits, _Allocator>&
2846 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s)
2847 {
2848     _LIBCPP_ASSERT(__s != nullptr, "string::insert received nullptr");
2849     return insert(__pos, __s, traits_type::length(__s));
2850 }
2851
2852 template <class _CharT, class _Traits, class _Allocator>
2853 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2854 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c)
2855 {
2856     size_type __ip = static_cast<size_type>(__pos - begin());
2857     size_type __sz = size();
2858     size_type __cap = capacity();
2859     value_type* __p;
2860     if (__cap == __sz)
2861     {
2862         __grow_by(__cap, 1, __sz, __ip, 0, 1);
2863         __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2864     }
2865     else
2866     {
2867         __p = _VSTD::__to_raw_pointer(__get_pointer());
2868         size_type __n_move = __sz - __ip;
2869         if (__n_move != 0)
2870             traits_type::move(__p + __ip + 1, __p + __ip, __n_move);
2871     }
2872     traits_type::assign(__p[__ip], __c);
2873     traits_type::assign(__p[++__sz], value_type());
2874     __set_size(__sz);
2875     return begin() + static_cast<difference_type>(__ip);
2876 }
2877
2878 template <class _CharT, class _Traits, class _Allocator>
2879 inline _LIBCPP_INLINE_VISIBILITY
2880 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2881 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, size_type __n, value_type __c)
2882 {
2883 #if _LIBCPP_DEBUG_LEVEL >= 2
2884     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
2885         "string::insert(iterator, n, value) called with an iterator not"
2886         " referring to this string");
2887 #endif
2888     difference_type __p = __pos - begin();
2889     insert(static_cast<size_type>(__p), __n, __c);
2890     return begin() + __p;
2891 }
2892
2893 // replace
2894
2895 template <class _CharT, class _Traits, class _Allocator>
2896 basic_string<_CharT, _Traits, _Allocator>&
2897 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2)
2898 {
2899     _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::replace received nullptr");
2900     size_type __sz = size();
2901     if (__pos > __sz)
2902         this->__throw_out_of_range();
2903     __n1 = _VSTD::min(__n1, __sz - __pos);
2904     size_type __cap = capacity();
2905     if (__cap - __sz + __n1 >= __n2)
2906     {
2907         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
2908         if (__n1 != __n2)
2909         {
2910             size_type __n_move = __sz - __pos - __n1;
2911             if (__n_move != 0)
2912             {
2913                 if (__n1 > __n2)
2914                 {
2915                     traits_type::move(__p + __pos, __s, __n2);
2916                     traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2917                     goto __finish;
2918                 }
2919                 if (__p + __pos < __s && __s < __p + __sz)
2920                 {
2921                     if (__p + __pos + __n1 <= __s)
2922                         __s += __n2 - __n1;
2923                     else // __p + __pos < __s < __p + __pos + __n1
2924                     {
2925                         traits_type::move(__p + __pos, __s, __n1);
2926                         __pos += __n1;
2927                         __s += __n2;
2928                         __n2 -= __n1;
2929                         __n1 = 0;
2930                     }
2931                 }
2932                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2933             }
2934         }
2935         traits_type::move(__p + __pos, __s, __n2);
2936 __finish:
2937         __sz += __n2 - __n1;
2938         __set_size(__sz);
2939         __invalidate_iterators_past(__sz);
2940         traits_type::assign(__p[__sz], value_type());
2941     }
2942     else
2943         __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s);
2944     return *this;
2945 }
2946
2947 template <class _CharT, class _Traits, class _Allocator>
2948 basic_string<_CharT, _Traits, _Allocator>&
2949 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c)
2950 {
2951     size_type __sz = size();
2952     if (__pos > __sz)
2953         this->__throw_out_of_range();
2954     __n1 = _VSTD::min(__n1, __sz - __pos);
2955     size_type __cap = capacity();
2956     value_type* __p;
2957     if (__cap - __sz + __n1 >= __n2)
2958     {
2959         __p = _VSTD::__to_raw_pointer(__get_pointer());
2960         if (__n1 != __n2)
2961         {
2962             size_type __n_move = __sz - __pos - __n1;
2963             if (__n_move != 0)
2964                 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2965         }
2966     }
2967     else
2968     {
2969         __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2);
2970         __p = _VSTD::__to_raw_pointer(__get_long_pointer());
2971     }
2972     traits_type::assign(__p + __pos, __n2, __c);
2973     __sz += __n2 - __n1;
2974     __set_size(__sz);
2975     __invalidate_iterators_past(__sz);
2976     traits_type::assign(__p[__sz], value_type());
2977     return *this;
2978 }
2979
2980 template <class _CharT, class _Traits, class _Allocator>
2981 template<class _InputIterator>
2982 typename enable_if
2983 <
2984     __is_input_iterator<_InputIterator>::value,
2985     basic_string<_CharT, _Traits, _Allocator>&
2986 >::type
2987 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2,
2988                                                    _InputIterator __j1, _InputIterator __j2)
2989 {
2990     for (; true; ++__i1, ++__j1)
2991     {
2992         if (__i1 == __i2)
2993         {
2994             if (__j1 != __j2)
2995                 insert(__i1, __j1, __j2);
2996             break;
2997         }
2998         if (__j1 == __j2)
2999         {
3000             erase(__i1, __i2);
3001             break;
3002         }
3003         traits_type::assign(const_cast<value_type&>(*__i1), *__j1);
3004     }
3005     return *this;
3006 }
3007
3008 template <class _CharT, class _Traits, class _Allocator>
3009 inline _LIBCPP_INLINE_VISIBILITY
3010 basic_string<_CharT, _Traits, _Allocator>&
3011 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str)
3012 {
3013     return replace(__pos1, __n1, __str.data(), __str.size());
3014 }
3015
3016 template <class _CharT, class _Traits, class _Allocator>
3017 basic_string<_CharT, _Traits, _Allocator>&
3018 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str,
3019                                                    size_type __pos2, size_type __n2)
3020 {
3021     size_type __str_sz = __str.size();
3022     if (__pos2 > __str_sz)
3023         this->__throw_out_of_range();
3024     return replace(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, __str_sz - __pos2));
3025 }
3026
3027 template <class _CharT, class _Traits, class _Allocator>
3028 basic_string<_CharT, _Traits, _Allocator>&
3029 basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s)
3030 {
3031     _LIBCPP_ASSERT(__s != nullptr, "string::replace received nullptr");
3032     return replace(__pos, __n1, __s, traits_type::length(__s));
3033 }
3034
3035 template <class _CharT, class _Traits, class _Allocator>
3036 inline _LIBCPP_INLINE_VISIBILITY
3037 basic_string<_CharT, _Traits, _Allocator>&
3038 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const basic_string& __str)
3039 {
3040     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1),
3041                    __str.data(), __str.size());
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, size_type __n)
3048 {
3049     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n);
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, const value_type* __s)
3056 {
3057     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s);
3058 }
3059
3060 template <class _CharT, class _Traits, class _Allocator>
3061 inline _LIBCPP_INLINE_VISIBILITY
3062 basic_string<_CharT, _Traits, _Allocator>&
3063 basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c)
3064 {
3065     return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c);
3066 }
3067
3068 // erase
3069
3070 template <class _CharT, class _Traits, class _Allocator>
3071 basic_string<_CharT, _Traits, _Allocator>&
3072 basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos, size_type __n)
3073 {
3074     size_type __sz = size();
3075     if (__pos > __sz)
3076         this->__throw_out_of_range();
3077     if (__n)
3078     {
3079         value_type* __p = _VSTD::__to_raw_pointer(__get_pointer());
3080         __n = _VSTD::min(__n, __sz - __pos);
3081         size_type __n_move = __sz - __pos - __n;
3082         if (__n_move != 0)
3083             traits_type::move(__p + __pos, __p + __pos + __n, __n_move);
3084         __sz -= __n;
3085         __set_size(__sz);
3086         __invalidate_iterators_past(__sz);
3087         traits_type::assign(__p[__sz], value_type());
3088     }
3089     return *this;
3090 }
3091
3092 template <class _CharT, class _Traits, class _Allocator>
3093 inline _LIBCPP_INLINE_VISIBILITY
3094 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3095 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos)
3096 {
3097 #if _LIBCPP_DEBUG_LEVEL >= 2
3098     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
3099         "string::erase(iterator) called with an iterator not"
3100         " referring to this string");
3101 #endif
3102     _LIBCPP_ASSERT(__pos != end(),
3103         "string::erase(iterator) called with a non-dereferenceable iterator");
3104     iterator __b = begin();
3105     size_type __r = static_cast<size_type>(__pos - __b);
3106     erase(__r, 1);
3107     return __b + static_cast<difference_type>(__r);
3108 }
3109
3110 template <class _CharT, class _Traits, class _Allocator>
3111 inline _LIBCPP_INLINE_VISIBILITY
3112 typename basic_string<_CharT, _Traits, _Allocator>::iterator
3113 basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last)
3114 {
3115 #if _LIBCPP_DEBUG_LEVEL >= 2
3116     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
3117         "string::erase(iterator,  iterator) called with an iterator not"
3118         " referring to this string");
3119 #endif
3120     _LIBCPP_ASSERT(__first <= __last, "string::erase(first, last) called with invalid range");
3121     iterator __b = begin();
3122     size_type __r = static_cast<size_type>(__first - __b);
3123     erase(__r, static_cast<size_type>(__last - __first));
3124     return __b + static_cast<difference_type>(__r);
3125 }
3126
3127 template <class _CharT, class _Traits, class _Allocator>
3128 inline _LIBCPP_INLINE_VISIBILITY
3129 void
3130 basic_string<_CharT, _Traits, _Allocator>::pop_back()
3131 {
3132     _LIBCPP_ASSERT(!empty(), "string::pop_back(): string is already empty");
3133     size_type __sz;
3134     if (__is_long())
3135     {
3136         __sz = __get_long_size() - 1;
3137         __set_long_size(__sz);
3138         traits_type::assign(*(__get_long_pointer() + __sz), value_type());
3139     }
3140     else
3141     {
3142         __sz = __get_short_size() - 1;
3143         __set_short_size(__sz);
3144         traits_type::assign(*(__get_short_pointer() + __sz), value_type());
3145     }
3146     __invalidate_iterators_past(__sz);
3147 }
3148
3149 template <class _CharT, class _Traits, class _Allocator>
3150 inline _LIBCPP_INLINE_VISIBILITY
3151 void
3152 basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT
3153 {
3154     __invalidate_all_iterators();
3155     if (__is_long())
3156     {
3157         traits_type::assign(*__get_long_pointer(), value_type());
3158         __set_long_size(0);
3159     }
3160     else
3161     {
3162         traits_type::assign(*__get_short_pointer(), value_type());
3163         __set_short_size(0);
3164     }
3165 }
3166
3167 template <class _CharT, class _Traits, class _Allocator>
3168 inline _LIBCPP_INLINE_VISIBILITY
3169 void
3170 basic_string<_CharT, _Traits, _Allocator>::__erase_to_end(size_type __pos)
3171 {
3172     if (__is_long())
3173     {
3174         traits_type::assign(*(__get_long_pointer() + __pos), value_type());
3175         __set_long_size(__pos);
3176     }
3177     else
3178     {
3179         traits_type::assign(*(__get_short_pointer() + __pos), value_type());
3180         __set_short_size(__pos);
3181     }
3182     __invalidate_iterators_past(__pos);
3183 }
3184
3185 template <class _CharT, class _Traits, class _Allocator>
3186 void
3187 basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
3188 {
3189     size_type __sz = size();
3190     if (__n > __sz)
3191         append(__n - __sz, __c);
3192     else
3193         __erase_to_end(__n);
3194 }
3195
3196 template <class _CharT, class _Traits, class _Allocator>
3197 inline _LIBCPP_INLINE_VISIBILITY
3198 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3199 basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT
3200 {
3201     size_type __m = __alloc_traits::max_size(__alloc());
3202 #if _LIBCPP_BIG_ENDIAN
3203     return (__m <= ~__long_mask ? __m : __m/2) - __alignment;
3204 #else
3205     return __m - __alignment;
3206 #endif
3207 }
3208
3209 template <class _CharT, class _Traits, class _Allocator>
3210 void
3211 basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __res_arg)
3212 {
3213     if (__res_arg > max_size())
3214         this->__throw_length_error();
3215     size_type __cap = capacity();
3216     size_type __sz = size();
3217     __res_arg = _VSTD::max(__res_arg, __sz);
3218     __res_arg = __recommend(__res_arg);
3219     if (__res_arg != __cap)
3220     {
3221         pointer __new_data, __p;
3222         bool __was_long, __now_long;
3223         if (__res_arg == __min_cap - 1)
3224         {
3225             __was_long = true;
3226             __now_long = false;
3227             __new_data = __get_short_pointer();
3228             __p = __get_long_pointer();
3229         }
3230         else
3231         {
3232             if (__res_arg > __cap)
3233                 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
3234             else
3235             {
3236             #ifndef _LIBCPP_NO_EXCEPTIONS
3237                 try
3238                 {
3239             #endif  // _LIBCPP_NO_EXCEPTIONS
3240                     __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
3241             #ifndef _LIBCPP_NO_EXCEPTIONS
3242                 }
3243                 catch (...)
3244                 {
3245                     return;
3246                 }
3247             #else  // _LIBCPP_NO_EXCEPTIONS
3248                 if (__new_data == nullptr)
3249                     return;
3250             #endif  // _LIBCPP_NO_EXCEPTIONS
3251             }
3252             __now_long = true;
3253             __was_long = __is_long();
3254             __p = __get_pointer();
3255         }
3256         traits_type::copy(_VSTD::__to_raw_pointer(__new_data),
3257                           _VSTD::__to_raw_pointer(__p), size()+1);
3258         if (__was_long)
3259             __alloc_traits::deallocate(__alloc(), __p, __cap+1);
3260         if (__now_long)
3261         {
3262             __set_long_cap(__res_arg+1);
3263             __set_long_size(__sz);
3264             __set_long_pointer(__new_data);
3265         }
3266         else
3267             __set_short_size(__sz);
3268         __invalidate_all_iterators();
3269     }
3270 }
3271
3272 template <class _CharT, class _Traits, class _Allocator>
3273 inline _LIBCPP_INLINE_VISIBILITY
3274 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3275 basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) const
3276 {
3277     _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds");
3278     return *(data() + __pos);
3279 }
3280
3281 template <class _CharT, class _Traits, class _Allocator>
3282 inline _LIBCPP_INLINE_VISIBILITY
3283 typename basic_string<_CharT, _Traits, _Allocator>::reference
3284 basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos)
3285 {
3286     _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds");
3287     return *(__get_pointer() + __pos);
3288 }
3289
3290 template <class _CharT, class _Traits, class _Allocator>
3291 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3292 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const
3293 {
3294     if (__n >= size())
3295         this->__throw_out_of_range();
3296     return (*this)[__n];
3297 }
3298
3299 template <class _CharT, class _Traits, class _Allocator>
3300 typename basic_string<_CharT, _Traits, _Allocator>::reference
3301 basic_string<_CharT, _Traits, _Allocator>::at(size_type __n)
3302 {
3303     if (__n >= size())
3304         this->__throw_out_of_range();
3305     return (*this)[__n];
3306 }
3307
3308 template <class _CharT, class _Traits, class _Allocator>
3309 inline _LIBCPP_INLINE_VISIBILITY
3310 typename basic_string<_CharT, _Traits, _Allocator>::reference
3311 basic_string<_CharT, _Traits, _Allocator>::front()
3312 {
3313     _LIBCPP_ASSERT(!empty(), "string::front(): string is empty");
3314     return *__get_pointer();
3315 }
3316
3317 template <class _CharT, class _Traits, class _Allocator>
3318 inline _LIBCPP_INLINE_VISIBILITY
3319 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3320 basic_string<_CharT, _Traits, _Allocator>::front() const
3321 {
3322     _LIBCPP_ASSERT(!empty(), "string::front(): string is empty");
3323     return *data();
3324 }
3325
3326 template <class _CharT, class _Traits, class _Allocator>
3327 inline _LIBCPP_INLINE_VISIBILITY
3328 typename basic_string<_CharT, _Traits, _Allocator>::reference
3329 basic_string<_CharT, _Traits, _Allocator>::back()
3330 {
3331     _LIBCPP_ASSERT(!empty(), "string::back(): string is empty");
3332     return *(__get_pointer() + size() - 1);
3333 }
3334
3335 template <class _CharT, class _Traits, class _Allocator>
3336 inline _LIBCPP_INLINE_VISIBILITY
3337 typename basic_string<_CharT, _Traits, _Allocator>::const_reference
3338 basic_string<_CharT, _Traits, _Allocator>::back() const
3339 {
3340     _LIBCPP_ASSERT(!empty(), "string::back(): string is empty");
3341     return *(data() + size() - 1);
3342 }
3343
3344 template <class _CharT, class _Traits, class _Allocator>
3345 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3346 basic_string<_CharT, _Traits, _Allocator>::copy(value_type* __s, size_type __n, size_type __pos) const
3347 {
3348     size_type __sz = size();
3349     if (__pos > __sz)
3350         this->__throw_out_of_range();
3351     size_type __rlen = _VSTD::min(__n, __sz - __pos);
3352     traits_type::copy(__s, data() + __pos, __rlen);
3353     return __rlen;
3354 }
3355
3356 template <class _CharT, class _Traits, class _Allocator>
3357 inline _LIBCPP_INLINE_VISIBILITY
3358 basic_string<_CharT, _Traits, _Allocator>
3359 basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const
3360 {
3361     return basic_string(*this, __pos, __n, __alloc());
3362 }
3363
3364 template <class _CharT, class _Traits, class _Allocator>
3365 inline _LIBCPP_INLINE_VISIBILITY
3366 void
3367 basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str)
3368 #if _LIBCPP_STD_VER >= 14
3369         _NOEXCEPT
3370 #else
3371         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3372                     __is_nothrow_swappable<allocator_type>::value)
3373 #endif
3374 {
3375 #if _LIBCPP_DEBUG_LEVEL >= 2
3376     if (!__is_long())
3377         __get_db()->__invalidate_all(this);
3378     if (!__str.__is_long())
3379         __get_db()->__invalidate_all(&__str);
3380     __get_db()->swap(this, &__str);
3381 #endif
3382     _VSTD::swap(__r_.first(), __str.__r_.first());
3383     __swap_allocator(__alloc(), __str.__alloc());
3384 }
3385
3386 // find
3387
3388 template <class _Traits>
3389 struct _LIBCPP_HIDDEN __traits_eq
3390 {
3391     typedef typename _Traits::char_type char_type;
3392     _LIBCPP_INLINE_VISIBILITY
3393     bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT
3394         {return _Traits::eq(__x, __y);}
3395 };
3396
3397 template<class _CharT, class _Traits, class _Allocator>
3398 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3399 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3400                                                 size_type __pos,
3401                                                 size_type __n) const _NOEXCEPT
3402 {
3403     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find(): received nullptr");
3404     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3405         (data(), size(), __s, __pos, __n);
3406 }
3407
3408 template<class _CharT, class _Traits, class _Allocator>
3409 inline _LIBCPP_INLINE_VISIBILITY
3410 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3411 basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str,
3412                                                 size_type __pos) const _NOEXCEPT
3413 {
3414     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3415         (data(), size(), __str.data(), __pos, __str.size());
3416 }
3417
3418 template<class _CharT, class _Traits, class _Allocator>
3419 inline _LIBCPP_INLINE_VISIBILITY
3420 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3421 basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
3422                                                 size_type __pos) const _NOEXCEPT
3423 {
3424     _LIBCPP_ASSERT(__s != nullptr, "string::find(): received nullptr");
3425     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3426         (data(), size(), __s, __pos, traits_type::length(__s));
3427 }
3428
3429 template<class _CharT, class _Traits, class _Allocator>
3430 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3431 basic_string<_CharT, _Traits, _Allocator>::find(value_type __c,
3432                                                 size_type __pos) const _NOEXCEPT
3433 {
3434     return _VSTD::__str_find<value_type, size_type, traits_type, npos>
3435         (data(), size(), __c, __pos);
3436 }
3437
3438 // rfind
3439
3440 template<class _CharT, class _Traits, class _Allocator>
3441 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3442 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3443                                                  size_type __pos,
3444                                                  size_type __n) const _NOEXCEPT
3445 {
3446     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::rfind(): received nullptr");
3447     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3448         (data(), size(), __s, __pos, __n);
3449 }
3450
3451 template<class _CharT, class _Traits, class _Allocator>
3452 inline _LIBCPP_INLINE_VISIBILITY
3453 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3454 basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str,
3455                                                  size_type __pos) const _NOEXCEPT
3456 {
3457     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3458         (data(), size(), __str.data(), __pos, __str.size());
3459 }
3460
3461 template<class _CharT, class _Traits, class _Allocator>
3462 inline _LIBCPP_INLINE_VISIBILITY
3463 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3464 basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s,
3465                                                  size_type __pos) const _NOEXCEPT
3466 {
3467     _LIBCPP_ASSERT(__s != nullptr, "string::rfind(): received nullptr");
3468     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3469         (data(), size(), __s, __pos, traits_type::length(__s));
3470 }
3471
3472 template<class _CharT, class _Traits, class _Allocator>
3473 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3474 basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c,
3475                                                  size_type __pos) const _NOEXCEPT
3476 {
3477     return _VSTD::__str_rfind<value_type, size_type, traits_type, npos>
3478         (data(), size(), __c, __pos);
3479 }
3480
3481 // find_first_of
3482
3483 template<class _CharT, class _Traits, class _Allocator>
3484 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3485 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3486                                                          size_type __pos,
3487                                                          size_type __n) const _NOEXCEPT
3488 {
3489     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_of(): received nullptr");
3490     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3491         (data(), size(), __s, __pos, __n);
3492 }
3493
3494 template<class _CharT, class _Traits, class _Allocator>
3495 inline _LIBCPP_INLINE_VISIBILITY
3496 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3497 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str,
3498                                                          size_type __pos) const _NOEXCEPT
3499 {
3500     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3501         (data(), size(), __str.data(), __pos, __str.size());
3502 }
3503
3504 template<class _CharT, class _Traits, class _Allocator>
3505 inline _LIBCPP_INLINE_VISIBILITY
3506 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3507 basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s,
3508                                                          size_type __pos) const _NOEXCEPT
3509 {
3510     _LIBCPP_ASSERT(__s != nullptr, "string::find_first_of(): received nullptr");
3511     return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos>
3512         (data(), size(), __s, __pos, traits_type::length(__s));
3513 }
3514
3515 template<class _CharT, class _Traits, class _Allocator>
3516 inline _LIBCPP_INLINE_VISIBILITY
3517 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3518 basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c,
3519                                                          size_type __pos) const _NOEXCEPT
3520 {
3521     return find(__c, __pos);
3522 }
3523
3524 // find_last_of
3525
3526 template<class _CharT, class _Traits, class _Allocator>
3527 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3528 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3529                                                         size_type __pos,
3530                                                         size_type __n) const _NOEXCEPT
3531 {
3532     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_of(): received nullptr");
3533     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3534         (data(), size(), __s, __pos, __n);
3535 }
3536
3537 template<class _CharT, class _Traits, class _Allocator>
3538 inline _LIBCPP_INLINE_VISIBILITY
3539 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3540 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str,
3541                                                         size_type __pos) const _NOEXCEPT
3542 {
3543     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3544         (data(), size(), __str.data(), __pos, __str.size());
3545 }
3546
3547 template<class _CharT, class _Traits, class _Allocator>
3548 inline _LIBCPP_INLINE_VISIBILITY
3549 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3550 basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s,
3551                                                         size_type __pos) const _NOEXCEPT
3552 {
3553     _LIBCPP_ASSERT(__s != nullptr, "string::find_last_of(): received nullptr");
3554     return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos>
3555         (data(), size(), __s, __pos, traits_type::length(__s));
3556 }
3557
3558 template<class _CharT, class _Traits, class _Allocator>
3559 inline _LIBCPP_INLINE_VISIBILITY
3560 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3561 basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c,
3562                                                         size_type __pos) const _NOEXCEPT
3563 {
3564     return rfind(__c, __pos);
3565 }
3566
3567 // find_first_not_of
3568
3569 template<class _CharT, class _Traits, class _Allocator>
3570 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3571 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3572                                                              size_type __pos,
3573                                                              size_type __n) const _NOEXCEPT
3574 {
3575     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_not_of(): received nullptr");
3576     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3577         (data(), size(), __s, __pos, __n);
3578 }
3579
3580 template<class _CharT, class _Traits, class _Allocator>
3581 inline _LIBCPP_INLINE_VISIBILITY
3582 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3583 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str,
3584                                                              size_type __pos) const _NOEXCEPT
3585 {
3586     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3587         (data(), size(), __str.data(), __pos, __str.size());
3588 }
3589
3590 template<class _CharT, class _Traits, class _Allocator>
3591 inline _LIBCPP_INLINE_VISIBILITY
3592 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3593 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s,
3594                                                              size_type __pos) const _NOEXCEPT
3595 {
3596     _LIBCPP_ASSERT(__s != nullptr, "string::find_first_not_of(): received nullptr");
3597     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3598         (data(), size(), __s, __pos, traits_type::length(__s));
3599 }
3600
3601 template<class _CharT, class _Traits, class _Allocator>
3602 inline _LIBCPP_INLINE_VISIBILITY
3603 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3604 basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c,
3605                                                              size_type __pos) const _NOEXCEPT
3606 {
3607     return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos>
3608         (data(), size(), __c, __pos);
3609 }
3610
3611 // find_last_not_of
3612
3613 template<class _CharT, class _Traits, class _Allocator>
3614 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3615 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3616                                                             size_type __pos,
3617                                                             size_type __n) const _NOEXCEPT
3618 {
3619     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_not_of(): received nullptr");
3620     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3621         (data(), size(), __s, __pos, __n);
3622 }
3623
3624 template<class _CharT, class _Traits, class _Allocator>
3625 inline _LIBCPP_INLINE_VISIBILITY
3626 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3627 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str,
3628                                                             size_type __pos) const _NOEXCEPT
3629 {
3630     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3631         (data(), size(), __str.data(), __pos, __str.size());
3632 }
3633
3634 template<class _CharT, class _Traits, class _Allocator>
3635 inline _LIBCPP_INLINE_VISIBILITY
3636 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3637 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s,
3638                                                             size_type __pos) const _NOEXCEPT
3639 {
3640     _LIBCPP_ASSERT(__s != nullptr, "string::find_last_not_of(): received nullptr");
3641     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3642         (data(), size(), __s, __pos, traits_type::length(__s));
3643 }
3644
3645 template<class _CharT, class _Traits, class _Allocator>
3646 inline _LIBCPP_INLINE_VISIBILITY
3647 typename basic_string<_CharT, _Traits, _Allocator>::size_type
3648 basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c,
3649                                                             size_type __pos) const _NOEXCEPT
3650 {
3651     return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos>
3652         (data(), size(), __c, __pos);
3653 }
3654
3655 // compare
3656
3657 template <class _CharT, class _Traits, class _Allocator>
3658 inline _LIBCPP_INLINE_VISIBILITY
3659 int
3660 basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT
3661 {
3662     size_t __lhs_sz = size();
3663     size_t __rhs_sz = __str.size();
3664     int __result = traits_type::compare(data(), __str.data(),
3665                                         _VSTD::min(__lhs_sz, __rhs_sz));
3666     if (__result != 0)
3667         return __result;
3668     if (__lhs_sz < __rhs_sz)
3669         return -1;
3670     if (__lhs_sz > __rhs_sz)
3671         return 1;
3672     return 0;
3673 }
3674
3675 template <class _CharT, class _Traits, class _Allocator>
3676 inline _LIBCPP_INLINE_VISIBILITY
3677 int
3678 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3679                                                    size_type __n1,
3680                                                    const basic_string& __str) const
3681 {
3682     return compare(__pos1, __n1, __str.data(), __str.size());
3683 }
3684
3685 template <class _CharT, class _Traits, class _Allocator>
3686 int
3687 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3688                                                    size_type __n1,
3689                                                    const basic_string& __str,
3690                                                    size_type __pos2,
3691                                                    size_type __n2) const
3692 {
3693     size_type __sz = __str.size();
3694     if (__pos2 > __sz)
3695         this->__throw_out_of_range();
3696     return compare(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2,
3697                                                                   __sz - __pos2));
3698 }
3699
3700 template <class _CharT, class _Traits, class _Allocator>
3701 int
3702 basic_string<_CharT, _Traits, _Allocator>::compare(const value_type* __s) const _NOEXCEPT
3703 {
3704     _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr");
3705     return compare(0, npos, __s, traits_type::length(__s));
3706 }
3707
3708 template <class _CharT, class _Traits, class _Allocator>
3709 int
3710 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3711                                                    size_type __n1,
3712                                                    const value_type* __s) const
3713 {
3714     _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr");
3715     return compare(__pos1, __n1, __s, traits_type::length(__s));
3716 }
3717
3718 template <class _CharT, class _Traits, class _Allocator>
3719 int
3720 basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3721                                                    size_type __n1,
3722                                                    const value_type* __s,
3723                                                    size_type __n2) const
3724 {
3725     _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::compare(): received nullptr");
3726     size_type __sz = size();
3727     if (__pos1 > __sz || __n2 == npos)
3728         this->__throw_out_of_range();
3729     size_type __rlen = _VSTD::min(__n1, __sz - __pos1);
3730     int __r = traits_type::compare(data() + __pos1, __s, _VSTD::min(__rlen, __n2));
3731     if (__r == 0)
3732     {
3733         if (__rlen < __n2)
3734             __r = -1;
3735         else if (__rlen > __n2)
3736             __r = 1;
3737     }
3738     return __r;
3739 }
3740
3741 // __invariants
3742
3743 template<class _CharT, class _Traits, class _Allocator>
3744 inline _LIBCPP_INLINE_VISIBILITY
3745 bool
3746 basic_string<_CharT, _Traits, _Allocator>::__invariants() const
3747 {
3748     if (size() > capacity())
3749         return false;
3750     if (capacity() < __min_cap - 1)
3751         return false;
3752     if (data() == 0)
3753         return false;
3754     if (data()[size()] != value_type(0))
3755         return false;
3756     return true;
3757 }
3758
3759 // operator==
3760
3761 template<class _CharT, class _Traits, class _Allocator>
3762 inline _LIBCPP_INLINE_VISIBILITY
3763 bool
3764 operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3765            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3766 {
3767     size_t __lhs_sz = __lhs.size();
3768     return __lhs_sz == __rhs.size() && _Traits::compare(__lhs.data(),
3769                                                         __rhs.data(),
3770                                                         __lhs_sz) == 0;
3771 }
3772
3773 template<class _Allocator>
3774 inline _LIBCPP_INLINE_VISIBILITY
3775 bool
3776 operator==(const basic_string<char, char_traits<char>, _Allocator>& __lhs,
3777            const basic_string<char, char_traits<char>, _Allocator>& __rhs) _NOEXCEPT
3778 {
3779     size_t __lhs_sz = __lhs.size();
3780     if (__lhs_sz != __rhs.size())
3781         return false;
3782     const char* __lp = __lhs.data();
3783     const char* __rp = __rhs.data();
3784     if (__lhs.__is_long())
3785         return char_traits<char>::compare(__lp, __rp, __lhs_sz) == 0;
3786     for (; __lhs_sz != 0; --__lhs_sz, ++__lp, ++__rp)
3787         if (*__lp != *__rp)
3788             return false;
3789     return true;
3790 }
3791
3792 template<class _CharT, class _Traits, class _Allocator>
3793 inline _LIBCPP_INLINE_VISIBILITY
3794 bool
3795 operator==(const _CharT* __lhs,
3796            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3797 {
3798     return __rhs.compare(__lhs) == 0;
3799 }
3800
3801 template<class _CharT, class _Traits, class _Allocator>
3802 inline _LIBCPP_INLINE_VISIBILITY
3803 bool
3804 operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3805            const _CharT* __rhs) _NOEXCEPT
3806 {
3807     return __lhs.compare(__rhs) == 0;
3808 }
3809
3810 // operator!=
3811
3812 template<class _CharT, class _Traits, class _Allocator>
3813 inline _LIBCPP_INLINE_VISIBILITY
3814 bool
3815 operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3816            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3817 {
3818     return !(__lhs == __rhs);
3819 }
3820
3821 template<class _CharT, class _Traits, class _Allocator>
3822 inline _LIBCPP_INLINE_VISIBILITY
3823 bool
3824 operator!=(const _CharT* __lhs,
3825            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3826 {
3827     return !(__lhs == __rhs);
3828 }
3829
3830 template<class _CharT, class _Traits, class _Allocator>
3831 inline _LIBCPP_INLINE_VISIBILITY
3832 bool
3833 operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3834            const _CharT* __rhs) _NOEXCEPT
3835 {
3836     return !(__lhs == __rhs);
3837 }
3838
3839 // operator<
3840
3841 template<class _CharT, class _Traits, class _Allocator>
3842 inline _LIBCPP_INLINE_VISIBILITY
3843 bool
3844 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3845            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3846 {
3847     return __lhs.compare(__rhs) < 0;
3848 }
3849
3850 template<class _CharT, class _Traits, class _Allocator>
3851 inline _LIBCPP_INLINE_VISIBILITY
3852 bool
3853 operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3854            const _CharT* __rhs) _NOEXCEPT
3855 {
3856     return __lhs.compare(__rhs) < 0;
3857 }
3858
3859 template<class _CharT, class _Traits, class _Allocator>
3860 inline _LIBCPP_INLINE_VISIBILITY
3861 bool
3862 operator< (const _CharT* __lhs,
3863            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3864 {
3865     return __rhs.compare(__lhs) > 0;
3866 }
3867
3868 // operator>
3869
3870 template<class _CharT, class _Traits, class _Allocator>
3871 inline _LIBCPP_INLINE_VISIBILITY
3872 bool
3873 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3874            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3875 {
3876     return __rhs < __lhs;
3877 }
3878
3879 template<class _CharT, class _Traits, class _Allocator>
3880 inline _LIBCPP_INLINE_VISIBILITY
3881 bool
3882 operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3883            const _CharT* __rhs) _NOEXCEPT
3884 {
3885     return __rhs < __lhs;
3886 }
3887
3888 template<class _CharT, class _Traits, class _Allocator>
3889 inline _LIBCPP_INLINE_VISIBILITY
3890 bool
3891 operator> (const _CharT* __lhs,
3892            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3893 {
3894     return __rhs < __lhs;
3895 }
3896
3897 // operator<=
3898
3899 template<class _CharT, class _Traits, class _Allocator>
3900 inline _LIBCPP_INLINE_VISIBILITY
3901 bool
3902 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3903            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3904 {
3905     return !(__rhs < __lhs);
3906 }
3907
3908 template<class _CharT, class _Traits, class _Allocator>
3909 inline _LIBCPP_INLINE_VISIBILITY
3910 bool
3911 operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3912            const _CharT* __rhs) _NOEXCEPT
3913 {
3914     return !(__rhs < __lhs);
3915 }
3916
3917 template<class _CharT, class _Traits, class _Allocator>
3918 inline _LIBCPP_INLINE_VISIBILITY
3919 bool
3920 operator<=(const _CharT* __lhs,
3921            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3922 {
3923     return !(__rhs < __lhs);
3924 }
3925
3926 // operator>=
3927
3928 template<class _CharT, class _Traits, class _Allocator>
3929 inline _LIBCPP_INLINE_VISIBILITY
3930 bool
3931 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3932            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3933 {
3934     return !(__lhs < __rhs);
3935 }
3936
3937 template<class _CharT, class _Traits, class _Allocator>
3938 inline _LIBCPP_INLINE_VISIBILITY
3939 bool
3940 operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3941            const _CharT* __rhs) _NOEXCEPT
3942 {
3943     return !(__lhs < __rhs);
3944 }
3945
3946 template<class _CharT, class _Traits, class _Allocator>
3947 inline _LIBCPP_INLINE_VISIBILITY
3948 bool
3949 operator>=(const _CharT* __lhs,
3950            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
3951 {
3952     return !(__lhs < __rhs);
3953 }
3954
3955 // operator +
3956
3957 template<class _CharT, class _Traits, class _Allocator>
3958 basic_string<_CharT, _Traits, _Allocator>
3959 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3960           const basic_string<_CharT, _Traits, _Allocator>& __rhs)
3961 {
3962     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3963     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3964     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3965     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
3966     __r.append(__rhs.data(), __rhs_sz);
3967     return __r;
3968 }
3969
3970 template<class _CharT, class _Traits, class _Allocator>
3971 basic_string<_CharT, _Traits, _Allocator>
3972 operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs)
3973 {
3974     basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
3975     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = _Traits::length(__lhs);
3976     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3977     __r.__init(__lhs, __lhs_sz, __lhs_sz + __rhs_sz);
3978     __r.append(__rhs.data(), __rhs_sz);
3979     return __r;
3980 }
3981
3982 template<class _CharT, class _Traits, class _Allocator>
3983 basic_string<_CharT, _Traits, _Allocator>
3984 operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs)
3985 {
3986     basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
3987     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3988     __r.__init(&__lhs, 1, 1 + __rhs_sz);
3989     __r.append(__rhs.data(), __rhs_sz);
3990     return __r;
3991 }
3992
3993 template<class _CharT, class _Traits, class _Allocator>
3994 basic_string<_CharT, _Traits, _Allocator>
3995 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs)
3996 {
3997     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3998     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3999     typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = _Traits::length(__rhs);
4000     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
4001     __r.append(__rhs, __rhs_sz);
4002     return __r;
4003 }
4004
4005 template<class _CharT, class _Traits, class _Allocator>
4006 basic_string<_CharT, _Traits, _Allocator>
4007 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs)
4008 {
4009     basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
4010     typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
4011     __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + 1);
4012     __r.push_back(__rhs);
4013     return __r;
4014 }
4015
4016 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4017
4018 template<class _CharT, class _Traits, class _Allocator>
4019 inline _LIBCPP_INLINE_VISIBILITY
4020 basic_string<_CharT, _Traits, _Allocator>
4021 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs)
4022 {
4023     return _VSTD::move(__lhs.append(__rhs));
4024 }
4025
4026 template<class _CharT, class _Traits, class _Allocator>
4027 inline _LIBCPP_INLINE_VISIBILITY
4028 basic_string<_CharT, _Traits, _Allocator>
4029 operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4030 {
4031     return _VSTD::move(__rhs.insert(0, __lhs));
4032 }
4033
4034 template<class _CharT, class _Traits, class _Allocator>
4035 inline _LIBCPP_INLINE_VISIBILITY
4036 basic_string<_CharT, _Traits, _Allocator>
4037 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
4038 {
4039     return _VSTD::move(__lhs.append(__rhs));
4040 }
4041
4042 template<class _CharT, class _Traits, class _Allocator>
4043 inline _LIBCPP_INLINE_VISIBILITY
4044 basic_string<_CharT, _Traits, _Allocator>
4045 operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4046 {
4047     return _VSTD::move(__rhs.insert(0, __lhs));
4048 }
4049
4050 template<class _CharT, class _Traits, class _Allocator>
4051 inline _LIBCPP_INLINE_VISIBILITY
4052 basic_string<_CharT, _Traits, _Allocator>
4053 operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs)
4054 {
4055     __rhs.insert(__rhs.begin(), __lhs);
4056     return _VSTD::move(__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, const _CharT* __rhs)
4063 {
4064     return _VSTD::move(__lhs.append(__rhs));
4065 }
4066
4067 template<class _CharT, class _Traits, class _Allocator>
4068 inline _LIBCPP_INLINE_VISIBILITY
4069 basic_string<_CharT, _Traits, _Allocator>
4070 operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs)
4071 {
4072     __lhs.push_back(__rhs);
4073     return _VSTD::move(__lhs);
4074 }
4075
4076 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4077
4078 // swap
4079
4080 template<class _CharT, class _Traits, class _Allocator>
4081 inline _LIBCPP_INLINE_VISIBILITY
4082 void
4083 swap(basic_string<_CharT, _Traits, _Allocator>& __lhs,
4084      basic_string<_CharT, _Traits, _Allocator>& __rhs)
4085      _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs)))
4086 {
4087     __lhs.swap(__rhs);
4088 }
4089
4090 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
4091
4092 typedef basic_string<char16_t> u16string;
4093 typedef basic_string<char32_t> u32string;
4094
4095 #endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
4096
4097 _LIBCPP_FUNC_VIS int                stoi  (const string& __str, size_t* __idx = 0, int __base = 10);
4098 _LIBCPP_FUNC_VIS long               stol  (const string& __str, size_t* __idx = 0, int __base = 10);
4099 _LIBCPP_FUNC_VIS unsigned long      stoul (const string& __str, size_t* __idx = 0, int __base = 10);
4100 _LIBCPP_FUNC_VIS long long          stoll (const string& __str, size_t* __idx = 0, int __base = 10);
4101 _LIBCPP_FUNC_VIS unsigned long long stoull(const string& __str, size_t* __idx = 0, int __base = 10);
4102
4103 _LIBCPP_FUNC_VIS float       stof (const string& __str, size_t* __idx = 0);
4104 _LIBCPP_FUNC_VIS double      stod (const string& __str, size_t* __idx = 0);
4105 _LIBCPP_FUNC_VIS long double stold(const string& __str, size_t* __idx = 0);
4106
4107 _LIBCPP_FUNC_VIS string to_string(int __val);
4108 _LIBCPP_FUNC_VIS string to_string(unsigned __val);
4109 _LIBCPP_FUNC_VIS string to_string(long __val);
4110 _LIBCPP_FUNC_VIS string to_string(unsigned long __val);
4111 _LIBCPP_FUNC_VIS string to_string(long long __val);
4112 _LIBCPP_FUNC_VIS string to_string(unsigned long long __val);
4113 _LIBCPP_FUNC_VIS string to_string(float __val);
4114 _LIBCPP_FUNC_VIS string to_string(double __val);
4115 _LIBCPP_FUNC_VIS string to_string(long double __val);
4116
4117 _LIBCPP_FUNC_VIS int                stoi  (const wstring& __str, size_t* __idx = 0, int __base = 10);
4118 _LIBCPP_FUNC_VIS long               stol  (const wstring& __str, size_t* __idx = 0, int __base = 10);
4119 _LIBCPP_FUNC_VIS unsigned long      stoul (const wstring& __str, size_t* __idx = 0, int __base = 10);
4120 _LIBCPP_FUNC_VIS long long          stoll (const wstring& __str, size_t* __idx = 0, int __base = 10);
4121 _LIBCPP_FUNC_VIS unsigned long long stoull(const wstring& __str, size_t* __idx = 0, int __base = 10);
4122
4123 _LIBCPP_FUNC_VIS float       stof (const wstring& __str, size_t* __idx = 0);
4124 _LIBCPP_FUNC_VIS double      stod (const wstring& __str, size_t* __idx = 0);
4125 _LIBCPP_FUNC_VIS long double stold(const wstring& __str, size_t* __idx = 0);
4126
4127 _LIBCPP_FUNC_VIS wstring to_wstring(int __val);
4128 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned __val);
4129 _LIBCPP_FUNC_VIS wstring to_wstring(long __val);
4130 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned long __val);
4131 _LIBCPP_FUNC_VIS wstring to_wstring(long long __val);
4132 _LIBCPP_FUNC_VIS wstring to_wstring(unsigned long long __val);
4133 _LIBCPP_FUNC_VIS wstring to_wstring(float __val);
4134 _LIBCPP_FUNC_VIS wstring to_wstring(double __val);
4135 _LIBCPP_FUNC_VIS wstring to_wstring(long double __val);
4136
4137 template<class _CharT, class _Traits, class _Allocator>
4138     const typename basic_string<_CharT, _Traits, _Allocator>::size_type
4139                    basic_string<_CharT, _Traits, _Allocator>::npos;
4140
4141 template<class _CharT, class _Traits, class _Allocator>
4142 struct _LIBCPP_TYPE_VIS_ONLY hash<basic_string<_CharT, _Traits, _Allocator> >
4143     : public unary_function<basic_string<_CharT, _Traits, _Allocator>, size_t>
4144 {
4145     size_t
4146         operator()(const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT;
4147 };
4148
4149 template<class _CharT, class _Traits, class _Allocator>
4150 size_t
4151 hash<basic_string<_CharT, _Traits, _Allocator> >::operator()(
4152         const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT
4153 {
4154     return __do_string_hash(__val.data(), __val.data() + __val.size());
4155 }
4156
4157 template<class _CharT, class _Traits, class _Allocator>
4158 basic_ostream<_CharT, _Traits>&
4159 operator<<(basic_ostream<_CharT, _Traits>& __os,
4160            const basic_string<_CharT, _Traits, _Allocator>& __str);
4161
4162 template<class _CharT, class _Traits, class _Allocator>
4163 basic_istream<_CharT, _Traits>&
4164 operator>>(basic_istream<_CharT, _Traits>& __is,
4165            basic_string<_CharT, _Traits, _Allocator>& __str);
4166
4167 template<class _CharT, class _Traits, class _Allocator>
4168 basic_istream<_CharT, _Traits>&
4169 getline(basic_istream<_CharT, _Traits>& __is,
4170         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
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);
4177
4178 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4179
4180 template<class _CharT, class _Traits, class _Allocator>
4181 inline _LIBCPP_INLINE_VISIBILITY
4182 basic_istream<_CharT, _Traits>&
4183 getline(basic_istream<_CharT, _Traits>&& __is,
4184         basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
4185
4186 template<class _CharT, class _Traits, class _Allocator>
4187 inline _LIBCPP_INLINE_VISIBILITY
4188 basic_istream<_CharT, _Traits>&
4189 getline(basic_istream<_CharT, _Traits>&& __is,
4190         basic_string<_CharT, _Traits, _Allocator>& __str);
4191
4192 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4193
4194 #if _LIBCPP_DEBUG_LEVEL >= 2
4195
4196 template<class _CharT, class _Traits, class _Allocator>
4197 bool
4198 basic_string<_CharT, _Traits, _Allocator>::__dereferenceable(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>::__decrementable(const const_iterator* __i) const
4207 {
4208     return this->data() < _VSTD::__to_raw_pointer(__i->base()) &&
4209            _VSTD::__to_raw_pointer(__i->base()) <= this->data() + this->size();
4210 }
4211
4212 template<class _CharT, class _Traits, class _Allocator>
4213 bool
4214 basic_string<_CharT, _Traits, _Allocator>::__addable(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 template<class _CharT, class _Traits, class _Allocator>
4221 bool
4222 basic_string<_CharT, _Traits, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
4223 {
4224     const value_type* __p = _VSTD::__to_raw_pointer(__i->base()) + __n;
4225     return this->data() <= __p && __p < this->data() + this->size();
4226 }
4227
4228 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
4229
4230 #if _LIBCPP_STD_VER > 11
4231 // Literal suffixes for basic_string [basic.string.literals]
4232 inline namespace literals
4233 {
4234   inline namespace string_literals
4235   {
4236     inline _LIBCPP_INLINE_VISIBILITY
4237     basic_string<char> operator "" s( const char *__str, size_t __len )
4238     {
4239         return basic_string<char> (__str, __len);
4240     }
4241
4242     inline _LIBCPP_INLINE_VISIBILITY
4243     basic_string<wchar_t> operator "" s( const wchar_t *__str, size_t __len )
4244     {
4245         return basic_string<wchar_t> (__str, __len);
4246     }
4247
4248     inline _LIBCPP_INLINE_VISIBILITY
4249     basic_string<char16_t> operator "" s( const char16_t *__str, size_t __len )
4250     {
4251         return basic_string<char16_t> (__str, __len);
4252     }
4253
4254     inline _LIBCPP_INLINE_VISIBILITY
4255     basic_string<char32_t> operator "" s( const char32_t *__str, size_t __len )
4256     {
4257         return basic_string<char32_t> (__str, __len);
4258     }
4259   }
4260 }
4261 #endif
4262
4263 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<char>)
4264 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<wchar_t>)
4265 _LIBCPP_EXTERN_TEMPLATE(string operator+<char, char_traits<char>, allocator<char> >(char const*, string const&))
4266
4267 _LIBCPP_END_NAMESPACE_STD
4268
4269 #endif  // _LIBCPP_STRING