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