1// Components for manipulating sequences of characters -*- C++ -*-
2
3// Copyright (C) 1997-2022 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/basic_string.tcc
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{string}
28 */
29
30//
31// ISO C++ 14882: 21 Strings library
32//
33
34// Written by Jason Merrill based upon the specification by Takanori Adachi
35// in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882.
36// Non-reference-counted implementation written by Paolo Carlini and
37// updated by Jonathan Wakely for ISO-14882-2011.
38
39#ifndef _BASIC_STRING_TCC
40#define _BASIC_STRING_TCC 1
41
42#pragma GCC system_header
43
44#include <bits/cxxabi_forced.h>
45
46namespace std _GLIBCXX_VISIBILITY(default)
47{
48_GLIBCXX_BEGIN_NAMESPACE_VERSION
49
50#if _GLIBCXX_USE_CXX11_ABI
51
52 template<typename _CharT, typename _Traits, typename _Alloc>
53 const typename basic_string<_CharT, _Traits, _Alloc>::size_type
54 basic_string<_CharT, _Traits, _Alloc>::npos;
55
56 template<typename _CharT, typename _Traits, typename _Alloc>
57 _GLIBCXX20_CONSTEXPR
58 void
59 basic_string<_CharT, _Traits, _Alloc>::
60 swap(basic_string& __s) _GLIBCXX_NOEXCEPT
61 {
62 if (this == std::__addressof(__s))
63 return;
64
65 _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
66
67 if (_M_is_local())
68 if (__s._M_is_local())
69 {
70 if (length() && __s.length())
71 {
72 _CharT __tmp_data[_S_local_capacity + 1];
73 traits_type::copy(__tmp_data, __s._M_local_buf,
74 __s.length() + 1);
75 traits_type::copy(__s._M_local_buf, _M_local_buf,
76 length() + 1);
77 traits_type::copy(_M_local_buf, __tmp_data,
78 __s.length() + 1);
79 }
80 else if (__s.length())
81 {
82 traits_type::copy(_M_local_buf, __s._M_local_buf,
83 __s.length() + 1);
84 _M_length(__s.length());
85 __s._M_set_length(0);
86 return;
87 }
88 else if (length())
89 {
90 traits_type::copy(__s._M_local_buf, _M_local_buf,
91 length() + 1);
92 __s._M_length(length());
93 _M_set_length(0);
94 return;
95 }
96 }
97 else
98 {
99 const size_type __tmp_capacity = __s._M_allocated_capacity;
100 traits_type::copy(__s._M_local_buf, _M_local_buf,
101 length() + 1);
102 _M_data(__s._M_data());
103 __s._M_data(__s._M_local_buf);
104 _M_capacity(__tmp_capacity);
105 }
106 else
107 {
108 const size_type __tmp_capacity = _M_allocated_capacity;
109 if (__s._M_is_local())
110 {
111 traits_type::copy(_M_local_buf, __s._M_local_buf,
112 __s.length() + 1);
113 __s._M_data(_M_data());
114 _M_data(_M_local_buf);
115 }
116 else
117 {
118 pointer __tmp_ptr = _M_data();
119 _M_data(__s._M_data());
120 __s._M_data(__tmp_ptr);
121 _M_capacity(__s._M_allocated_capacity);
122 }
123 __s._M_capacity(__tmp_capacity);
124 }
125
126 const size_type __tmp_length = length();
127 _M_length(__s.length());
128 __s._M_length(__tmp_length);
129 }
130
131 template<typename _CharT, typename _Traits, typename _Alloc>
132 _GLIBCXX20_CONSTEXPR
133 typename basic_string<_CharT, _Traits, _Alloc>::pointer
134 basic_string<_CharT, _Traits, _Alloc>::
135 _M_create(size_type& __capacity, size_type __old_capacity)
136 {
137 // _GLIBCXX_RESOLVE_LIB_DEFECTS
138 // 83. String::npos vs. string::max_size()
139 if (__capacity > max_size())
140 std::__throw_length_error(__N("basic_string::_M_create"));
141
142 // The below implements an exponential growth policy, necessary to
143 // meet amortized linear time requirements of the library: see
144 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
145 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
146 {
147 __capacity = 2 * __old_capacity;
148 // Never allocate a string bigger than max_size.
149 if (__capacity > max_size())
150 __capacity = max_size();
151 }
152
153 // NB: Need an array of char_type[__capacity], plus a terminating
154 // null char_type() element.
155 return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);
156 }
157
158 // NB: This is the special case for Input Iterators, used in
159 // istreambuf_iterators, etc.
160 // Input Iterators have a cost structure very different from
161 // pointers, calling for a different coding style.
162 template<typename _CharT, typename _Traits, typename _Alloc>
163 template<typename _InIterator>
164 _GLIBCXX20_CONSTEXPR
165 void
166 basic_string<_CharT, _Traits, _Alloc>::
167 _M_construct(_InIterator __beg, _InIterator __end,
168 std::input_iterator_tag)
169 {
170 size_type __len = 0;
171 size_type __capacity = size_type(_S_local_capacity);
172
173 pointer __p = _M_use_local_data();
174
175 while (__beg != __end && __len < __capacity)
176 {
177 __p[__len++] = *__beg;
178 ++__beg;
179 }
180
181 struct _Guard
182 {
183 _GLIBCXX20_CONSTEXPR
184 explicit _Guard(basic_string* __s) : _M_guarded(__s) { }
185
186 _GLIBCXX20_CONSTEXPR
187 ~_Guard() { if (_M_guarded) _M_guarded->_M_dispose(); }
188
189 basic_string* _M_guarded;
190 } __guard(this);
191
192 while (__beg != __end)
193 {
194 if (__len == __capacity)
195 {
196 // Allocate more space.
197 __capacity = __len + 1;
198 pointer __another = _M_create(__capacity, __len);
199 this->_S_copy(__another, _M_data(), __len);
200 _M_dispose();
201 _M_data(__another);
202 _M_capacity(__capacity);
203 }
204 traits_type::assign(_M_data()[__len++], *__beg);
205 ++__beg;
206 }
207
208 __guard._M_guarded = 0;
209
210 _M_set_length(__len);
211 }
212
213 template<typename _CharT, typename _Traits, typename _Alloc>
214 template<typename _InIterator>
215 _GLIBCXX20_CONSTEXPR
216 void
217 basic_string<_CharT, _Traits, _Alloc>::
218 _M_construct(_InIterator __beg, _InIterator __end,
219 std::forward_iterator_tag)
220 {
221 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
222
223 if (__dnew > size_type(_S_local_capacity))
224 {
225 _M_data(_M_create(__dnew, size_type(0)));
226 _M_capacity(__dnew);
227 }
228 else
229 _M_use_local_data();
230
231 // Check for out_of_range and length_error exceptions.
232 struct _Guard
233 {
234 _GLIBCXX20_CONSTEXPR
235 explicit _Guard(basic_string* __s) : _M_guarded(__s) { }
236
237 _GLIBCXX20_CONSTEXPR
238 ~_Guard() { if (_M_guarded) _M_guarded->_M_dispose(); }
239
240 basic_string* _M_guarded;
241 } __guard(this);
242
243 this->_S_copy_chars(_M_data(), __beg, __end);
244
245 __guard._M_guarded = 0;
246
247 _M_set_length(__dnew);
248 }
249
250 template<typename _CharT, typename _Traits, typename _Alloc>
251 _GLIBCXX20_CONSTEXPR
252 void
253 basic_string<_CharT, _Traits, _Alloc>::
254 _M_construct(size_type __n, _CharT __c)
255 {
256 if (__n > size_type(_S_local_capacity))
257 {
258 _M_data(_M_create(__n, size_type(0)));
259 _M_capacity(__n);
260 }
261 else
262 _M_use_local_data();
263
264 if (__n)
265 this->_S_assign(_M_data(), __n, __c);
266
267 _M_set_length(__n);
268 }
269
270 template<typename _CharT, typename _Traits, typename _Alloc>
271 _GLIBCXX20_CONSTEXPR
272 void
273 basic_string<_CharT, _Traits, _Alloc>::
274 _M_assign(const basic_string& __str)
275 {
276 if (this != std::__addressof(__str))
277 {
278 const size_type __rsize = __str.length();
279 const size_type __capacity = capacity();
280
281 if (__rsize > __capacity)
282 {
283 size_type __new_capacity = __rsize;
284 pointer __tmp = _M_create(__new_capacity, __capacity);
285 _M_dispose();
286 _M_data(__tmp);
287 _M_capacity(__new_capacity);
288 }
289
290 if (__rsize)
291 this->_S_copy(_M_data(), __str._M_data(), __rsize);
292
293 _M_set_length(__rsize);
294 }
295 }
296
297 template<typename _CharT, typename _Traits, typename _Alloc>
298 _GLIBCXX20_CONSTEXPR
299 void
300 basic_string<_CharT, _Traits, _Alloc>::
301 reserve(size_type __res)
302 {
303 const size_type __capacity = capacity();
304 // _GLIBCXX_RESOLVE_LIB_DEFECTS
305 // 2968. Inconsistencies between basic_string reserve and
306 // vector/unordered_map/unordered_set reserve functions
307 // P0966 reserve should not shrink
308 if (__res <= __capacity)
309 return;
310
311 pointer __tmp = _M_create(__res, __capacity);
312 this->_S_copy(__tmp, _M_data(), length() + 1);
313 _M_dispose();
314 _M_data(__tmp);
315 _M_capacity(__res);
316 }
317
318 template<typename _CharT, typename _Traits, typename _Alloc>
319 _GLIBCXX20_CONSTEXPR
320 void
321 basic_string<_CharT, _Traits, _Alloc>::
322 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
323 size_type __len2)
324 {
325 const size_type __how_much = length() - __pos - __len1;
326
327 size_type __new_capacity = length() + __len2 - __len1;
328 pointer __r = _M_create(__new_capacity, capacity());
329
330 if (__pos)
331 this->_S_copy(__r, _M_data(), __pos);
332 if (__s && __len2)
333 this->_S_copy(__r + __pos, __s, __len2);
334 if (__how_much)
335 this->_S_copy(__r + __pos + __len2,
336 _M_data() + __pos + __len1, __how_much);
337
338 _M_dispose();
339 _M_data(__r);
340 _M_capacity(__new_capacity);
341 }
342
343 template<typename _CharT, typename _Traits, typename _Alloc>
344 _GLIBCXX20_CONSTEXPR
345 void
346 basic_string<_CharT, _Traits, _Alloc>::
347 _M_erase(size_type __pos, size_type __n)
348 {
349 const size_type __how_much = length() - __pos - __n;
350
351 if (__how_much && __n)
352 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
353
354 _M_set_length(length() - __n);
355 }
356
357 template<typename _CharT, typename _Traits, typename _Alloc>
358 _GLIBCXX20_CONSTEXPR
359 void
360 basic_string<_CharT, _Traits, _Alloc>::
361 reserve()
362 {
363 if (_M_is_local())
364 return;
365
366 const size_type __length = length();
367 const size_type __capacity = _M_allocated_capacity;
368
369 if (__length <= size_type(_S_local_capacity))
370 {
371 this->_S_copy(_M_use_local_data(), _M_data(), __length + 1);
372 _M_destroy(__capacity);
373 _M_data(_M_local_data());
374 }
375#if __cpp_exceptions
376 else if (__length < __capacity)
377 try
378 {
379 pointer __tmp
380 = _Alloc_traits::allocate(_M_get_allocator(), __length + 1);
381 this->_S_copy(__tmp, _M_data(), __length + 1);
382 _M_dispose();
383 _M_data(__tmp);
384 _M_capacity(__length);
385 }
386 catch (const __cxxabiv1::__forced_unwind&)
387 { throw; }
388 catch (...)
389 { /* swallow the exception */ }
390#endif
391 }
392
393 template<typename _CharT, typename _Traits, typename _Alloc>
394 _GLIBCXX20_CONSTEXPR
395 void
396 basic_string<_CharT, _Traits, _Alloc>::
397 resize(size_type __n, _CharT __c)
398 {
399 const size_type __size = this->size();
400 if (__size < __n)
401 this->append(__n - __size, __c);
402 else if (__n < __size)
403 this->_M_set_length(__n);
404 }
405
406 template<typename _CharT, typename _Traits, typename _Alloc>
407 _GLIBCXX20_CONSTEXPR
408 basic_string<_CharT, _Traits, _Alloc>&
409 basic_string<_CharT, _Traits, _Alloc>::
410 _M_append(const _CharT* __s, size_type __n)
411 {
412 const size_type __len = __n + this->size();
413
414 if (__len <= this->capacity())
415 {
416 if (__n)
417 this->_S_copy(this->_M_data() + this->size(), __s, __n);
418 }
419 else
420 this->_M_mutate(this->size(), size_type(0), __s, __n);
421
422 this->_M_set_length(__len);
423 return *this;
424 }
425
426 template<typename _CharT, typename _Traits, typename _Alloc>
427 template<typename _InputIterator>
428 _GLIBCXX20_CONSTEXPR
429 basic_string<_CharT, _Traits, _Alloc>&
430 basic_string<_CharT, _Traits, _Alloc>::
431 _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
432 _InputIterator __k1, _InputIterator __k2,
433 std::__false_type)
434 {
435 // _GLIBCXX_RESOLVE_LIB_DEFECTS
436 // 2788. unintentionally require a default constructible allocator
437 const basic_string __s(__k1, __k2, this->get_allocator());
438 const size_type __n1 = __i2 - __i1;
439 return _M_replace(__i1 - begin(), __n1, __s._M_data(),
440 __s.size());
441 }
442
443 template<typename _CharT, typename _Traits, typename _Alloc>
444 _GLIBCXX20_CONSTEXPR
445 basic_string<_CharT, _Traits, _Alloc>&
446 basic_string<_CharT, _Traits, _Alloc>::
447 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
448 _CharT __c)
449 {
450 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
451
452 const size_type __old_size = this->size();
453 const size_type __new_size = __old_size + __n2 - __n1;
454
455 if (__new_size <= this->capacity())
456 {
457 pointer __p = this->_M_data() + __pos1;
458
459 const size_type __how_much = __old_size - __pos1 - __n1;
460 if (__how_much && __n1 != __n2)
461 this->_S_move(__p + __n2, __p + __n1, __how_much);
462 }
463 else
464 this->_M_mutate(__pos1, __n1, 0, __n2);
465
466 if (__n2)
467 this->_S_assign(this->_M_data() + __pos1, __n2, __c);
468
469 this->_M_set_length(__new_size);
470 return *this;
471 }
472
473 template<typename _CharT, typename _Traits, typename _Alloc>
474 _GLIBCXX20_CONSTEXPR
475 basic_string<_CharT, _Traits, _Alloc>&
476 basic_string<_CharT, _Traits, _Alloc>::
477 _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
478 const size_type __len2)
479 {
480 _M_check_length(__len1, __len2, "basic_string::_M_replace");
481
482 const size_type __old_size = this->size();
483 const size_type __new_size = __old_size + __len2 - __len1;
484
485 if (__new_size <= this->capacity())
486 {
487 pointer __p = this->_M_data() + __pos;
488
489 const size_type __how_much = __old_size - __pos - __len1;
490#if __cpp_lib_is_constant_evaluated
491 if (std::is_constant_evaluated())
492 {
493 auto __newp = _Alloc_traits::allocate(_M_get_allocator(),
494 __new_size);
495 _S_copy(__newp, this->_M_data(), __pos);
496 _S_copy(__newp + __pos, __s, __len2);
497 _S_copy(__newp + __pos + __len2, __p + __len1, __how_much);
498 _S_copy(this->_M_data(), __newp, __new_size);
499 this->_M_get_allocator().deallocate(__newp, __new_size);
500 }
501 else
502#endif
503 if (_M_disjunct(__s))
504 {
505 if (__how_much && __len1 != __len2)
506 this->_S_move(__p + __len2, __p + __len1, __how_much);
507 if (__len2)
508 this->_S_copy(__p, __s, __len2);
509 }
510 else
511 {
512 // Work in-place.
513 if (__len2 && __len2 <= __len1)
514 this->_S_move(__p, __s, __len2);
515 if (__how_much && __len1 != __len2)
516 this->_S_move(__p + __len2, __p + __len1, __how_much);
517 if (__len2 > __len1)
518 {
519 if (__s + __len2 <= __p + __len1)
520 this->_S_move(__p, __s, __len2);
521 else if (__s >= __p + __len1)
522 {
523 // Hint to middle end that __p and __s overlap
524 // (PR 98465).
525 const size_type __poff = (__s - __p) + (__len2 - __len1);
526 this->_S_copy(__p, __p + __poff, __len2);
527 }
528 else
529 {
530 const size_type __nleft = (__p + __len1) - __s;
531 this->_S_move(__p, __s, __nleft);
532 this->_S_copy(__p + __nleft, __p + __len2,
533 __len2 - __nleft);
534 }
535 }
536 }
537 }
538 else
539 this->_M_mutate(__pos, __len1, __s, __len2);
540
541 this->_M_set_length(__new_size);
542 return *this;
543 }
544
545 template<typename _CharT, typename _Traits, typename _Alloc>
546 _GLIBCXX20_CONSTEXPR
547 typename basic_string<_CharT, _Traits, _Alloc>::size_type
548 basic_string<_CharT, _Traits, _Alloc>::
549 copy(_CharT* __s, size_type __n, size_type __pos) const
550 {
551 _M_check(__pos, "basic_string::copy");
552 __n = _M_limit(__pos, __n);
553 __glibcxx_requires_string_len(__s, __n);
554 if (__n)
555 _S_copy(__s, _M_data() + __pos, __n);
556 // 21.3.5.7 par 3: do not append null. (good.)
557 return __n;
558 }
559
560#if __cplusplus > 202002L
561 template<typename _CharT, typename _Traits, typename _Alloc>
562 template<typename _Operation>
563 constexpr void
564 basic_string<_CharT, _Traits, _Alloc>::
565 resize_and_overwrite(size_type __n, _Operation __op)
566 {
567 const size_type __capacity = capacity();
568 _CharT* __p;
569 if (__n > __capacity)
570 {
571 __p = _M_create(__n, __capacity);
572 this->_S_copy(__p, _M_data(), length()); // exclude trailing null
573#if __cpp_lib_is_constant_evaluated
574 if (std::is_constant_evaluated())
575 traits_type::assign(__p + length(), __n - length(), _CharT());
576#endif
577 _M_dispose();
578 _M_data(__p);
579 _M_capacity(__n);
580 }
581 else
582 __p = _M_data();
583 struct _Terminator {
584 constexpr ~_Terminator() { _M_this->_M_set_length(_M_r); }
585 basic_string* _M_this;
586 size_type _M_r;
587 };
588 _Terminator __term{this};
589 const size_type __n2 [[maybe_unused]] = __n;
590 __term._M_r = std::move(__op)(__p, __n);
591 _GLIBCXX_DEBUG_ASSERT(__term._M_r >= 0 && __term._M_r <= __n2);
592 }
593#endif // C++23
594
595#endif // _GLIBCXX_USE_CXX11_ABI
596
597#if __cpp_lib_constexpr_string >= 201907L
598# define _GLIBCXX_STRING_CONSTEXPR constexpr
599#else
600# define _GLIBCXX_STRING_CONSTEXPR
601#endif
602
603 template<typename _CharT, typename _Traits, typename _Alloc>
604 _GLIBCXX20_CONSTEXPR
605 basic_string<_CharT, _Traits, _Alloc>
606 operator+(const _CharT* __lhs,
607 const basic_string<_CharT, _Traits, _Alloc>& __rhs)
608 {
609 __glibcxx_requires_string(__lhs);
610 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
611 typedef typename __string_type::size_type __size_type;
612 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
613 rebind<_CharT>::other _Char_alloc_type;
614 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
615 const __size_type __len = _Traits::length(__lhs);
616 __string_type __str(_Alloc_traits::_S_select_on_copy(
617 __rhs.get_allocator()));
618 __str.reserve(__len + __rhs.size());
619 __str.append(__lhs, __len);
620 __str.append(__rhs);
621 return __str;
622 }
623
624 template<typename _CharT, typename _Traits, typename _Alloc>
625 _GLIBCXX20_CONSTEXPR
626 basic_string<_CharT, _Traits, _Alloc>
627 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
628 {
629 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
630 typedef typename __string_type::size_type __size_type;
631 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
632 rebind<_CharT>::other _Char_alloc_type;
633 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
634 __string_type __str(_Alloc_traits::_S_select_on_copy(
635 __rhs.get_allocator()));
636 const __size_type __len = __rhs.size();
637 __str.reserve(__len + 1);
638 __str.append(__size_type(1), __lhs);
639 __str.append(__rhs);
640 return __str;
641 }
642
643 template<typename _CharT, typename _Traits, typename _Alloc>
644 _GLIBCXX_STRING_CONSTEXPR
645 typename basic_string<_CharT, _Traits, _Alloc>::size_type
646 basic_string<_CharT, _Traits, _Alloc>::
647 find(const _CharT* __s, size_type __pos, size_type __n) const
648 _GLIBCXX_NOEXCEPT
649 {
650 __glibcxx_requires_string_len(__s, __n);
651 const size_type __size = this->size();
652
653 if (__n == 0)
654 return __pos <= __size ? __pos : npos;
655 if (__pos >= __size)
656 return npos;
657
658 const _CharT __elem0 = __s[0];
659 const _CharT* const __data = data();
660 const _CharT* __first = __data + __pos;
661 const _CharT* const __last = __data + __size;
662 size_type __len = __size - __pos;
663
664 while (__len >= __n)
665 {
666 // Find the first occurrence of __elem0:
667 __first = traits_type::find(__first, __len - __n + 1, __elem0);
668 if (!__first)
669 return npos;
670 // Compare the full strings from the first occurrence of __elem0.
671 // We already know that __first[0] == __s[0] but compare them again
672 // anyway because __s is probably aligned, which helps memcmp.
673 if (traits_type::compare(__first, __s, __n) == 0)
674 return __first - __data;
675 __len = __last - ++__first;
676 }
677 return npos;
678 }
679
680 template<typename _CharT, typename _Traits, typename _Alloc>
681 _GLIBCXX_STRING_CONSTEXPR
682 typename basic_string<_CharT, _Traits, _Alloc>::size_type
683 basic_string<_CharT, _Traits, _Alloc>::
684 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
685 {
686 size_type __ret = npos;
687 const size_type __size = this->size();
688 if (__pos < __size)
689 {
690 const _CharT* __data = _M_data();
691 const size_type __n = __size - __pos;
692 const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
693 if (__p)
694 __ret = __p - __data;
695 }
696 return __ret;
697 }
698
699 template<typename _CharT, typename _Traits, typename _Alloc>
700 _GLIBCXX_STRING_CONSTEXPR
701 typename basic_string<_CharT, _Traits, _Alloc>::size_type
702 basic_string<_CharT, _Traits, _Alloc>::
703 rfind(const _CharT* __s, size_type __pos, size_type __n) const
704 _GLIBCXX_NOEXCEPT
705 {
706 __glibcxx_requires_string_len(__s, __n);
707 const size_type __size = this->size();
708 if (__n <= __size)
709 {
710 __pos = std::min(size_type(__size - __n), __pos);
711 const _CharT* __data = _M_data();
712 do
713 {
714 if (traits_type::compare(__data + __pos, __s, __n) == 0)
715 return __pos;
716 }
717 while (__pos-- > 0);
718 }
719 return npos;
720 }
721
722 template<typename _CharT, typename _Traits, typename _Alloc>
723 _GLIBCXX_STRING_CONSTEXPR
724 typename basic_string<_CharT, _Traits, _Alloc>::size_type
725 basic_string<_CharT, _Traits, _Alloc>::
726 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
727 {
728 size_type __size = this->size();
729 if (__size)
730 {
731 if (--__size > __pos)
732 __size = __pos;
733 for (++__size; __size-- > 0; )
734 if (traits_type::eq(_M_data()[__size], __c))
735 return __size;
736 }
737 return npos;
738 }
739
740 template<typename _CharT, typename _Traits, typename _Alloc>
741 _GLIBCXX_STRING_CONSTEXPR
742 typename basic_string<_CharT, _Traits, _Alloc>::size_type
743 basic_string<_CharT, _Traits, _Alloc>::
744 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
745 _GLIBCXX_NOEXCEPT
746 {
747 __glibcxx_requires_string_len(__s, __n);
748 for (; __n && __pos < this->size(); ++__pos)
749 {
750 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
751 if (__p)
752 return __pos;
753 }
754 return npos;
755 }
756
757 template<typename _CharT, typename _Traits, typename _Alloc>
758 _GLIBCXX_STRING_CONSTEXPR
759 typename basic_string<_CharT, _Traits, _Alloc>::size_type
760 basic_string<_CharT, _Traits, _Alloc>::
761 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
762 _GLIBCXX_NOEXCEPT
763 {
764 __glibcxx_requires_string_len(__s, __n);
765 size_type __size = this->size();
766 if (__size && __n)
767 {
768 if (--__size > __pos)
769 __size = __pos;
770 do
771 {
772 if (traits_type::find(__s, __n, _M_data()[__size]))
773 return __size;
774 }
775 while (__size-- != 0);
776 }
777 return npos;
778 }
779
780 template<typename _CharT, typename _Traits, typename _Alloc>
781 _GLIBCXX_STRING_CONSTEXPR
782 typename basic_string<_CharT, _Traits, _Alloc>::size_type
783 basic_string<_CharT, _Traits, _Alloc>::
784 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
785 _GLIBCXX_NOEXCEPT
786 {
787 __glibcxx_requires_string_len(__s, __n);
788 for (; __pos < this->size(); ++__pos)
789 if (!traits_type::find(__s, __n, _M_data()[__pos]))
790 return __pos;
791 return npos;
792 }
793
794 template<typename _CharT, typename _Traits, typename _Alloc>
795 _GLIBCXX_STRING_CONSTEXPR
796 typename basic_string<_CharT, _Traits, _Alloc>::size_type
797 basic_string<_CharT, _Traits, _Alloc>::
798 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
799 {
800 for (; __pos < this->size(); ++__pos)
801 if (!traits_type::eq(_M_data()[__pos], __c))
802 return __pos;
803 return npos;
804 }
805
806 template<typename _CharT, typename _Traits, typename _Alloc>
807 _GLIBCXX_STRING_CONSTEXPR
808 typename basic_string<_CharT, _Traits, _Alloc>::size_type
809 basic_string<_CharT, _Traits, _Alloc>::
810 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
811 _GLIBCXX_NOEXCEPT
812 {
813 __glibcxx_requires_string_len(__s, __n);
814 size_type __size = this->size();
815 if (__size)
816 {
817 if (--__size > __pos)
818 __size = __pos;
819 do
820 {
821 if (!traits_type::find(__s, __n, _M_data()[__size]))
822 return __size;
823 }
824 while (__size--);
825 }
826 return npos;
827 }
828
829 template<typename _CharT, typename _Traits, typename _Alloc>
830 _GLIBCXX_STRING_CONSTEXPR
831 typename basic_string<_CharT, _Traits, _Alloc>::size_type
832 basic_string<_CharT, _Traits, _Alloc>::
833 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
834 {
835 size_type __size = this->size();
836 if (__size)
837 {
838 if (--__size > __pos)
839 __size = __pos;
840 do
841 {
842 if (!traits_type::eq(_M_data()[__size], __c))
843 return __size;
844 }
845 while (__size--);
846 }
847 return npos;
848 }
849
850 template<typename _CharT, typename _Traits, typename _Alloc>
851 _GLIBCXX_STRING_CONSTEXPR
852 int
853 basic_string<_CharT, _Traits, _Alloc>::
854 compare(size_type __pos, size_type __n, const basic_string& __str) const
855 {
856 _M_check(__pos, "basic_string::compare");
857 __n = _M_limit(__pos, __n);
858 const size_type __osize = __str.size();
859 const size_type __len = std::min(__n, __osize);
860 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
861 if (!__r)
862 __r = _S_compare(__n, __osize);
863 return __r;
864 }
865
866 template<typename _CharT, typename _Traits, typename _Alloc>
867 _GLIBCXX_STRING_CONSTEXPR
868 int
869 basic_string<_CharT, _Traits, _Alloc>::
870 compare(size_type __pos1, size_type __n1, const basic_string& __str,
871 size_type __pos2, size_type __n2) const
872 {
873 _M_check(__pos1, "basic_string::compare");
874 __str._M_check(__pos2, "basic_string::compare");
875 __n1 = _M_limit(__pos1, __n1);
876 __n2 = __str._M_limit(__pos2, __n2);
877 const size_type __len = std::min(__n1, __n2);
878 int __r = traits_type::compare(_M_data() + __pos1,
879 __str.data() + __pos2, __len);
880 if (!__r)
881 __r = _S_compare(__n1, __n2);
882 return __r;
883 }
884
885 template<typename _CharT, typename _Traits, typename _Alloc>
886 _GLIBCXX_STRING_CONSTEXPR
887 int
888 basic_string<_CharT, _Traits, _Alloc>::
889 compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
890 {
891 __glibcxx_requires_string(__s);
892 const size_type __size = this->size();
893 const size_type __osize = traits_type::length(__s);
894 const size_type __len = std::min(__size, __osize);
895 int __r = traits_type::compare(_M_data(), __s, __len);
896 if (!__r)
897 __r = _S_compare(__size, __osize);
898 return __r;
899 }
900
901 template<typename _CharT, typename _Traits, typename _Alloc>
902 _GLIBCXX_STRING_CONSTEXPR
903 int
904 basic_string <_CharT, _Traits, _Alloc>::
905 compare(size_type __pos, size_type __n1, const _CharT* __s) const
906 {
907 __glibcxx_requires_string(__s);
908 _M_check(__pos, "basic_string::compare");
909 __n1 = _M_limit(__pos, __n1);
910 const size_type __osize = traits_type::length(__s);
911 const size_type __len = std::min(__n1, __osize);
912 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
913 if (!__r)
914 __r = _S_compare(__n1, __osize);
915 return __r;
916 }
917
918 template<typename _CharT, typename _Traits, typename _Alloc>
919 _GLIBCXX_STRING_CONSTEXPR
920 int
921 basic_string <_CharT, _Traits, _Alloc>::
922 compare(size_type __pos, size_type __n1, const _CharT* __s,
923 size_type __n2) const
924 {
925 __glibcxx_requires_string_len(__s, __n2);
926 _M_check(__pos, "basic_string::compare");
927 __n1 = _M_limit(__pos, __n1);
928 const size_type __len = std::min(__n1, __n2);
929 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
930 if (!__r)
931 __r = _S_compare(__n1, __n2);
932 return __r;
933 }
934
935#undef _GLIBCXX_STRING_CONSTEXPR
936
937 // 21.3.7.9 basic_string::getline and operators
938 template<typename _CharT, typename _Traits, typename _Alloc>
939 basic_istream<_CharT, _Traits>&
940 operator>>(basic_istream<_CharT, _Traits>& __in,
941 basic_string<_CharT, _Traits, _Alloc>& __str)
942 {
943 typedef basic_istream<_CharT, _Traits> __istream_type;
944 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
945 typedef typename __istream_type::ios_base __ios_base;
946 typedef typename __istream_type::int_type __int_type;
947 typedef typename __string_type::size_type __size_type;
948 typedef ctype<_CharT> __ctype_type;
949 typedef typename __ctype_type::ctype_base __ctype_base;
950
951 __size_type __extracted = 0;
952 typename __ios_base::iostate __err = __ios_base::goodbit;
953 typename __istream_type::sentry __cerb(__in, false);
954 if (__cerb)
955 {
956 __try
957 {
958 // Avoid reallocation for common case.
959 __str.erase();
960 _CharT __buf[128];
961 __size_type __len = 0;
962 const streamsize __w = __in.width();
963 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
964 : __str.max_size();
965 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
966 const __int_type __eof = _Traits::eof();
967 __int_type __c = __in.rdbuf()->sgetc();
968
969 while (__extracted < __n
970 && !_Traits::eq_int_type(__c, __eof)
971 && !__ct.is(__ctype_base::space,
972 _Traits::to_char_type(__c)))
973 {
974 if (__len == sizeof(__buf) / sizeof(_CharT))
975 {
976 __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
977 __len = 0;
978 }
979 __buf[__len++] = _Traits::to_char_type(__c);
980 ++__extracted;
981 __c = __in.rdbuf()->snextc();
982 }
983 __str.append(__buf, __len);
984
985 if (__extracted < __n && _Traits::eq_int_type(__c, __eof))
986 __err |= __ios_base::eofbit;
987 __in.width(0);
988 }
989 __catch(__cxxabiv1::__forced_unwind&)
990 {
991 __in._M_setstate(__ios_base::badbit);
992 __throw_exception_again;
993 }
994 __catch(...)
995 {
996 // _GLIBCXX_RESOLVE_LIB_DEFECTS
997 // 91. Description of operator>> and getline() for string<>
998 // might cause endless loop
999 __in._M_setstate(__ios_base::badbit);
1000 }
1001 }
1002 // 211. operator>>(istream&, string&) doesn't set failbit
1003 if (!__extracted)
1004 __err |= __ios_base::failbit;
1005 if (__err)
1006 __in.setstate(__err);
1007 return __in;
1008 }
1009
1010 template<typename _CharT, typename _Traits, typename _Alloc>
1011 basic_istream<_CharT, _Traits>&
1012 getline(basic_istream<_CharT, _Traits>& __in,
1013 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1014 {
1015 typedef basic_istream<_CharT, _Traits> __istream_type;
1016 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1017 typedef typename __istream_type::ios_base __ios_base;
1018 typedef typename __istream_type::int_type __int_type;
1019 typedef typename __string_type::size_type __size_type;
1020
1021 __size_type __extracted = 0;
1022 const __size_type __n = __str.max_size();
1023 typename __ios_base::iostate __err = __ios_base::goodbit;
1024 typename __istream_type::sentry __cerb(__in, true);
1025 if (__cerb)
1026 {
1027 __try
1028 {
1029 __str.erase();
1030 const __int_type __idelim = _Traits::to_int_type(__delim);
1031 const __int_type __eof = _Traits::eof();
1032 __int_type __c = __in.rdbuf()->sgetc();
1033
1034 while (__extracted < __n
1035 && !_Traits::eq_int_type(__c, __eof)
1036 && !_Traits::eq_int_type(__c, __idelim))
1037 {
1038 __str += _Traits::to_char_type(__c);
1039 ++__extracted;
1040 __c = __in.rdbuf()->snextc();
1041 }
1042
1043 if (_Traits::eq_int_type(__c, __eof))
1044 __err |= __ios_base::eofbit;
1045 else if (_Traits::eq_int_type(__c, __idelim))
1046 {
1047 ++__extracted;
1048 __in.rdbuf()->sbumpc();
1049 }
1050 else
1051 __err |= __ios_base::failbit;
1052 }
1053 __catch(__cxxabiv1::__forced_unwind&)
1054 {
1055 __in._M_setstate(__ios_base::badbit);
1056 __throw_exception_again;
1057 }
1058 __catch(...)
1059 {
1060 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1061 // 91. Description of operator>> and getline() for string<>
1062 // might cause endless loop
1063 __in._M_setstate(__ios_base::badbit);
1064 }
1065 }
1066 if (!__extracted)
1067 __err |= __ios_base::failbit;
1068 if (__err)
1069 __in.setstate(__err);
1070 return __in;
1071 }
1072
1073 // Inhibit implicit instantiations for required instantiations,
1074 // which are defined via explicit instantiations elsewhere.
1075#if _GLIBCXX_EXTERN_TEMPLATE
1076 // The explicit instantiation definitions in src/c++11/string-inst.cc and
1077 // src/c++17/string-inst.cc only instantiate the members required for C++17
1078 // and earlier standards (so not C++20's starts_with and ends_with).
1079 // Suppress the explicit instantiation declarations for C++20, so C++20
1080 // code will implicitly instantiate std::string and std::wstring as needed.
1081# if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
1082 extern template class basic_string<char>;
1083# elif ! _GLIBCXX_USE_CXX11_ABI
1084 // Still need to prevent implicit instantiation of the COW empty rep,
1085 // to ensure the definition in libstdc++.so is unique (PR 86138).
1086 extern template basic_string<char>::size_type
1087 basic_string<char>::_Rep::_S_empty_rep_storage[];
1088# endif
1089
1090 extern template
1091 basic_istream<char>&
1092 operator>>(basic_istream<char>&, string&);
1093 extern template
1094 basic_ostream<char>&
1095 operator<<(basic_ostream<char>&, const string&);
1096 extern template
1097 basic_istream<char>&
1098 getline(basic_istream<char>&, string&, char);
1099 extern template
1100 basic_istream<char>&
1101 getline(basic_istream<char>&, string&);
1102
1103#ifdef _GLIBCXX_USE_WCHAR_T
1104# if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
1105 extern template class basic_string<wchar_t>;
1106# elif ! _GLIBCXX_USE_CXX11_ABI
1107 extern template basic_string<wchar_t>::size_type
1108 basic_string<wchar_t>::_Rep::_S_empty_rep_storage[];
1109# endif
1110
1111 extern template
1112 basic_istream<wchar_t>&
1113 operator>>(basic_istream<wchar_t>&, wstring&);
1114 extern template
1115 basic_ostream<wchar_t>&
1116 operator<<(basic_ostream<wchar_t>&, const wstring&);
1117 extern template
1118 basic_istream<wchar_t>&
1119 getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1120 extern template
1121 basic_istream<wchar_t>&
1122 getline(basic_istream<wchar_t>&, wstring&);
1123#endif // _GLIBCXX_USE_WCHAR_T
1124#endif // _GLIBCXX_EXTERN_TEMPLATE
1125
1126_GLIBCXX_END_NAMESPACE_VERSION
1127} // namespace std
1128
1129#endif
1130