contrib/libc++/include/string

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