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