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