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