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 = 0x1ul}; 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_ & size_type(~__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&, 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&, 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&, allocator_type&, 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 1673#ifdef _LIBCPP_DEBUG 1674 __pos 1675#endif 1676 ) 1677{ 1678#ifdef _LIBCPP_DEBUG 1679 const_iterator __beg = begin(); 1680 if (__iterator_list_.first) 1681 { 1682 for (iterator* __p = __iterator_list_.first; __p;) 1683 { 1684 if (*__p - __beg > static_cast<difference_type>(__pos)) 1685 { 1686 iterator* __n = __p; 1687 __p = __p->__next; 1688 __n->__remove_owner(); 1689 } 1690 else 1691 __p = __p->__next; 1692 } 1693 } 1694 if (__iterator_list_.second) 1695 { 1696 for (const_iterator* __p = __iterator_list_.second; __p;) 1697 { 1698 if (*__p - __beg > static_cast<difference_type>(__pos)) 1699 { 1700 const_iterator* __n = __p; 1701 __p = __p->__next; 1702 __n->__remove_owner(); 1703 } 1704 else 1705 __p = __p->__next; 1706 } 1707 } 1708#endif // _LIBCPP_DEBUG 1709} 1710 1711template <class _CharT, class _Traits, class _Allocator> 1712_LIBCPP_INLINE_VISIBILITY inline 1713basic_string<_CharT, _Traits, _Allocator>::basic_string() 1714 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1715{ 1716 __zero(); 1717} 1718 1719template <class _CharT, class _Traits, class _Allocator> 1720_LIBCPP_INLINE_VISIBILITY inline 1721basic_string<_CharT, _Traits, _Allocator>::basic_string(const allocator_type& __a) 1722 : __r_(__a) 1723{ 1724 __zero(); 1725} 1726 1727template <class _CharT, class _Traits, class _Allocator> 1728void 1729basic_string<_CharT, _Traits, _Allocator>::__init(const_pointer __s, size_type __sz, size_type __reserve) 1730{ 1731 if (__reserve > max_size()) 1732 this->__throw_length_error(); 1733 pointer __p; 1734 if (__reserve < __min_cap) 1735 { 1736 __set_short_size(__sz); 1737 __p = __get_short_pointer(); 1738 } 1739 else 1740 { 1741 size_type __cap = __recommend(__reserve); 1742 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1743 __set_long_pointer(__p); 1744 __set_long_cap(__cap+1); 1745 __set_long_size(__sz); 1746 } 1747 traits_type::copy(__p, __s, __sz); 1748 traits_type::assign(__p[__sz], value_type()); 1749} 1750 1751template <class _CharT, class _Traits, class _Allocator> 1752void 1753basic_string<_CharT, _Traits, _Allocator>::__init(const_pointer __s, size_type __sz) 1754{ 1755 if (__sz > max_size()) 1756 this->__throw_length_error(); 1757 pointer __p; 1758 if (__sz < __min_cap) 1759 { 1760 __set_short_size(__sz); 1761 __p = __get_short_pointer(); 1762 } 1763 else 1764 { 1765 size_type __cap = __recommend(__sz); 1766 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1767 __set_long_pointer(__p); 1768 __set_long_cap(__cap+1); 1769 __set_long_size(__sz); 1770 } 1771 traits_type::copy(__p, __s, __sz); 1772 traits_type::assign(__p[__sz], value_type()); 1773} 1774 1775template <class _CharT, class _Traits, class _Allocator> 1776_LIBCPP_INLINE_VISIBILITY inline 1777basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s) 1778{ 1779#ifdef _LIBCPP_DEBUG 1780 assert(__s != 0); 1781#endif 1782 __init(__s, traits_type::length(__s)); 1783} 1784 1785template <class _CharT, class _Traits, class _Allocator> 1786_LIBCPP_INLINE_VISIBILITY inline 1787basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, const allocator_type& __a) 1788 : __r_(__a) 1789{ 1790#ifdef _LIBCPP_DEBUG 1791 assert(__s != 0); 1792#endif 1793 __init(__s, traits_type::length(__s)); 1794} 1795 1796template <class _CharT, class _Traits, class _Allocator> 1797_LIBCPP_INLINE_VISIBILITY inline 1798basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, size_type __n) 1799{ 1800#ifdef _LIBCPP_DEBUG 1801 assert(__s != 0); 1802#endif 1803 __init(__s, __n); 1804} 1805 1806template <class _CharT, class _Traits, class _Allocator> 1807_LIBCPP_INLINE_VISIBILITY inline 1808basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, size_type __n, const allocator_type& __a) 1809 : __r_(__a) 1810{ 1811#ifdef _LIBCPP_DEBUG 1812 assert(__s != 0); 1813#endif 1814 __init(__s, __n); 1815} 1816 1817template <class _CharT, class _Traits, class _Allocator> 1818basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str) 1819 : __r_(__alloc_traits::select_on_container_copy_construction(__str.__alloc())) 1820{ 1821 if (!__str.__is_long()) 1822 __r_.first().__r = __str.__r_.first().__r; 1823 else 1824 __init(__str.__get_long_pointer(), __str.__get_long_size()); 1825} 1826 1827template <class _CharT, class _Traits, class _Allocator> 1828basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, const allocator_type& __a) 1829 : __r_(__a) 1830{ 1831 if (!__str.__is_long()) 1832 __r_.first().__r = __str.__r_.first().__r; 1833 else 1834 __init(__str.__get_long_pointer(), __str.__get_long_size()); 1835} 1836 1837#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1838 1839template <class _CharT, class _Traits, class _Allocator> 1840_LIBCPP_INLINE_VISIBILITY inline 1841basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str) 1842 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1843 : __r_(_VSTD::move(__str.__r_)) 1844{ 1845 __str.__zero(); 1846#ifdef _LIBCPP_DEBUG 1847 __str.__invalidate_all_iterators(); 1848#endif 1849} 1850 1851template <class _CharT, class _Traits, class _Allocator> 1852_LIBCPP_INLINE_VISIBILITY inline 1853basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str, const allocator_type& __a) 1854 : __r_(__a) 1855{ 1856 if (__a == __str.__alloc() || !__str.__is_long()) 1857 __r_.first().__r = __str.__r_.first().__r; 1858 else 1859 __init(__str.__get_long_pointer(), __str.__get_long_size()); 1860 __str.__zero(); 1861#ifdef _LIBCPP_DEBUG 1862 __str.__invalidate_all_iterators(); 1863#endif 1864} 1865 1866#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1867 1868template <class _CharT, class _Traits, class _Allocator> 1869void 1870basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c) 1871{ 1872 if (__n > max_size()) 1873 this->__throw_length_error(); 1874 pointer __p; 1875 if (__n < __min_cap) 1876 { 1877 __set_short_size(__n); 1878 __p = __get_short_pointer(); 1879 } 1880 else 1881 { 1882 size_type __cap = __recommend(__n); 1883 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1884 __set_long_pointer(__p); 1885 __set_long_cap(__cap+1); 1886 __set_long_size(__n); 1887 } 1888 traits_type::assign(__p, __n, __c); 1889 traits_type::assign(__p[__n], value_type()); 1890} 1891 1892template <class _CharT, class _Traits, class _Allocator> 1893_LIBCPP_INLINE_VISIBILITY inline 1894basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c) 1895{ 1896 __init(__n, __c); 1897} 1898 1899template <class _CharT, class _Traits, class _Allocator> 1900_LIBCPP_INLINE_VISIBILITY inline 1901basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c, const allocator_type& __a) 1902 : __r_(__a) 1903{ 1904 __init(__n, __c); 1905} 1906 1907template <class _CharT, class _Traits, class _Allocator> 1908basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, size_type __pos, size_type __n, 1909 const allocator_type& __a) 1910 : __r_(__a) 1911{ 1912 size_type __str_sz = __str.size(); 1913 if (__pos > __str_sz) 1914 this->__throw_out_of_range(); 1915 __init(__str.data() + __pos, _VSTD::min(__n, __str_sz - __pos)); 1916} 1917 1918template <class _CharT, class _Traits, class _Allocator> 1919template <class _InputIterator> 1920typename enable_if 1921< 1922 __is_input_iterator <_InputIterator>::value && 1923 !__is_forward_iterator<_InputIterator>::value, 1924 void 1925>::type 1926basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last) 1927{ 1928 __zero(); 1929#ifndef _LIBCPP_NO_EXCEPTIONS 1930 try 1931 { 1932#endif // _LIBCPP_NO_EXCEPTIONS 1933 for (; __first != __last; ++__first) 1934 push_back(*__first); 1935#ifndef _LIBCPP_NO_EXCEPTIONS 1936 } 1937 catch (...) 1938 { 1939 if (__is_long()) 1940 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap()); 1941 throw; 1942 } 1943#endif // _LIBCPP_NO_EXCEPTIONS 1944} 1945 1946template <class _CharT, class _Traits, class _Allocator> 1947template <class _ForwardIterator> 1948typename enable_if 1949< 1950 __is_forward_iterator<_ForwardIterator>::value, 1951 void 1952>::type 1953basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last) 1954{ 1955 size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last)); 1956 if (__sz > max_size()) 1957 this->__throw_length_error(); 1958 pointer __p; 1959 if (__sz < __min_cap) 1960 { 1961 __set_short_size(__sz); 1962 __p = __get_short_pointer(); 1963 } 1964 else 1965 { 1966 size_type __cap = __recommend(__sz); 1967 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1968 __set_long_pointer(__p); 1969 __set_long_cap(__cap+1); 1970 __set_long_size(__sz); 1971 } 1972 for (; __first != __last; ++__first, ++__p) 1973 traits_type::assign(*__p, *__first); 1974 traits_type::assign(*__p, value_type()); 1975} 1976 1977template <class _CharT, class _Traits, class _Allocator> 1978template<class _InputIterator> 1979_LIBCPP_INLINE_VISIBILITY inline 1980basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last) 1981{ 1982 __init(__first, __last); 1983} 1984 1985template <class _CharT, class _Traits, class _Allocator> 1986template<class _InputIterator> 1987_LIBCPP_INLINE_VISIBILITY inline 1988basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last, 1989 const allocator_type& __a) 1990 : __r_(__a) 1991{ 1992 __init(__first, __last); 1993} 1994 1995#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1996 1997template <class _CharT, class _Traits, class _Allocator> 1998_LIBCPP_INLINE_VISIBILITY inline 1999basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il) 2000{ 2001 __init(__il.begin(), __il.end()); 2002} 2003 2004template <class _CharT, class _Traits, class _Allocator> 2005_LIBCPP_INLINE_VISIBILITY inline 2006basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il, const allocator_type& __a) 2007 : __r_(__a) 2008{ 2009 __init(__il.begin(), __il.end()); 2010} 2011 2012#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2013 2014template <class _CharT, class _Traits, class _Allocator> 2015basic_string<_CharT, _Traits, _Allocator>::~basic_string() 2016{ 2017 __invalidate_all_iterators(); 2018 if (__is_long()) 2019 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap()); 2020} 2021 2022template <class _CharT, class _Traits, class _Allocator> 2023void 2024basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace 2025 (size_type __old_cap, size_type __delta_cap, size_type __old_sz, 2026 size_type __n_copy, size_type __n_del, size_type __n_add, const_pointer __p_new_stuff) 2027{ 2028 size_type __ms = max_size(); 2029 if (__delta_cap > __ms - __old_cap - 1) 2030 this->__throw_length_error(); 2031 pointer __old_p = __get_pointer(); 2032 size_type __cap = __old_cap < __ms / 2 - __alignment ? 2033 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) : 2034 __ms - 1; 2035 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1); 2036 __invalidate_all_iterators(); 2037 if (__n_copy != 0) 2038 traits_type::copy(__p, __old_p, __n_copy); 2039 if (__n_add != 0) 2040 traits_type::copy(__p + __n_copy, __p_new_stuff, __n_add); 2041 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy; 2042 if (__sec_cp_sz != 0) 2043 traits_type::copy(__p + __n_copy + __n_add, __old_p + __n_copy + __n_del, __sec_cp_sz); 2044 if (__old_cap+1 != __min_cap) 2045 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1); 2046 __set_long_pointer(__p); 2047 __set_long_cap(__cap+1); 2048 __old_sz = __n_copy + __n_add + __sec_cp_sz; 2049 __set_long_size(__old_sz); 2050 traits_type::assign(__p[__old_sz], value_type()); 2051} 2052 2053template <class _CharT, class _Traits, class _Allocator> 2054void 2055basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz, 2056 size_type __n_copy, size_type __n_del, size_type __n_add) 2057{ 2058 size_type __ms = max_size(); 2059 if (__delta_cap > __ms - __old_cap - 1) 2060 this->__throw_length_error(); 2061 pointer __old_p = __get_pointer(); 2062 size_type __cap = __old_cap < __ms / 2 - __alignment ? 2063 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) : 2064 __ms - 1; 2065 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1); 2066 __invalidate_all_iterators(); 2067 if (__n_copy != 0) 2068 traits_type::copy(__p, __old_p, __n_copy); 2069 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy; 2070 if (__sec_cp_sz != 0) 2071 traits_type::copy(__p + __n_copy + __n_add, __old_p + __n_copy + __n_del, __sec_cp_sz); 2072 if (__old_cap+1 != __min_cap) 2073 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1); 2074 __set_long_pointer(__p); 2075 __set_long_cap(__cap+1); 2076} 2077 2078// assign 2079 2080template <class _CharT, class _Traits, class _Allocator> 2081basic_string<_CharT, _Traits, _Allocator>& 2082basic_string<_CharT, _Traits, _Allocator>::assign(const_pointer __s, size_type __n) 2083{ 2084#ifdef _LIBCPP_DEBUG 2085 assert(__s != 0); 2086#endif 2087 size_type __cap = capacity(); 2088 if (__cap >= __n) 2089 { 2090 pointer __p = __get_pointer(); 2091 traits_type::move(__p, __s, __n); 2092 traits_type::assign(__p[__n], value_type()); 2093 __set_size(__n); 2094 __invalidate_iterators_past(__n); 2095 } 2096 else 2097 { 2098 size_type __sz = size(); 2099 __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s); 2100 } 2101 return *this; 2102} 2103 2104template <class _CharT, class _Traits, class _Allocator> 2105basic_string<_CharT, _Traits, _Allocator>& 2106basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c) 2107{ 2108 size_type __cap = capacity(); 2109 if (__cap < __n) 2110 { 2111 size_type __sz = size(); 2112 __grow_by(__cap, __n - __cap, __sz, 0, __sz); 2113 } 2114 else 2115 __invalidate_iterators_past(__n); 2116 pointer __p = __get_pointer(); 2117 traits_type::assign(__p, __n, __c); 2118 traits_type::assign(__p[__n], value_type()); 2119 __set_size(__n); 2120 return *this; 2121} 2122 2123template <class _CharT, class _Traits, class _Allocator> 2124basic_string<_CharT, _Traits, _Allocator>& 2125basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c) 2126{ 2127 pointer __p; 2128 if (__is_long()) 2129 { 2130 __p = __get_long_pointer(); 2131 __set_long_size(1); 2132 } 2133 else 2134 { 2135 __p = __get_short_pointer(); 2136 __set_short_size(1); 2137 } 2138 traits_type::assign(*__p, __c); 2139 traits_type::assign(*++__p, value_type()); 2140 __invalidate_iterators_past(1); 2141 return *this; 2142} 2143 2144template <class _CharT, class _Traits, class _Allocator> 2145basic_string<_CharT, _Traits, _Allocator>& 2146basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str) 2147{ 2148 if (this != &__str) 2149 { 2150 __copy_assign_alloc(__str); 2151 assign(__str); 2152 } 2153 return *this; 2154} 2155 2156#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2157 2158template <class _CharT, class _Traits, class _Allocator> 2159_LIBCPP_INLINE_VISIBILITY inline 2160void 2161basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type) 2162{ 2163 if (__alloc() != __str.__alloc()) 2164 assign(__str); 2165 else 2166 __move_assign(__str, true_type()); 2167} 2168 2169template <class _CharT, class _Traits, class _Allocator> 2170_LIBCPP_INLINE_VISIBILITY inline 2171void 2172basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type) 2173 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2174{ 2175 clear(); 2176 shrink_to_fit(); 2177 __r_.first() = __str.__r_.first(); 2178 __move_assign_alloc(__str); 2179 __str.__zero(); 2180} 2181 2182template <class _CharT, class _Traits, class _Allocator> 2183_LIBCPP_INLINE_VISIBILITY inline 2184basic_string<_CharT, _Traits, _Allocator>& 2185basic_string<_CharT, _Traits, _Allocator>::operator=(basic_string&& __str) 2186 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 2187 is_nothrow_move_assignable<allocator_type>::value) 2188{ 2189 __move_assign(__str, integral_constant<bool, 2190 __alloc_traits::propagate_on_container_move_assignment::value>()); 2191 return *this; 2192} 2193 2194#endif 2195 2196template <class _CharT, class _Traits, class _Allocator> 2197template<class _InputIterator> 2198typename enable_if 2199< 2200 __is_input_iterator <_InputIterator>::value && 2201 !__is_forward_iterator<_InputIterator>::value, 2202 basic_string<_CharT, _Traits, _Allocator>& 2203>::type 2204basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2205{ 2206 clear(); 2207 for (; __first != __last; ++__first) 2208 push_back(*__first); 2209} 2210 2211template <class _CharT, class _Traits, class _Allocator> 2212template<class _ForwardIterator> 2213typename enable_if 2214< 2215 __is_forward_iterator<_ForwardIterator>::value, 2216 basic_string<_CharT, _Traits, _Allocator>& 2217>::type 2218basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2219{ 2220 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2221 size_type __cap = capacity(); 2222 if (__cap < __n) 2223 { 2224 size_type __sz = size(); 2225 __grow_by(__cap, __n - __cap, __sz, 0, __sz); 2226 } 2227 else 2228 __invalidate_iterators_past(__n); 2229 pointer __p = __get_pointer(); 2230 for (; __first != __last; ++__first, ++__p) 2231 traits_type::assign(*__p, *__first); 2232 traits_type::assign(*__p, value_type()); 2233 __set_size(__n); 2234 return *this; 2235} 2236 2237template <class _CharT, class _Traits, class _Allocator> 2238_LIBCPP_INLINE_VISIBILITY inline 2239basic_string<_CharT, _Traits, _Allocator>& 2240basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str) 2241{ 2242 return assign(__str.data(), __str.size()); 2243} 2244 2245template <class _CharT, class _Traits, class _Allocator> 2246basic_string<_CharT, _Traits, _Allocator>& 2247basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n) 2248{ 2249 size_type __sz = __str.size(); 2250 if (__pos > __sz) 2251 this->__throw_out_of_range(); 2252 return assign(__str.data() + __pos, _VSTD::min(__n, __sz - __pos)); 2253} 2254 2255template <class _CharT, class _Traits, class _Allocator> 2256basic_string<_CharT, _Traits, _Allocator>& 2257basic_string<_CharT, _Traits, _Allocator>::assign(const_pointer __s) 2258{ 2259#ifdef _LIBCPP_DEBUG 2260 assert(__s != 0); 2261#endif 2262 return assign(__s, traits_type::length(__s)); 2263} 2264 2265// append 2266 2267template <class _CharT, class _Traits, class _Allocator> 2268basic_string<_CharT, _Traits, _Allocator>& 2269basic_string<_CharT, _Traits, _Allocator>::append(const_pointer __s, size_type __n) 2270{ 2271#ifdef _LIBCPP_DEBUG 2272 assert(__s != 0); 2273#endif 2274 size_type __cap = capacity(); 2275 size_type __sz = size(); 2276 if (__cap - __sz >= __n) 2277 { 2278 if (__n) 2279 { 2280 pointer __p = __get_pointer(); 2281 traits_type::copy(__p + __sz, __s, __n); 2282 __sz += __n; 2283 __set_size(__sz); 2284 traits_type::assign(__p[__sz], value_type()); 2285 } 2286 } 2287 else 2288 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s); 2289 return *this; 2290} 2291 2292template <class _CharT, class _Traits, class _Allocator> 2293basic_string<_CharT, _Traits, _Allocator>& 2294basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c) 2295{ 2296 if (__n) 2297 { 2298 size_type __cap = capacity(); 2299 size_type __sz = size(); 2300 if (__cap - __sz < __n) 2301 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0); 2302 pointer __p = __get_pointer(); 2303 traits_type::assign(__p + __sz, __n, __c); 2304 __sz += __n; 2305 __set_size(__sz); 2306 traits_type::assign(__p[__sz], value_type()); 2307 } 2308 return *this; 2309} 2310 2311template <class _CharT, class _Traits, class _Allocator> 2312void 2313basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c) 2314{ 2315 size_type __cap = capacity(); 2316 size_type __sz = size(); 2317 if (__sz == __cap) 2318 __grow_by(__cap, 1, __sz, __sz, 0); 2319 pointer __p = __get_pointer() + __sz; 2320 traits_type::assign(*__p, __c); 2321 traits_type::assign(*++__p, value_type()); 2322 __set_size(__sz+1); 2323} 2324 2325template <class _CharT, class _Traits, class _Allocator> 2326template<class _InputIterator> 2327typename enable_if 2328< 2329 __is_input_iterator <_InputIterator>::value && 2330 !__is_forward_iterator<_InputIterator>::value, 2331 basic_string<_CharT, _Traits, _Allocator>& 2332>::type 2333basic_string<_CharT, _Traits, _Allocator>::append(_InputIterator __first, _InputIterator __last) 2334{ 2335 for (; __first != __last; ++__first) 2336 push_back(*__first); 2337 return *this; 2338} 2339 2340template <class _CharT, class _Traits, class _Allocator> 2341template<class _ForwardIterator> 2342typename enable_if 2343< 2344 __is_forward_iterator<_ForwardIterator>::value, 2345 basic_string<_CharT, _Traits, _Allocator>& 2346>::type 2347basic_string<_CharT, _Traits, _Allocator>::append(_ForwardIterator __first, _ForwardIterator __last) 2348{ 2349 size_type __sz = size(); 2350 size_type __cap = capacity(); 2351 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2352 if (__n) 2353 { 2354 if (__cap - __sz < __n) 2355 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0); 2356 pointer __p = __get_pointer() + __sz; 2357 for (; __first != __last; ++__p, ++__first) 2358 traits_type::assign(*__p, *__first); 2359 traits_type::assign(*__p, value_type()); 2360 __set_size(__sz + __n); 2361 } 2362 return *this; 2363} 2364 2365template <class _CharT, class _Traits, class _Allocator> 2366_LIBCPP_INLINE_VISIBILITY inline 2367basic_string<_CharT, _Traits, _Allocator>& 2368basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str) 2369{ 2370 return append(__str.data(), __str.size()); 2371} 2372 2373template <class _CharT, class _Traits, class _Allocator> 2374basic_string<_CharT, _Traits, _Allocator>& 2375basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n) 2376{ 2377 size_type __sz = __str.size(); 2378 if (__pos > __sz) 2379 this->__throw_out_of_range(); 2380 return append(__str.data() + __pos, _VSTD::min(__n, __sz - __pos)); 2381} 2382 2383template <class _CharT, class _Traits, class _Allocator> 2384basic_string<_CharT, _Traits, _Allocator>& 2385basic_string<_CharT, _Traits, _Allocator>::append(const_pointer __s) 2386{ 2387#ifdef _LIBCPP_DEBUG 2388 assert(__s != 0); 2389#endif 2390 return append(__s, traits_type::length(__s)); 2391} 2392 2393// insert 2394 2395template <class _CharT, class _Traits, class _Allocator> 2396basic_string<_CharT, _Traits, _Allocator>& 2397basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const_pointer __s, size_type __n) 2398{ 2399#ifdef _LIBCPP_DEBUG 2400 assert(__s != 0); 2401#endif 2402 size_type __sz = size(); 2403 if (__pos > __sz) 2404 this->__throw_out_of_range(); 2405 size_type __cap = capacity(); 2406 if (__cap - __sz >= __n) 2407 { 2408 if (__n) 2409 { 2410 pointer __p = __get_pointer(); 2411 size_type __n_move = __sz - __pos; 2412 if (__n_move != 0) 2413 { 2414 if (__p + __pos <= __s && __s < __p + __sz) 2415 __s += __n; 2416 traits_type::move(__p + __pos + __n, __p + __pos, __n_move); 2417 } 2418 traits_type::move(__p + __pos, __s, __n); 2419 __sz += __n; 2420 __set_size(__sz); 2421 traits_type::assign(__p[__sz], value_type()); 2422 } 2423 } 2424 else 2425 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s); 2426 return *this; 2427} 2428 2429template <class _CharT, class _Traits, class _Allocator> 2430basic_string<_CharT, _Traits, _Allocator>& 2431basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c) 2432{ 2433 size_type __sz = size(); 2434 if (__pos > __sz) 2435 this->__throw_out_of_range(); 2436 if (__n) 2437 { 2438 size_type __cap = capacity(); 2439 pointer __p; 2440 if (__cap - __sz >= __n) 2441 { 2442 __p = __get_pointer(); 2443 size_type __n_move = __sz - __pos; 2444 if (__n_move != 0) 2445 traits_type::move(__p + __pos + __n, __p + __pos, __n_move); 2446 } 2447 else 2448 { 2449 __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n); 2450 __p = __get_long_pointer(); 2451 } 2452 traits_type::assign(__p + __pos, __n, __c); 2453 __sz += __n; 2454 __set_size(__sz); 2455 traits_type::assign(__p[__sz], value_type()); 2456 } 2457 return *this; 2458} 2459 2460template <class _CharT, class _Traits, class _Allocator> 2461template<class _InputIterator> 2462typename enable_if 2463< 2464 __is_input_iterator <_InputIterator>::value && 2465 !__is_forward_iterator<_InputIterator>::value, 2466 typename basic_string<_CharT, _Traits, _Allocator>::iterator 2467>::type 2468basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last) 2469{ 2470 size_type __old_sz = size(); 2471 difference_type __ip = __pos - begin(); 2472 for (; __first != __last; ++__first) 2473 push_back(*__first); 2474 pointer __p = __get_pointer(); 2475 _VSTD::rotate(__p + __ip, __p + __old_sz, __p + size()); 2476 return iterator(__p + __ip); 2477} 2478 2479template <class _CharT, class _Traits, class _Allocator> 2480template<class _ForwardIterator> 2481typename enable_if 2482< 2483 __is_forward_iterator<_ForwardIterator>::value, 2484 typename basic_string<_CharT, _Traits, _Allocator>::iterator 2485>::type 2486basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last) 2487{ 2488 size_type __ip = static_cast<size_type>(__pos - begin()); 2489 size_type __sz = size(); 2490 size_type __cap = capacity(); 2491 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2492 if (__n) 2493 { 2494 pointer __p; 2495 if (__cap - __sz >= __n) 2496 { 2497 __p = __get_pointer(); 2498 size_type __n_move = __sz - __ip; 2499 if (__n_move != 0) 2500 traits_type::move(__p + __ip + __n, __p + __ip, __n_move); 2501 } 2502 else 2503 { 2504 __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n); 2505 __p = __get_long_pointer(); 2506 } 2507 __sz += __n; 2508 __set_size(__sz); 2509 traits_type::assign(__p[__sz], value_type()); 2510 for (__p += __ip; __first != __last; ++__p, ++__first) 2511 traits_type::assign(*__p, *__first); 2512 } 2513 return begin() + __ip; 2514} 2515 2516template <class _CharT, class _Traits, class _Allocator> 2517_LIBCPP_INLINE_VISIBILITY inline 2518basic_string<_CharT, _Traits, _Allocator>& 2519basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str) 2520{ 2521 return insert(__pos1, __str.data(), __str.size()); 2522} 2523 2524template <class _CharT, class _Traits, class _Allocator> 2525basic_string<_CharT, _Traits, _Allocator>& 2526basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str, 2527 size_type __pos2, size_type __n) 2528{ 2529 size_type __str_sz = __str.size(); 2530 if (__pos2 > __str_sz) 2531 this->__throw_out_of_range(); 2532 return insert(__pos1, __str.data() + __pos2, _VSTD::min(__n, __str_sz - __pos2)); 2533} 2534 2535template <class _CharT, class _Traits, class _Allocator> 2536basic_string<_CharT, _Traits, _Allocator>& 2537basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const_pointer __s) 2538{ 2539#ifdef _LIBCPP_DEBUG 2540 assert(__s != 0); 2541#endif 2542 return insert(__pos, __s, traits_type::length(__s)); 2543} 2544 2545template <class _CharT, class _Traits, class _Allocator> 2546typename basic_string<_CharT, _Traits, _Allocator>::iterator 2547basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c) 2548{ 2549 size_type __ip = static_cast<size_type>(__pos - begin()); 2550 size_type __sz = size(); 2551 size_type __cap = capacity(); 2552 pointer __p; 2553 if (__cap == __sz) 2554 { 2555 __grow_by(__cap, 1, __sz, __ip, 0, 1); 2556 __p = __get_long_pointer(); 2557 } 2558 else 2559 { 2560 __p = __get_pointer(); 2561 size_type __n_move = __sz - __ip; 2562 if (__n_move != 0) 2563 traits_type::move(__p + __ip + 1, __p + __ip, __n_move); 2564 } 2565 traits_type::assign(__p[__ip], __c); 2566 traits_type::assign(__p[++__sz], value_type()); 2567 __set_size(__sz); 2568 return begin() + static_cast<difference_type>(__ip); 2569} 2570 2571template <class _CharT, class _Traits, class _Allocator> 2572_LIBCPP_INLINE_VISIBILITY inline 2573typename basic_string<_CharT, _Traits, _Allocator>::iterator 2574basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, size_type __n, value_type __c) 2575{ 2576 difference_type __p = __pos - begin(); 2577 insert(static_cast<size_type>(__p), __n, __c); 2578 return begin() + __p; 2579} 2580 2581// replace 2582 2583template <class _CharT, class _Traits, class _Allocator> 2584basic_string<_CharT, _Traits, _Allocator>& 2585basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const_pointer __s, size_type __n2) 2586{ 2587#ifdef _LIBCPP_DEBUG 2588 assert(__s != 0); 2589#endif 2590 size_type __sz = size(); 2591 if (__pos > __sz) 2592 this->__throw_out_of_range(); 2593 __n1 = _VSTD::min(__n1, __sz - __pos); 2594 size_type __cap = capacity(); 2595 if (__cap - __sz + __n1 >= __n2) 2596 { 2597 pointer __p = __get_pointer(); 2598 if (__n1 != __n2) 2599 { 2600 size_type __n_move = __sz - __pos - __n1; 2601 if (__n_move != 0) 2602 { 2603 if (__n1 > __n2) 2604 { 2605 traits_type::move(__p + __pos, __s, __n2); 2606 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2607 goto __finish; 2608 } 2609 if (__p + __pos < __s && __s < __p + __sz) 2610 { 2611 if (__p + __pos + __n1 <= __s) 2612 __s += __n2 - __n1; 2613 else // __p + __pos < __s < __p + __pos + __n1 2614 { 2615 traits_type::move(__p + __pos, __s, __n1); 2616 __pos += __n1; 2617 __s += __n2; 2618 __n2 -= __n1; 2619 __n1 = 0; 2620 } 2621 } 2622 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2623 } 2624 } 2625 traits_type::move(__p + __pos, __s, __n2); 2626__finish: 2627 __sz += __n2 - __n1; 2628 __set_size(__sz); 2629 __invalidate_iterators_past(__sz); 2630 traits_type::assign(__p[__sz], value_type()); 2631 } 2632 else 2633 __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s); 2634 return *this; 2635} 2636 2637template <class _CharT, class _Traits, class _Allocator> 2638basic_string<_CharT, _Traits, _Allocator>& 2639basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c) 2640{ 2641 size_type __sz = size(); 2642 if (__pos > __sz) 2643 this->__throw_out_of_range(); 2644 __n1 = _VSTD::min(__n1, __sz - __pos); 2645 size_type __cap = capacity(); 2646 pointer __p; 2647 if (__cap - __sz + __n1 >= __n2) 2648 { 2649 __p = __get_pointer(); 2650 if (__n1 != __n2) 2651 { 2652 size_type __n_move = __sz - __pos - __n1; 2653 if (__n_move != 0) 2654 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2655 } 2656 } 2657 else 2658 { 2659 __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2); 2660 __p = __get_long_pointer(); 2661 } 2662 traits_type::assign(__p + __pos, __n2, __c); 2663 __sz += __n2 - __n1; 2664 __set_size(__sz); 2665 __invalidate_iterators_past(__sz); 2666 traits_type::assign(__p[__sz], value_type()); 2667 return *this; 2668} 2669 2670template <class _CharT, class _Traits, class _Allocator> 2671template<class _InputIterator> 2672typename enable_if 2673< 2674 __is_input_iterator<_InputIterator>::value, 2675 basic_string<_CharT, _Traits, _Allocator>& 2676>::type 2677basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, 2678 _InputIterator __j1, _InputIterator __j2) 2679{ 2680 for (; true; ++__i1, ++__j1) 2681 { 2682 if (__i1 == __i2) 2683 { 2684 if (__j1 != __j2) 2685 insert(__i1, __j1, __j2); 2686 break; 2687 } 2688 if (__j1 == __j2) 2689 { 2690 erase(__i1, __i2); 2691 break; 2692 } 2693 traits_type::assign(const_cast<value_type&>(*__i1), *__j1); 2694 } 2695 return *this; 2696} 2697 2698template <class _CharT, class _Traits, class _Allocator> 2699_LIBCPP_INLINE_VISIBILITY inline 2700basic_string<_CharT, _Traits, _Allocator>& 2701basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str) 2702{ 2703 return replace(__pos1, __n1, __str.data(), __str.size()); 2704} 2705 2706template <class _CharT, class _Traits, class _Allocator> 2707basic_string<_CharT, _Traits, _Allocator>& 2708basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str, 2709 size_type __pos2, size_type __n2) 2710{ 2711 size_type __str_sz = __str.size(); 2712 if (__pos2 > __str_sz) 2713 this->__throw_out_of_range(); 2714 return replace(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, __str_sz - __pos2)); 2715} 2716 2717template <class _CharT, class _Traits, class _Allocator> 2718basic_string<_CharT, _Traits, _Allocator>& 2719basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const_pointer __s) 2720{ 2721#ifdef _LIBCPP_DEBUG 2722 assert(__s != 0); 2723#endif 2724 return replace(__pos, __n1, __s, traits_type::length(__s)); 2725} 2726 2727template <class _CharT, class _Traits, class _Allocator> 2728_LIBCPP_INLINE_VISIBILITY inline 2729basic_string<_CharT, _Traits, _Allocator>& 2730basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const basic_string& __str) 2731{ 2732 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), 2733 __str.data(), __str.size()); 2734} 2735 2736template <class _CharT, class _Traits, class _Allocator> 2737_LIBCPP_INLINE_VISIBILITY inline 2738basic_string<_CharT, _Traits, _Allocator>& 2739basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const_pointer __s, size_type __n) 2740{ 2741 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n); 2742} 2743 2744template <class _CharT, class _Traits, class _Allocator> 2745_LIBCPP_INLINE_VISIBILITY inline 2746basic_string<_CharT, _Traits, _Allocator>& 2747basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const_pointer __s) 2748{ 2749 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s); 2750} 2751 2752template <class _CharT, class _Traits, class _Allocator> 2753_LIBCPP_INLINE_VISIBILITY inline 2754basic_string<_CharT, _Traits, _Allocator>& 2755basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c) 2756{ 2757 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c); 2758} 2759 2760// erase 2761 2762template <class _CharT, class _Traits, class _Allocator> 2763basic_string<_CharT, _Traits, _Allocator>& 2764basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos, size_type __n) 2765{ 2766 size_type __sz = size(); 2767 if (__pos > __sz) 2768 this->__throw_out_of_range(); 2769 if (__n) 2770 { 2771 pointer __p = __get_pointer(); 2772 __n = _VSTD::min(__n, __sz - __pos); 2773 size_type __n_move = __sz - __pos - __n; 2774 if (__n_move != 0) 2775 traits_type::move(__p + __pos, __p + __pos + __n, __n_move); 2776 __sz -= __n; 2777 __set_size(__sz); 2778 __invalidate_iterators_past(__sz); 2779 traits_type::assign(__p[__sz], value_type()); 2780 } 2781 return *this; 2782} 2783 2784template <class _CharT, class _Traits, class _Allocator> 2785_LIBCPP_INLINE_VISIBILITY inline 2786typename basic_string<_CharT, _Traits, _Allocator>::iterator 2787basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos) 2788{ 2789 iterator __b = begin(); 2790 size_type __r = static_cast<size_type>(__pos - __b); 2791 erase(__r, 1); 2792 return __b + static_cast<difference_type>(__r); 2793} 2794 2795template <class _CharT, class _Traits, class _Allocator> 2796_LIBCPP_INLINE_VISIBILITY inline 2797typename basic_string<_CharT, _Traits, _Allocator>::iterator 2798basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last) 2799{ 2800 iterator __b = begin(); 2801 size_type __r = static_cast<size_type>(__first - __b); 2802 erase(__r, static_cast<size_type>(__last - __first)); 2803 return __b + static_cast<difference_type>(__r); 2804} 2805 2806template <class _CharT, class _Traits, class _Allocator> 2807_LIBCPP_INLINE_VISIBILITY inline 2808void 2809basic_string<_CharT, _Traits, _Allocator>::pop_back() 2810{ 2811#ifdef _LIBCPP_DEBUG 2812 assert(!empty()); 2813#endif 2814 size_type __sz; 2815 if (__is_long()) 2816 { 2817 __sz = __get_long_size() - 1; 2818 __set_long_size(__sz); 2819 traits_type::assign(*(__get_long_pointer() + __sz), value_type()); 2820 } 2821 else 2822 { 2823 __sz = __get_short_size() - 1; 2824 __set_short_size(__sz); 2825 traits_type::assign(*(__get_short_pointer() + __sz), value_type()); 2826 } 2827 __invalidate_iterators_past(__sz); 2828} 2829 2830template <class _CharT, class _Traits, class _Allocator> 2831_LIBCPP_INLINE_VISIBILITY inline 2832void 2833basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT 2834{ 2835 __invalidate_all_iterators(); 2836 if (__is_long()) 2837 { 2838 traits_type::assign(*__get_long_pointer(), value_type()); 2839 __set_long_size(0); 2840 } 2841 else 2842 { 2843 traits_type::assign(*__get_short_pointer(), value_type()); 2844 __set_short_size(0); 2845 } 2846} 2847 2848template <class _CharT, class _Traits, class _Allocator> 2849_LIBCPP_INLINE_VISIBILITY inline 2850void 2851basic_string<_CharT, _Traits, _Allocator>::__erase_to_end(size_type __pos) 2852{ 2853 if (__is_long()) 2854 { 2855 traits_type::assign(*(__get_long_pointer() + __pos), value_type()); 2856 __set_long_size(__pos); 2857 } 2858 else 2859 { 2860 traits_type::assign(*(__get_short_pointer() + __pos), value_type()); 2861 __set_short_size(__pos); 2862 } 2863 __invalidate_iterators_past(__pos); 2864} 2865 2866template <class _CharT, class _Traits, class _Allocator> 2867void 2868basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c) 2869{ 2870 size_type __sz = size(); 2871 if (__n > __sz) 2872 append(__n - __sz, __c); 2873 else 2874 __erase_to_end(__n); 2875} 2876 2877template <class _CharT, class _Traits, class _Allocator> 2878_LIBCPP_INLINE_VISIBILITY inline 2879typename basic_string<_CharT, _Traits, _Allocator>::size_type 2880basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT 2881{ 2882 size_type __m = __alloc_traits::max_size(__alloc()); 2883#if _LIBCPP_BIG_ENDIAN 2884 return (__m <= ~__long_mask ? __m : __m/2) - 1; 2885#else 2886 return __m - 1; 2887#endif 2888} 2889 2890template <class _CharT, class _Traits, class _Allocator> 2891void 2892basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __res_arg) 2893{ 2894 if (__res_arg > max_size()) 2895 this->__throw_length_error(); 2896 size_type __cap = capacity(); 2897 size_type __sz = size(); 2898 __res_arg = _VSTD::max(__res_arg, __sz); 2899 __res_arg = __recommend(__res_arg); 2900 if (__res_arg != __cap) 2901 { 2902 pointer __new_data, __p; 2903 bool __was_long, __now_long; 2904 if (__res_arg == __min_cap - 1) 2905 { 2906 __was_long = true; 2907 __now_long = false; 2908 __new_data = __get_short_pointer(); 2909 __p = __get_long_pointer(); 2910 } 2911 else 2912 { 2913 if (__res_arg > __cap) 2914 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1); 2915 else 2916 { 2917 #ifndef _LIBCPP_NO_EXCEPTIONS 2918 try 2919 { 2920 #endif // _LIBCPP_NO_EXCEPTIONS 2921 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1); 2922 #ifndef _LIBCPP_NO_EXCEPTIONS 2923 } 2924 catch (...) 2925 { 2926 return; 2927 } 2928 #else // _LIBCPP_NO_EXCEPTIONS 2929 if (__new_data == 0) 2930 return; 2931 #endif // _LIBCPP_NO_EXCEPTIONS 2932 } 2933 __now_long = true; 2934 __was_long = __is_long(); 2935 __p = __get_pointer(); 2936 } 2937 traits_type::copy(__new_data, __p, size()+1); 2938 if (__was_long) 2939 __alloc_traits::deallocate(__alloc(), __p, __cap+1); 2940 if (__now_long) 2941 { 2942 __set_long_cap(__res_arg+1); 2943 __set_long_size(__sz); 2944 __set_long_pointer(__new_data); 2945 } 2946 else 2947 __set_short_size(__sz); 2948 __invalidate_all_iterators(); 2949 } 2950} 2951 2952template <class _CharT, class _Traits, class _Allocator> 2953_LIBCPP_INLINE_VISIBILITY inline 2954typename basic_string<_CharT, _Traits, _Allocator>::const_reference 2955basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) const 2956{ 2957#ifdef __LIBCPP_DEBUG 2958 assert(__pos <= size()); 2959#endif 2960 return *(data() + __pos); 2961} 2962 2963template <class _CharT, class _Traits, class _Allocator> 2964_LIBCPP_INLINE_VISIBILITY inline 2965typename basic_string<_CharT, _Traits, _Allocator>::reference 2966basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) 2967{ 2968#ifdef __LIBCPP_DEBUG 2969 assert(__pos < size()); 2970#endif 2971 return *(__get_pointer() + __pos); 2972} 2973 2974template <class _CharT, class _Traits, class _Allocator> 2975typename basic_string<_CharT, _Traits, _Allocator>::const_reference 2976basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const 2977{ 2978 if (__n >= size()) 2979 this->__throw_out_of_range(); 2980 return (*this)[__n]; 2981} 2982 2983template <class _CharT, class _Traits, class _Allocator> 2984typename basic_string<_CharT, _Traits, _Allocator>::reference 2985basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) 2986{ 2987 if (__n >= size()) 2988 this->__throw_out_of_range(); 2989 return (*this)[__n]; 2990} 2991 2992template <class _CharT, class _Traits, class _Allocator> 2993_LIBCPP_INLINE_VISIBILITY inline 2994typename basic_string<_CharT, _Traits, _Allocator>::reference 2995basic_string<_CharT, _Traits, _Allocator>::front() 2996{ 2997#ifdef _LIBCPP_DEBUG 2998 assert(!empty()); 2999#endif 3000 return *__get_pointer(); 3001} 3002 3003template <class _CharT, class _Traits, class _Allocator> 3004_LIBCPP_INLINE_VISIBILITY inline 3005typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3006basic_string<_CharT, _Traits, _Allocator>::front() const 3007{ 3008#ifdef _LIBCPP_DEBUG 3009 assert(!empty()); 3010#endif 3011 return *data(); 3012} 3013 3014template <class _CharT, class _Traits, class _Allocator> 3015_LIBCPP_INLINE_VISIBILITY inline 3016typename basic_string<_CharT, _Traits, _Allocator>::reference 3017basic_string<_CharT, _Traits, _Allocator>::back() 3018{ 3019#ifdef _LIBCPP_DEBUG 3020 assert(!empty()); 3021#endif 3022 return *(__get_pointer() + size() - 1); 3023} 3024 3025template <class _CharT, class _Traits, class _Allocator> 3026_LIBCPP_INLINE_VISIBILITY inline 3027typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3028basic_string<_CharT, _Traits, _Allocator>::back() const 3029{ 3030#ifdef _LIBCPP_DEBUG 3031 assert(!empty()); 3032#endif 3033 return *(data() + size() - 1); 3034} 3035 3036template <class _CharT, class _Traits, class _Allocator> 3037typename basic_string<_CharT, _Traits, _Allocator>::size_type 3038basic_string<_CharT, _Traits, _Allocator>::copy(pointer __s, size_type __n, size_type __pos) const 3039{ 3040 size_type __sz = size(); 3041 if (__pos > __sz) 3042 this->__throw_out_of_range(); 3043 size_type __rlen = _VSTD::min(__n, __sz - __pos); 3044 traits_type::copy(__s, data() + __pos, __rlen); 3045 return __rlen; 3046} 3047 3048template <class _CharT, class _Traits, class _Allocator> 3049_LIBCPP_INLINE_VISIBILITY inline 3050basic_string<_CharT, _Traits, _Allocator> 3051basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const 3052{ 3053 return basic_string(*this, __pos, __n, __alloc()); 3054} 3055 3056template <class _CharT, class _Traits, class _Allocator> 3057_LIBCPP_INLINE_VISIBILITY inline 3058void 3059basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str) 3060 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3061 __is_nothrow_swappable<allocator_type>::value) 3062{ 3063 _VSTD::swap(__r_.first(), __str.__r_.first()); 3064 __swap_alloc(__alloc(), __str.__alloc()); 3065#ifdef _LIBCPP_DEBUG 3066 __invalidate_all_iterators(); 3067 __str.__invalidate_all_iterators(); 3068#endif // _LIBCPP_DEBUG 3069} 3070 3071// find 3072 3073template <class _Traits> 3074struct _LIBCPP_HIDDEN __traits_eq 3075{ 3076 typedef typename _Traits::char_type char_type; 3077 _LIBCPP_INLINE_VISIBILITY 3078 bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT 3079 {return _Traits::eq(__x, __y);} 3080}; 3081 3082template<class _CharT, class _Traits, class _Allocator> 3083typename basic_string<_CharT, _Traits, _Allocator>::size_type 3084basic_string<_CharT, _Traits, _Allocator>::find(const_pointer __s, 3085 size_type __pos, 3086 size_type __n) const _NOEXCEPT 3087{ 3088#ifdef _LIBCPP_DEBUG 3089 assert(__s != 0); 3090#endif 3091 size_type __sz = size(); 3092 if (__pos > __sz || __sz - __pos < __n) 3093 return npos; 3094 if (__n == 0) 3095 return __pos; 3096 const_pointer __p = data(); 3097 const_pointer __r = _VSTD::search(__p + __pos, __p + __sz, __s, __s + __n, 3098 __traits_eq<traits_type>()); 3099 if (__r == __p + __sz) 3100 return npos; 3101 return static_cast<size_type>(__r - __p); 3102} 3103 3104template<class _CharT, class _Traits, class _Allocator> 3105_LIBCPP_INLINE_VISIBILITY inline 3106typename basic_string<_CharT, _Traits, _Allocator>::size_type 3107basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str, 3108 size_type __pos) const _NOEXCEPT 3109{ 3110 return find(__str.data(), __pos, __str.size()); 3111} 3112 3113template<class _CharT, class _Traits, class _Allocator> 3114_LIBCPP_INLINE_VISIBILITY inline 3115typename basic_string<_CharT, _Traits, _Allocator>::size_type 3116basic_string<_CharT, _Traits, _Allocator>::find(const_pointer __s, 3117 size_type __pos) const _NOEXCEPT 3118{ 3119#ifdef _LIBCPP_DEBUG 3120 assert(__s != 0); 3121#endif 3122 return find(__s, __pos, traits_type::length(__s)); 3123} 3124 3125template<class _CharT, class _Traits, class _Allocator> 3126typename basic_string<_CharT, _Traits, _Allocator>::size_type 3127basic_string<_CharT, _Traits, _Allocator>::find(value_type __c, 3128 size_type __pos) const _NOEXCEPT 3129{ 3130 size_type __sz = size(); 3131 if (__pos >= __sz) 3132 return npos; 3133 const_pointer __p = data(); 3134 const_pointer __r = traits_type::find(__p + __pos, __sz - __pos, __c); 3135 if (__r == 0) 3136 return npos; 3137 return static_cast<size_type>(__r - __p); 3138} 3139 3140// rfind 3141 3142template<class _CharT, class _Traits, class _Allocator> 3143typename basic_string<_CharT, _Traits, _Allocator>::size_type 3144basic_string<_CharT, _Traits, _Allocator>::rfind(const_pointer __s, 3145 size_type __pos, 3146 size_type __n) const _NOEXCEPT 3147{ 3148#ifdef _LIBCPP_DEBUG 3149 assert(__s != 0); 3150#endif 3151 size_type __sz = size(); 3152 __pos = _VSTD::min(__pos, __sz); 3153 if (__n < __sz - __pos) 3154 __pos += __n; 3155 else 3156 __pos = __sz; 3157 const_pointer __p = data(); 3158 const_pointer __r = _VSTD::find_end(__p, __p + __pos, __s, __s + __n, 3159 __traits_eq<traits_type>()); 3160 if (__n > 0 && __r == __p + __pos) 3161 return npos; 3162 return static_cast<size_type>(__r - __p); 3163} 3164 3165template<class _CharT, class _Traits, class _Allocator> 3166_LIBCPP_INLINE_VISIBILITY inline 3167typename basic_string<_CharT, _Traits, _Allocator>::size_type 3168basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str, 3169 size_type __pos) const _NOEXCEPT 3170{ 3171 return rfind(__str.data(), __pos, __str.size()); 3172} 3173 3174template<class _CharT, class _Traits, class _Allocator> 3175_LIBCPP_INLINE_VISIBILITY inline 3176typename basic_string<_CharT, _Traits, _Allocator>::size_type 3177basic_string<_CharT, _Traits, _Allocator>::rfind(const_pointer __s, 3178 size_type __pos) const _NOEXCEPT 3179{ 3180#ifdef _LIBCPP_DEBUG 3181 assert(__s != 0); 3182#endif 3183 return rfind(__s, __pos, traits_type::length(__s)); 3184} 3185 3186template<class _CharT, class _Traits, class _Allocator> 3187typename basic_string<_CharT, _Traits, _Allocator>::size_type 3188basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c, 3189 size_type __pos) const _NOEXCEPT 3190{ 3191 size_type __sz = size(); 3192 if (__sz) 3193 { 3194 if (__pos < __sz) 3195 ++__pos; 3196 else 3197 __pos = __sz; 3198 const_pointer __p = data(); 3199 for (const_pointer __ps = __p + __pos; __ps != __p;) 3200 { 3201 if (traits_type::eq(*--__ps, __c)) 3202 return static_cast<size_type>(__ps - __p); 3203 } 3204 } 3205 return npos; 3206} 3207 3208// find_first_of 3209 3210template<class _CharT, class _Traits, class _Allocator> 3211typename basic_string<_CharT, _Traits, _Allocator>::size_type 3212basic_string<_CharT, _Traits, _Allocator>::find_first_of(const_pointer __s, 3213 size_type __pos, 3214 size_type __n) const _NOEXCEPT 3215{ 3216#ifdef _LIBCPP_DEBUG 3217 assert(__s != 0); 3218#endif 3219 size_type __sz = size(); 3220 if (__pos >= __sz || __n == 0) 3221 return npos; 3222 const_pointer __p = data(); 3223 const_pointer __r = _VSTD::find_first_of(__p + __pos, __p + __sz, __s, 3224 __s + __n, __traits_eq<traits_type>()); 3225 if (__r == __p + __sz) 3226 return npos; 3227 return static_cast<size_type>(__r - __p); 3228} 3229 3230template<class _CharT, class _Traits, class _Allocator> 3231_LIBCPP_INLINE_VISIBILITY inline 3232typename basic_string<_CharT, _Traits, _Allocator>::size_type 3233basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str, 3234 size_type __pos) const _NOEXCEPT 3235{ 3236 return find_first_of(__str.data(), __pos, __str.size()); 3237} 3238 3239template<class _CharT, class _Traits, class _Allocator> 3240_LIBCPP_INLINE_VISIBILITY inline 3241typename basic_string<_CharT, _Traits, _Allocator>::size_type 3242basic_string<_CharT, _Traits, _Allocator>::find_first_of(const_pointer __s, 3243 size_type __pos) const _NOEXCEPT 3244{ 3245#ifdef _LIBCPP_DEBUG 3246 assert(__s != 0); 3247#endif 3248 return find_first_of(__s, __pos, traits_type::length(__s)); 3249} 3250 3251template<class _CharT, class _Traits, class _Allocator> 3252_LIBCPP_INLINE_VISIBILITY inline 3253typename basic_string<_CharT, _Traits, _Allocator>::size_type 3254basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c, 3255 size_type __pos) const _NOEXCEPT 3256{ 3257 return find(__c, __pos); 3258} 3259 3260// find_last_of 3261 3262template<class _CharT, class _Traits, class _Allocator> 3263typename basic_string<_CharT, _Traits, _Allocator>::size_type 3264basic_string<_CharT, _Traits, _Allocator>::find_last_of(const_pointer __s, 3265 size_type __pos, 3266 size_type __n) const _NOEXCEPT 3267{ 3268#ifdef _LIBCPP_DEBUG 3269 assert(__s != 0); 3270#endif 3271 if (__n != 0) 3272 { 3273 size_type __sz = size(); 3274 if (__pos < __sz) 3275 ++__pos; 3276 else 3277 __pos = __sz; 3278 const_pointer __p = data(); 3279 for (const_pointer __ps = __p + __pos; __ps != __p;) 3280 { 3281 const_pointer __r = traits_type::find(__s, __n, *--__ps); 3282 if (__r) 3283 return static_cast<size_type>(__ps - __p); 3284 } 3285 } 3286 return npos; 3287} 3288 3289template<class _CharT, class _Traits, class _Allocator> 3290_LIBCPP_INLINE_VISIBILITY inline 3291typename basic_string<_CharT, _Traits, _Allocator>::size_type 3292basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str, 3293 size_type __pos) const _NOEXCEPT 3294{ 3295 return find_last_of(__str.data(), __pos, __str.size()); 3296} 3297 3298template<class _CharT, class _Traits, class _Allocator> 3299_LIBCPP_INLINE_VISIBILITY inline 3300typename basic_string<_CharT, _Traits, _Allocator>::size_type 3301basic_string<_CharT, _Traits, _Allocator>::find_last_of(const_pointer __s, 3302 size_type __pos) const _NOEXCEPT 3303{ 3304#ifdef _LIBCPP_DEBUG 3305 assert(__s != 0); 3306#endif 3307 return find_last_of(__s, __pos, traits_type::length(__s)); 3308} 3309 3310template<class _CharT, class _Traits, class _Allocator> 3311_LIBCPP_INLINE_VISIBILITY inline 3312typename basic_string<_CharT, _Traits, _Allocator>::size_type 3313basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c, 3314 size_type __pos) const _NOEXCEPT 3315{ 3316 return rfind(__c, __pos); 3317} 3318 3319// find_first_not_of 3320 3321template<class _CharT, class _Traits, class _Allocator> 3322typename basic_string<_CharT, _Traits, _Allocator>::size_type 3323basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const_pointer __s, 3324 size_type __pos, 3325 size_type __n) const _NOEXCEPT 3326{ 3327#ifdef _LIBCPP_DEBUG 3328 assert(__s != 0); 3329#endif 3330 size_type __sz = size(); 3331 if (__pos < __sz) 3332 { 3333 const_pointer __p = data(); 3334 const_pointer __pe = __p + __sz; 3335 for (const_pointer __ps = __p + __pos; __ps != __pe; ++__ps) 3336 if (traits_type::find(__s, __n, *__ps) == 0) 3337 return static_cast<size_type>(__ps - __p); 3338 } 3339 return npos; 3340} 3341 3342template<class _CharT, class _Traits, class _Allocator> 3343_LIBCPP_INLINE_VISIBILITY inline 3344typename basic_string<_CharT, _Traits, _Allocator>::size_type 3345basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str, 3346 size_type __pos) const _NOEXCEPT 3347{ 3348 return find_first_not_of(__str.data(), __pos, __str.size()); 3349} 3350 3351template<class _CharT, class _Traits, class _Allocator> 3352_LIBCPP_INLINE_VISIBILITY inline 3353typename basic_string<_CharT, _Traits, _Allocator>::size_type 3354basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const_pointer __s, 3355 size_type __pos) const _NOEXCEPT 3356{ 3357#ifdef _LIBCPP_DEBUG 3358 assert(__s != 0); 3359#endif 3360 return find_first_not_of(__s, __pos, traits_type::length(__s)); 3361} 3362 3363template<class _CharT, class _Traits, class _Allocator> 3364_LIBCPP_INLINE_VISIBILITY inline 3365typename basic_string<_CharT, _Traits, _Allocator>::size_type 3366basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c, 3367 size_type __pos) const _NOEXCEPT 3368{ 3369 size_type __sz = size(); 3370 if (__pos < __sz) 3371 { 3372 const_pointer __p = data(); 3373 const_pointer __pe = __p + __sz; 3374 for (const_pointer __ps = __p + __pos; __p != __pe; ++__ps) 3375 if (!traits_type::eq(*__ps, __c)) 3376 return static_cast<size_type>(__ps - __p); 3377 } 3378 return npos; 3379} 3380 3381// find_last_not_of 3382 3383template<class _CharT, class _Traits, class _Allocator> 3384typename basic_string<_CharT, _Traits, _Allocator>::size_type 3385basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const_pointer __s, 3386 size_type __pos, 3387 size_type __n) const _NOEXCEPT 3388{ 3389#ifdef _LIBCPP_DEBUG 3390 assert(__s != 0); 3391#endif 3392 size_type __sz = size(); 3393 if (__pos < __sz) 3394 ++__pos; 3395 else 3396 __pos = __sz; 3397 const_pointer __p = data(); 3398 for (const_pointer __ps = __p + __pos; __ps != __p;) 3399 if (traits_type::find(__s, __n, *--__ps) == 0) 3400 return static_cast<size_type>(__ps - __p); 3401 return npos; 3402} 3403 3404template<class _CharT, class _Traits, class _Allocator> 3405_LIBCPP_INLINE_VISIBILITY inline 3406typename basic_string<_CharT, _Traits, _Allocator>::size_type 3407basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str, 3408 size_type __pos) const _NOEXCEPT 3409{ 3410 return find_last_not_of(__str.data(), __pos, __str.size()); 3411} 3412 3413template<class _CharT, class _Traits, class _Allocator> 3414_LIBCPP_INLINE_VISIBILITY inline 3415typename basic_string<_CharT, _Traits, _Allocator>::size_type 3416basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const_pointer __s, 3417 size_type __pos) const _NOEXCEPT 3418{ 3419#ifdef _LIBCPP_DEBUG 3420 assert(__s != 0); 3421#endif 3422 return find_last_not_of(__s, __pos, traits_type::length(__s)); 3423} 3424 3425template<class _CharT, class _Traits, class _Allocator> 3426_LIBCPP_INLINE_VISIBILITY inline 3427typename basic_string<_CharT, _Traits, _Allocator>::size_type 3428basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c, 3429 size_type __pos) const _NOEXCEPT 3430{ 3431 size_type __sz = size(); 3432 if (__pos < __sz) 3433 ++__pos; 3434 else 3435 __pos = __sz; 3436 const_pointer __p = data(); 3437 for (const_pointer __ps = __p + __pos; __ps != __p;) 3438 if (!traits_type::eq(*--__ps, __c)) 3439 return static_cast<size_type>(__ps - __p); 3440 return npos; 3441} 3442 3443// compare 3444 3445template <class _CharT, class _Traits, class _Allocator> 3446_LIBCPP_INLINE_VISIBILITY inline 3447int 3448basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT 3449{ 3450 size_t __lhs_sz = size(); 3451 size_t __rhs_sz = __str.size(); 3452 int __result = traits_type::compare(data(), __str.data(), 3453 _VSTD::min(__lhs_sz, __rhs_sz)); 3454 if (__result != 0) 3455 return __result; 3456 if (__lhs_sz < __rhs_sz) 3457 return -1; 3458 if (__lhs_sz > __rhs_sz) 3459 return 1; 3460 return 0; 3461} 3462 3463template <class _CharT, class _Traits, class _Allocator> 3464_LIBCPP_INLINE_VISIBILITY inline 3465int 3466basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3467 size_type __n1, 3468 const basic_string& __str) const 3469{ 3470 return compare(__pos1, __n1, __str.data(), __str.size()); 3471} 3472 3473template <class _CharT, class _Traits, class _Allocator> 3474int 3475basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3476 size_type __n1, 3477 const basic_string& __str, 3478 size_type __pos2, 3479 size_type __n2) const 3480{ 3481 size_type __sz = __str.size(); 3482 if (__pos2 > __sz) 3483 this->__throw_out_of_range(); 3484 return compare(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, 3485 __sz - __pos2)); 3486} 3487 3488template <class _CharT, class _Traits, class _Allocator> 3489int 3490basic_string<_CharT, _Traits, _Allocator>::compare(const_pointer __s) const _NOEXCEPT 3491{ 3492#ifdef _LIBCPP_DEBUG 3493 assert(__s != 0); 3494#endif 3495 return compare(0, npos, __s, traits_type::length(__s)); 3496} 3497 3498template <class _CharT, class _Traits, class _Allocator> 3499int 3500basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3501 size_type __n1, 3502 const_pointer __s) const 3503{ 3504#ifdef _LIBCPP_DEBUG 3505 assert(__s != 0); 3506#endif 3507 return compare(__pos1, __n1, __s, traits_type::length(__s)); 3508} 3509 3510template <class _CharT, class _Traits, class _Allocator> 3511int 3512basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3513 size_type __n1, 3514 const_pointer __s, 3515 size_type __n2) const 3516{ 3517#ifdef _LIBCPP_DEBUG 3518 assert(__s != 0); 3519#endif 3520 size_type __sz = size(); 3521 if (__pos1 > __sz || __n2 == npos) 3522 this->__throw_out_of_range(); 3523 size_type __rlen = _VSTD::min(__n1, __sz - __pos1); 3524 int __r = traits_type::compare(data() + __pos1, __s, _VSTD::min(__rlen, __n2)); 3525 if (__r == 0) 3526 { 3527 if (__rlen < __n2) 3528 __r = -1; 3529 else if (__rlen > __n2) 3530 __r = 1; 3531 } 3532 return __r; 3533} 3534 3535// __invariants 3536 3537template<class _CharT, class _Traits, class _Allocator> 3538_LIBCPP_INLINE_VISIBILITY inline 3539bool 3540basic_string<_CharT, _Traits, _Allocator>::__invariants() const 3541{ 3542 if (size() > capacity()) 3543 return false; 3544 if (capacity() < __min_cap - 1) 3545 return false; 3546 if (data() == 0) 3547 return false; 3548 if (data()[size()] != value_type(0)) 3549 return false; 3550 return true; 3551} 3552 3553// operator== 3554 3555template<class _CharT, class _Traits, class _Allocator> 3556_LIBCPP_INLINE_VISIBILITY inline 3557bool 3558operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3559 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3560{ 3561 return __lhs.size() == __rhs.size() && _Traits::compare(__lhs.data(), 3562 __rhs.data(), 3563 __lhs.size()) == 0; 3564} 3565 3566template<class _CharT, class _Traits, class _Allocator> 3567_LIBCPP_INLINE_VISIBILITY inline 3568bool 3569operator==(const _CharT* __lhs, 3570 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3571{ 3572 return __rhs.compare(__lhs) == 0; 3573} 3574 3575template<class _CharT, class _Traits, class _Allocator> 3576_LIBCPP_INLINE_VISIBILITY inline 3577bool 3578operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs, 3579 const _CharT* __rhs) _NOEXCEPT 3580{ 3581 return __lhs.compare(__rhs) == 0; 3582} 3583 3584// operator!= 3585 3586template<class _CharT, class _Traits, class _Allocator> 3587_LIBCPP_INLINE_VISIBILITY inline 3588bool 3589operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs, 3590 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3591{ 3592 return !(__lhs == __rhs); 3593} 3594 3595template<class _CharT, class _Traits, class _Allocator> 3596_LIBCPP_INLINE_VISIBILITY inline 3597bool 3598operator!=(const _CharT* __lhs, 3599 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3600{ 3601 return !(__lhs == __rhs); 3602} 3603 3604template<class _CharT, class _Traits, class _Allocator> 3605_LIBCPP_INLINE_VISIBILITY inline 3606bool 3607operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3608 const _CharT* __rhs) _NOEXCEPT 3609{ 3610 return !(__lhs == __rhs); 3611} 3612 3613// operator< 3614 3615template<class _CharT, class _Traits, class _Allocator> 3616_LIBCPP_INLINE_VISIBILITY inline 3617bool 3618operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3619 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3620{ 3621 return __lhs.compare(__rhs) < 0; 3622} 3623 3624template<class _CharT, class _Traits, class _Allocator> 3625_LIBCPP_INLINE_VISIBILITY inline 3626bool 3627operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3628 const _CharT* __rhs) _NOEXCEPT 3629{ 3630 return __lhs.compare(__rhs) < 0; 3631} 3632 3633template<class _CharT, class _Traits, class _Allocator> 3634_LIBCPP_INLINE_VISIBILITY inline 3635bool 3636operator< (const _CharT* __lhs, 3637 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3638{ 3639 return __rhs.compare(__lhs) > 0; 3640} 3641 3642// operator> 3643 3644template<class _CharT, class _Traits, class _Allocator> 3645_LIBCPP_INLINE_VISIBILITY inline 3646bool 3647operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3648 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3649{ 3650 return __rhs < __lhs; 3651} 3652 3653template<class _CharT, class _Traits, class _Allocator> 3654_LIBCPP_INLINE_VISIBILITY inline 3655bool 3656operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3657 const _CharT* __rhs) _NOEXCEPT 3658{ 3659 return __rhs < __lhs; 3660} 3661 3662template<class _CharT, class _Traits, class _Allocator> 3663_LIBCPP_INLINE_VISIBILITY inline 3664bool 3665operator> (const _CharT* __lhs, 3666 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3667{ 3668 return __rhs < __lhs; 3669} 3670 3671// operator<= 3672 3673template<class _CharT, class _Traits, class _Allocator> 3674_LIBCPP_INLINE_VISIBILITY inline 3675bool 3676operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3677 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3678{ 3679 return !(__rhs < __lhs); 3680} 3681 3682template<class _CharT, class _Traits, class _Allocator> 3683_LIBCPP_INLINE_VISIBILITY inline 3684bool 3685operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3686 const _CharT* __rhs) _NOEXCEPT 3687{ 3688 return !(__rhs < __lhs); 3689} 3690 3691template<class _CharT, class _Traits, class _Allocator> 3692_LIBCPP_INLINE_VISIBILITY inline 3693bool 3694operator<=(const _CharT* __lhs, 3695 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3696{ 3697 return !(__rhs < __lhs); 3698} 3699 3700// operator>= 3701 3702template<class _CharT, class _Traits, class _Allocator> 3703_LIBCPP_INLINE_VISIBILITY inline 3704bool 3705operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3706 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3707{ 3708 return !(__lhs < __rhs); 3709} 3710 3711template<class _CharT, class _Traits, class _Allocator> 3712_LIBCPP_INLINE_VISIBILITY inline 3713bool 3714operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3715 const _CharT* __rhs) _NOEXCEPT 3716{ 3717 return !(__lhs < __rhs); 3718} 3719 3720template<class _CharT, class _Traits, class _Allocator> 3721_LIBCPP_INLINE_VISIBILITY inline 3722bool 3723operator>=(const _CharT* __lhs, 3724 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3725{ 3726 return !(__lhs < __rhs); 3727} 3728 3729// operator + 3730 3731template<class _CharT, class _Traits, class _Allocator> 3732basic_string<_CharT, _Traits, _Allocator> 3733operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3734 const basic_string<_CharT, _Traits, _Allocator>& __rhs) 3735{ 3736 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 3737 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 3738 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3739 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz); 3740 __r.append(__rhs.data(), __rhs_sz); 3741 return __r; 3742} 3743 3744template<class _CharT, class _Traits, class _Allocator> 3745basic_string<_CharT, _Traits, _Allocator> 3746operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs) 3747{ 3748 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator()); 3749 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = _Traits::length(__lhs); 3750 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3751 __r.__init(__lhs, __lhs_sz, __lhs_sz + __rhs_sz); 3752 __r.append(__rhs.data(), __rhs_sz); 3753 return __r; 3754} 3755 3756template<class _CharT, class _Traits, class _Allocator> 3757basic_string<_CharT, _Traits, _Allocator> 3758operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs) 3759{ 3760 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator()); 3761 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3762 __r.__init(&__lhs, 1, 1 + __rhs_sz); 3763 __r.append(__rhs.data(), __rhs_sz); 3764 return __r; 3765} 3766 3767template<class _CharT, class _Traits, class _Allocator> 3768basic_string<_CharT, _Traits, _Allocator> 3769operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs) 3770{ 3771 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 3772 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 3773 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = _Traits::length(__rhs); 3774 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz); 3775 __r.append(__rhs, __rhs_sz); 3776 return __r; 3777} 3778 3779template<class _CharT, class _Traits, class _Allocator> 3780basic_string<_CharT, _Traits, _Allocator> 3781operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs) 3782{ 3783 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 3784 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 3785 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + 1); 3786 __r.push_back(__rhs); 3787 return __r; 3788} 3789 3790#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 3791 3792template<class _CharT, class _Traits, class _Allocator> 3793_LIBCPP_INLINE_VISIBILITY inline 3794basic_string<_CharT, _Traits, _Allocator> 3795operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs) 3796{ 3797 return _VSTD::move(__lhs.append(__rhs)); 3798} 3799 3800template<class _CharT, class _Traits, class _Allocator> 3801_LIBCPP_INLINE_VISIBILITY inline 3802basic_string<_CharT, _Traits, _Allocator> 3803operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs) 3804{ 3805 return _VSTD::move(__rhs.insert(0, __lhs)); 3806} 3807 3808template<class _CharT, class _Traits, class _Allocator> 3809_LIBCPP_INLINE_VISIBILITY inline 3810basic_string<_CharT, _Traits, _Allocator> 3811operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs) 3812{ 3813 return _VSTD::move(__lhs.append(__rhs)); 3814} 3815 3816template<class _CharT, class _Traits, class _Allocator> 3817_LIBCPP_INLINE_VISIBILITY inline 3818basic_string<_CharT, _Traits, _Allocator> 3819operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs) 3820{ 3821 return _VSTD::move(__rhs.insert(0, __lhs)); 3822} 3823 3824template<class _CharT, class _Traits, class _Allocator> 3825_LIBCPP_INLINE_VISIBILITY inline 3826basic_string<_CharT, _Traits, _Allocator> 3827operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs) 3828{ 3829 __rhs.insert(__rhs.begin(), __lhs); 3830 return _VSTD::move(__rhs); 3831} 3832 3833template<class _CharT, class _Traits, class _Allocator> 3834_LIBCPP_INLINE_VISIBILITY inline 3835basic_string<_CharT, _Traits, _Allocator> 3836operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const _CharT* __rhs) 3837{ 3838 return _VSTD::move(__lhs.append(__rhs)); 3839} 3840 3841template<class _CharT, class _Traits, class _Allocator> 3842_LIBCPP_INLINE_VISIBILITY inline 3843basic_string<_CharT, _Traits, _Allocator> 3844operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs) 3845{ 3846 __lhs.push_back(__rhs); 3847 return _VSTD::move(__lhs); 3848} 3849 3850#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 3851 3852// swap 3853 3854template<class _CharT, class _Traits, class _Allocator> 3855_LIBCPP_INLINE_VISIBILITY inline 3856void 3857swap(basic_string<_CharT, _Traits, _Allocator>& __lhs, 3858 basic_string<_CharT, _Traits, _Allocator>& __rhs) 3859 _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs))) 3860{ 3861 __lhs.swap(__rhs); 3862} 3863 3864#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 3865 3866typedef basic_string<char16_t> u16string; 3867typedef basic_string<char32_t> u32string; 3868 3869#endif // _LIBCPP_HAS_NO_UNICODE_CHARS 3870 3871int stoi (const string& __str, size_t* __idx = 0, int __base = 10); 3872long stol (const string& __str, size_t* __idx = 0, int __base = 10); 3873unsigned long stoul (const string& __str, size_t* __idx = 0, int __base = 10); 3874long long stoll (const string& __str, size_t* __idx = 0, int __base = 10); 3875unsigned long long stoull(const string& __str, size_t* __idx = 0, int __base = 10); 3876 3877float stof (const string& __str, size_t* __idx = 0); 3878double stod (const string& __str, size_t* __idx = 0); 3879long double stold(const string& __str, size_t* __idx = 0); 3880 3881string to_string(int __val); 3882string to_string(unsigned __val); 3883string to_string(long __val); 3884string to_string(unsigned long __val); 3885string to_string(long long __val); 3886string to_string(unsigned long long __val); 3887string to_string(float __val); 3888string to_string(double __val); 3889string to_string(long double __val); 3890 3891int stoi (const wstring& __str, size_t* __idx = 0, int __base = 10); 3892long stol (const wstring& __str, size_t* __idx = 0, int __base = 10); 3893unsigned long stoul (const wstring& __str, size_t* __idx = 0, int __base = 10); 3894long long stoll (const wstring& __str, size_t* __idx = 0, int __base = 10); 3895unsigned long long stoull(const wstring& __str, size_t* __idx = 0, int __base = 10); 3896 3897float stof (const wstring& __str, size_t* __idx = 0); 3898double stod (const wstring& __str, size_t* __idx = 0); 3899long double stold(const wstring& __str, size_t* __idx = 0); 3900 3901wstring to_wstring(int __val); 3902wstring to_wstring(unsigned __val); 3903wstring to_wstring(long __val); 3904wstring to_wstring(unsigned long __val); 3905wstring to_wstring(long long __val); 3906wstring to_wstring(unsigned long long __val); 3907wstring to_wstring(float __val); 3908wstring to_wstring(double __val); 3909wstring to_wstring(long double __val); 3910 3911template<class _CharT, class _Traits, class _Allocator> 3912 const typename basic_string<_CharT, _Traits, _Allocator>::size_type 3913 basic_string<_CharT, _Traits, _Allocator>::npos; 3914 3915template<class _Ptr> 3916size_t _LIBCPP_INLINE_VISIBILITY __do_string_hash(_Ptr __p, _Ptr __e) 3917{ 3918 typedef typename iterator_traits<_Ptr>::value_type value_type; 3919 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type)); 3920} 3921 3922template<class _CharT, class _Traits, class _Allocator> 3923struct _LIBCPP_VISIBLE hash<basic_string<_CharT, _Traits, _Allocator> > 3924 : public unary_function<basic_string<_CharT, _Traits, _Allocator>, size_t> 3925{ 3926 size_t 3927 operator()(const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT; 3928}; 3929 3930template<class _CharT, class _Traits, class _Allocator> 3931size_t 3932hash<basic_string<_CharT, _Traits, _Allocator> >::operator()( 3933 const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT 3934{ 3935 return __do_string_hash(__val.data(), __val.data() + __val.size()); 3936} 3937 3938template<class _CharT, class _Traits, class _Allocator> 3939basic_ostream<_CharT, _Traits>& 3940operator<<(basic_ostream<_CharT, _Traits>& __os, 3941 const basic_string<_CharT, _Traits, _Allocator>& __str); 3942 3943template<class _CharT, class _Traits, class _Allocator> 3944basic_istream<_CharT, _Traits>& 3945operator>>(basic_istream<_CharT, _Traits>& __is, 3946 basic_string<_CharT, _Traits, _Allocator>& __str); 3947 3948template<class _CharT, class _Traits, class _Allocator> 3949basic_istream<_CharT, _Traits>& 3950getline(basic_istream<_CharT, _Traits>& __is, 3951 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm); 3952 3953template<class _CharT, class _Traits, class _Allocator> 3954inline _LIBCPP_INLINE_VISIBILITY 3955basic_istream<_CharT, _Traits>& 3956getline(basic_istream<_CharT, _Traits>& __is, 3957 basic_string<_CharT, _Traits, _Allocator>& __str); 3958 3959#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 3960 3961template<class _CharT, class _Traits, class _Allocator> 3962inline _LIBCPP_INLINE_VISIBILITY 3963basic_istream<_CharT, _Traits>& 3964getline(basic_istream<_CharT, _Traits>&& __is, 3965 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm); 3966 3967template<class _CharT, class _Traits, class _Allocator> 3968inline _LIBCPP_INLINE_VISIBILITY 3969basic_istream<_CharT, _Traits>& 3970getline(basic_istream<_CharT, _Traits>&& __is, 3971 basic_string<_CharT, _Traits, _Allocator>& __str); 3972 3973#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 3974 3975extern template class basic_string<char>; 3976extern template class basic_string<wchar_t>; 3977 3978extern template 3979 string 3980 operator+<char, char_traits<char>, allocator<char> >(char const*, string const&); 3981 3982_LIBCPP_END_NAMESPACE_STD 3983 3984#endif // _LIBCPP_STRING 3985