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