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