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