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