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