libstdc++
basic_string.tcc
Go to the documentation of this file.
1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997-2021 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
55 
56  template<typename _CharT, typename _Traits, typename _Alloc>
57  void
59  swap(basic_string& __s) _GLIBCXX_NOEXCEPT
60  {
61  if (this == &__s)
62  return;
63 
64  _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
65 
66  if (_M_is_local())
67  if (__s._M_is_local())
68  {
69  if (length() && __s.length())
70  {
71  _CharT __tmp_data[_S_local_capacity + 1];
72  traits_type::copy(__tmp_data, __s._M_local_buf,
73  _S_local_capacity + 1);
74  traits_type::copy(__s._M_local_buf, _M_local_buf,
75  _S_local_capacity + 1);
76  traits_type::copy(_M_local_buf, __tmp_data,
77  _S_local_capacity + 1);
78  }
79  else if (__s.length())
80  {
81  traits_type::copy(_M_local_buf, __s._M_local_buf,
82  _S_local_capacity + 1);
83  _M_length(__s.length());
84  __s._M_set_length(0);
85  return;
86  }
87  else if (length())
88  {
89  traits_type::copy(__s._M_local_buf, _M_local_buf,
90  _S_local_capacity + 1);
91  __s._M_length(length());
92  _M_set_length(0);
93  return;
94  }
95  }
96  else
97  {
98  const size_type __tmp_capacity = __s._M_allocated_capacity;
99  traits_type::copy(__s._M_local_buf, _M_local_buf,
100  _S_local_capacity + 1);
101  _M_data(__s._M_data());
102  __s._M_data(__s._M_local_buf);
103  _M_capacity(__tmp_capacity);
104  }
105  else
106  {
107  const size_type __tmp_capacity = _M_allocated_capacity;
108  if (__s._M_is_local())
109  {
110  traits_type::copy(_M_local_buf, __s._M_local_buf,
111  _S_local_capacity + 1);
112  __s._M_data(_M_data());
113  _M_data(_M_local_buf);
114  }
115  else
116  {
117  pointer __tmp_ptr = _M_data();
118  _M_data(__s._M_data());
119  __s._M_data(__tmp_ptr);
120  _M_capacity(__s._M_allocated_capacity);
121  }
122  __s._M_capacity(__tmp_capacity);
123  }
124 
125  const size_type __tmp_length = length();
126  _M_length(__s.length());
127  __s._M_length(__tmp_length);
128  }
129 
130  template<typename _CharT, typename _Traits, typename _Alloc>
131  typename basic_string<_CharT, _Traits, _Alloc>::pointer
132  basic_string<_CharT, _Traits, _Alloc>::
133  _M_create(size_type& __capacity, size_type __old_capacity)
134  {
135  // _GLIBCXX_RESOLVE_LIB_DEFECTS
136  // 83. String::npos vs. string::max_size()
137  if (__capacity > max_size())
138  std::__throw_length_error(__N("basic_string::_M_create"));
139 
140  // The below implements an exponential growth policy, necessary to
141  // meet amortized linear time requirements of the library: see
142  // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
143  if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
144  {
145  __capacity = 2 * __old_capacity;
146  // Never allocate a string bigger than max_size.
147  if (__capacity > max_size())
148  __capacity = max_size();
149  }
150 
151  // NB: Need an array of char_type[__capacity], plus a terminating
152  // null char_type() element.
153  return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);
154  }
155 
156  // NB: This is the special case for Input Iterators, used in
157  // istreambuf_iterators, etc.
158  // Input Iterators have a cost structure very different from
159  // pointers, calling for a different coding style.
160  template<typename _CharT, typename _Traits, typename _Alloc>
161  template<typename _InIterator>
162  void
163  basic_string<_CharT, _Traits, _Alloc>::
164  _M_construct(_InIterator __beg, _InIterator __end,
166  {
167  size_type __len = 0;
168  size_type __capacity = size_type(_S_local_capacity);
169 
170  while (__beg != __end && __len < __capacity)
171  {
172  _M_data()[__len++] = *__beg;
173  ++__beg;
174  }
175 
176  __try
177  {
178  while (__beg != __end)
179  {
180  if (__len == __capacity)
181  {
182  // Allocate more space.
183  __capacity = __len + 1;
184  pointer __another = _M_create(__capacity, __len);
185  this->_S_copy(__another, _M_data(), __len);
186  _M_dispose();
187  _M_data(__another);
188  _M_capacity(__capacity);
189  }
190  _M_data()[__len++] = *__beg;
191  ++__beg;
192  }
193  }
194  __catch(...)
195  {
196  _M_dispose();
197  __throw_exception_again;
198  }
199 
200  _M_set_length(__len);
201  }
202 
203  template<typename _CharT, typename _Traits, typename _Alloc>
204  template<typename _InIterator>
205  void
206  basic_string<_CharT, _Traits, _Alloc>::
207  _M_construct(_InIterator __beg, _InIterator __end,
209  {
210  // NB: Not required, but considered best practice.
211  if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
212  std::__throw_logic_error(__N("basic_string::"
213  "_M_construct null not valid"));
214 
215  size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
216 
217  if (__dnew > size_type(_S_local_capacity))
218  {
219  _M_data(_M_create(__dnew, size_type(0)));
220  _M_capacity(__dnew);
221  }
222 
223  // Check for out_of_range and length_error exceptions.
224  __try
225  { this->_S_copy_chars(_M_data(), __beg, __end); }
226  __catch(...)
227  {
228  _M_dispose();
229  __throw_exception_again;
230  }
231 
232  _M_set_length(__dnew);
233  }
234 
235  template<typename _CharT, typename _Traits, typename _Alloc>
236  void
237  basic_string<_CharT, _Traits, _Alloc>::
238  _M_construct(size_type __n, _CharT __c)
239  {
240  if (__n > size_type(_S_local_capacity))
241  {
242  _M_data(_M_create(__n, size_type(0)));
243  _M_capacity(__n);
244  }
245 
246  if (__n)
247  this->_S_assign(_M_data(), __n, __c);
248 
249  _M_set_length(__n);
250  }
251 
252  template<typename _CharT, typename _Traits, typename _Alloc>
253  void
254  basic_string<_CharT, _Traits, _Alloc>::
255  _M_assign(const basic_string& __str)
256  {
257  if (this != &__str)
258  {
259  const size_type __rsize = __str.length();
260  const size_type __capacity = capacity();
261 
262  if (__rsize > __capacity)
263  {
264  size_type __new_capacity = __rsize;
265  pointer __tmp = _M_create(__new_capacity, __capacity);
266  _M_dispose();
267  _M_data(__tmp);
268  _M_capacity(__new_capacity);
269  }
270 
271  if (__rsize)
272  this->_S_copy(_M_data(), __str._M_data(), __rsize);
273 
274  _M_set_length(__rsize);
275  }
276  }
277 
278  template<typename _CharT, typename _Traits, typename _Alloc>
279  void
281  reserve(size_type __res)
282  {
283  const size_type __capacity = capacity();
284  // _GLIBCXX_RESOLVE_LIB_DEFECTS
285  // 2968. Inconsistencies between basic_string reserve and
286  // vector/unordered_map/unordered_set reserve functions
287  // P0966 reserve should not shrink
288  if (__res <= __capacity)
289  return;
290 
291  pointer __tmp = _M_create(__res, __capacity);
292  this->_S_copy(__tmp, _M_data(), length() + 1);
293  _M_dispose();
294  _M_data(__tmp);
295  _M_capacity(__res);
296  }
297 
298  template<typename _CharT, typename _Traits, typename _Alloc>
299  void
300  basic_string<_CharT, _Traits, _Alloc>::
301  _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
302  size_type __len2)
303  {
304  const size_type __how_much = length() - __pos - __len1;
305 
306  size_type __new_capacity = length() + __len2 - __len1;
307  pointer __r = _M_create(__new_capacity, capacity());
308 
309  if (__pos)
310  this->_S_copy(__r, _M_data(), __pos);
311  if (__s && __len2)
312  this->_S_copy(__r + __pos, __s, __len2);
313  if (__how_much)
314  this->_S_copy(__r + __pos + __len2,
315  _M_data() + __pos + __len1, __how_much);
316 
317  _M_dispose();
318  _M_data(__r);
319  _M_capacity(__new_capacity);
320  }
321 
322  template<typename _CharT, typename _Traits, typename _Alloc>
323  void
324  basic_string<_CharT, _Traits, _Alloc>::
325  _M_erase(size_type __pos, size_type __n)
326  {
327  const size_type __how_much = length() - __pos - __n;
328 
329  if (__how_much && __n)
330  this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
331 
332  _M_set_length(length() - __n);
333  }
334 
335  template<typename _CharT, typename _Traits, typename _Alloc>
336  void
338  reserve()
339  {
340  if (_M_is_local())
341  return;
342 
343  const size_type __length = length();
344  const size_type __capacity = _M_allocated_capacity;
345 
346  if (__length <= size_type(_S_local_capacity))
347  {
348  this->_S_copy(_M_local_data(), _M_data(), __length + 1);
349  _M_destroy(__capacity);
350  _M_data(_M_local_data());
351  }
352 #if __cpp_exceptions
353  else if (__length < __capacity)
354  try
355  {
356  pointer __tmp
357  = _Alloc_traits::allocate(_M_get_allocator(), __length + 1);
358  this->_S_copy(__tmp, _M_data(), __length + 1);
359  _M_dispose();
360  _M_data(__tmp);
361  _M_capacity(__length);
362  }
363  catch (const __cxxabiv1::__forced_unwind&)
364  { throw; }
365  catch (...)
366  { /* swallow the exception */ }
367 #endif
368  }
369 
370  template<typename _CharT, typename _Traits, typename _Alloc>
371  void
373  resize(size_type __n, _CharT __c)
374  {
375  const size_type __size = this->size();
376  if (__size < __n)
377  this->append(__n - __size, __c);
378  else if (__n < __size)
379  this->_M_set_length(__n);
380  }
381 
382  template<typename _CharT, typename _Traits, typename _Alloc>
383  basic_string<_CharT, _Traits, _Alloc>&
384  basic_string<_CharT, _Traits, _Alloc>::
385  _M_append(const _CharT* __s, size_type __n)
386  {
387  const size_type __len = __n + this->size();
388 
389  if (__len <= this->capacity())
390  {
391  if (__n)
392  this->_S_copy(this->_M_data() + this->size(), __s, __n);
393  }
394  else
395  this->_M_mutate(this->size(), size_type(0), __s, __n);
396 
397  this->_M_set_length(__len);
398  return *this;
399  }
400 
401  template<typename _CharT, typename _Traits, typename _Alloc>
402  template<typename _InputIterator>
403  basic_string<_CharT, _Traits, _Alloc>&
404  basic_string<_CharT, _Traits, _Alloc>::
405  _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
406  _InputIterator __k1, _InputIterator __k2,
407  std::__false_type)
408  {
409  // _GLIBCXX_RESOLVE_LIB_DEFECTS
410  // 2788. unintentionally require a default constructible allocator
411  const basic_string __s(__k1, __k2, this->get_allocator());
412  const size_type __n1 = __i2 - __i1;
413  return _M_replace(__i1 - begin(), __n1, __s._M_data(),
414  __s.size());
415  }
416 
417  template<typename _CharT, typename _Traits, typename _Alloc>
418  basic_string<_CharT, _Traits, _Alloc>&
419  basic_string<_CharT, _Traits, _Alloc>::
420  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
421  _CharT __c)
422  {
423  _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
424 
425  const size_type __old_size = this->size();
426  const size_type __new_size = __old_size + __n2 - __n1;
427 
428  if (__new_size <= this->capacity())
429  {
430  pointer __p = this->_M_data() + __pos1;
431 
432  const size_type __how_much = __old_size - __pos1 - __n1;
433  if (__how_much && __n1 != __n2)
434  this->_S_move(__p + __n2, __p + __n1, __how_much);
435  }
436  else
437  this->_M_mutate(__pos1, __n1, 0, __n2);
438 
439  if (__n2)
440  this->_S_assign(this->_M_data() + __pos1, __n2, __c);
441 
442  this->_M_set_length(__new_size);
443  return *this;
444  }
445 
446  template<typename _CharT, typename _Traits, typename _Alloc>
447  basic_string<_CharT, _Traits, _Alloc>&
448  basic_string<_CharT, _Traits, _Alloc>::
449  _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
450  const size_type __len2)
451  {
452  _M_check_length(__len1, __len2, "basic_string::_M_replace");
453 
454  const size_type __old_size = this->size();
455  const size_type __new_size = __old_size + __len2 - __len1;
456 
457  if (__new_size <= this->capacity())
458  {
459  pointer __p = this->_M_data() + __pos;
460 
461  const size_type __how_much = __old_size - __pos - __len1;
462  if (_M_disjunct(__s))
463  {
464  if (__how_much && __len1 != __len2)
465  this->_S_move(__p + __len2, __p + __len1, __how_much);
466  if (__len2)
467  this->_S_copy(__p, __s, __len2);
468  }
469  else
470  {
471  // Work in-place.
472  if (__len2 && __len2 <= __len1)
473  this->_S_move(__p, __s, __len2);
474  if (__how_much && __len1 != __len2)
475  this->_S_move(__p + __len2, __p + __len1, __how_much);
476  if (__len2 > __len1)
477  {
478  if (__s + __len2 <= __p + __len1)
479  this->_S_move(__p, __s, __len2);
480  else if (__s >= __p + __len1)
481  {
482  // Hint to middle end that __p and __s overlap
483  // (PR 98465).
484  const size_type __poff = (__s - __p) + (__len2 - __len1);
485  this->_S_copy(__p, __p + __poff, __len2);
486  }
487  else
488  {
489  const size_type __nleft = (__p + __len1) - __s;
490  this->_S_move(__p, __s, __nleft);
491  this->_S_copy(__p + __nleft, __p + __len2,
492  __len2 - __nleft);
493  }
494  }
495  }
496  }
497  else
498  this->_M_mutate(__pos, __len1, __s, __len2);
499 
500  this->_M_set_length(__new_size);
501  return *this;
502  }
503 
504  template<typename _CharT, typename _Traits, typename _Alloc>
505  typename basic_string<_CharT, _Traits, _Alloc>::size_type
507  copy(_CharT* __s, size_type __n, size_type __pos) const
508  {
509  _M_check(__pos, "basic_string::copy");
510  __n = _M_limit(__pos, __n);
511  __glibcxx_requires_string_len(__s, __n);
512  if (__n)
513  _S_copy(__s, _M_data() + __pos, __n);
514  // 21.3.5.7 par 3: do not append null. (good.)
515  return __n;
516  }
517 
518 #else // !_GLIBCXX_USE_CXX11_ABI
519 
520  template<typename _CharT, typename _Traits, typename _Alloc>
521  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
522  basic_string<_CharT, _Traits, _Alloc>::
523  _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
524 
525  template<typename _CharT, typename _Traits, typename _Alloc>
526  const _CharT
527  basic_string<_CharT, _Traits, _Alloc>::
528  _Rep::_S_terminal = _CharT();
529 
530  template<typename _CharT, typename _Traits, typename _Alloc>
531  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
532  basic_string<_CharT, _Traits, _Alloc>::npos;
533 
534  // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
535  // at static init time (before static ctors are run).
536  template<typename _CharT, typename _Traits, typename _Alloc>
537  typename basic_string<_CharT, _Traits, _Alloc>::size_type
538  basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
539  (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
540  sizeof(size_type)];
541 
542  // NB: This is the special case for Input Iterators, used in
543  // istreambuf_iterators, etc.
544  // Input Iterators have a cost structure very different from
545  // pointers, calling for a different coding style.
546  template<typename _CharT, typename _Traits, typename _Alloc>
547  template<typename _InIterator>
548  _CharT*
549  basic_string<_CharT, _Traits, _Alloc>::
550  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
551  input_iterator_tag)
552  {
553 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
554  if (__beg == __end && __a == _Alloc())
555  return _S_empty_rep()._M_refdata();
556 #endif
557  // Avoid reallocation for common case.
558  _CharT __buf[128];
559  size_type __len = 0;
560  while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
561  {
562  __buf[__len++] = *__beg;
563  ++__beg;
564  }
565  _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
566  _M_copy(__r->_M_refdata(), __buf, __len);
567  __try
568  {
569  while (__beg != __end)
570  {
571  if (__len == __r->_M_capacity)
572  {
573  // Allocate more space.
574  _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
575  _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
576  __r->_M_destroy(__a);
577  __r = __another;
578  }
579  __r->_M_refdata()[__len++] = *__beg;
580  ++__beg;
581  }
582  }
583  __catch(...)
584  {
585  __r->_M_destroy(__a);
586  __throw_exception_again;
587  }
588  __r->_M_set_length_and_sharable(__len);
589  return __r->_M_refdata();
590  }
591 
592  template<typename _CharT, typename _Traits, typename _Alloc>
593  template <typename _InIterator>
594  _CharT*
595  basic_string<_CharT, _Traits, _Alloc>::
596  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
597  forward_iterator_tag)
598  {
599 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
600  if (__beg == __end && __a == _Alloc())
601  return _S_empty_rep()._M_refdata();
602 #endif
603  // NB: Not required, but considered best practice.
604  if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
605  __throw_logic_error(__N("basic_string::_S_construct null not valid"));
606 
607  const size_type __dnew = static_cast<size_type>(std::distance(__beg,
608  __end));
609  // Check for out_of_range and length_error exceptions.
610  _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
611  __try
612  { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
613  __catch(...)
614  {
615  __r->_M_destroy(__a);
616  __throw_exception_again;
617  }
618  __r->_M_set_length_and_sharable(__dnew);
619  return __r->_M_refdata();
620  }
621 
622  template<typename _CharT, typename _Traits, typename _Alloc>
623  _CharT*
624  basic_string<_CharT, _Traits, _Alloc>::
625  _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
626  {
627 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
628  if (__n == 0 && __a == _Alloc())
629  return _S_empty_rep()._M_refdata();
630 #endif
631  // Check for out_of_range and length_error exceptions.
632  _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
633  if (__n)
634  _M_assign(__r->_M_refdata(), __n, __c);
635 
636  __r->_M_set_length_and_sharable(__n);
637  return __r->_M_refdata();
638  }
639 
640  template<typename _CharT, typename _Traits, typename _Alloc>
642  basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
643  : _M_dataplus(_S_construct(__str._M_data()
644  + __str._M_check(__pos,
645  "basic_string::basic_string"),
646  __str._M_data() + __str._M_limit(__pos, npos)
647  + __pos, __a), __a)
648  { }
649 
650  template<typename _CharT, typename _Traits, typename _Alloc>
652  basic_string(const basic_string& __str, size_type __pos, size_type __n)
653  : _M_dataplus(_S_construct(__str._M_data()
654  + __str._M_check(__pos,
655  "basic_string::basic_string"),
656  __str._M_data() + __str._M_limit(__pos, __n)
657  + __pos, _Alloc()), _Alloc())
658  { }
659 
660  template<typename _CharT, typename _Traits, typename _Alloc>
662  basic_string(const basic_string& __str, size_type __pos,
663  size_type __n, const _Alloc& __a)
664  : _M_dataplus(_S_construct(__str._M_data()
665  + __str._M_check(__pos,
666  "basic_string::basic_string"),
667  __str._M_data() + __str._M_limit(__pos, __n)
668  + __pos, __a), __a)
669  { }
670 
671  template<typename _CharT, typename _Traits, typename _Alloc>
674  assign(const basic_string& __str)
675  {
676  if (_M_rep() != __str._M_rep())
677  {
678  // XXX MT
679  const allocator_type __a = this->get_allocator();
680  _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
681  _M_rep()->_M_dispose(__a);
682  _M_data(__tmp);
683  }
684  return *this;
685  }
686 
687  template<typename _CharT, typename _Traits, typename _Alloc>
690  assign(const _CharT* __s, size_type __n)
691  {
692  __glibcxx_requires_string_len(__s, __n);
693  _M_check_length(this->size(), __n, "basic_string::assign");
694  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
695  return _M_replace_safe(size_type(0), this->size(), __s, __n);
696  else
697  {
698  // Work in-place.
699  const size_type __pos = __s - _M_data();
700  if (__pos >= __n)
701  _M_copy(_M_data(), __s, __n);
702  else if (__pos)
703  _M_move(_M_data(), __s, __n);
704  _M_rep()->_M_set_length_and_sharable(__n);
705  return *this;
706  }
707  }
708 
709  template<typename _CharT, typename _Traits, typename _Alloc>
712  append(size_type __n, _CharT __c)
713  {
714  if (__n)
715  {
716  _M_check_length(size_type(0), __n, "basic_string::append");
717  const size_type __len = __n + this->size();
718  if (__len > this->capacity() || _M_rep()->_M_is_shared())
719  this->reserve(__len);
720  _M_assign(_M_data() + this->size(), __n, __c);
721  _M_rep()->_M_set_length_and_sharable(__len);
722  }
723  return *this;
724  }
725 
726  template<typename _CharT, typename _Traits, typename _Alloc>
729  append(const _CharT* __s, size_type __n)
730  {
731  __glibcxx_requires_string_len(__s, __n);
732  if (__n)
733  {
734  _M_check_length(size_type(0), __n, "basic_string::append");
735  const size_type __len = __n + this->size();
736  if (__len > this->capacity() || _M_rep()->_M_is_shared())
737  {
738  if (_M_disjunct(__s))
739  this->reserve(__len);
740  else
741  {
742  const size_type __off = __s - _M_data();
743  this->reserve(__len);
744  __s = _M_data() + __off;
745  }
746  }
747  _M_copy(_M_data() + this->size(), __s, __n);
748  _M_rep()->_M_set_length_and_sharable(__len);
749  }
750  return *this;
751  }
752 
753  template<typename _CharT, typename _Traits, typename _Alloc>
756  append(const basic_string& __str)
757  {
758  const size_type __size = __str.size();
759  if (__size)
760  {
761  const size_type __len = __size + this->size();
762  if (__len > this->capacity() || _M_rep()->_M_is_shared())
763  this->reserve(__len);
764  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
765  _M_rep()->_M_set_length_and_sharable(__len);
766  }
767  return *this;
768  }
769 
770  template<typename _CharT, typename _Traits, typename _Alloc>
773  append(const basic_string& __str, size_type __pos, size_type __n)
774  {
775  __str._M_check(__pos, "basic_string::append");
776  __n = __str._M_limit(__pos, __n);
777  if (__n)
778  {
779  const size_type __len = __n + this->size();
780  if (__len > this->capacity() || _M_rep()->_M_is_shared())
781  this->reserve(__len);
782  _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
783  _M_rep()->_M_set_length_and_sharable(__len);
784  }
785  return *this;
786  }
787 
788  template<typename _CharT, typename _Traits, typename _Alloc>
791  insert(size_type __pos, const _CharT* __s, size_type __n)
792  {
793  __glibcxx_requires_string_len(__s, __n);
794  _M_check(__pos, "basic_string::insert");
795  _M_check_length(size_type(0), __n, "basic_string::insert");
796  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
797  return _M_replace_safe(__pos, size_type(0), __s, __n);
798  else
799  {
800  // Work in-place.
801  const size_type __off = __s - _M_data();
802  _M_mutate(__pos, 0, __n);
803  __s = _M_data() + __off;
804  _CharT* __p = _M_data() + __pos;
805  if (__s + __n <= __p)
806  _M_copy(__p, __s, __n);
807  else if (__s >= __p)
808  _M_copy(__p, __s + __n, __n);
809  else
810  {
811  const size_type __nleft = __p - __s;
812  _M_copy(__p, __s, __nleft);
813  _M_copy(__p + __nleft, __p + __n, __n - __nleft);
814  }
815  return *this;
816  }
817  }
818 
819  template<typename _CharT, typename _Traits, typename _Alloc>
820  typename basic_string<_CharT, _Traits, _Alloc>::iterator
822  erase(iterator __first, iterator __last)
823  {
824  _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
825  && __last <= _M_iend());
826 
827  // NB: This isn't just an optimization (bail out early when
828  // there is nothing to do, really), it's also a correctness
829  // issue vs MT, see libstdc++/40518.
830  const size_type __size = __last - __first;
831  if (__size)
832  {
833  const size_type __pos = __first - _M_ibegin();
834  _M_mutate(__pos, __size, size_type(0));
835  _M_rep()->_M_set_leaked();
836  return iterator(_M_data() + __pos);
837  }
838  else
839  return __first;
840  }
841 
842  template<typename _CharT, typename _Traits, typename _Alloc>
845  replace(size_type __pos, size_type __n1, const _CharT* __s,
846  size_type __n2)
847  {
848  __glibcxx_requires_string_len(__s, __n2);
849  _M_check(__pos, "basic_string::replace");
850  __n1 = _M_limit(__pos, __n1);
851  _M_check_length(__n1, __n2, "basic_string::replace");
852  bool __left;
853  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
854  return _M_replace_safe(__pos, __n1, __s, __n2);
855  else if ((__left = __s + __n2 <= _M_data() + __pos)
856  || _M_data() + __pos + __n1 <= __s)
857  {
858  // Work in-place: non-overlapping case.
859  size_type __off = __s - _M_data();
860  __left ? __off : (__off += __n2 - __n1);
861  _M_mutate(__pos, __n1, __n2);
862  _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
863  return *this;
864  }
865  else
866  {
867  // Todo: overlapping case.
868  const basic_string __tmp(__s, __n2);
869  return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
870  }
871  }
872 
873  template<typename _CharT, typename _Traits, typename _Alloc>
874  void
876  _M_destroy(const _Alloc& __a) throw ()
877  {
878  const size_type __size = sizeof(_Rep_base) +
879  (this->_M_capacity + 1) * sizeof(_CharT);
880  _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
881  }
882 
883  template<typename _CharT, typename _Traits, typename _Alloc>
884  void
887  {
888 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
889  if (_M_rep() == &_S_empty_rep())
890  return;
891 #endif
892  if (_M_rep()->_M_is_shared())
893  _M_mutate(0, 0, 0);
894  _M_rep()->_M_set_leaked();
895  }
896 
897  template<typename _CharT, typename _Traits, typename _Alloc>
898  void
900  _M_mutate(size_type __pos, size_type __len1, size_type __len2)
901  {
902  const size_type __old_size = this->size();
903  const size_type __new_size = __old_size + __len2 - __len1;
904  const size_type __how_much = __old_size - __pos - __len1;
905 
906  if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
907  {
908  // Must reallocate.
909  const allocator_type __a = get_allocator();
910  _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
911 
912  if (__pos)
913  _M_copy(__r->_M_refdata(), _M_data(), __pos);
914  if (__how_much)
915  _M_copy(__r->_M_refdata() + __pos + __len2,
916  _M_data() + __pos + __len1, __how_much);
917 
918  _M_rep()->_M_dispose(__a);
919  _M_data(__r->_M_refdata());
920  }
921  else if (__how_much && __len1 != __len2)
922  {
923  // Work in-place.
924  _M_move(_M_data() + __pos + __len2,
925  _M_data() + __pos + __len1, __how_much);
926  }
927  _M_rep()->_M_set_length_and_sharable(__new_size);
928  }
929 
930  template<typename _CharT, typename _Traits, typename _Alloc>
931  void
933  reserve(size_type __res)
934  {
935  const size_type __capacity = capacity();
936 
937  // _GLIBCXX_RESOLVE_LIB_DEFECTS
938  // 2968. Inconsistencies between basic_string reserve and
939  // vector/unordered_map/unordered_set reserve functions
940  // P0966 reserve should not shrink
941  if (__res <= __capacity)
942  {
943  if (!_M_rep()->_M_is_shared())
944  return;
945 
946  // unshare, but keep same capacity
947  __res = __capacity;
948  }
949 
950  const allocator_type __a = get_allocator();
951  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
952  _M_rep()->_M_dispose(__a);
953  _M_data(__tmp);
954  }
955 
956  template<typename _CharT, typename _Traits, typename _Alloc>
957  void
961  {
962  if (_M_rep()->_M_is_leaked())
963  _M_rep()->_M_set_sharable();
964  if (__s._M_rep()->_M_is_leaked())
965  __s._M_rep()->_M_set_sharable();
966  if (this->get_allocator() == __s.get_allocator())
967  {
968  _CharT* __tmp = _M_data();
969  _M_data(__s._M_data());
970  __s._M_data(__tmp);
971  }
972  // The code below can usually be optimized away.
973  else
974  {
975  const basic_string __tmp1(_M_ibegin(), _M_iend(),
976  __s.get_allocator());
977  const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
978  this->get_allocator());
979  *this = __tmp2;
980  __s = __tmp1;
981  }
982  }
983 
984  template<typename _CharT, typename _Traits, typename _Alloc>
987  _S_create(size_type __capacity, size_type __old_capacity,
988  const _Alloc& __alloc)
989  {
990  // _GLIBCXX_RESOLVE_LIB_DEFECTS
991  // 83. String::npos vs. string::max_size()
992  if (__capacity > _S_max_size)
993  __throw_length_error(__N("basic_string::_S_create"));
994 
995  // The standard places no restriction on allocating more memory
996  // than is strictly needed within this layer at the moment or as
997  // requested by an explicit application call to reserve(n).
998 
999  // Many malloc implementations perform quite poorly when an
1000  // application attempts to allocate memory in a stepwise fashion
1001  // growing each allocation size by only 1 char. Additionally,
1002  // it makes little sense to allocate less linear memory than the
1003  // natural blocking size of the malloc implementation.
1004  // Unfortunately, we would need a somewhat low-level calculation
1005  // with tuned parameters to get this perfect for any particular
1006  // malloc implementation. Fortunately, generalizations about
1007  // common features seen among implementations seems to suffice.
1008 
1009  // __pagesize need not match the actual VM page size for good
1010  // results in practice, thus we pick a common value on the low
1011  // side. __malloc_header_size is an estimate of the amount of
1012  // overhead per memory allocation (in practice seen N * sizeof
1013  // (void*) where N is 0, 2 or 4). According to folklore,
1014  // picking this value on the high side is better than
1015  // low-balling it (especially when this algorithm is used with
1016  // malloc implementations that allocate memory blocks rounded up
1017  // to a size which is a power of 2).
1018  const size_type __pagesize = 4096;
1019  const size_type __malloc_header_size = 4 * sizeof(void*);
1020 
1021  // The below implements an exponential growth policy, necessary to
1022  // meet amortized linear time requirements of the library: see
1023  // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
1024  // It's active for allocations requiring an amount of memory above
1025  // system pagesize. This is consistent with the requirements of the
1026  // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
1027  if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
1028  __capacity = 2 * __old_capacity;
1029 
1030  // NB: Need an array of char_type[__capacity], plus a terminating
1031  // null char_type() element, plus enough for the _Rep data structure.
1032  // Whew. Seemingly so needy, yet so elemental.
1033  size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1034 
1035  const size_type __adj_size = __size + __malloc_header_size;
1036  if (__adj_size > __pagesize && __capacity > __old_capacity)
1037  {
1038  const size_type __extra = __pagesize - __adj_size % __pagesize;
1039  __capacity += __extra / sizeof(_CharT);
1040  // Never allocate a string bigger than _S_max_size.
1041  if (__capacity > _S_max_size)
1042  __capacity = _S_max_size;
1043  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1044  }
1045 
1046  // NB: Might throw, but no worries about a leak, mate: _Rep()
1047  // does not throw.
1048  void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
1049  _Rep *__p = new (__place) _Rep;
1050  __p->_M_capacity = __capacity;
1051  // ABI compatibility - 3.4.x set in _S_create both
1052  // _M_refcount and _M_length. All callers of _S_create
1053  // in basic_string.tcc then set just _M_length.
1054  // In 4.0.x and later both _M_refcount and _M_length
1055  // are initialized in the callers, unfortunately we can
1056  // have 3.4.x compiled code with _S_create callers inlined
1057  // calling 4.0.x+ _S_create.
1058  __p->_M_set_sharable();
1059  return __p;
1060  }
1061 
1062  template<typename _CharT, typename _Traits, typename _Alloc>
1063  _CharT*
1065  _M_clone(const _Alloc& __alloc, size_type __res)
1066  {
1067  // Requested capacity of the clone.
1068  const size_type __requested_cap = this->_M_length + __res;
1069  _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
1070  __alloc);
1071  if (this->_M_length)
1072  _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
1073 
1074  __r->_M_set_length_and_sharable(this->_M_length);
1075  return __r->_M_refdata();
1076  }
1077 
1078  template<typename _CharT, typename _Traits, typename _Alloc>
1079  void
1081  resize(size_type __n, _CharT __c)
1082  {
1083  const size_type __size = this->size();
1084  _M_check_length(__size, __n, "basic_string::resize");
1085  if (__size < __n)
1086  this->append(__n - __size, __c);
1087  else if (__n < __size)
1088  this->erase(__n);
1089  // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
1090  }
1091 
1092  template<typename _CharT, typename _Traits, typename _Alloc>
1093  template<typename _InputIterator>
1096  _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1097  _InputIterator __k2, __false_type)
1098  {
1099  const basic_string __s(__k1, __k2);
1100  const size_type __n1 = __i2 - __i1;
1101  _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
1102  return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
1103  __s.size());
1104  }
1105 
1106  template<typename _CharT, typename _Traits, typename _Alloc>
1109  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1110  _CharT __c)
1111  {
1112  _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
1113  _M_mutate(__pos1, __n1, __n2);
1114  if (__n2)
1115  _M_assign(_M_data() + __pos1, __n2, __c);
1116  return *this;
1117  }
1118 
1119  template<typename _CharT, typename _Traits, typename _Alloc>
1122  _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1123  size_type __n2)
1124  {
1125  _M_mutate(__pos1, __n1, __n2);
1126  if (__n2)
1127  _M_copy(_M_data() + __pos1, __s, __n2);
1128  return *this;
1129  }
1130 
1131  template<typename _CharT, typename _Traits, typename _Alloc>
1132  void
1135  {
1136 #if __cpp_exceptions
1137  if (length() < capacity() || _M_rep()->_M_is_shared())
1138  try
1139  {
1140  const allocator_type __a = get_allocator();
1141  _CharT* __tmp = _M_rep()->_M_clone(__a);
1142  _M_rep()->_M_dispose(__a);
1143  _M_data(__tmp);
1144  }
1145  catch (const __cxxabiv1::__forced_unwind&)
1146  { throw; }
1147  catch (...)
1148  { /* swallow the exception */ }
1149 #endif
1150  }
1151 
1152  template<typename _CharT, typename _Traits, typename _Alloc>
1153  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1155  copy(_CharT* __s, size_type __n, size_type __pos) const
1156  {
1157  _M_check(__pos, "basic_string::copy");
1158  __n = _M_limit(__pos, __n);
1159  __glibcxx_requires_string_len(__s, __n);
1160  if (__n)
1161  _M_copy(__s, _M_data() + __pos, __n);
1162  // 21.3.5.7 par 3: do not append null. (good.)
1163  return __n;
1164  }
1165 #endif // !_GLIBCXX_USE_CXX11_ABI
1166 
1167  template<typename _CharT, typename _Traits, typename _Alloc>
1169  operator+(const _CharT* __lhs,
1171  {
1172  __glibcxx_requires_string(__lhs);
1173  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1174  typedef typename __string_type::size_type __size_type;
1176  rebind<_CharT>::other _Char_alloc_type;
1177  typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
1178  const __size_type __len = _Traits::length(__lhs);
1179  __string_type __str(_Alloc_traits::_S_select_on_copy(
1180  __rhs.get_allocator()));
1181  __str.reserve(__len + __rhs.size());
1182  __str.append(__lhs, __len);
1183  __str.append(__rhs);
1184  return __str;
1185  }
1186 
1187  template<typename _CharT, typename _Traits, typename _Alloc>
1190  {
1191  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1192  typedef typename __string_type::size_type __size_type;
1194  rebind<_CharT>::other _Char_alloc_type;
1195  typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
1196  __string_type __str(_Alloc_traits::_S_select_on_copy(
1197  __rhs.get_allocator()));
1198  const __size_type __len = __rhs.size();
1199  __str.reserve(__len + 1);
1200  __str.append(__size_type(1), __lhs);
1201  __str.append(__rhs);
1202  return __str;
1203  }
1204 
1205  template<typename _CharT, typename _Traits, typename _Alloc>
1206  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1208  find(const _CharT* __s, size_type __pos, size_type __n) const
1209  _GLIBCXX_NOEXCEPT
1210  {
1211  __glibcxx_requires_string_len(__s, __n);
1212  const size_type __size = this->size();
1213 
1214  if (__n == 0)
1215  return __pos <= __size ? __pos : npos;
1216  if (__pos >= __size)
1217  return npos;
1218 
1219  const _CharT __elem0 = __s[0];
1220  const _CharT* const __data = data();
1221  const _CharT* __first = __data + __pos;
1222  const _CharT* const __last = __data + __size;
1223  size_type __len = __size - __pos;
1224 
1225  while (__len >= __n)
1226  {
1227  // Find the first occurrence of __elem0:
1228  __first = traits_type::find(__first, __len - __n + 1, __elem0);
1229  if (!__first)
1230  return npos;
1231  // Compare the full strings from the first occurrence of __elem0.
1232  // We already know that __first[0] == __s[0] but compare them again
1233  // anyway because __s is probably aligned, which helps memcmp.
1234  if (traits_type::compare(__first, __s, __n) == 0)
1235  return __first - __data;
1236  __len = __last - ++__first;
1237  }
1238  return npos;
1239  }
1240 
1241  template<typename _CharT, typename _Traits, typename _Alloc>
1242  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1244  find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1245  {
1246  size_type __ret = npos;
1247  const size_type __size = this->size();
1248  if (__pos < __size)
1249  {
1250  const _CharT* __data = _M_data();
1251  const size_type __n = __size - __pos;
1252  const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
1253  if (__p)
1254  __ret = __p - __data;
1255  }
1256  return __ret;
1257  }
1258 
1259  template<typename _CharT, typename _Traits, typename _Alloc>
1260  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1262  rfind(const _CharT* __s, size_type __pos, size_type __n) const
1263  _GLIBCXX_NOEXCEPT
1264  {
1265  __glibcxx_requires_string_len(__s, __n);
1266  const size_type __size = this->size();
1267  if (__n <= __size)
1268  {
1269  __pos = std::min(size_type(__size - __n), __pos);
1270  const _CharT* __data = _M_data();
1271  do
1272  {
1273  if (traits_type::compare(__data + __pos, __s, __n) == 0)
1274  return __pos;
1275  }
1276  while (__pos-- > 0);
1277  }
1278  return npos;
1279  }
1280 
1281  template<typename _CharT, typename _Traits, typename _Alloc>
1282  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1284  rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1285  {
1286  size_type __size = this->size();
1287  if (__size)
1288  {
1289  if (--__size > __pos)
1290  __size = __pos;
1291  for (++__size; __size-- > 0; )
1292  if (traits_type::eq(_M_data()[__size], __c))
1293  return __size;
1294  }
1295  return npos;
1296  }
1297 
1298  template<typename _CharT, typename _Traits, typename _Alloc>
1299  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1301  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
1302  _GLIBCXX_NOEXCEPT
1303  {
1304  __glibcxx_requires_string_len(__s, __n);
1305  for (; __n && __pos < this->size(); ++__pos)
1306  {
1307  const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
1308  if (__p)
1309  return __pos;
1310  }
1311  return npos;
1312  }
1313 
1314  template<typename _CharT, typename _Traits, typename _Alloc>
1315  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1317  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
1318  _GLIBCXX_NOEXCEPT
1319  {
1320  __glibcxx_requires_string_len(__s, __n);
1321  size_type __size = this->size();
1322  if (__size && __n)
1323  {
1324  if (--__size > __pos)
1325  __size = __pos;
1326  do
1327  {
1328  if (traits_type::find(__s, __n, _M_data()[__size]))
1329  return __size;
1330  }
1331  while (__size-- != 0);
1332  }
1333  return npos;
1334  }
1335 
1336  template<typename _CharT, typename _Traits, typename _Alloc>
1337  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1339  find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1340  _GLIBCXX_NOEXCEPT
1341  {
1342  __glibcxx_requires_string_len(__s, __n);
1343  for (; __pos < this->size(); ++__pos)
1344  if (!traits_type::find(__s, __n, _M_data()[__pos]))
1345  return __pos;
1346  return npos;
1347  }
1348 
1349  template<typename _CharT, typename _Traits, typename _Alloc>
1350  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1352  find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1353  {
1354  for (; __pos < this->size(); ++__pos)
1355  if (!traits_type::eq(_M_data()[__pos], __c))
1356  return __pos;
1357  return npos;
1358  }
1359 
1360  template<typename _CharT, typename _Traits, typename _Alloc>
1361  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1363  find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1364  _GLIBCXX_NOEXCEPT
1365  {
1366  __glibcxx_requires_string_len(__s, __n);
1367  size_type __size = this->size();
1368  if (__size)
1369  {
1370  if (--__size > __pos)
1371  __size = __pos;
1372  do
1373  {
1374  if (!traits_type::find(__s, __n, _M_data()[__size]))
1375  return __size;
1376  }
1377  while (__size--);
1378  }
1379  return npos;
1380  }
1381 
1382  template<typename _CharT, typename _Traits, typename _Alloc>
1383  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1385  find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1386  {
1387  size_type __size = this->size();
1388  if (__size)
1389  {
1390  if (--__size > __pos)
1391  __size = __pos;
1392  do
1393  {
1394  if (!traits_type::eq(_M_data()[__size], __c))
1395  return __size;
1396  }
1397  while (__size--);
1398  }
1399  return npos;
1400  }
1401 
1402  template<typename _CharT, typename _Traits, typename _Alloc>
1403  int
1405  compare(size_type __pos, size_type __n, const basic_string& __str) const
1406  {
1407  _M_check(__pos, "basic_string::compare");
1408  __n = _M_limit(__pos, __n);
1409  const size_type __osize = __str.size();
1410  const size_type __len = std::min(__n, __osize);
1411  int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
1412  if (!__r)
1413  __r = _S_compare(__n, __osize);
1414  return __r;
1415  }
1416 
1417  template<typename _CharT, typename _Traits, typename _Alloc>
1418  int
1420  compare(size_type __pos1, size_type __n1, const basic_string& __str,
1421  size_type __pos2, size_type __n2) const
1422  {
1423  _M_check(__pos1, "basic_string::compare");
1424  __str._M_check(__pos2, "basic_string::compare");
1425  __n1 = _M_limit(__pos1, __n1);
1426  __n2 = __str._M_limit(__pos2, __n2);
1427  const size_type __len = std::min(__n1, __n2);
1428  int __r = traits_type::compare(_M_data() + __pos1,
1429  __str.data() + __pos2, __len);
1430  if (!__r)
1431  __r = _S_compare(__n1, __n2);
1432  return __r;
1433  }
1434 
1435  template<typename _CharT, typename _Traits, typename _Alloc>
1436  int
1438  compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
1439  {
1440  __glibcxx_requires_string(__s);
1441  const size_type __size = this->size();
1442  const size_type __osize = traits_type::length(__s);
1443  const size_type __len = std::min(__size, __osize);
1444  int __r = traits_type::compare(_M_data(), __s, __len);
1445  if (!__r)
1446  __r = _S_compare(__size, __osize);
1447  return __r;
1448  }
1449 
1450  template<typename _CharT, typename _Traits, typename _Alloc>
1451  int
1453  compare(size_type __pos, size_type __n1, const _CharT* __s) const
1454  {
1455  __glibcxx_requires_string(__s);
1456  _M_check(__pos, "basic_string::compare");
1457  __n1 = _M_limit(__pos, __n1);
1458  const size_type __osize = traits_type::length(__s);
1459  const size_type __len = std::min(__n1, __osize);
1460  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1461  if (!__r)
1462  __r = _S_compare(__n1, __osize);
1463  return __r;
1464  }
1465 
1466  template<typename _CharT, typename _Traits, typename _Alloc>
1467  int
1469  compare(size_type __pos, size_type __n1, const _CharT* __s,
1470  size_type __n2) const
1471  {
1472  __glibcxx_requires_string_len(__s, __n2);
1473  _M_check(__pos, "basic_string::compare");
1474  __n1 = _M_limit(__pos, __n1);
1475  const size_type __len = std::min(__n1, __n2);
1476  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1477  if (!__r)
1478  __r = _S_compare(__n1, __n2);
1479  return __r;
1480  }
1481 
1482  // 21.3.7.9 basic_string::getline and operators
1483  template<typename _CharT, typename _Traits, typename _Alloc>
1487  {
1488  typedef basic_istream<_CharT, _Traits> __istream_type;
1489  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1490  typedef typename __istream_type::ios_base __ios_base;
1491  typedef typename __istream_type::int_type __int_type;
1492  typedef typename __string_type::size_type __size_type;
1493  typedef ctype<_CharT> __ctype_type;
1494  typedef typename __ctype_type::ctype_base __ctype_base;
1495 
1496  __size_type __extracted = 0;
1497  typename __ios_base::iostate __err = __ios_base::goodbit;
1498  typename __istream_type::sentry __cerb(__in, false);
1499  if (__cerb)
1500  {
1501  __try
1502  {
1503  // Avoid reallocation for common case.
1504  __str.erase();
1505  _CharT __buf[128];
1506  __size_type __len = 0;
1507  const streamsize __w = __in.width();
1508  const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1509  : __str.max_size();
1510  const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1511  const __int_type __eof = _Traits::eof();
1512  __int_type __c = __in.rdbuf()->sgetc();
1513 
1514  while (__extracted < __n
1515  && !_Traits::eq_int_type(__c, __eof)
1516  && !__ct.is(__ctype_base::space,
1517  _Traits::to_char_type(__c)))
1518  {
1519  if (__len == sizeof(__buf) / sizeof(_CharT))
1520  {
1521  __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1522  __len = 0;
1523  }
1524  __buf[__len++] = _Traits::to_char_type(__c);
1525  ++__extracted;
1526  __c = __in.rdbuf()->snextc();
1527  }
1528  __str.append(__buf, __len);
1529 
1530  if (__extracted < __n && _Traits::eq_int_type(__c, __eof))
1531  __err |= __ios_base::eofbit;
1532  __in.width(0);
1533  }
1534  __catch(__cxxabiv1::__forced_unwind&)
1535  {
1536  __in._M_setstate(__ios_base::badbit);
1537  __throw_exception_again;
1538  }
1539  __catch(...)
1540  {
1541  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1542  // 91. Description of operator>> and getline() for string<>
1543  // might cause endless loop
1544  __in._M_setstate(__ios_base::badbit);
1545  }
1546  }
1547  // 211. operator>>(istream&, string&) doesn't set failbit
1548  if (!__extracted)
1549  __err |= __ios_base::failbit;
1550  if (__err)
1551  __in.setstate(__err);
1552  return __in;
1553  }
1554 
1555  template<typename _CharT, typename _Traits, typename _Alloc>
1558  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1559  {
1560  typedef basic_istream<_CharT, _Traits> __istream_type;
1561  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1562  typedef typename __istream_type::ios_base __ios_base;
1563  typedef typename __istream_type::int_type __int_type;
1564  typedef typename __string_type::size_type __size_type;
1565 
1566  __size_type __extracted = 0;
1567  const __size_type __n = __str.max_size();
1568  typename __ios_base::iostate __err = __ios_base::goodbit;
1569  typename __istream_type::sentry __cerb(__in, true);
1570  if (__cerb)
1571  {
1572  __try
1573  {
1574  __str.erase();
1575  const __int_type __idelim = _Traits::to_int_type(__delim);
1576  const __int_type __eof = _Traits::eof();
1577  __int_type __c = __in.rdbuf()->sgetc();
1578 
1579  while (__extracted < __n
1580  && !_Traits::eq_int_type(__c, __eof)
1581  && !_Traits::eq_int_type(__c, __idelim))
1582  {
1583  __str += _Traits::to_char_type(__c);
1584  ++__extracted;
1585  __c = __in.rdbuf()->snextc();
1586  }
1587 
1588  if (_Traits::eq_int_type(__c, __eof))
1589  __err |= __ios_base::eofbit;
1590  else if (_Traits::eq_int_type(__c, __idelim))
1591  {
1592  ++__extracted;
1593  __in.rdbuf()->sbumpc();
1594  }
1595  else
1596  __err |= __ios_base::failbit;
1597  }
1598  __catch(__cxxabiv1::__forced_unwind&)
1599  {
1600  __in._M_setstate(__ios_base::badbit);
1601  __throw_exception_again;
1602  }
1603  __catch(...)
1604  {
1605  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1606  // 91. Description of operator>> and getline() for string<>
1607  // might cause endless loop
1608  __in._M_setstate(__ios_base::badbit);
1609  }
1610  }
1611  if (!__extracted)
1612  __err |= __ios_base::failbit;
1613  if (__err)
1614  __in.setstate(__err);
1615  return __in;
1616  }
1617 
1618  // Inhibit implicit instantiations for required instantiations,
1619  // which are defined via explicit instantiations elsewhere.
1620 #if _GLIBCXX_EXTERN_TEMPLATE
1621  // The explicit instantiation definitions in src/c++11/string-inst.cc and
1622  // src/c++17/string-inst.cc only instantiate the members required for C++17
1623  // and earlier standards (so not C++20's starts_with and ends_with).
1624  // Suppress the explicit instantiation declarations for C++20, so C++20
1625  // code will implicitly instantiate std::string and std::wstring as needed.
1626 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
1627  extern template class basic_string<char>;
1628 # elif ! _GLIBCXX_USE_CXX11_ABI
1629  // Still need to prevent implicit instantiation of the COW empty rep,
1630  // to ensure the definition in libstdc++.so is unique (PR 86138).
1631  extern template basic_string<char>::size_type
1633 # endif
1634 
1635  extern template
1637  operator>>(basic_istream<char>&, string&);
1638  extern template
1640  operator<<(basic_ostream<char>&, const string&);
1641  extern template
1643  getline(basic_istream<char>&, string&, char);
1644  extern template
1646  getline(basic_istream<char>&, string&);
1647 
1648 #ifdef _GLIBCXX_USE_WCHAR_T
1649 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
1650  extern template class basic_string<wchar_t>;
1651 # elif ! _GLIBCXX_USE_CXX11_ABI
1652  extern template basic_string<wchar_t>::size_type
1654 # endif
1655 
1656  extern template
1659  extern template
1661  operator<<(basic_ostream<wchar_t>&, const wstring&);
1662  extern template
1664  getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1665  extern template
1668 #endif // _GLIBCXX_USE_WCHAR_T
1669 #endif // _GLIBCXX_EXTERN_TEMPLATE
1670 
1671 _GLIBCXX_END_NAMESPACE_VERSION
1672 } // namespace std
1673 
1674 #endif
basic_string & erase(size_type __pos=0, size_type __n=npos)
Remove characters.
basic_string() noexcept
Default constructor creates an empty string.
ptrdiff_t streamsize
Integral type for I/O operation counts and buffer sizes.
Definition: postypes.h:98
Marking input iterators.
static const size_type npos
Value returned by various member functions when they fail.
void reserve()
Equivalent to shrink_to_fit().
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:157
void swap(basic_string &__s) noexcept(/*conditional */)
Swap contents with another string.
Forward iterators support a superset of input iterator operations.
basic_string & append(const basic_string &__str)
Append a string to this string.
size_type copy(_CharT *__s, size_type __n, size_type __pos=0) const
Copy substring into C string.
streamsize width() const
Flags access.
Definition: ios_base.h:742
Uniform interface to all allocator types.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
Definition: range_access.h:290
Primary class template ctype facet.This template class defines classification and conversion function...
Thrown as part of forced unwinding.A magic placeholder class that can be caught by reference to recog...
Definition: cxxabi_forced.h:48
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
allocator_type get_allocator() const noexcept
Return copy of allocator used to construct this string.
const _CharT * data() const noexcept
Return const pointer to contents.
Managing sequences of characters and character-like objects.
locale getloc() const
Locale access.
Definition: ios_base.h:793
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:321
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.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1217
size_type max_size() const noexcept
Returns the size() of the largest possible string.
Uniform interface to C++98 and C++11 allocators.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
Template class basic_istream.
Definition: iosfwd:83
void resize(size_type __n, _CharT __c)
Resizes the string to the specified number of characters.
constexpr time_point< _Clock, typename common_type< duration< _Rep1, _Period1 >, _Dur2 >::type > operator+(const duration< _Rep1, _Period1 > &__lhs, const time_point< _Clock, _Dur2 > &__rhs)
Adjust a time point forwards by the given duration.
Definition: chrono:1016
ISO C++ entities toplevel namespace is std.
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1472