include/string

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