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