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