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