contrib/llvm-project/libcxx/include/string

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