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