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 is_nothrow_move_assignable<allocator_type>::value); 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(0xDFFF);} 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_(__alloc_traits::propagate_on_container_move_assignment::value && 1381 is_nothrow_move_assignable<allocator_type>::value); 1382#endif 1383 _LIBCPP_INLINE_VISIBILITY basic_string& operator=(const value_type* __s) {return assign(__s);} 1384 basic_string& operator=(value_type __c); 1385#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1386 _LIBCPP_INLINE_VISIBILITY 1387 basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());} 1388#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1389 1390#if _LIBCPP_DEBUG_LEVEL >= 2 1391 _LIBCPP_INLINE_VISIBILITY 1392 iterator begin() _NOEXCEPT 1393 {return iterator(this, __get_pointer());} 1394 _LIBCPP_INLINE_VISIBILITY 1395 const_iterator begin() const _NOEXCEPT 1396 {return const_iterator(this, __get_pointer());} 1397 _LIBCPP_INLINE_VISIBILITY 1398 iterator end() _NOEXCEPT 1399 {return iterator(this, __get_pointer() + size());} 1400 _LIBCPP_INLINE_VISIBILITY 1401 const_iterator end() const _NOEXCEPT 1402 {return const_iterator(this, __get_pointer() + size());} 1403#else 1404 _LIBCPP_INLINE_VISIBILITY 1405 iterator begin() _NOEXCEPT 1406 {return iterator(__get_pointer());} 1407 _LIBCPP_INLINE_VISIBILITY 1408 const_iterator begin() const _NOEXCEPT 1409 {return const_iterator(__get_pointer());} 1410 _LIBCPP_INLINE_VISIBILITY 1411 iterator end() _NOEXCEPT 1412 {return iterator(__get_pointer() + size());} 1413 _LIBCPP_INLINE_VISIBILITY 1414 const_iterator end() const _NOEXCEPT 1415 {return const_iterator(__get_pointer() + size());} 1416#endif // _LIBCPP_DEBUG_LEVEL >= 2 1417 _LIBCPP_INLINE_VISIBILITY 1418 reverse_iterator rbegin() _NOEXCEPT 1419 {return reverse_iterator(end());} 1420 _LIBCPP_INLINE_VISIBILITY 1421 const_reverse_iterator rbegin() const _NOEXCEPT 1422 {return const_reverse_iterator(end());} 1423 _LIBCPP_INLINE_VISIBILITY 1424 reverse_iterator rend() _NOEXCEPT 1425 {return reverse_iterator(begin());} 1426 _LIBCPP_INLINE_VISIBILITY 1427 const_reverse_iterator rend() const _NOEXCEPT 1428 {return const_reverse_iterator(begin());} 1429 1430 _LIBCPP_INLINE_VISIBILITY 1431 const_iterator cbegin() const _NOEXCEPT 1432 {return begin();} 1433 _LIBCPP_INLINE_VISIBILITY 1434 const_iterator cend() const _NOEXCEPT 1435 {return end();} 1436 _LIBCPP_INLINE_VISIBILITY 1437 const_reverse_iterator crbegin() const _NOEXCEPT 1438 {return rbegin();} 1439 _LIBCPP_INLINE_VISIBILITY 1440 const_reverse_iterator crend() const _NOEXCEPT 1441 {return rend();} 1442 1443 _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT 1444 {return __is_long() ? __get_long_size() : __get_short_size();} 1445 _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();} 1446 _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT; 1447 _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT 1448 {return (__is_long() ? __get_long_cap() 1449 : static_cast<size_type>(__min_cap)) - 1;} 1450 1451 void resize(size_type __n, value_type __c); 1452 _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());} 1453 1454 void reserve(size_type res_arg = 0); 1455 _LIBCPP_INLINE_VISIBILITY 1456 void shrink_to_fit() _NOEXCEPT {reserve();} 1457 _LIBCPP_INLINE_VISIBILITY 1458 void clear() _NOEXCEPT; 1459 _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return size() == 0;} 1460 1461 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const; 1462 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __pos); 1463 1464 const_reference at(size_type __n) const; 1465 reference at(size_type __n); 1466 1467 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const basic_string& __str) {return append(__str);} 1468 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const value_type* __s) {return append(__s);} 1469 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(value_type __c) {push_back(__c); return *this;} 1470#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1471 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(initializer_list<value_type> __il) {return append(__il);} 1472#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1473 1474 _LIBCPP_INLINE_VISIBILITY 1475 basic_string& append(const basic_string& __str); 1476 basic_string& append(const basic_string& __str, size_type __pos, size_type __n=npos); 1477 basic_string& append(const value_type* __s, size_type __n); 1478 basic_string& append(const value_type* __s); 1479 basic_string& append(size_type __n, value_type __c); 1480 template<class _InputIterator> 1481 typename enable_if 1482 < 1483 __is_input_iterator <_InputIterator>::value && 1484 !__is_forward_iterator<_InputIterator>::value, 1485 basic_string& 1486 >::type 1487 append(_InputIterator __first, _InputIterator __last); 1488 template<class _ForwardIterator> 1489 typename enable_if 1490 < 1491 __is_forward_iterator<_ForwardIterator>::value, 1492 basic_string& 1493 >::type 1494 append(_ForwardIterator __first, _ForwardIterator __last); 1495#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1496 _LIBCPP_INLINE_VISIBILITY 1497 basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());} 1498#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1499 1500 void push_back(value_type __c); 1501 _LIBCPP_INLINE_VISIBILITY 1502 void pop_back(); 1503 _LIBCPP_INLINE_VISIBILITY reference front(); 1504 _LIBCPP_INLINE_VISIBILITY const_reference front() const; 1505 _LIBCPP_INLINE_VISIBILITY reference back(); 1506 _LIBCPP_INLINE_VISIBILITY const_reference back() const; 1507 1508 _LIBCPP_INLINE_VISIBILITY 1509 basic_string& assign(const basic_string& __str); 1510#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1511 _LIBCPP_INLINE_VISIBILITY 1512 basic_string& assign(basic_string&& str) 1513 {*this = _VSTD::move(str); return *this;} 1514#endif 1515 basic_string& assign(const basic_string& __str, size_type __pos, size_type __n=npos); 1516 basic_string& assign(const value_type* __s, size_type __n); 1517 basic_string& assign(const value_type* __s); 1518 basic_string& assign(size_type __n, value_type __c); 1519 template<class _InputIterator> 1520 typename enable_if 1521 < 1522 __is_input_iterator <_InputIterator>::value && 1523 !__is_forward_iterator<_InputIterator>::value, 1524 basic_string& 1525 >::type 1526 assign(_InputIterator __first, _InputIterator __last); 1527 template<class _ForwardIterator> 1528 typename enable_if 1529 < 1530 __is_forward_iterator<_ForwardIterator>::value, 1531 basic_string& 1532 >::type 1533 assign(_ForwardIterator __first, _ForwardIterator __last); 1534#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1535 _LIBCPP_INLINE_VISIBILITY 1536 basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());} 1537#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1538 1539 _LIBCPP_INLINE_VISIBILITY 1540 basic_string& insert(size_type __pos1, const basic_string& __str); 1541 basic_string& insert(size_type __pos1, const basic_string& __str, size_type __pos2, size_type __n=npos); 1542 basic_string& insert(size_type __pos, const value_type* __s, size_type __n); 1543 basic_string& insert(size_type __pos, const value_type* __s); 1544 basic_string& insert(size_type __pos, size_type __n, value_type __c); 1545 iterator insert(const_iterator __pos, value_type __c); 1546 _LIBCPP_INLINE_VISIBILITY 1547 iterator insert(const_iterator __pos, size_type __n, value_type __c); 1548 template<class _InputIterator> 1549 typename enable_if 1550 < 1551 __is_input_iterator <_InputIterator>::value && 1552 !__is_forward_iterator<_InputIterator>::value, 1553 iterator 1554 >::type 1555 insert(const_iterator __pos, _InputIterator __first, _InputIterator __last); 1556 template<class _ForwardIterator> 1557 typename enable_if 1558 < 1559 __is_forward_iterator<_ForwardIterator>::value, 1560 iterator 1561 >::type 1562 insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last); 1563#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1564 _LIBCPP_INLINE_VISIBILITY 1565 iterator insert(const_iterator __pos, initializer_list<value_type> __il) 1566 {return insert(__pos, __il.begin(), __il.end());} 1567#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1568 1569 basic_string& erase(size_type __pos = 0, size_type __n = npos); 1570 _LIBCPP_INLINE_VISIBILITY 1571 iterator erase(const_iterator __pos); 1572 _LIBCPP_INLINE_VISIBILITY 1573 iterator erase(const_iterator __first, const_iterator __last); 1574 1575 _LIBCPP_INLINE_VISIBILITY 1576 basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str); 1577 basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos); 1578 basic_string& replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2); 1579 basic_string& replace(size_type __pos, size_type __n1, const value_type* __s); 1580 basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c); 1581 _LIBCPP_INLINE_VISIBILITY 1582 basic_string& replace(const_iterator __i1, const_iterator __i2, const basic_string& __str); 1583 _LIBCPP_INLINE_VISIBILITY 1584 basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n); 1585 _LIBCPP_INLINE_VISIBILITY 1586 basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s); 1587 _LIBCPP_INLINE_VISIBILITY 1588 basic_string& replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c); 1589 template<class _InputIterator> 1590 typename enable_if 1591 < 1592 __is_input_iterator<_InputIterator>::value, 1593 basic_string& 1594 >::type 1595 replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2); 1596#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1597 _LIBCPP_INLINE_VISIBILITY 1598 basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list<value_type> __il) 1599 {return replace(__i1, __i2, __il.begin(), __il.end());} 1600#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1601 1602 size_type copy(value_type* __s, size_type __n, size_type __pos = 0) const; 1603 _LIBCPP_INLINE_VISIBILITY 1604 basic_string substr(size_type __pos = 0, size_type __n = npos) const; 1605 1606 _LIBCPP_INLINE_VISIBILITY 1607 void swap(basic_string& __str) 1608#if _LIBCPP_STD_VER >= 14 1609 _NOEXCEPT; 1610#else 1611 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1612 __is_nothrow_swappable<allocator_type>::value); 1613#endif 1614 1615 _LIBCPP_INLINE_VISIBILITY 1616 const value_type* c_str() const _NOEXCEPT {return data();} 1617 _LIBCPP_INLINE_VISIBILITY 1618 const value_type* data() const _NOEXCEPT {return _VSTD::__to_raw_pointer(__get_pointer());} 1619 1620 _LIBCPP_INLINE_VISIBILITY 1621 allocator_type get_allocator() const _NOEXCEPT {return __alloc();} 1622 1623 _LIBCPP_INLINE_VISIBILITY 1624 size_type find(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT; 1625 size_type find(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1626 _LIBCPP_INLINE_VISIBILITY 1627 size_type find(const value_type* __s, size_type __pos = 0) const _NOEXCEPT; 1628 size_type find(value_type __c, size_type __pos = 0) const _NOEXCEPT; 1629 1630 _LIBCPP_INLINE_VISIBILITY 1631 size_type rfind(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT; 1632 size_type rfind(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1633 _LIBCPP_INLINE_VISIBILITY 1634 size_type rfind(const value_type* __s, size_type __pos = npos) const _NOEXCEPT; 1635 size_type rfind(value_type __c, size_type __pos = npos) const _NOEXCEPT; 1636 1637 _LIBCPP_INLINE_VISIBILITY 1638 size_type find_first_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT; 1639 size_type find_first_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1640 _LIBCPP_INLINE_VISIBILITY 1641 size_type find_first_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT; 1642 _LIBCPP_INLINE_VISIBILITY 1643 size_type find_first_of(value_type __c, size_type __pos = 0) const _NOEXCEPT; 1644 1645 _LIBCPP_INLINE_VISIBILITY 1646 size_type find_last_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT; 1647 size_type find_last_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1648 _LIBCPP_INLINE_VISIBILITY 1649 size_type find_last_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT; 1650 _LIBCPP_INLINE_VISIBILITY 1651 size_type find_last_of(value_type __c, size_type __pos = npos) const _NOEXCEPT; 1652 1653 _LIBCPP_INLINE_VISIBILITY 1654 size_type find_first_not_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT; 1655 size_type find_first_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1656 _LIBCPP_INLINE_VISIBILITY 1657 size_type find_first_not_of(const value_type* __s, size_type __pos = 0) const _NOEXCEPT; 1658 _LIBCPP_INLINE_VISIBILITY 1659 size_type find_first_not_of(value_type __c, size_type __pos = 0) const _NOEXCEPT; 1660 1661 _LIBCPP_INLINE_VISIBILITY 1662 size_type find_last_not_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT; 1663 size_type find_last_not_of(const value_type* __s, size_type __pos, size_type __n) const _NOEXCEPT; 1664 _LIBCPP_INLINE_VISIBILITY 1665 size_type find_last_not_of(const value_type* __s, size_type __pos = npos) const _NOEXCEPT; 1666 _LIBCPP_INLINE_VISIBILITY 1667 size_type find_last_not_of(value_type __c, size_type __pos = npos) const _NOEXCEPT; 1668 1669 _LIBCPP_INLINE_VISIBILITY 1670 int compare(const basic_string& __str) const _NOEXCEPT; 1671 _LIBCPP_INLINE_VISIBILITY 1672 int compare(size_type __pos1, size_type __n1, const basic_string& __str) const; 1673 int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2=npos) const; 1674 int compare(const value_type* __s) const _NOEXCEPT; 1675 int compare(size_type __pos1, size_type __n1, const value_type* __s) const; 1676 int compare(size_type __pos1, size_type __n1, const value_type* __s, size_type __n2) const; 1677 1678 _LIBCPP_INLINE_VISIBILITY bool __invariants() const; 1679 1680 _LIBCPP_INLINE_VISIBILITY 1681 bool __is_long() const _NOEXCEPT 1682 {return bool(__r_.first().__s.__size_ & __short_mask);} 1683 1684#if _LIBCPP_DEBUG_LEVEL >= 2 1685 1686 bool __dereferenceable(const const_iterator* __i) const; 1687 bool __decrementable(const const_iterator* __i) const; 1688 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1689 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1690 1691#endif // _LIBCPP_DEBUG_LEVEL >= 2 1692 1693private: 1694 _LIBCPP_INLINE_VISIBILITY 1695 allocator_type& __alloc() _NOEXCEPT 1696 {return __r_.second();} 1697 _LIBCPP_INLINE_VISIBILITY 1698 const allocator_type& __alloc() const _NOEXCEPT 1699 {return __r_.second();} 1700 1701#ifdef _LIBCPP_ALTERNATE_STRING_LAYOUT 1702 1703 _LIBCPP_INLINE_VISIBILITY 1704 void __set_short_size(size_type __s) _NOEXCEPT 1705# if _LIBCPP_BIG_ENDIAN 1706 {__r_.first().__s.__size_ = (unsigned char)(__s << 1);} 1707# else 1708 {__r_.first().__s.__size_ = (unsigned char)(__s);} 1709# endif 1710 1711 _LIBCPP_INLINE_VISIBILITY 1712 size_type __get_short_size() const _NOEXCEPT 1713# if _LIBCPP_BIG_ENDIAN 1714 {return __r_.first().__s.__size_ >> 1;} 1715# else 1716 {return __r_.first().__s.__size_;} 1717# endif 1718 1719#else // _LIBCPP_ALTERNATE_STRING_LAYOUT 1720 1721 _LIBCPP_INLINE_VISIBILITY 1722 void __set_short_size(size_type __s) _NOEXCEPT 1723# if _LIBCPP_BIG_ENDIAN 1724 {__r_.first().__s.__size_ = (unsigned char)(__s);} 1725# else 1726 {__r_.first().__s.__size_ = (unsigned char)(__s << 1);} 1727# endif 1728 1729 _LIBCPP_INLINE_VISIBILITY 1730 size_type __get_short_size() const _NOEXCEPT 1731# if _LIBCPP_BIG_ENDIAN 1732 {return __r_.first().__s.__size_;} 1733# else 1734 {return __r_.first().__s.__size_ >> 1;} 1735# endif 1736 1737#endif // _LIBCPP_ALTERNATE_STRING_LAYOUT 1738 1739 _LIBCPP_INLINE_VISIBILITY 1740 void __set_long_size(size_type __s) _NOEXCEPT 1741 {__r_.first().__l.__size_ = __s;} 1742 _LIBCPP_INLINE_VISIBILITY 1743 size_type __get_long_size() const _NOEXCEPT 1744 {return __r_.first().__l.__size_;} 1745 _LIBCPP_INLINE_VISIBILITY 1746 void __set_size(size_type __s) _NOEXCEPT 1747 {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);} 1748 1749 _LIBCPP_INLINE_VISIBILITY 1750 void __set_long_cap(size_type __s) _NOEXCEPT 1751 {__r_.first().__l.__cap_ = __long_mask | __s;} 1752 _LIBCPP_INLINE_VISIBILITY 1753 size_type __get_long_cap() const _NOEXCEPT 1754 {return __r_.first().__l.__cap_ & size_type(~__long_mask);} 1755 1756 _LIBCPP_INLINE_VISIBILITY 1757 void __set_long_pointer(pointer __p) _NOEXCEPT 1758 {__r_.first().__l.__data_ = __p;} 1759 _LIBCPP_INLINE_VISIBILITY 1760 pointer __get_long_pointer() _NOEXCEPT 1761 {return __r_.first().__l.__data_;} 1762 _LIBCPP_INLINE_VISIBILITY 1763 const_pointer __get_long_pointer() const _NOEXCEPT 1764 {return __r_.first().__l.__data_;} 1765 _LIBCPP_INLINE_VISIBILITY 1766 pointer __get_short_pointer() _NOEXCEPT 1767 {return pointer_traits<pointer>::pointer_to(__r_.first().__s.__data_[0]);} 1768 _LIBCPP_INLINE_VISIBILITY 1769 const_pointer __get_short_pointer() const _NOEXCEPT 1770 {return pointer_traits<const_pointer>::pointer_to(__r_.first().__s.__data_[0]);} 1771 _LIBCPP_INLINE_VISIBILITY 1772 pointer __get_pointer() _NOEXCEPT 1773 {return __is_long() ? __get_long_pointer() : __get_short_pointer();} 1774 _LIBCPP_INLINE_VISIBILITY 1775 const_pointer __get_pointer() const _NOEXCEPT 1776 {return __is_long() ? __get_long_pointer() : __get_short_pointer();} 1777 1778 _LIBCPP_INLINE_VISIBILITY 1779 void __zero() _NOEXCEPT 1780 { 1781 size_type (&__a)[__n_words] = __r_.first().__r.__words; 1782 for (unsigned __i = 0; __i < __n_words; ++__i) 1783 __a[__i] = 0; 1784 } 1785 1786 template <size_type __a> static 1787 _LIBCPP_INLINE_VISIBILITY 1788 size_type __align_it(size_type __s) _NOEXCEPT 1789 {return (__s + (__a-1)) & ~(__a-1);} 1790 enum {__alignment = 16}; 1791 static _LIBCPP_INLINE_VISIBILITY 1792 size_type __recommend(size_type __s) _NOEXCEPT 1793 {return (__s < __min_cap ? static_cast<size_type>(__min_cap) : 1794 __align_it<sizeof(value_type) < __alignment ? 1795 __alignment/sizeof(value_type) : 1 > (__s+1)) - 1;} 1796 1797 void __init(const value_type* __s, size_type __sz, size_type __reserve); 1798 void __init(const value_type* __s, size_type __sz); 1799 void __init(size_type __n, value_type __c); 1800 1801 template <class _InputIterator> 1802 typename enable_if 1803 < 1804 __is_input_iterator <_InputIterator>::value && 1805 !__is_forward_iterator<_InputIterator>::value, 1806 void 1807 >::type 1808 __init(_InputIterator __first, _InputIterator __last); 1809 1810 template <class _ForwardIterator> 1811 typename enable_if 1812 < 1813 __is_forward_iterator<_ForwardIterator>::value, 1814 void 1815 >::type 1816 __init(_ForwardIterator __first, _ForwardIterator __last); 1817 1818 void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz, 1819 size_type __n_copy, size_type __n_del, size_type __n_add = 0); 1820 void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz, 1821 size_type __n_copy, size_type __n_del, 1822 size_type __n_add, const value_type* __p_new_stuff); 1823 1824 _LIBCPP_INLINE_VISIBILITY 1825 void __erase_to_end(size_type __pos); 1826 1827 _LIBCPP_INLINE_VISIBILITY 1828 void __copy_assign_alloc(const basic_string& __str) 1829 {__copy_assign_alloc(__str, integral_constant<bool, 1830 __alloc_traits::propagate_on_container_copy_assignment::value>());} 1831 1832 _LIBCPP_INLINE_VISIBILITY 1833 void __copy_assign_alloc(const basic_string& __str, true_type) 1834 { 1835 if (__alloc() != __str.__alloc()) 1836 { 1837 clear(); 1838 shrink_to_fit(); 1839 } 1840 __alloc() = __str.__alloc(); 1841 } 1842 1843 _LIBCPP_INLINE_VISIBILITY 1844 void __copy_assign_alloc(const basic_string&, false_type) _NOEXCEPT 1845 {} 1846 1847#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1848 _LIBCPP_INLINE_VISIBILITY 1849 void __move_assign(basic_string& __str, false_type); 1850 _LIBCPP_INLINE_VISIBILITY 1851 void __move_assign(basic_string& __str, true_type) 1852 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 1853#endif 1854 1855 _LIBCPP_INLINE_VISIBILITY 1856 void 1857 __move_assign_alloc(basic_string& __str) 1858 _NOEXCEPT_( 1859 !__alloc_traits::propagate_on_container_move_assignment::value || 1860 is_nothrow_move_assignable<allocator_type>::value) 1861 {__move_assign_alloc(__str, integral_constant<bool, 1862 __alloc_traits::propagate_on_container_move_assignment::value>());} 1863 1864 _LIBCPP_INLINE_VISIBILITY 1865 void __move_assign_alloc(basic_string& __c, true_type) 1866 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1867 { 1868 __alloc() = _VSTD::move(__c.__alloc()); 1869 } 1870 1871 _LIBCPP_INLINE_VISIBILITY 1872 void __move_assign_alloc(basic_string&, false_type) 1873 _NOEXCEPT 1874 {} 1875 1876 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 1877 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type); 1878 1879 friend basic_string operator+<>(const basic_string&, const basic_string&); 1880 friend basic_string operator+<>(const value_type*, const basic_string&); 1881 friend basic_string operator+<>(value_type, const basic_string&); 1882 friend basic_string operator+<>(const basic_string&, const value_type*); 1883 friend basic_string operator+<>(const basic_string&, value_type); 1884}; 1885 1886template <class _CharT, class _Traits, class _Allocator> 1887inline _LIBCPP_INLINE_VISIBILITY 1888void 1889basic_string<_CharT, _Traits, _Allocator>::__invalidate_all_iterators() 1890{ 1891#if _LIBCPP_DEBUG_LEVEL >= 2 1892 __get_db()->__invalidate_all(this); 1893#endif // _LIBCPP_DEBUG_LEVEL >= 2 1894} 1895 1896template <class _CharT, class _Traits, class _Allocator> 1897inline _LIBCPP_INLINE_VISIBILITY 1898void 1899basic_string<_CharT, _Traits, _Allocator>::__invalidate_iterators_past(size_type 1900#if _LIBCPP_DEBUG_LEVEL >= 2 1901 __pos 1902#endif 1903 ) 1904{ 1905#if _LIBCPP_DEBUG_LEVEL >= 2 1906 __c_node* __c = __get_db()->__find_c_and_lock(this); 1907 if (__c) 1908 { 1909 const_pointer __new_last = __get_pointer() + __pos; 1910 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1911 { 1912 --__p; 1913 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 1914 if (__i->base() > __new_last) 1915 { 1916 (*__p)->__c_ = nullptr; 1917 if (--__c->end_ != __p) 1918 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1919 } 1920 } 1921 __get_db()->unlock(); 1922 } 1923#endif // _LIBCPP_DEBUG_LEVEL >= 2 1924} 1925 1926template <class _CharT, class _Traits, class _Allocator> 1927inline _LIBCPP_INLINE_VISIBILITY 1928basic_string<_CharT, _Traits, _Allocator>::basic_string() 1929 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1930{ 1931#if _LIBCPP_DEBUG_LEVEL >= 2 1932 __get_db()->__insert_c(this); 1933#endif 1934 __zero(); 1935} 1936 1937template <class _CharT, class _Traits, class _Allocator> 1938inline _LIBCPP_INLINE_VISIBILITY 1939basic_string<_CharT, _Traits, _Allocator>::basic_string(const allocator_type& __a) 1940#if _LIBCPP_STD_VER <= 14 1941 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 1942#else 1943 _NOEXCEPT 1944#endif 1945: __r_(__a) 1946{ 1947#if _LIBCPP_DEBUG_LEVEL >= 2 1948 __get_db()->__insert_c(this); 1949#endif 1950 __zero(); 1951} 1952 1953template <class _CharT, class _Traits, class _Allocator> 1954void 1955basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz, size_type __reserve) 1956{ 1957 if (__reserve > max_size()) 1958 this->__throw_length_error(); 1959 pointer __p; 1960 if (__reserve < __min_cap) 1961 { 1962 __set_short_size(__sz); 1963 __p = __get_short_pointer(); 1964 } 1965 else 1966 { 1967 size_type __cap = __recommend(__reserve); 1968 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1969 __set_long_pointer(__p); 1970 __set_long_cap(__cap+1); 1971 __set_long_size(__sz); 1972 } 1973 traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz); 1974 traits_type::assign(__p[__sz], value_type()); 1975} 1976 1977template <class _CharT, class _Traits, class _Allocator> 1978void 1979basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz) 1980{ 1981 if (__sz > max_size()) 1982 this->__throw_length_error(); 1983 pointer __p; 1984 if (__sz < __min_cap) 1985 { 1986 __set_short_size(__sz); 1987 __p = __get_short_pointer(); 1988 } 1989 else 1990 { 1991 size_type __cap = __recommend(__sz); 1992 __p = __alloc_traits::allocate(__alloc(), __cap+1); 1993 __set_long_pointer(__p); 1994 __set_long_cap(__cap+1); 1995 __set_long_size(__sz); 1996 } 1997 traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz); 1998 traits_type::assign(__p[__sz], value_type()); 1999} 2000 2001template <class _CharT, class _Traits, class _Allocator> 2002inline _LIBCPP_INLINE_VISIBILITY 2003basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s) 2004{ 2005 _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*) detected nullptr"); 2006 __init(__s, traits_type::length(__s)); 2007#if _LIBCPP_DEBUG_LEVEL >= 2 2008 __get_db()->__insert_c(this); 2009#endif 2010} 2011 2012template <class _CharT, class _Traits, class _Allocator> 2013inline _LIBCPP_INLINE_VISIBILITY 2014basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, const allocator_type& __a) 2015 : __r_(__a) 2016{ 2017 _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*, allocator) detected nullptr"); 2018 __init(__s, traits_type::length(__s)); 2019#if _LIBCPP_DEBUG_LEVEL >= 2 2020 __get_db()->__insert_c(this); 2021#endif 2022} 2023 2024template <class _CharT, class _Traits, class _Allocator> 2025inline _LIBCPP_INLINE_VISIBILITY 2026basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n) 2027{ 2028 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n) detected nullptr"); 2029 __init(__s, __n); 2030#if _LIBCPP_DEBUG_LEVEL >= 2 2031 __get_db()->__insert_c(this); 2032#endif 2033} 2034 2035template <class _CharT, class _Traits, class _Allocator> 2036inline _LIBCPP_INLINE_VISIBILITY 2037basic_string<_CharT, _Traits, _Allocator>::basic_string(const value_type* __s, size_type __n, const allocator_type& __a) 2038 : __r_(__a) 2039{ 2040 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "basic_string(const char*, n, allocator) detected nullptr"); 2041 __init(__s, __n); 2042#if _LIBCPP_DEBUG_LEVEL >= 2 2043 __get_db()->__insert_c(this); 2044#endif 2045} 2046 2047template <class _CharT, class _Traits, class _Allocator> 2048basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str) 2049 : __r_(__alloc_traits::select_on_container_copy_construction(__str.__alloc())) 2050{ 2051 if (!__str.__is_long()) 2052 __r_.first().__r = __str.__r_.first().__r; 2053 else 2054 __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size()); 2055#if _LIBCPP_DEBUG_LEVEL >= 2 2056 __get_db()->__insert_c(this); 2057#endif 2058} 2059 2060template <class _CharT, class _Traits, class _Allocator> 2061basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, const allocator_type& __a) 2062 : __r_(__a) 2063{ 2064 if (!__str.__is_long()) 2065 __r_.first().__r = __str.__r_.first().__r; 2066 else 2067 __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size()); 2068#if _LIBCPP_DEBUG_LEVEL >= 2 2069 __get_db()->__insert_c(this); 2070#endif 2071} 2072 2073#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2074 2075template <class _CharT, class _Traits, class _Allocator> 2076inline _LIBCPP_INLINE_VISIBILITY 2077basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str) 2078#if _LIBCPP_STD_VER <= 14 2079 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2080#else 2081 _NOEXCEPT 2082#endif 2083 : __r_(_VSTD::move(__str.__r_)) 2084{ 2085 __str.__zero(); 2086#if _LIBCPP_DEBUG_LEVEL >= 2 2087 __get_db()->__insert_c(this); 2088 if (__is_long()) 2089 __get_db()->swap(this, &__str); 2090#endif 2091} 2092 2093template <class _CharT, class _Traits, class _Allocator> 2094inline _LIBCPP_INLINE_VISIBILITY 2095basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str, const allocator_type& __a) 2096 : __r_(__a) 2097{ 2098 if (__str.__is_long() && __a != __str.__alloc()) // copy, not move 2099 __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size()); 2100 else 2101 { 2102 __r_.first().__r = __str.__r_.first().__r; 2103 __str.__zero(); 2104 } 2105#if _LIBCPP_DEBUG_LEVEL >= 2 2106 __get_db()->__insert_c(this); 2107 if (__is_long()) 2108 __get_db()->swap(this, &__str); 2109#endif 2110} 2111 2112#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2113 2114template <class _CharT, class _Traits, class _Allocator> 2115void 2116basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c) 2117{ 2118 if (__n > max_size()) 2119 this->__throw_length_error(); 2120 pointer __p; 2121 if (__n < __min_cap) 2122 { 2123 __set_short_size(__n); 2124 __p = __get_short_pointer(); 2125 } 2126 else 2127 { 2128 size_type __cap = __recommend(__n); 2129 __p = __alloc_traits::allocate(__alloc(), __cap+1); 2130 __set_long_pointer(__p); 2131 __set_long_cap(__cap+1); 2132 __set_long_size(__n); 2133 } 2134 traits_type::assign(_VSTD::__to_raw_pointer(__p), __n, __c); 2135 traits_type::assign(__p[__n], value_type()); 2136} 2137 2138template <class _CharT, class _Traits, class _Allocator> 2139inline _LIBCPP_INLINE_VISIBILITY 2140basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c) 2141{ 2142 __init(__n, __c); 2143#if _LIBCPP_DEBUG_LEVEL >= 2 2144 __get_db()->__insert_c(this); 2145#endif 2146} 2147 2148template <class _CharT, class _Traits, class _Allocator> 2149inline _LIBCPP_INLINE_VISIBILITY 2150basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c, const allocator_type& __a) 2151 : __r_(__a) 2152{ 2153 __init(__n, __c); 2154#if _LIBCPP_DEBUG_LEVEL >= 2 2155 __get_db()->__insert_c(this); 2156#endif 2157} 2158 2159template <class _CharT, class _Traits, class _Allocator> 2160basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, size_type __pos, size_type __n, 2161 const allocator_type& __a) 2162 : __r_(__a) 2163{ 2164 size_type __str_sz = __str.size(); 2165 if (__pos > __str_sz) 2166 this->__throw_out_of_range(); 2167 __init(__str.data() + __pos, _VSTD::min(__n, __str_sz - __pos)); 2168#if _LIBCPP_DEBUG_LEVEL >= 2 2169 __get_db()->__insert_c(this); 2170#endif 2171} 2172 2173template <class _CharT, class _Traits, class _Allocator> 2174template <class _InputIterator> 2175typename enable_if 2176< 2177 __is_input_iterator <_InputIterator>::value && 2178 !__is_forward_iterator<_InputIterator>::value, 2179 void 2180>::type 2181basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last) 2182{ 2183 __zero(); 2184#ifndef _LIBCPP_NO_EXCEPTIONS 2185 try 2186 { 2187#endif // _LIBCPP_NO_EXCEPTIONS 2188 for (; __first != __last; ++__first) 2189 push_back(*__first); 2190#ifndef _LIBCPP_NO_EXCEPTIONS 2191 } 2192 catch (...) 2193 { 2194 if (__is_long()) 2195 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap()); 2196 throw; 2197 } 2198#endif // _LIBCPP_NO_EXCEPTIONS 2199} 2200 2201template <class _CharT, class _Traits, class _Allocator> 2202template <class _ForwardIterator> 2203typename enable_if 2204< 2205 __is_forward_iterator<_ForwardIterator>::value, 2206 void 2207>::type 2208basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last) 2209{ 2210 size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last)); 2211 if (__sz > max_size()) 2212 this->__throw_length_error(); 2213 pointer __p; 2214 if (__sz < __min_cap) 2215 { 2216 __set_short_size(__sz); 2217 __p = __get_short_pointer(); 2218 } 2219 else 2220 { 2221 size_type __cap = __recommend(__sz); 2222 __p = __alloc_traits::allocate(__alloc(), __cap+1); 2223 __set_long_pointer(__p); 2224 __set_long_cap(__cap+1); 2225 __set_long_size(__sz); 2226 } 2227 for (; __first != __last; ++__first, (void) ++__p) 2228 traits_type::assign(*__p, *__first); 2229 traits_type::assign(*__p, value_type()); 2230} 2231 2232template <class _CharT, class _Traits, class _Allocator> 2233template<class _InputIterator> 2234inline _LIBCPP_INLINE_VISIBILITY 2235basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last) 2236{ 2237 __init(__first, __last); 2238#if _LIBCPP_DEBUG_LEVEL >= 2 2239 __get_db()->__insert_c(this); 2240#endif 2241} 2242 2243template <class _CharT, class _Traits, class _Allocator> 2244template<class _InputIterator> 2245inline _LIBCPP_INLINE_VISIBILITY 2246basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last, 2247 const allocator_type& __a) 2248 : __r_(__a) 2249{ 2250 __init(__first, __last); 2251#if _LIBCPP_DEBUG_LEVEL >= 2 2252 __get_db()->__insert_c(this); 2253#endif 2254} 2255 2256#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2257 2258template <class _CharT, class _Traits, class _Allocator> 2259inline _LIBCPP_INLINE_VISIBILITY 2260basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il) 2261{ 2262 __init(__il.begin(), __il.end()); 2263#if _LIBCPP_DEBUG_LEVEL >= 2 2264 __get_db()->__insert_c(this); 2265#endif 2266} 2267 2268template <class _CharT, class _Traits, class _Allocator> 2269inline _LIBCPP_INLINE_VISIBILITY 2270basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il, const allocator_type& __a) 2271 : __r_(__a) 2272{ 2273 __init(__il.begin(), __il.end()); 2274#if _LIBCPP_DEBUG_LEVEL >= 2 2275 __get_db()->__insert_c(this); 2276#endif 2277} 2278 2279#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2280 2281template <class _CharT, class _Traits, class _Allocator> 2282basic_string<_CharT, _Traits, _Allocator>::~basic_string() 2283{ 2284#if _LIBCPP_DEBUG_LEVEL >= 2 2285 __get_db()->__erase_c(this); 2286#endif 2287 if (__is_long()) 2288 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap()); 2289} 2290 2291template <class _CharT, class _Traits, class _Allocator> 2292void 2293basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace 2294 (size_type __old_cap, size_type __delta_cap, size_type __old_sz, 2295 size_type __n_copy, size_type __n_del, size_type __n_add, const value_type* __p_new_stuff) 2296{ 2297 size_type __ms = max_size(); 2298 if (__delta_cap > __ms - __old_cap - 1) 2299 this->__throw_length_error(); 2300 pointer __old_p = __get_pointer(); 2301 size_type __cap = __old_cap < __ms / 2 - __alignment ? 2302 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) : 2303 __ms - 1; 2304 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1); 2305 __invalidate_all_iterators(); 2306 if (__n_copy != 0) 2307 traits_type::copy(_VSTD::__to_raw_pointer(__p), 2308 _VSTD::__to_raw_pointer(__old_p), __n_copy); 2309 if (__n_add != 0) 2310 traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy, __p_new_stuff, __n_add); 2311 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy; 2312 if (__sec_cp_sz != 0) 2313 traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add, 2314 _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del, __sec_cp_sz); 2315 if (__old_cap+1 != __min_cap) 2316 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1); 2317 __set_long_pointer(__p); 2318 __set_long_cap(__cap+1); 2319 __old_sz = __n_copy + __n_add + __sec_cp_sz; 2320 __set_long_size(__old_sz); 2321 traits_type::assign(__p[__old_sz], value_type()); 2322} 2323 2324template <class _CharT, class _Traits, class _Allocator> 2325void 2326basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz, 2327 size_type __n_copy, size_type __n_del, size_type __n_add) 2328{ 2329 size_type __ms = max_size(); 2330 if (__delta_cap > __ms - __old_cap) 2331 this->__throw_length_error(); 2332 pointer __old_p = __get_pointer(); 2333 size_type __cap = __old_cap < __ms / 2 - __alignment ? 2334 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) : 2335 __ms - 1; 2336 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1); 2337 __invalidate_all_iterators(); 2338 if (__n_copy != 0) 2339 traits_type::copy(_VSTD::__to_raw_pointer(__p), 2340 _VSTD::__to_raw_pointer(__old_p), __n_copy); 2341 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy; 2342 if (__sec_cp_sz != 0) 2343 traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add, 2344 _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del, 2345 __sec_cp_sz); 2346 if (__old_cap+1 != __min_cap) 2347 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1); 2348 __set_long_pointer(__p); 2349 __set_long_cap(__cap+1); 2350} 2351 2352// assign 2353 2354template <class _CharT, class _Traits, class _Allocator> 2355basic_string<_CharT, _Traits, _Allocator>& 2356basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n) 2357{ 2358 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr"); 2359 size_type __cap = capacity(); 2360 if (__cap >= __n) 2361 { 2362 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 2363 traits_type::move(__p, __s, __n); 2364 traits_type::assign(__p[__n], value_type()); 2365 __set_size(__n); 2366 __invalidate_iterators_past(__n); 2367 } 2368 else 2369 { 2370 size_type __sz = size(); 2371 __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s); 2372 } 2373 return *this; 2374} 2375 2376template <class _CharT, class _Traits, class _Allocator> 2377basic_string<_CharT, _Traits, _Allocator>& 2378basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c) 2379{ 2380 size_type __cap = capacity(); 2381 if (__cap < __n) 2382 { 2383 size_type __sz = size(); 2384 __grow_by(__cap, __n - __cap, __sz, 0, __sz); 2385 } 2386 else 2387 __invalidate_iterators_past(__n); 2388 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 2389 traits_type::assign(__p, __n, __c); 2390 traits_type::assign(__p[__n], value_type()); 2391 __set_size(__n); 2392 return *this; 2393} 2394 2395template <class _CharT, class _Traits, class _Allocator> 2396basic_string<_CharT, _Traits, _Allocator>& 2397basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c) 2398{ 2399 pointer __p; 2400 if (__is_long()) 2401 { 2402 __p = __get_long_pointer(); 2403 __set_long_size(1); 2404 } 2405 else 2406 { 2407 __p = __get_short_pointer(); 2408 __set_short_size(1); 2409 } 2410 traits_type::assign(*__p, __c); 2411 traits_type::assign(*++__p, value_type()); 2412 __invalidate_iterators_past(1); 2413 return *this; 2414} 2415 2416template <class _CharT, class _Traits, class _Allocator> 2417basic_string<_CharT, _Traits, _Allocator>& 2418basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str) 2419{ 2420 if (this != &__str) 2421 { 2422 __copy_assign_alloc(__str); 2423 assign(__str); 2424 } 2425 return *this; 2426} 2427 2428#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2429 2430template <class _CharT, class _Traits, class _Allocator> 2431inline _LIBCPP_INLINE_VISIBILITY 2432void 2433basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type) 2434{ 2435 if (__alloc() != __str.__alloc()) 2436 assign(__str); 2437 else 2438 __move_assign(__str, true_type()); 2439} 2440 2441template <class _CharT, class _Traits, class _Allocator> 2442inline _LIBCPP_INLINE_VISIBILITY 2443void 2444basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type) 2445 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2446{ 2447 clear(); 2448 shrink_to_fit(); 2449 __r_.first() = __str.__r_.first(); 2450 __move_assign_alloc(__str); 2451 __str.__zero(); 2452} 2453 2454template <class _CharT, class _Traits, class _Allocator> 2455inline _LIBCPP_INLINE_VISIBILITY 2456basic_string<_CharT, _Traits, _Allocator>& 2457basic_string<_CharT, _Traits, _Allocator>::operator=(basic_string&& __str) 2458 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 2459 is_nothrow_move_assignable<allocator_type>::value) 2460{ 2461 __move_assign(__str, integral_constant<bool, 2462 __alloc_traits::propagate_on_container_move_assignment::value>()); 2463 return *this; 2464} 2465 2466#endif 2467 2468template <class _CharT, class _Traits, class _Allocator> 2469template<class _InputIterator> 2470typename enable_if 2471< 2472 __is_input_iterator <_InputIterator>::value && 2473 !__is_forward_iterator<_InputIterator>::value, 2474 basic_string<_CharT, _Traits, _Allocator>& 2475>::type 2476basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2477{ 2478 clear(); 2479 for (; __first != __last; ++__first) 2480 push_back(*__first); 2481 return *this; 2482} 2483 2484template <class _CharT, class _Traits, class _Allocator> 2485template<class _ForwardIterator> 2486typename enable_if 2487< 2488 __is_forward_iterator<_ForwardIterator>::value, 2489 basic_string<_CharT, _Traits, _Allocator>& 2490>::type 2491basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2492{ 2493 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2494 size_type __cap = capacity(); 2495 if (__cap < __n) 2496 { 2497 size_type __sz = size(); 2498 __grow_by(__cap, __n - __cap, __sz, 0, __sz); 2499 } 2500 else 2501 __invalidate_iterators_past(__n); 2502 pointer __p = __get_pointer(); 2503 for (; __first != __last; ++__first, ++__p) 2504 traits_type::assign(*__p, *__first); 2505 traits_type::assign(*__p, value_type()); 2506 __set_size(__n); 2507 return *this; 2508} 2509 2510template <class _CharT, class _Traits, class _Allocator> 2511inline _LIBCPP_INLINE_VISIBILITY 2512basic_string<_CharT, _Traits, _Allocator>& 2513basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str) 2514{ 2515 return assign(__str.data(), __str.size()); 2516} 2517 2518template <class _CharT, class _Traits, class _Allocator> 2519basic_string<_CharT, _Traits, _Allocator>& 2520basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n) 2521{ 2522 size_type __sz = __str.size(); 2523 if (__pos > __sz) 2524 this->__throw_out_of_range(); 2525 return assign(__str.data() + __pos, _VSTD::min(__n, __sz - __pos)); 2526} 2527 2528template <class _CharT, class _Traits, class _Allocator> 2529basic_string<_CharT, _Traits, _Allocator>& 2530basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s) 2531{ 2532 _LIBCPP_ASSERT(__s != nullptr, "string::assign received nullptr"); 2533 return assign(__s, traits_type::length(__s)); 2534} 2535 2536// append 2537 2538template <class _CharT, class _Traits, class _Allocator> 2539basic_string<_CharT, _Traits, _Allocator>& 2540basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n) 2541{ 2542 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::append received nullptr"); 2543 size_type __cap = capacity(); 2544 size_type __sz = size(); 2545 if (__cap - __sz >= __n) 2546 { 2547 if (__n) 2548 { 2549 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 2550 traits_type::copy(__p + __sz, __s, __n); 2551 __sz += __n; 2552 __set_size(__sz); 2553 traits_type::assign(__p[__sz], value_type()); 2554 } 2555 } 2556 else 2557 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s); 2558 return *this; 2559} 2560 2561template <class _CharT, class _Traits, class _Allocator> 2562basic_string<_CharT, _Traits, _Allocator>& 2563basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c) 2564{ 2565 if (__n) 2566 { 2567 size_type __cap = capacity(); 2568 size_type __sz = size(); 2569 if (__cap - __sz < __n) 2570 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0); 2571 pointer __p = __get_pointer(); 2572 traits_type::assign(_VSTD::__to_raw_pointer(__p) + __sz, __n, __c); 2573 __sz += __n; 2574 __set_size(__sz); 2575 traits_type::assign(__p[__sz], value_type()); 2576 } 2577 return *this; 2578} 2579 2580template <class _CharT, class _Traits, class _Allocator> 2581void 2582basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c) 2583{ 2584 bool __is_short = !__is_long(); 2585 size_type __cap; 2586 size_type __sz; 2587 if (__is_short) 2588 { 2589 __cap = __min_cap - 1; 2590 __sz = __get_short_size(); 2591 } 2592 else 2593 { 2594 __cap = __get_long_cap() - 1; 2595 __sz = __get_long_size(); 2596 } 2597 if (__sz == __cap) 2598 { 2599 __grow_by(__cap, 1, __sz, __sz, 0); 2600 __is_short = !__is_long(); 2601 } 2602 pointer __p; 2603 if (__is_short) 2604 { 2605 __p = __get_short_pointer() + __sz; 2606 __set_short_size(__sz+1); 2607 } 2608 else 2609 { 2610 __p = __get_long_pointer() + __sz; 2611 __set_long_size(__sz+1); 2612 } 2613 traits_type::assign(*__p, __c); 2614 traits_type::assign(*++__p, value_type()); 2615} 2616 2617template <class _CharT, class _Traits, class _Allocator> 2618template<class _InputIterator> 2619typename enable_if 2620< 2621 __is_input_iterator <_InputIterator>::value && 2622 !__is_forward_iterator<_InputIterator>::value, 2623 basic_string<_CharT, _Traits, _Allocator>& 2624>::type 2625basic_string<_CharT, _Traits, _Allocator>::append(_InputIterator __first, _InputIterator __last) 2626{ 2627 for (; __first != __last; ++__first) 2628 push_back(*__first); 2629 return *this; 2630} 2631 2632template <class _CharT, class _Traits, class _Allocator> 2633template<class _ForwardIterator> 2634typename enable_if 2635< 2636 __is_forward_iterator<_ForwardIterator>::value, 2637 basic_string<_CharT, _Traits, _Allocator>& 2638>::type 2639basic_string<_CharT, _Traits, _Allocator>::append(_ForwardIterator __first, _ForwardIterator __last) 2640{ 2641 size_type __sz = size(); 2642 size_type __cap = capacity(); 2643 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2644 if (__n) 2645 { 2646 if (__cap - __sz < __n) 2647 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0); 2648 pointer __p = __get_pointer() + __sz; 2649 for (; __first != __last; ++__p, ++__first) 2650 traits_type::assign(*__p, *__first); 2651 traits_type::assign(*__p, value_type()); 2652 __set_size(__sz + __n); 2653 } 2654 return *this; 2655} 2656 2657template <class _CharT, class _Traits, class _Allocator> 2658inline _LIBCPP_INLINE_VISIBILITY 2659basic_string<_CharT, _Traits, _Allocator>& 2660basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str) 2661{ 2662 return append(__str.data(), __str.size()); 2663} 2664 2665template <class _CharT, class _Traits, class _Allocator> 2666basic_string<_CharT, _Traits, _Allocator>& 2667basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n) 2668{ 2669 size_type __sz = __str.size(); 2670 if (__pos > __sz) 2671 this->__throw_out_of_range(); 2672 return append(__str.data() + __pos, _VSTD::min(__n, __sz - __pos)); 2673} 2674 2675template <class _CharT, class _Traits, class _Allocator> 2676basic_string<_CharT, _Traits, _Allocator>& 2677basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s) 2678{ 2679 _LIBCPP_ASSERT(__s != nullptr, "string::append received nullptr"); 2680 return append(__s, traits_type::length(__s)); 2681} 2682 2683// insert 2684 2685template <class _CharT, class _Traits, class _Allocator> 2686basic_string<_CharT, _Traits, _Allocator>& 2687basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s, size_type __n) 2688{ 2689 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::insert received nullptr"); 2690 size_type __sz = size(); 2691 if (__pos > __sz) 2692 this->__throw_out_of_range(); 2693 size_type __cap = capacity(); 2694 if (__cap - __sz >= __n) 2695 { 2696 if (__n) 2697 { 2698 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 2699 size_type __n_move = __sz - __pos; 2700 if (__n_move != 0) 2701 { 2702 if (__p + __pos <= __s && __s < __p + __sz) 2703 __s += __n; 2704 traits_type::move(__p + __pos + __n, __p + __pos, __n_move); 2705 } 2706 traits_type::move(__p + __pos, __s, __n); 2707 __sz += __n; 2708 __set_size(__sz); 2709 traits_type::assign(__p[__sz], value_type()); 2710 } 2711 } 2712 else 2713 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s); 2714 return *this; 2715} 2716 2717template <class _CharT, class _Traits, class _Allocator> 2718basic_string<_CharT, _Traits, _Allocator>& 2719basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c) 2720{ 2721 size_type __sz = size(); 2722 if (__pos > __sz) 2723 this->__throw_out_of_range(); 2724 if (__n) 2725 { 2726 size_type __cap = capacity(); 2727 value_type* __p; 2728 if (__cap - __sz >= __n) 2729 { 2730 __p = _VSTD::__to_raw_pointer(__get_pointer()); 2731 size_type __n_move = __sz - __pos; 2732 if (__n_move != 0) 2733 traits_type::move(__p + __pos + __n, __p + __pos, __n_move); 2734 } 2735 else 2736 { 2737 __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n); 2738 __p = _VSTD::__to_raw_pointer(__get_long_pointer()); 2739 } 2740 traits_type::assign(__p + __pos, __n, __c); 2741 __sz += __n; 2742 __set_size(__sz); 2743 traits_type::assign(__p[__sz], value_type()); 2744 } 2745 return *this; 2746} 2747 2748template <class _CharT, class _Traits, class _Allocator> 2749template<class _InputIterator> 2750typename enable_if 2751< 2752 __is_input_iterator <_InputIterator>::value && 2753 !__is_forward_iterator<_InputIterator>::value, 2754 typename basic_string<_CharT, _Traits, _Allocator>::iterator 2755>::type 2756basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last) 2757{ 2758#if _LIBCPP_DEBUG_LEVEL >= 2 2759 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, 2760 "string::insert(iterator, range) called with an iterator not" 2761 " referring to this string"); 2762#endif 2763 size_type __old_sz = size(); 2764 difference_type __ip = __pos - begin(); 2765 for (; __first != __last; ++__first) 2766 push_back(*__first); 2767 pointer __p = __get_pointer(); 2768 _VSTD::rotate(__p + __ip, __p + __old_sz, __p + size()); 2769#if _LIBCPP_DEBUG_LEVEL >= 2 2770 return iterator(this, __p + __ip); 2771#else 2772 return iterator(__p + __ip); 2773#endif 2774} 2775 2776template <class _CharT, class _Traits, class _Allocator> 2777template<class _ForwardIterator> 2778typename enable_if 2779< 2780 __is_forward_iterator<_ForwardIterator>::value, 2781 typename basic_string<_CharT, _Traits, _Allocator>::iterator 2782>::type 2783basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last) 2784{ 2785#if _LIBCPP_DEBUG_LEVEL >= 2 2786 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, 2787 "string::insert(iterator, range) called with an iterator not" 2788 " referring to this string"); 2789#endif 2790 size_type __ip = static_cast<size_type>(__pos - begin()); 2791 size_type __sz = size(); 2792 size_type __cap = capacity(); 2793 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2794 if (__n) 2795 { 2796 value_type* __p; 2797 if (__cap - __sz >= __n) 2798 { 2799 __p = _VSTD::__to_raw_pointer(__get_pointer()); 2800 size_type __n_move = __sz - __ip; 2801 if (__n_move != 0) 2802 traits_type::move(__p + __ip + __n, __p + __ip, __n_move); 2803 } 2804 else 2805 { 2806 __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n); 2807 __p = _VSTD::__to_raw_pointer(__get_long_pointer()); 2808 } 2809 __sz += __n; 2810 __set_size(__sz); 2811 traits_type::assign(__p[__sz], value_type()); 2812 for (__p += __ip; __first != __last; ++__p, ++__first) 2813 traits_type::assign(*__p, *__first); 2814 } 2815 return begin() + __ip; 2816} 2817 2818template <class _CharT, class _Traits, class _Allocator> 2819inline _LIBCPP_INLINE_VISIBILITY 2820basic_string<_CharT, _Traits, _Allocator>& 2821basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str) 2822{ 2823 return insert(__pos1, __str.data(), __str.size()); 2824} 2825 2826template <class _CharT, class _Traits, class _Allocator> 2827basic_string<_CharT, _Traits, _Allocator>& 2828basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str, 2829 size_type __pos2, size_type __n) 2830{ 2831 size_type __str_sz = __str.size(); 2832 if (__pos2 > __str_sz) 2833 this->__throw_out_of_range(); 2834 return insert(__pos1, __str.data() + __pos2, _VSTD::min(__n, __str_sz - __pos2)); 2835} 2836 2837template <class _CharT, class _Traits, class _Allocator> 2838basic_string<_CharT, _Traits, _Allocator>& 2839basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s) 2840{ 2841 _LIBCPP_ASSERT(__s != nullptr, "string::insert received nullptr"); 2842 return insert(__pos, __s, traits_type::length(__s)); 2843} 2844 2845template <class _CharT, class _Traits, class _Allocator> 2846typename basic_string<_CharT, _Traits, _Allocator>::iterator 2847basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c) 2848{ 2849 size_type __ip = static_cast<size_type>(__pos - begin()); 2850 size_type __sz = size(); 2851 size_type __cap = capacity(); 2852 value_type* __p; 2853 if (__cap == __sz) 2854 { 2855 __grow_by(__cap, 1, __sz, __ip, 0, 1); 2856 __p = _VSTD::__to_raw_pointer(__get_long_pointer()); 2857 } 2858 else 2859 { 2860 __p = _VSTD::__to_raw_pointer(__get_pointer()); 2861 size_type __n_move = __sz - __ip; 2862 if (__n_move != 0) 2863 traits_type::move(__p + __ip + 1, __p + __ip, __n_move); 2864 } 2865 traits_type::assign(__p[__ip], __c); 2866 traits_type::assign(__p[++__sz], value_type()); 2867 __set_size(__sz); 2868 return begin() + static_cast<difference_type>(__ip); 2869} 2870 2871template <class _CharT, class _Traits, class _Allocator> 2872inline _LIBCPP_INLINE_VISIBILITY 2873typename basic_string<_CharT, _Traits, _Allocator>::iterator 2874basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, size_type __n, value_type __c) 2875{ 2876#if _LIBCPP_DEBUG_LEVEL >= 2 2877 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, 2878 "string::insert(iterator, n, value) called with an iterator not" 2879 " referring to this string"); 2880#endif 2881 difference_type __p = __pos - begin(); 2882 insert(static_cast<size_type>(__p), __n, __c); 2883 return begin() + __p; 2884} 2885 2886// replace 2887 2888template <class _CharT, class _Traits, class _Allocator> 2889basic_string<_CharT, _Traits, _Allocator>& 2890basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2) 2891{ 2892 _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::replace received nullptr"); 2893 size_type __sz = size(); 2894 if (__pos > __sz) 2895 this->__throw_out_of_range(); 2896 __n1 = _VSTD::min(__n1, __sz - __pos); 2897 size_type __cap = capacity(); 2898 if (__cap - __sz + __n1 >= __n2) 2899 { 2900 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 2901 if (__n1 != __n2) 2902 { 2903 size_type __n_move = __sz - __pos - __n1; 2904 if (__n_move != 0) 2905 { 2906 if (__n1 > __n2) 2907 { 2908 traits_type::move(__p + __pos, __s, __n2); 2909 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2910 goto __finish; 2911 } 2912 if (__p + __pos < __s && __s < __p + __sz) 2913 { 2914 if (__p + __pos + __n1 <= __s) 2915 __s += __n2 - __n1; 2916 else // __p + __pos < __s < __p + __pos + __n1 2917 { 2918 traits_type::move(__p + __pos, __s, __n1); 2919 __pos += __n1; 2920 __s += __n2; 2921 __n2 -= __n1; 2922 __n1 = 0; 2923 } 2924 } 2925 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2926 } 2927 } 2928 traits_type::move(__p + __pos, __s, __n2); 2929__finish: 2930 __sz += __n2 - __n1; 2931 __set_size(__sz); 2932 __invalidate_iterators_past(__sz); 2933 traits_type::assign(__p[__sz], value_type()); 2934 } 2935 else 2936 __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s); 2937 return *this; 2938} 2939 2940template <class _CharT, class _Traits, class _Allocator> 2941basic_string<_CharT, _Traits, _Allocator>& 2942basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c) 2943{ 2944 size_type __sz = size(); 2945 if (__pos > __sz) 2946 this->__throw_out_of_range(); 2947 __n1 = _VSTD::min(__n1, __sz - __pos); 2948 size_type __cap = capacity(); 2949 value_type* __p; 2950 if (__cap - __sz + __n1 >= __n2) 2951 { 2952 __p = _VSTD::__to_raw_pointer(__get_pointer()); 2953 if (__n1 != __n2) 2954 { 2955 size_type __n_move = __sz - __pos - __n1; 2956 if (__n_move != 0) 2957 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); 2958 } 2959 } 2960 else 2961 { 2962 __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2); 2963 __p = _VSTD::__to_raw_pointer(__get_long_pointer()); 2964 } 2965 traits_type::assign(__p + __pos, __n2, __c); 2966 __sz += __n2 - __n1; 2967 __set_size(__sz); 2968 __invalidate_iterators_past(__sz); 2969 traits_type::assign(__p[__sz], value_type()); 2970 return *this; 2971} 2972 2973template <class _CharT, class _Traits, class _Allocator> 2974template<class _InputIterator> 2975typename enable_if 2976< 2977 __is_input_iterator<_InputIterator>::value, 2978 basic_string<_CharT, _Traits, _Allocator>& 2979>::type 2980basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, 2981 _InputIterator __j1, _InputIterator __j2) 2982{ 2983 for (; true; ++__i1, ++__j1) 2984 { 2985 if (__i1 == __i2) 2986 { 2987 if (__j1 != __j2) 2988 insert(__i1, __j1, __j2); 2989 break; 2990 } 2991 if (__j1 == __j2) 2992 { 2993 erase(__i1, __i2); 2994 break; 2995 } 2996 traits_type::assign(const_cast<value_type&>(*__i1), *__j1); 2997 } 2998 return *this; 2999} 3000 3001template <class _CharT, class _Traits, class _Allocator> 3002inline _LIBCPP_INLINE_VISIBILITY 3003basic_string<_CharT, _Traits, _Allocator>& 3004basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str) 3005{ 3006 return replace(__pos1, __n1, __str.data(), __str.size()); 3007} 3008 3009template <class _CharT, class _Traits, class _Allocator> 3010basic_string<_CharT, _Traits, _Allocator>& 3011basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str, 3012 size_type __pos2, size_type __n2) 3013{ 3014 size_type __str_sz = __str.size(); 3015 if (__pos2 > __str_sz) 3016 this->__throw_out_of_range(); 3017 return replace(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, __str_sz - __pos2)); 3018} 3019 3020template <class _CharT, class _Traits, class _Allocator> 3021basic_string<_CharT, _Traits, _Allocator>& 3022basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s) 3023{ 3024 _LIBCPP_ASSERT(__s != nullptr, "string::replace received nullptr"); 3025 return replace(__pos, __n1, __s, traits_type::length(__s)); 3026} 3027 3028template <class _CharT, class _Traits, class _Allocator> 3029inline _LIBCPP_INLINE_VISIBILITY 3030basic_string<_CharT, _Traits, _Allocator>& 3031basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const basic_string& __str) 3032{ 3033 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), 3034 __str.data(), __str.size()); 3035} 3036 3037template <class _CharT, class _Traits, class _Allocator> 3038inline _LIBCPP_INLINE_VISIBILITY 3039basic_string<_CharT, _Traits, _Allocator>& 3040basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n) 3041{ 3042 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n); 3043} 3044 3045template <class _CharT, class _Traits, class _Allocator> 3046inline _LIBCPP_INLINE_VISIBILITY 3047basic_string<_CharT, _Traits, _Allocator>& 3048basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const value_type* __s) 3049{ 3050 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s); 3051} 3052 3053template <class _CharT, class _Traits, class _Allocator> 3054inline _LIBCPP_INLINE_VISIBILITY 3055basic_string<_CharT, _Traits, _Allocator>& 3056basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c) 3057{ 3058 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c); 3059} 3060 3061// erase 3062 3063template <class _CharT, class _Traits, class _Allocator> 3064basic_string<_CharT, _Traits, _Allocator>& 3065basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos, size_type __n) 3066{ 3067 size_type __sz = size(); 3068 if (__pos > __sz) 3069 this->__throw_out_of_range(); 3070 if (__n) 3071 { 3072 value_type* __p = _VSTD::__to_raw_pointer(__get_pointer()); 3073 __n = _VSTD::min(__n, __sz - __pos); 3074 size_type __n_move = __sz - __pos - __n; 3075 if (__n_move != 0) 3076 traits_type::move(__p + __pos, __p + __pos + __n, __n_move); 3077 __sz -= __n; 3078 __set_size(__sz); 3079 __invalidate_iterators_past(__sz); 3080 traits_type::assign(__p[__sz], value_type()); 3081 } 3082 return *this; 3083} 3084 3085template <class _CharT, class _Traits, class _Allocator> 3086inline _LIBCPP_INLINE_VISIBILITY 3087typename basic_string<_CharT, _Traits, _Allocator>::iterator 3088basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos) 3089{ 3090#if _LIBCPP_DEBUG_LEVEL >= 2 3091 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, 3092 "string::erase(iterator) called with an iterator not" 3093 " referring to this string"); 3094#endif 3095 _LIBCPP_ASSERT(__pos != end(), 3096 "string::erase(iterator) called with a non-dereferenceable iterator"); 3097 iterator __b = begin(); 3098 size_type __r = static_cast<size_type>(__pos - __b); 3099 erase(__r, 1); 3100 return __b + static_cast<difference_type>(__r); 3101} 3102 3103template <class _CharT, class _Traits, class _Allocator> 3104inline _LIBCPP_INLINE_VISIBILITY 3105typename basic_string<_CharT, _Traits, _Allocator>::iterator 3106basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last) 3107{ 3108#if _LIBCPP_DEBUG_LEVEL >= 2 3109 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 3110 "string::erase(iterator, iterator) called with an iterator not" 3111 " referring to this string"); 3112#endif 3113 _LIBCPP_ASSERT(__first <= __last, "string::erase(first, last) called with invalid range"); 3114 iterator __b = begin(); 3115 size_type __r = static_cast<size_type>(__first - __b); 3116 erase(__r, static_cast<size_type>(__last - __first)); 3117 return __b + static_cast<difference_type>(__r); 3118} 3119 3120template <class _CharT, class _Traits, class _Allocator> 3121inline _LIBCPP_INLINE_VISIBILITY 3122void 3123basic_string<_CharT, _Traits, _Allocator>::pop_back() 3124{ 3125 _LIBCPP_ASSERT(!empty(), "string::pop_back(): string is already empty"); 3126 size_type __sz; 3127 if (__is_long()) 3128 { 3129 __sz = __get_long_size() - 1; 3130 __set_long_size(__sz); 3131 traits_type::assign(*(__get_long_pointer() + __sz), value_type()); 3132 } 3133 else 3134 { 3135 __sz = __get_short_size() - 1; 3136 __set_short_size(__sz); 3137 traits_type::assign(*(__get_short_pointer() + __sz), value_type()); 3138 } 3139 __invalidate_iterators_past(__sz); 3140} 3141 3142template <class _CharT, class _Traits, class _Allocator> 3143inline _LIBCPP_INLINE_VISIBILITY 3144void 3145basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT 3146{ 3147 __invalidate_all_iterators(); 3148 if (__is_long()) 3149 { 3150 traits_type::assign(*__get_long_pointer(), value_type()); 3151 __set_long_size(0); 3152 } 3153 else 3154 { 3155 traits_type::assign(*__get_short_pointer(), value_type()); 3156 __set_short_size(0); 3157 } 3158} 3159 3160template <class _CharT, class _Traits, class _Allocator> 3161inline _LIBCPP_INLINE_VISIBILITY 3162void 3163basic_string<_CharT, _Traits, _Allocator>::__erase_to_end(size_type __pos) 3164{ 3165 if (__is_long()) 3166 { 3167 traits_type::assign(*(__get_long_pointer() + __pos), value_type()); 3168 __set_long_size(__pos); 3169 } 3170 else 3171 { 3172 traits_type::assign(*(__get_short_pointer() + __pos), value_type()); 3173 __set_short_size(__pos); 3174 } 3175 __invalidate_iterators_past(__pos); 3176} 3177 3178template <class _CharT, class _Traits, class _Allocator> 3179void 3180basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c) 3181{ 3182 size_type __sz = size(); 3183 if (__n > __sz) 3184 append(__n - __sz, __c); 3185 else 3186 __erase_to_end(__n); 3187} 3188 3189template <class _CharT, class _Traits, class _Allocator> 3190inline _LIBCPP_INLINE_VISIBILITY 3191typename basic_string<_CharT, _Traits, _Allocator>::size_type 3192basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT 3193{ 3194 size_type __m = __alloc_traits::max_size(__alloc()); 3195#if _LIBCPP_BIG_ENDIAN 3196 return (__m <= ~__long_mask ? __m : __m/2) - __alignment; 3197#else 3198 return __m - __alignment; 3199#endif 3200} 3201 3202template <class _CharT, class _Traits, class _Allocator> 3203void 3204basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __res_arg) 3205{ 3206 if (__res_arg > max_size()) 3207 this->__throw_length_error(); 3208 size_type __cap = capacity(); 3209 size_type __sz = size(); 3210 __res_arg = _VSTD::max(__res_arg, __sz); 3211 __res_arg = __recommend(__res_arg); 3212 if (__res_arg != __cap) 3213 { 3214 pointer __new_data, __p; 3215 bool __was_long, __now_long; 3216 if (__res_arg == __min_cap - 1) 3217 { 3218 __was_long = true; 3219 __now_long = false; 3220 __new_data = __get_short_pointer(); 3221 __p = __get_long_pointer(); 3222 } 3223 else 3224 { 3225 if (__res_arg > __cap) 3226 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1); 3227 else 3228 { 3229 #ifndef _LIBCPP_NO_EXCEPTIONS 3230 try 3231 { 3232 #endif // _LIBCPP_NO_EXCEPTIONS 3233 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1); 3234 #ifndef _LIBCPP_NO_EXCEPTIONS 3235 } 3236 catch (...) 3237 { 3238 return; 3239 } 3240 #else // _LIBCPP_NO_EXCEPTIONS 3241 if (__new_data == nullptr) 3242 return; 3243 #endif // _LIBCPP_NO_EXCEPTIONS 3244 } 3245 __now_long = true; 3246 __was_long = __is_long(); 3247 __p = __get_pointer(); 3248 } 3249 traits_type::copy(_VSTD::__to_raw_pointer(__new_data), 3250 _VSTD::__to_raw_pointer(__p), size()+1); 3251 if (__was_long) 3252 __alloc_traits::deallocate(__alloc(), __p, __cap+1); 3253 if (__now_long) 3254 { 3255 __set_long_cap(__res_arg+1); 3256 __set_long_size(__sz); 3257 __set_long_pointer(__new_data); 3258 } 3259 else 3260 __set_short_size(__sz); 3261 __invalidate_all_iterators(); 3262 } 3263} 3264 3265template <class _CharT, class _Traits, class _Allocator> 3266inline _LIBCPP_INLINE_VISIBILITY 3267typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3268basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) const 3269{ 3270 _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds"); 3271 return *(data() + __pos); 3272} 3273 3274template <class _CharT, class _Traits, class _Allocator> 3275inline _LIBCPP_INLINE_VISIBILITY 3276typename basic_string<_CharT, _Traits, _Allocator>::reference 3277basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) 3278{ 3279 _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds"); 3280 return *(__get_pointer() + __pos); 3281} 3282 3283template <class _CharT, class _Traits, class _Allocator> 3284typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3285basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const 3286{ 3287 if (__n >= size()) 3288 this->__throw_out_of_range(); 3289 return (*this)[__n]; 3290} 3291 3292template <class _CharT, class _Traits, class _Allocator> 3293typename basic_string<_CharT, _Traits, _Allocator>::reference 3294basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) 3295{ 3296 if (__n >= size()) 3297 this->__throw_out_of_range(); 3298 return (*this)[__n]; 3299} 3300 3301template <class _CharT, class _Traits, class _Allocator> 3302inline _LIBCPP_INLINE_VISIBILITY 3303typename basic_string<_CharT, _Traits, _Allocator>::reference 3304basic_string<_CharT, _Traits, _Allocator>::front() 3305{ 3306 _LIBCPP_ASSERT(!empty(), "string::front(): string is empty"); 3307 return *__get_pointer(); 3308} 3309 3310template <class _CharT, class _Traits, class _Allocator> 3311inline _LIBCPP_INLINE_VISIBILITY 3312typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3313basic_string<_CharT, _Traits, _Allocator>::front() const 3314{ 3315 _LIBCPP_ASSERT(!empty(), "string::front(): string is empty"); 3316 return *data(); 3317} 3318 3319template <class _CharT, class _Traits, class _Allocator> 3320inline _LIBCPP_INLINE_VISIBILITY 3321typename basic_string<_CharT, _Traits, _Allocator>::reference 3322basic_string<_CharT, _Traits, _Allocator>::back() 3323{ 3324 _LIBCPP_ASSERT(!empty(), "string::back(): string is empty"); 3325 return *(__get_pointer() + size() - 1); 3326} 3327 3328template <class _CharT, class _Traits, class _Allocator> 3329inline _LIBCPP_INLINE_VISIBILITY 3330typename basic_string<_CharT, _Traits, _Allocator>::const_reference 3331basic_string<_CharT, _Traits, _Allocator>::back() const 3332{ 3333 _LIBCPP_ASSERT(!empty(), "string::back(): string is empty"); 3334 return *(data() + size() - 1); 3335} 3336 3337template <class _CharT, class _Traits, class _Allocator> 3338typename basic_string<_CharT, _Traits, _Allocator>::size_type 3339basic_string<_CharT, _Traits, _Allocator>::copy(value_type* __s, size_type __n, size_type __pos) const 3340{ 3341 size_type __sz = size(); 3342 if (__pos > __sz) 3343 this->__throw_out_of_range(); 3344 size_type __rlen = _VSTD::min(__n, __sz - __pos); 3345 traits_type::copy(__s, data() + __pos, __rlen); 3346 return __rlen; 3347} 3348 3349template <class _CharT, class _Traits, class _Allocator> 3350inline _LIBCPP_INLINE_VISIBILITY 3351basic_string<_CharT, _Traits, _Allocator> 3352basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const 3353{ 3354 return basic_string(*this, __pos, __n, __alloc()); 3355} 3356 3357template <class _CharT, class _Traits, class _Allocator> 3358inline _LIBCPP_INLINE_VISIBILITY 3359void 3360basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str) 3361#if _LIBCPP_STD_VER >= 14 3362 _NOEXCEPT 3363#else 3364 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3365 __is_nothrow_swappable<allocator_type>::value) 3366#endif 3367{ 3368#if _LIBCPP_DEBUG_LEVEL >= 2 3369 if (!__is_long()) 3370 __get_db()->__invalidate_all(this); 3371 if (!__str.__is_long()) 3372 __get_db()->__invalidate_all(&__str); 3373 __get_db()->swap(this, &__str); 3374#endif 3375 _VSTD::swap(__r_.first(), __str.__r_.first()); 3376 __swap_allocator(__alloc(), __str.__alloc()); 3377} 3378 3379// find 3380 3381template <class _Traits> 3382struct _LIBCPP_HIDDEN __traits_eq 3383{ 3384 typedef typename _Traits::char_type char_type; 3385 _LIBCPP_INLINE_VISIBILITY 3386 bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT 3387 {return _Traits::eq(__x, __y);} 3388}; 3389 3390template<class _CharT, class _Traits, class _Allocator> 3391typename basic_string<_CharT, _Traits, _Allocator>::size_type 3392basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s, 3393 size_type __pos, 3394 size_type __n) const _NOEXCEPT 3395{ 3396 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find(): received nullptr"); 3397 return _VSTD::__str_find<value_type, size_type, traits_type, npos> 3398 (data(), size(), __s, __pos, __n); 3399} 3400 3401template<class _CharT, class _Traits, class _Allocator> 3402inline _LIBCPP_INLINE_VISIBILITY 3403typename basic_string<_CharT, _Traits, _Allocator>::size_type 3404basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str, 3405 size_type __pos) const _NOEXCEPT 3406{ 3407 return _VSTD::__str_find<value_type, size_type, traits_type, npos> 3408 (data(), size(), __str.data(), __pos, __str.size()); 3409} 3410 3411template<class _CharT, class _Traits, class _Allocator> 3412inline _LIBCPP_INLINE_VISIBILITY 3413typename basic_string<_CharT, _Traits, _Allocator>::size_type 3414basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s, 3415 size_type __pos) const _NOEXCEPT 3416{ 3417 _LIBCPP_ASSERT(__s != nullptr, "string::find(): received nullptr"); 3418 return _VSTD::__str_find<value_type, size_type, traits_type, npos> 3419 (data(), size(), __s, __pos, traits_type::length(__s)); 3420} 3421 3422template<class _CharT, class _Traits, class _Allocator> 3423typename basic_string<_CharT, _Traits, _Allocator>::size_type 3424basic_string<_CharT, _Traits, _Allocator>::find(value_type __c, 3425 size_type __pos) const _NOEXCEPT 3426{ 3427 return _VSTD::__str_find<value_type, size_type, traits_type, npos> 3428 (data(), size(), __c, __pos); 3429} 3430 3431// rfind 3432 3433template<class _CharT, class _Traits, class _Allocator> 3434typename basic_string<_CharT, _Traits, _Allocator>::size_type 3435basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s, 3436 size_type __pos, 3437 size_type __n) const _NOEXCEPT 3438{ 3439 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::rfind(): received nullptr"); 3440 return _VSTD::__str_rfind<value_type, size_type, traits_type, npos> 3441 (data(), size(), __s, __pos, __n); 3442} 3443 3444template<class _CharT, class _Traits, class _Allocator> 3445inline _LIBCPP_INLINE_VISIBILITY 3446typename basic_string<_CharT, _Traits, _Allocator>::size_type 3447basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str, 3448 size_type __pos) const _NOEXCEPT 3449{ 3450 return _VSTD::__str_rfind<value_type, size_type, traits_type, npos> 3451 (data(), size(), __str.data(), __pos, __str.size()); 3452} 3453 3454template<class _CharT, class _Traits, class _Allocator> 3455inline _LIBCPP_INLINE_VISIBILITY 3456typename basic_string<_CharT, _Traits, _Allocator>::size_type 3457basic_string<_CharT, _Traits, _Allocator>::rfind(const value_type* __s, 3458 size_type __pos) const _NOEXCEPT 3459{ 3460 _LIBCPP_ASSERT(__s != nullptr, "string::rfind(): received nullptr"); 3461 return _VSTD::__str_rfind<value_type, size_type, traits_type, npos> 3462 (data(), size(), __s, __pos, traits_type::length(__s)); 3463} 3464 3465template<class _CharT, class _Traits, class _Allocator> 3466typename basic_string<_CharT, _Traits, _Allocator>::size_type 3467basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c, 3468 size_type __pos) const _NOEXCEPT 3469{ 3470 return _VSTD::__str_rfind<value_type, size_type, traits_type, npos> 3471 (data(), size(), __c, __pos); 3472} 3473 3474// find_first_of 3475 3476template<class _CharT, class _Traits, class _Allocator> 3477typename basic_string<_CharT, _Traits, _Allocator>::size_type 3478basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s, 3479 size_type __pos, 3480 size_type __n) const _NOEXCEPT 3481{ 3482 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_of(): received nullptr"); 3483 return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos> 3484 (data(), size(), __s, __pos, __n); 3485} 3486 3487template<class _CharT, class _Traits, class _Allocator> 3488inline _LIBCPP_INLINE_VISIBILITY 3489typename basic_string<_CharT, _Traits, _Allocator>::size_type 3490basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str, 3491 size_type __pos) const _NOEXCEPT 3492{ 3493 return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos> 3494 (data(), size(), __str.data(), __pos, __str.size()); 3495} 3496 3497template<class _CharT, class _Traits, class _Allocator> 3498inline _LIBCPP_INLINE_VISIBILITY 3499typename basic_string<_CharT, _Traits, _Allocator>::size_type 3500basic_string<_CharT, _Traits, _Allocator>::find_first_of(const value_type* __s, 3501 size_type __pos) const _NOEXCEPT 3502{ 3503 _LIBCPP_ASSERT(__s != nullptr, "string::find_first_of(): received nullptr"); 3504 return _VSTD::__str_find_first_of<value_type, size_type, traits_type, npos> 3505 (data(), size(), __s, __pos, traits_type::length(__s)); 3506} 3507 3508template<class _CharT, class _Traits, class _Allocator> 3509inline _LIBCPP_INLINE_VISIBILITY 3510typename basic_string<_CharT, _Traits, _Allocator>::size_type 3511basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c, 3512 size_type __pos) const _NOEXCEPT 3513{ 3514 return find(__c, __pos); 3515} 3516 3517// find_last_of 3518 3519template<class _CharT, class _Traits, class _Allocator> 3520typename basic_string<_CharT, _Traits, _Allocator>::size_type 3521basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s, 3522 size_type __pos, 3523 size_type __n) const _NOEXCEPT 3524{ 3525 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_of(): received nullptr"); 3526 return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos> 3527 (data(), size(), __s, __pos, __n); 3528} 3529 3530template<class _CharT, class _Traits, class _Allocator> 3531inline _LIBCPP_INLINE_VISIBILITY 3532typename basic_string<_CharT, _Traits, _Allocator>::size_type 3533basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str, 3534 size_type __pos) const _NOEXCEPT 3535{ 3536 return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos> 3537 (data(), size(), __str.data(), __pos, __str.size()); 3538} 3539 3540template<class _CharT, class _Traits, class _Allocator> 3541inline _LIBCPP_INLINE_VISIBILITY 3542typename basic_string<_CharT, _Traits, _Allocator>::size_type 3543basic_string<_CharT, _Traits, _Allocator>::find_last_of(const value_type* __s, 3544 size_type __pos) const _NOEXCEPT 3545{ 3546 _LIBCPP_ASSERT(__s != nullptr, "string::find_last_of(): received nullptr"); 3547 return _VSTD::__str_find_last_of<value_type, size_type, traits_type, npos> 3548 (data(), size(), __s, __pos, traits_type::length(__s)); 3549} 3550 3551template<class _CharT, class _Traits, class _Allocator> 3552inline _LIBCPP_INLINE_VISIBILITY 3553typename basic_string<_CharT, _Traits, _Allocator>::size_type 3554basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c, 3555 size_type __pos) const _NOEXCEPT 3556{ 3557 return rfind(__c, __pos); 3558} 3559 3560// find_first_not_of 3561 3562template<class _CharT, class _Traits, class _Allocator> 3563typename basic_string<_CharT, _Traits, _Allocator>::size_type 3564basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s, 3565 size_type __pos, 3566 size_type __n) const _NOEXCEPT 3567{ 3568 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_first_not_of(): received nullptr"); 3569 return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos> 3570 (data(), size(), __s, __pos, __n); 3571} 3572 3573template<class _CharT, class _Traits, class _Allocator> 3574inline _LIBCPP_INLINE_VISIBILITY 3575typename basic_string<_CharT, _Traits, _Allocator>::size_type 3576basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str, 3577 size_type __pos) const _NOEXCEPT 3578{ 3579 return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos> 3580 (data(), size(), __str.data(), __pos, __str.size()); 3581} 3582 3583template<class _CharT, class _Traits, class _Allocator> 3584inline _LIBCPP_INLINE_VISIBILITY 3585typename basic_string<_CharT, _Traits, _Allocator>::size_type 3586basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const value_type* __s, 3587 size_type __pos) const _NOEXCEPT 3588{ 3589 _LIBCPP_ASSERT(__s != nullptr, "string::find_first_not_of(): received nullptr"); 3590 return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos> 3591 (data(), size(), __s, __pos, traits_type::length(__s)); 3592} 3593 3594template<class _CharT, class _Traits, class _Allocator> 3595inline _LIBCPP_INLINE_VISIBILITY 3596typename basic_string<_CharT, _Traits, _Allocator>::size_type 3597basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c, 3598 size_type __pos) const _NOEXCEPT 3599{ 3600 return _VSTD::__str_find_first_not_of<value_type, size_type, traits_type, npos> 3601 (data(), size(), __c, __pos); 3602} 3603 3604// find_last_not_of 3605 3606template<class _CharT, class _Traits, class _Allocator> 3607typename basic_string<_CharT, _Traits, _Allocator>::size_type 3608basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s, 3609 size_type __pos, 3610 size_type __n) const _NOEXCEPT 3611{ 3612 _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find_last_not_of(): received nullptr"); 3613 return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos> 3614 (data(), size(), __s, __pos, __n); 3615} 3616 3617template<class _CharT, class _Traits, class _Allocator> 3618inline _LIBCPP_INLINE_VISIBILITY 3619typename basic_string<_CharT, _Traits, _Allocator>::size_type 3620basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str, 3621 size_type __pos) const _NOEXCEPT 3622{ 3623 return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos> 3624 (data(), size(), __str.data(), __pos, __str.size()); 3625} 3626 3627template<class _CharT, class _Traits, class _Allocator> 3628inline _LIBCPP_INLINE_VISIBILITY 3629typename basic_string<_CharT, _Traits, _Allocator>::size_type 3630basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const value_type* __s, 3631 size_type __pos) const _NOEXCEPT 3632{ 3633 _LIBCPP_ASSERT(__s != nullptr, "string::find_last_not_of(): received nullptr"); 3634 return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos> 3635 (data(), size(), __s, __pos, traits_type::length(__s)); 3636} 3637 3638template<class _CharT, class _Traits, class _Allocator> 3639inline _LIBCPP_INLINE_VISIBILITY 3640typename basic_string<_CharT, _Traits, _Allocator>::size_type 3641basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c, 3642 size_type __pos) const _NOEXCEPT 3643{ 3644 return _VSTD::__str_find_last_not_of<value_type, size_type, traits_type, npos> 3645 (data(), size(), __c, __pos); 3646} 3647 3648// compare 3649 3650template <class _CharT, class _Traits, class _Allocator> 3651inline _LIBCPP_INLINE_VISIBILITY 3652int 3653basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT 3654{ 3655 size_t __lhs_sz = size(); 3656 size_t __rhs_sz = __str.size(); 3657 int __result = traits_type::compare(data(), __str.data(), 3658 _VSTD::min(__lhs_sz, __rhs_sz)); 3659 if (__result != 0) 3660 return __result; 3661 if (__lhs_sz < __rhs_sz) 3662 return -1; 3663 if (__lhs_sz > __rhs_sz) 3664 return 1; 3665 return 0; 3666} 3667 3668template <class _CharT, class _Traits, class _Allocator> 3669inline _LIBCPP_INLINE_VISIBILITY 3670int 3671basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3672 size_type __n1, 3673 const basic_string& __str) const 3674{ 3675 return compare(__pos1, __n1, __str.data(), __str.size()); 3676} 3677 3678template <class _CharT, class _Traits, class _Allocator> 3679int 3680basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3681 size_type __n1, 3682 const basic_string& __str, 3683 size_type __pos2, 3684 size_type __n2) const 3685{ 3686 size_type __sz = __str.size(); 3687 if (__pos2 > __sz) 3688 this->__throw_out_of_range(); 3689 return compare(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, 3690 __sz - __pos2)); 3691} 3692 3693template <class _CharT, class _Traits, class _Allocator> 3694int 3695basic_string<_CharT, _Traits, _Allocator>::compare(const value_type* __s) const _NOEXCEPT 3696{ 3697 _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr"); 3698 return compare(0, npos, __s, traits_type::length(__s)); 3699} 3700 3701template <class _CharT, class _Traits, class _Allocator> 3702int 3703basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3704 size_type __n1, 3705 const value_type* __s) const 3706{ 3707 _LIBCPP_ASSERT(__s != nullptr, "string::compare(): received nullptr"); 3708 return compare(__pos1, __n1, __s, traits_type::length(__s)); 3709} 3710 3711template <class _CharT, class _Traits, class _Allocator> 3712int 3713basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1, 3714 size_type __n1, 3715 const value_type* __s, 3716 size_type __n2) const 3717{ 3718 _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::compare(): received nullptr"); 3719 size_type __sz = size(); 3720 if (__pos1 > __sz || __n2 == npos) 3721 this->__throw_out_of_range(); 3722 size_type __rlen = _VSTD::min(__n1, __sz - __pos1); 3723 int __r = traits_type::compare(data() + __pos1, __s, _VSTD::min(__rlen, __n2)); 3724 if (__r == 0) 3725 { 3726 if (__rlen < __n2) 3727 __r = -1; 3728 else if (__rlen > __n2) 3729 __r = 1; 3730 } 3731 return __r; 3732} 3733 3734// __invariants 3735 3736template<class _CharT, class _Traits, class _Allocator> 3737inline _LIBCPP_INLINE_VISIBILITY 3738bool 3739basic_string<_CharT, _Traits, _Allocator>::__invariants() const 3740{ 3741 if (size() > capacity()) 3742 return false; 3743 if (capacity() < __min_cap - 1) 3744 return false; 3745 if (data() == 0) 3746 return false; 3747 if (data()[size()] != value_type(0)) 3748 return false; 3749 return true; 3750} 3751 3752// operator== 3753 3754template<class _CharT, class _Traits, class _Allocator> 3755inline _LIBCPP_INLINE_VISIBILITY 3756bool 3757operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3758 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3759{ 3760 size_t __lhs_sz = __lhs.size(); 3761 return __lhs_sz == __rhs.size() && _Traits::compare(__lhs.data(), 3762 __rhs.data(), 3763 __lhs_sz) == 0; 3764} 3765 3766template<class _Allocator> 3767inline _LIBCPP_INLINE_VISIBILITY 3768bool 3769operator==(const basic_string<char, char_traits<char>, _Allocator>& __lhs, 3770 const basic_string<char, char_traits<char>, _Allocator>& __rhs) _NOEXCEPT 3771{ 3772 size_t __lhs_sz = __lhs.size(); 3773 if (__lhs_sz != __rhs.size()) 3774 return false; 3775 const char* __lp = __lhs.data(); 3776 const char* __rp = __rhs.data(); 3777 if (__lhs.__is_long()) 3778 return char_traits<char>::compare(__lp, __rp, __lhs_sz) == 0; 3779 for (; __lhs_sz != 0; --__lhs_sz, ++__lp, ++__rp) 3780 if (*__lp != *__rp) 3781 return false; 3782 return true; 3783} 3784 3785template<class _CharT, class _Traits, class _Allocator> 3786inline _LIBCPP_INLINE_VISIBILITY 3787bool 3788operator==(const _CharT* __lhs, 3789 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3790{ 3791 return __rhs.compare(__lhs) == 0; 3792} 3793 3794template<class _CharT, class _Traits, class _Allocator> 3795inline _LIBCPP_INLINE_VISIBILITY 3796bool 3797operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs, 3798 const _CharT* __rhs) _NOEXCEPT 3799{ 3800 return __lhs.compare(__rhs) == 0; 3801} 3802 3803// operator!= 3804 3805template<class _CharT, class _Traits, class _Allocator> 3806inline _LIBCPP_INLINE_VISIBILITY 3807bool 3808operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs, 3809 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3810{ 3811 return !(__lhs == __rhs); 3812} 3813 3814template<class _CharT, class _Traits, class _Allocator> 3815inline _LIBCPP_INLINE_VISIBILITY 3816bool 3817operator!=(const _CharT* __lhs, 3818 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3819{ 3820 return !(__lhs == __rhs); 3821} 3822 3823template<class _CharT, class _Traits, class _Allocator> 3824inline _LIBCPP_INLINE_VISIBILITY 3825bool 3826operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3827 const _CharT* __rhs) _NOEXCEPT 3828{ 3829 return !(__lhs == __rhs); 3830} 3831 3832// operator< 3833 3834template<class _CharT, class _Traits, class _Allocator> 3835inline _LIBCPP_INLINE_VISIBILITY 3836bool 3837operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3838 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3839{ 3840 return __lhs.compare(__rhs) < 0; 3841} 3842 3843template<class _CharT, class _Traits, class _Allocator> 3844inline _LIBCPP_INLINE_VISIBILITY 3845bool 3846operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3847 const _CharT* __rhs) _NOEXCEPT 3848{ 3849 return __lhs.compare(__rhs) < 0; 3850} 3851 3852template<class _CharT, class _Traits, class _Allocator> 3853inline _LIBCPP_INLINE_VISIBILITY 3854bool 3855operator< (const _CharT* __lhs, 3856 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3857{ 3858 return __rhs.compare(__lhs) > 0; 3859} 3860 3861// operator> 3862 3863template<class _CharT, class _Traits, class _Allocator> 3864inline _LIBCPP_INLINE_VISIBILITY 3865bool 3866operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3867 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3868{ 3869 return __rhs < __lhs; 3870} 3871 3872template<class _CharT, class _Traits, class _Allocator> 3873inline _LIBCPP_INLINE_VISIBILITY 3874bool 3875operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3876 const _CharT* __rhs) _NOEXCEPT 3877{ 3878 return __rhs < __lhs; 3879} 3880 3881template<class _CharT, class _Traits, class _Allocator> 3882inline _LIBCPP_INLINE_VISIBILITY 3883bool 3884operator> (const _CharT* __lhs, 3885 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3886{ 3887 return __rhs < __lhs; 3888} 3889 3890// operator<= 3891 3892template<class _CharT, class _Traits, class _Allocator> 3893inline _LIBCPP_INLINE_VISIBILITY 3894bool 3895operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3896 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3897{ 3898 return !(__rhs < __lhs); 3899} 3900 3901template<class _CharT, class _Traits, class _Allocator> 3902inline _LIBCPP_INLINE_VISIBILITY 3903bool 3904operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3905 const _CharT* __rhs) _NOEXCEPT 3906{ 3907 return !(__rhs < __lhs); 3908} 3909 3910template<class _CharT, class _Traits, class _Allocator> 3911inline _LIBCPP_INLINE_VISIBILITY 3912bool 3913operator<=(const _CharT* __lhs, 3914 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3915{ 3916 return !(__rhs < __lhs); 3917} 3918 3919// operator>= 3920 3921template<class _CharT, class _Traits, class _Allocator> 3922inline _LIBCPP_INLINE_VISIBILITY 3923bool 3924operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3925 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3926{ 3927 return !(__lhs < __rhs); 3928} 3929 3930template<class _CharT, class _Traits, class _Allocator> 3931inline _LIBCPP_INLINE_VISIBILITY 3932bool 3933operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3934 const _CharT* __rhs) _NOEXCEPT 3935{ 3936 return !(__lhs < __rhs); 3937} 3938 3939template<class _CharT, class _Traits, class _Allocator> 3940inline _LIBCPP_INLINE_VISIBILITY 3941bool 3942operator>=(const _CharT* __lhs, 3943 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT 3944{ 3945 return !(__lhs < __rhs); 3946} 3947 3948// operator + 3949 3950template<class _CharT, class _Traits, class _Allocator> 3951basic_string<_CharT, _Traits, _Allocator> 3952operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, 3953 const basic_string<_CharT, _Traits, _Allocator>& __rhs) 3954{ 3955 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 3956 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 3957 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3958 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz); 3959 __r.append(__rhs.data(), __rhs_sz); 3960 return __r; 3961} 3962 3963template<class _CharT, class _Traits, class _Allocator> 3964basic_string<_CharT, _Traits, _Allocator> 3965operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs) 3966{ 3967 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator()); 3968 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = _Traits::length(__lhs); 3969 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3970 __r.__init(__lhs, __lhs_sz, __lhs_sz + __rhs_sz); 3971 __r.append(__rhs.data(), __rhs_sz); 3972 return __r; 3973} 3974 3975template<class _CharT, class _Traits, class _Allocator> 3976basic_string<_CharT, _Traits, _Allocator> 3977operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs) 3978{ 3979 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator()); 3980 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size(); 3981 __r.__init(&__lhs, 1, 1 + __rhs_sz); 3982 __r.append(__rhs.data(), __rhs_sz); 3983 return __r; 3984} 3985 3986template<class _CharT, class _Traits, class _Allocator> 3987basic_string<_CharT, _Traits, _Allocator> 3988operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs) 3989{ 3990 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 3991 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 3992 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = _Traits::length(__rhs); 3993 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz); 3994 __r.append(__rhs, __rhs_sz); 3995 return __r; 3996} 3997 3998template<class _CharT, class _Traits, class _Allocator> 3999basic_string<_CharT, _Traits, _Allocator> 4000operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs) 4001{ 4002 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator()); 4003 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size(); 4004 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + 1); 4005 __r.push_back(__rhs); 4006 return __r; 4007} 4008 4009#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 4010 4011template<class _CharT, class _Traits, class _Allocator> 4012inline _LIBCPP_INLINE_VISIBILITY 4013basic_string<_CharT, _Traits, _Allocator> 4014operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs) 4015{ 4016 return _VSTD::move(__lhs.append(__rhs)); 4017} 4018 4019template<class _CharT, class _Traits, class _Allocator> 4020inline _LIBCPP_INLINE_VISIBILITY 4021basic_string<_CharT, _Traits, _Allocator> 4022operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs) 4023{ 4024 return _VSTD::move(__rhs.insert(0, __lhs)); 4025} 4026 4027template<class _CharT, class _Traits, class _Allocator> 4028inline _LIBCPP_INLINE_VISIBILITY 4029basic_string<_CharT, _Traits, _Allocator> 4030operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs) 4031{ 4032 return _VSTD::move(__lhs.append(__rhs)); 4033} 4034 4035template<class _CharT, class _Traits, class _Allocator> 4036inline _LIBCPP_INLINE_VISIBILITY 4037basic_string<_CharT, _Traits, _Allocator> 4038operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs) 4039{ 4040 return _VSTD::move(__rhs.insert(0, __lhs)); 4041} 4042 4043template<class _CharT, class _Traits, class _Allocator> 4044inline _LIBCPP_INLINE_VISIBILITY 4045basic_string<_CharT, _Traits, _Allocator> 4046operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs) 4047{ 4048 __rhs.insert(__rhs.begin(), __lhs); 4049 return _VSTD::move(__rhs); 4050} 4051 4052template<class _CharT, class _Traits, class _Allocator> 4053inline _LIBCPP_INLINE_VISIBILITY 4054basic_string<_CharT, _Traits, _Allocator> 4055operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const _CharT* __rhs) 4056{ 4057 return _VSTD::move(__lhs.append(__rhs)); 4058} 4059 4060template<class _CharT, class _Traits, class _Allocator> 4061inline _LIBCPP_INLINE_VISIBILITY 4062basic_string<_CharT, _Traits, _Allocator> 4063operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs) 4064{ 4065 __lhs.push_back(__rhs); 4066 return _VSTD::move(__lhs); 4067} 4068 4069#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 4070 4071// swap 4072 4073template<class _CharT, class _Traits, class _Allocator> 4074inline _LIBCPP_INLINE_VISIBILITY 4075void 4076swap(basic_string<_CharT, _Traits, _Allocator>& __lhs, 4077 basic_string<_CharT, _Traits, _Allocator>& __rhs) 4078 _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs))) 4079{ 4080 __lhs.swap(__rhs); 4081} 4082 4083#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 4084 4085typedef basic_string<char16_t> u16string; 4086typedef basic_string<char32_t> u32string; 4087 4088#endif // _LIBCPP_HAS_NO_UNICODE_CHARS 4089 4090_LIBCPP_FUNC_VIS int stoi (const string& __str, size_t* __idx = 0, int __base = 10); 4091_LIBCPP_FUNC_VIS long stol (const string& __str, size_t* __idx = 0, int __base = 10); 4092_LIBCPP_FUNC_VIS unsigned long stoul (const string& __str, size_t* __idx = 0, int __base = 10); 4093_LIBCPP_FUNC_VIS long long stoll (const string& __str, size_t* __idx = 0, int __base = 10); 4094_LIBCPP_FUNC_VIS unsigned long long stoull(const string& __str, size_t* __idx = 0, int __base = 10); 4095 4096_LIBCPP_FUNC_VIS float stof (const string& __str, size_t* __idx = 0); 4097_LIBCPP_FUNC_VIS double stod (const string& __str, size_t* __idx = 0); 4098_LIBCPP_FUNC_VIS long double stold(const string& __str, size_t* __idx = 0); 4099 4100_LIBCPP_FUNC_VIS string to_string(int __val); 4101_LIBCPP_FUNC_VIS string to_string(unsigned __val); 4102_LIBCPP_FUNC_VIS string to_string(long __val); 4103_LIBCPP_FUNC_VIS string to_string(unsigned long __val); 4104_LIBCPP_FUNC_VIS string to_string(long long __val); 4105_LIBCPP_FUNC_VIS string to_string(unsigned long long __val); 4106_LIBCPP_FUNC_VIS string to_string(float __val); 4107_LIBCPP_FUNC_VIS string to_string(double __val); 4108_LIBCPP_FUNC_VIS string to_string(long double __val); 4109 4110_LIBCPP_FUNC_VIS int stoi (const wstring& __str, size_t* __idx = 0, int __base = 10); 4111_LIBCPP_FUNC_VIS long stol (const wstring& __str, size_t* __idx = 0, int __base = 10); 4112_LIBCPP_FUNC_VIS unsigned long stoul (const wstring& __str, size_t* __idx = 0, int __base = 10); 4113_LIBCPP_FUNC_VIS long long stoll (const wstring& __str, size_t* __idx = 0, int __base = 10); 4114_LIBCPP_FUNC_VIS unsigned long long stoull(const wstring& __str, size_t* __idx = 0, int __base = 10); 4115 4116_LIBCPP_FUNC_VIS float stof (const wstring& __str, size_t* __idx = 0); 4117_LIBCPP_FUNC_VIS double stod (const wstring& __str, size_t* __idx = 0); 4118_LIBCPP_FUNC_VIS long double stold(const wstring& __str, size_t* __idx = 0); 4119 4120_LIBCPP_FUNC_VIS wstring to_wstring(int __val); 4121_LIBCPP_FUNC_VIS wstring to_wstring(unsigned __val); 4122_LIBCPP_FUNC_VIS wstring to_wstring(long __val); 4123_LIBCPP_FUNC_VIS wstring to_wstring(unsigned long __val); 4124_LIBCPP_FUNC_VIS wstring to_wstring(long long __val); 4125_LIBCPP_FUNC_VIS wstring to_wstring(unsigned long long __val); 4126_LIBCPP_FUNC_VIS wstring to_wstring(float __val); 4127_LIBCPP_FUNC_VIS wstring to_wstring(double __val); 4128_LIBCPP_FUNC_VIS wstring to_wstring(long double __val); 4129 4130template<class _CharT, class _Traits, class _Allocator> 4131 const typename basic_string<_CharT, _Traits, _Allocator>::size_type 4132 basic_string<_CharT, _Traits, _Allocator>::npos; 4133 4134template<class _CharT, class _Traits, class _Allocator> 4135struct _LIBCPP_TYPE_VIS_ONLY hash<basic_string<_CharT, _Traits, _Allocator> > 4136 : public unary_function<basic_string<_CharT, _Traits, _Allocator>, size_t> 4137{ 4138 size_t 4139 operator()(const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT; 4140}; 4141 4142template<class _CharT, class _Traits, class _Allocator> 4143size_t 4144hash<basic_string<_CharT, _Traits, _Allocator> >::operator()( 4145 const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT 4146{ 4147 return __do_string_hash(__val.data(), __val.data() + __val.size()); 4148} 4149 4150template<class _CharT, class _Traits, class _Allocator> 4151basic_ostream<_CharT, _Traits>& 4152operator<<(basic_ostream<_CharT, _Traits>& __os, 4153 const basic_string<_CharT, _Traits, _Allocator>& __str); 4154 4155template<class _CharT, class _Traits, class _Allocator> 4156basic_istream<_CharT, _Traits>& 4157operator>>(basic_istream<_CharT, _Traits>& __is, 4158 basic_string<_CharT, _Traits, _Allocator>& __str); 4159 4160template<class _CharT, class _Traits, class _Allocator> 4161basic_istream<_CharT, _Traits>& 4162getline(basic_istream<_CharT, _Traits>& __is, 4163 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm); 4164 4165template<class _CharT, class _Traits, class _Allocator> 4166inline _LIBCPP_INLINE_VISIBILITY 4167basic_istream<_CharT, _Traits>& 4168getline(basic_istream<_CharT, _Traits>& __is, 4169 basic_string<_CharT, _Traits, _Allocator>& __str); 4170 4171#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 4172 4173template<class _CharT, class _Traits, class _Allocator> 4174inline _LIBCPP_INLINE_VISIBILITY 4175basic_istream<_CharT, _Traits>& 4176getline(basic_istream<_CharT, _Traits>&& __is, 4177 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm); 4178 4179template<class _CharT, class _Traits, class _Allocator> 4180inline _LIBCPP_INLINE_VISIBILITY 4181basic_istream<_CharT, _Traits>& 4182getline(basic_istream<_CharT, _Traits>&& __is, 4183 basic_string<_CharT, _Traits, _Allocator>& __str); 4184 4185#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 4186 4187#if _LIBCPP_DEBUG_LEVEL >= 2 4188 4189template<class _CharT, class _Traits, class _Allocator> 4190bool 4191basic_string<_CharT, _Traits, _Allocator>::__dereferenceable(const const_iterator* __i) const 4192{ 4193 return this->data() <= _VSTD::__to_raw_pointer(__i->base()) && 4194 _VSTD::__to_raw_pointer(__i->base()) < this->data() + this->size(); 4195} 4196 4197template<class _CharT, class _Traits, class _Allocator> 4198bool 4199basic_string<_CharT, _Traits, _Allocator>::__decrementable(const const_iterator* __i) const 4200{ 4201 return this->data() < _VSTD::__to_raw_pointer(__i->base()) && 4202 _VSTD::__to_raw_pointer(__i->base()) <= this->data() + this->size(); 4203} 4204 4205template<class _CharT, class _Traits, class _Allocator> 4206bool 4207basic_string<_CharT, _Traits, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const 4208{ 4209 const value_type* __p = _VSTD::__to_raw_pointer(__i->base()) + __n; 4210 return this->data() <= __p && __p <= this->data() + this->size(); 4211} 4212 4213template<class _CharT, class _Traits, class _Allocator> 4214bool 4215basic_string<_CharT, _Traits, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 4216{ 4217 const value_type* __p = _VSTD::__to_raw_pointer(__i->base()) + __n; 4218 return this->data() <= __p && __p < this->data() + this->size(); 4219} 4220 4221#endif // _LIBCPP_DEBUG_LEVEL >= 2 4222 4223#if _LIBCPP_STD_VER > 11 4224// Literal suffixes for basic_string [basic.string.literals] 4225inline namespace literals 4226{ 4227 inline namespace string_literals 4228 { 4229 inline _LIBCPP_INLINE_VISIBILITY 4230 basic_string<char> operator "" s( const char *__str, size_t __len ) 4231 { 4232 return basic_string<char> (__str, __len); 4233 } 4234 4235 inline _LIBCPP_INLINE_VISIBILITY 4236 basic_string<wchar_t> operator "" s( const wchar_t *__str, size_t __len ) 4237 { 4238 return basic_string<wchar_t> (__str, __len); 4239 } 4240 4241 inline _LIBCPP_INLINE_VISIBILITY 4242 basic_string<char16_t> operator "" s( const char16_t *__str, size_t __len ) 4243 { 4244 return basic_string<char16_t> (__str, __len); 4245 } 4246 4247 inline _LIBCPP_INLINE_VISIBILITY 4248 basic_string<char32_t> operator "" s( const char32_t *__str, size_t __len ) 4249 { 4250 return basic_string<char32_t> (__str, __len); 4251 } 4252 } 4253} 4254#endif 4255 4256_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<char>) 4257_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS basic_string<wchar_t>) 4258_LIBCPP_EXTERN_TEMPLATE(string operator+<char, char_traits<char>, allocator<char> >(char const*, string const&)) 4259 4260_LIBCPP_END_NAMESPACE_STD 4261 4262#endif // _LIBCPP_STRING 4263