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