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