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