contrib/libc++/include/string

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