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