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