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