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