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