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