libstdc++
basic_string.tcc
Go to the documentation of this file.
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 
46 namespace 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
std::operator+
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:332
std::is_constant_evaluated
constexpr bool is_constant_evaluated() noexcept
Returns true only when called during constant evaluation.
Definition: type_traits:3519
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1215
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
std::wstring
basic_string< wchar_t > wstring
A string of wchar_t.
Definition: stringfwd.h:80
std
ISO C++ entities toplevel namespace is std.
std::operator>>
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1472
std::streamsize
ptrdiff_t streamsize
Integral type for I/O operation counts and buffer sizes.
Definition: postypes.h:68
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:147
std::operator<<
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1540
std::getline
basic_istream< _CharT, _Traits > & getline(basic_istream< _CharT, _Traits > &__is, basic_string< _CharT, _Traits, _Alloc > &__str, _CharT __delim)
Read a line from stream into a string.
Definition: basic_string.tcc:1012
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:264
std::data
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
Definition: range_access.h:311
std::basic_ios::rdbuf
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:321
std::basic_ios::setstate
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:157
std::basic_istream
Template class basic_istream.
Definition: istream:59
std::basic_string
Managing sequences of characters and character-like objects.
Definition: cow_string.h:115
std::basic_string::swap
void swap(basic_string &__s) noexcept(/*conditional */)
Swap contents with another string.
Definition: cow_string.h:3448
std::basic_string::find_first_of
size_type find_first_of(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a character of string.
Definition: cow_string.h:2411
std::basic_string::find
size_type find(const _CharT *__s, size_type __pos, size_type __n) const noexcept
Find position of a C substring.
Definition: basic_string.tcc:647
std::basic_string::find_last_not_of
size_type find_last_not_of(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a character not in string.
Definition: cow_string.h:2660
std::basic_string::compare
int compare(const basic_string &__str) const
Compare to a string.
Definition: cow_string.h:2762
std::basic_string::find_first_not_of
size_type find_first_not_of(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a character not in string.
Definition: cow_string.h:2578
std::basic_string::copy
size_type copy(_CharT *__s, size_type __n, size_type __pos=0) const
Copy substring into C string.
Definition: cow_string.h:3644
std::basic_string::find_last_of
size_type find_last_of(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a character of string.
Definition: cow_string.h:2495
std::basic_string::size
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
Definition: cow_string.h:913
std::basic_string::rfind
size_type rfind(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a string.
Definition: cow_string.h:2332
std::basic_string::resize
void resize(size_type __n, _CharT __c)
Resizes the string to the specified number of characters.
Definition: cow_string.h:3570
std::basic_string::reserve
void reserve()
Equivalent to shrink_to_fit().
Definition: cow_string.h:3623
std::basic_string::data
const _CharT * data() const noexcept
Return const pointer to contents.
Definition: cow_string.h:2218
std::basic_string::append
basic_string & append(const basic_string &__str)
Append a string to this string.
Definition: cow_string.h:3242
std::basic_string::npos
static const size_type npos
Value returned by various member functions when they fail.
Definition: cow_string.h:328
std::basic_string::get_allocator
allocator_type get_allocator() const noexcept
Return copy of allocator used to construct this string.
Definition: cow_string.h:2240
std::basic_string::erase
basic_string & erase(size_type __pos=0, size_type __n=npos)
Remove characters.
Definition: cow_string.h:1709
std::basic_string::max_size
size_type max_size() const noexcept
Returns the size() of the largest possible string.
Definition: cow_string.h:924
__cxxabiv1::__forced_unwind
Thrown as part of forced unwinding.
Definition: cxxabi_forced.h:49
std::ios_base::width
streamsize width() const
Flags access.
Definition: ios_base.h:751
std::ios_base::getloc
locale getloc() const
Locale access.
Definition: ios_base.h:802
std::ctype
Primary class template ctype facet.
Definition: locale_facets.h:616
std::input_iterator_tag
Marking input iterators.
Definition: stl_iterator_base_types.h:93
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition: stl_iterator_base_types.h:99
__gnu_cxx::__alloc_traits
Uniform interface to C++98 and C++11 allocators.
Definition: ext/alloc_traits.h:52