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