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