libstdc++
basic_string.tcc
Go to the documentation of this file.
1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997-2017 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 #if __cplusplus >= 201103L
279  template<typename _CharT, typename _Traits, typename _Alloc>
280  void
281  basic_string<_CharT, _Traits, _Alloc>::
282  _M_copy_assign(const basic_string& __str, true_type)
283  {
284  struct _Guard // RAII type for strong exception-safety guarantee.
285  {
286  // Takes ownership of string's original state.
287  _Guard(basic_string* __self)
288  : _M_self(__self), _M_alloc(std::move(__self->_M_get_allocator())),
289  _M_ptr(__self->_M_data()),
290  _M_capacity(__self->_M_allocated_capacity), _M_len(__self->length())
291  {
292  __self->_M_data(__self->_M_local_data());
293  __self->_M_length(0);
294  }
295 
296  // Restores string's original state if _M_release() was not called.
297  ~_Guard()
298  {
299  if (_M_ptr)
300  {
301  _M_self->_M_get_allocator() = std::move(_M_alloc);
302  _M_self->_M_data(_M_ptr);
303  _M_self->_M_capacity(_M_capacity);
304  _M_self->_M_length(_M_len);
305  }
306  }
307 
308  _Guard(const _Guard&) = delete;
309  _Guard& operator=(const _Guard&) = delete;
310 
311  void _M_release()
312  {
313  // Original state can be freed now.
314  _Alloc_traits::deallocate(_M_alloc, _M_ptr, _M_capacity + 1);
315  _M_ptr = nullptr;
316  }
317 
318  basic_string* _M_self;
319  allocator_type _M_alloc;
320  pointer _M_ptr;
321  size_type _M_capacity;
322  size_type _M_len;
323  };
324 
325  if (!_Alloc_traits::_S_always_equal() && !_M_is_local()
326  && _M_get_allocator() != __str._M_get_allocator())
327  {
328  // The propagating allocator cannot free existing storage.
329  _Guard __guard(this);
330  _M_get_allocator() = __str._M_get_allocator();
331  this->_M_assign(__str);
332  __guard._M_release();
333  }
334  else
335  {
336  _M_get_allocator() = __str._M_get_allocator();
337  this->_M_assign(__str);
338  }
339  }
340 #endif
341 
342  template<typename _CharT, typename _Traits, typename _Alloc>
343  void
345  reserve(size_type __res)
346  {
347  // Make sure we don't shrink below the current size.
348  if (__res < length())
349  __res = length();
350 
351  const size_type __capacity = capacity();
352  if (__res != __capacity)
353  {
354  if (__res > __capacity
355  || __res > size_type(_S_local_capacity))
356  {
357  pointer __tmp = _M_create(__res, __capacity);
358  this->_S_copy(__tmp, _M_data(), length() + 1);
359  _M_dispose();
360  _M_data(__tmp);
361  _M_capacity(__res);
362  }
363  else if (!_M_is_local())
364  {
365  this->_S_copy(_M_local_data(), _M_data(), length() + 1);
366  _M_destroy(__capacity);
367  _M_data(_M_local_data());
368  }
369  }
370  }
371 
372  template<typename _CharT, typename _Traits, typename _Alloc>
373  void
374  basic_string<_CharT, _Traits, _Alloc>::
375  _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
376  size_type __len2)
377  {
378  const size_type __how_much = length() - __pos - __len1;
379 
380  size_type __new_capacity = length() + __len2 - __len1;
381  pointer __r = _M_create(__new_capacity, capacity());
382 
383  if (__pos)
384  this->_S_copy(__r, _M_data(), __pos);
385  if (__s && __len2)
386  this->_S_copy(__r + __pos, __s, __len2);
387  if (__how_much)
388  this->_S_copy(__r + __pos + __len2,
389  _M_data() + __pos + __len1, __how_much);
390 
391  _M_dispose();
392  _M_data(__r);
393  _M_capacity(__new_capacity);
394  }
395 
396  template<typename _CharT, typename _Traits, typename _Alloc>
397  void
398  basic_string<_CharT, _Traits, _Alloc>::
399  _M_erase(size_type __pos, size_type __n)
400  {
401  const size_type __how_much = length() - __pos - __n;
402 
403  if (__how_much && __n)
404  this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
405 
406  _M_set_length(length() - __n);
407  }
408 
409  template<typename _CharT, typename _Traits, typename _Alloc>
410  void
412  resize(size_type __n, _CharT __c)
413  {
414  const size_type __size = this->size();
415  if (__size < __n)
416  this->append(__n - __size, __c);
417  else if (__n < __size)
418  this->_M_set_length(__n);
419  }
420 
421  template<typename _CharT, typename _Traits, typename _Alloc>
422  basic_string<_CharT, _Traits, _Alloc>&
423  basic_string<_CharT, _Traits, _Alloc>::
424  _M_append(const _CharT* __s, size_type __n)
425  {
426  const size_type __len = __n + this->size();
427 
428  if (__len <= this->capacity())
429  {
430  if (__n)
431  this->_S_copy(this->_M_data() + this->size(), __s, __n);
432  }
433  else
434  this->_M_mutate(this->size(), size_type(0), __s, __n);
435 
436  this->_M_set_length(__len);
437  return *this;
438  }
439 
440  template<typename _CharT, typename _Traits, typename _Alloc>
441  template<typename _InputIterator>
442  basic_string<_CharT, _Traits, _Alloc>&
443  basic_string<_CharT, _Traits, _Alloc>::
444  _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
445  _InputIterator __k1, _InputIterator __k2,
446  std::__false_type)
447  {
448  const basic_string __s(__k1, __k2);
449  const size_type __n1 = __i2 - __i1;
450  return _M_replace(__i1 - begin(), __n1, __s._M_data(),
451  __s.size());
452  }
453 
454  template<typename _CharT, typename _Traits, typename _Alloc>
455  basic_string<_CharT, _Traits, _Alloc>&
456  basic_string<_CharT, _Traits, _Alloc>::
457  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
458  _CharT __c)
459  {
460  _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
461 
462  const size_type __old_size = this->size();
463  const size_type __new_size = __old_size + __n2 - __n1;
464 
465  if (__new_size <= this->capacity())
466  {
467  pointer __p = this->_M_data() + __pos1;
468 
469  const size_type __how_much = __old_size - __pos1 - __n1;
470  if (__how_much && __n1 != __n2)
471  this->_S_move(__p + __n2, __p + __n1, __how_much);
472  }
473  else
474  this->_M_mutate(__pos1, __n1, 0, __n2);
475 
476  if (__n2)
477  this->_S_assign(this->_M_data() + __pos1, __n2, __c);
478 
479  this->_M_set_length(__new_size);
480  return *this;
481  }
482 
483  template<typename _CharT, typename _Traits, typename _Alloc>
484  basic_string<_CharT, _Traits, _Alloc>&
485  basic_string<_CharT, _Traits, _Alloc>::
486  _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
487  const size_type __len2)
488  {
489  _M_check_length(__len1, __len2, "basic_string::_M_replace");
490 
491  const size_type __old_size = this->size();
492  const size_type __new_size = __old_size + __len2 - __len1;
493 
494  if (__new_size <= this->capacity())
495  {
496  pointer __p = this->_M_data() + __pos;
497 
498  const size_type __how_much = __old_size - __pos - __len1;
499  if (_M_disjunct(__s))
500  {
501  if (__how_much && __len1 != __len2)
502  this->_S_move(__p + __len2, __p + __len1, __how_much);
503  if (__len2)
504  this->_S_copy(__p, __s, __len2);
505  }
506  else
507  {
508  // Work in-place.
509  if (__len2 && __len2 <= __len1)
510  this->_S_move(__p, __s, __len2);
511  if (__how_much && __len1 != __len2)
512  this->_S_move(__p + __len2, __p + __len1, __how_much);
513  if (__len2 > __len1)
514  {
515  if (__s + __len2 <= __p + __len1)
516  this->_S_move(__p, __s, __len2);
517  else if (__s >= __p + __len1)
518  this->_S_copy(__p, __s + __len2 - __len1, __len2);
519  else
520  {
521  const size_type __nleft = (__p + __len1) - __s;
522  this->_S_move(__p, __s, __nleft);
523  this->_S_copy(__p + __nleft, __p + __len2,
524  __len2 - __nleft);
525  }
526  }
527  }
528  }
529  else
530  this->_M_mutate(__pos, __len1, __s, __len2);
531 
532  this->_M_set_length(__new_size);
533  return *this;
534  }
535 
536  template<typename _CharT, typename _Traits, typename _Alloc>
537  typename basic_string<_CharT, _Traits, _Alloc>::size_type
539  copy(_CharT* __s, size_type __n, size_type __pos) const
540  {
541  _M_check(__pos, "basic_string::copy");
542  __n = _M_limit(__pos, __n);
543  __glibcxx_requires_string_len(__s, __n);
544  if (__n)
545  _S_copy(__s, _M_data() + __pos, __n);
546  // 21.3.5.7 par 3: do not append null. (good.)
547  return __n;
548  }
549 
550 #else // !_GLIBCXX_USE_CXX11_ABI
551 
552  template<typename _CharT, typename _Traits, typename _Alloc>
553  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
554  basic_string<_CharT, _Traits, _Alloc>::
555  _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
556 
557  template<typename _CharT, typename _Traits, typename _Alloc>
558  const _CharT
559  basic_string<_CharT, _Traits, _Alloc>::
560  _Rep::_S_terminal = _CharT();
561 
562  template<typename _CharT, typename _Traits, typename _Alloc>
563  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
564  basic_string<_CharT, _Traits, _Alloc>::npos;
565 
566  // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
567  // at static init time (before static ctors are run).
568  template<typename _CharT, typename _Traits, typename _Alloc>
569  typename basic_string<_CharT, _Traits, _Alloc>::size_type
570  basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
571  (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
572  sizeof(size_type)];
573 
574  // NB: This is the special case for Input Iterators, used in
575  // istreambuf_iterators, etc.
576  // Input Iterators have a cost structure very different from
577  // pointers, calling for a different coding style.
578  template<typename _CharT, typename _Traits, typename _Alloc>
579  template<typename _InIterator>
580  _CharT*
581  basic_string<_CharT, _Traits, _Alloc>::
582  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
583  input_iterator_tag)
584  {
585 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
586  if (__beg == __end && __a == _Alloc())
587  return _S_empty_rep()._M_refdata();
588 #endif
589  // Avoid reallocation for common case.
590  _CharT __buf[128];
591  size_type __len = 0;
592  while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
593  {
594  __buf[__len++] = *__beg;
595  ++__beg;
596  }
597  _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
598  _M_copy(__r->_M_refdata(), __buf, __len);
599  __try
600  {
601  while (__beg != __end)
602  {
603  if (__len == __r->_M_capacity)
604  {
605  // Allocate more space.
606  _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
607  _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
608  __r->_M_destroy(__a);
609  __r = __another;
610  }
611  __r->_M_refdata()[__len++] = *__beg;
612  ++__beg;
613  }
614  }
615  __catch(...)
616  {
617  __r->_M_destroy(__a);
618  __throw_exception_again;
619  }
620  __r->_M_set_length_and_sharable(__len);
621  return __r->_M_refdata();
622  }
623 
624  template<typename _CharT, typename _Traits, typename _Alloc>
625  template <typename _InIterator>
626  _CharT*
627  basic_string<_CharT, _Traits, _Alloc>::
628  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
629  forward_iterator_tag)
630  {
631 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
632  if (__beg == __end && __a == _Alloc())
633  return _S_empty_rep()._M_refdata();
634 #endif
635  // NB: Not required, but considered best practice.
636  if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
637  __throw_logic_error(__N("basic_string::_S_construct null not valid"));
638 
639  const size_type __dnew = static_cast<size_type>(std::distance(__beg,
640  __end));
641  // Check for out_of_range and length_error exceptions.
642  _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
643  __try
644  { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
645  __catch(...)
646  {
647  __r->_M_destroy(__a);
648  __throw_exception_again;
649  }
650  __r->_M_set_length_and_sharable(__dnew);
651  return __r->_M_refdata();
652  }
653 
654  template<typename _CharT, typename _Traits, typename _Alloc>
655  _CharT*
656  basic_string<_CharT, _Traits, _Alloc>::
657  _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
658  {
659 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
660  if (__n == 0 && __a == _Alloc())
661  return _S_empty_rep()._M_refdata();
662 #endif
663  // Check for out_of_range and length_error exceptions.
664  _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
665  if (__n)
666  _M_assign(__r->_M_refdata(), __n, __c);
667 
668  __r->_M_set_length_and_sharable(__n);
669  return __r->_M_refdata();
670  }
671 
672  template<typename _CharT, typename _Traits, typename _Alloc>
675  : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
676  __str.get_allocator()),
677  __str.get_allocator())
678  { }
679 
680  template<typename _CharT, typename _Traits, typename _Alloc>
682  basic_string(const _Alloc& __a)
683  : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
684  { }
685 
686  template<typename _CharT, typename _Traits, typename _Alloc>
688  basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
689  : _M_dataplus(_S_construct(__str._M_data()
690  + __str._M_check(__pos,
691  "basic_string::basic_string"),
692  __str._M_data() + __str._M_limit(__pos, npos)
693  + __pos, __a), __a)
694  { }
695 
696  template<typename _CharT, typename _Traits, typename _Alloc>
698  basic_string(const basic_string& __str, size_type __pos, size_type __n)
699  : _M_dataplus(_S_construct(__str._M_data()
700  + __str._M_check(__pos,
701  "basic_string::basic_string"),
702  __str._M_data() + __str._M_limit(__pos, __n)
703  + __pos, _Alloc()), _Alloc())
704  { }
705 
706  template<typename _CharT, typename _Traits, typename _Alloc>
708  basic_string(const basic_string& __str, size_type __pos,
709  size_type __n, const _Alloc& __a)
710  : _M_dataplus(_S_construct(__str._M_data()
711  + __str._M_check(__pos,
712  "basic_string::basic_string"),
713  __str._M_data() + __str._M_limit(__pos, __n)
714  + __pos, __a), __a)
715  { }
716 
717  // TBD: DPG annotate
718  template<typename _CharT, typename _Traits, typename _Alloc>
720  basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
721  : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
722  { }
723 
724  // TBD: DPG annotate
725  template<typename _CharT, typename _Traits, typename _Alloc>
727  basic_string(const _CharT* __s, const _Alloc& __a)
728  : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
729  __s + npos, __a), __a)
730  { }
731 
732  template<typename _CharT, typename _Traits, typename _Alloc>
734  basic_string(size_type __n, _CharT __c, const _Alloc& __a)
735  : _M_dataplus(_S_construct(__n, __c, __a), __a)
736  { }
737 
738  // TBD: DPG annotate
739  template<typename _CharT, typename _Traits, typename _Alloc>
740  template<typename _InputIterator>
742  basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
743  : _M_dataplus(_S_construct(__beg, __end, __a), __a)
744  { }
745 
746 #if __cplusplus >= 201103L
747  template<typename _CharT, typename _Traits, typename _Alloc>
750  : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
751  { }
752 #endif
753 
754  template<typename _CharT, typename _Traits, typename _Alloc>
757  assign(const basic_string& __str)
758  {
759  if (_M_rep() != __str._M_rep())
760  {
761  // XXX MT
762  const allocator_type __a = this->get_allocator();
763  _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
764  _M_rep()->_M_dispose(__a);
765  _M_data(__tmp);
766  }
767  return *this;
768  }
769 
770  template<typename _CharT, typename _Traits, typename _Alloc>
773  assign(const _CharT* __s, size_type __n)
774  {
775  __glibcxx_requires_string_len(__s, __n);
776  _M_check_length(this->size(), __n, "basic_string::assign");
777  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
778  return _M_replace_safe(size_type(0), this->size(), __s, __n);
779  else
780  {
781  // Work in-place.
782  const size_type __pos = __s - _M_data();
783  if (__pos >= __n)
784  _M_copy(_M_data(), __s, __n);
785  else if (__pos)
786  _M_move(_M_data(), __s, __n);
787  _M_rep()->_M_set_length_and_sharable(__n);
788  return *this;
789  }
790  }
791 
792  template<typename _CharT, typename _Traits, typename _Alloc>
795  append(size_type __n, _CharT __c)
796  {
797  if (__n)
798  {
799  _M_check_length(size_type(0), __n, "basic_string::append");
800  const size_type __len = __n + this->size();
801  if (__len > this->capacity() || _M_rep()->_M_is_shared())
802  this->reserve(__len);
803  _M_assign(_M_data() + this->size(), __n, __c);
804  _M_rep()->_M_set_length_and_sharable(__len);
805  }
806  return *this;
807  }
808 
809  template<typename _CharT, typename _Traits, typename _Alloc>
812  append(const _CharT* __s, size_type __n)
813  {
814  __glibcxx_requires_string_len(__s, __n);
815  if (__n)
816  {
817  _M_check_length(size_type(0), __n, "basic_string::append");
818  const size_type __len = __n + this->size();
819  if (__len > this->capacity() || _M_rep()->_M_is_shared())
820  {
821  if (_M_disjunct(__s))
822  this->reserve(__len);
823  else
824  {
825  const size_type __off = __s - _M_data();
826  this->reserve(__len);
827  __s = _M_data() + __off;
828  }
829  }
830  _M_copy(_M_data() + this->size(), __s, __n);
831  _M_rep()->_M_set_length_and_sharable(__len);
832  }
833  return *this;
834  }
835 
836  template<typename _CharT, typename _Traits, typename _Alloc>
839  append(const basic_string& __str)
840  {
841  const size_type __size = __str.size();
842  if (__size)
843  {
844  const size_type __len = __size + this->size();
845  if (__len > this->capacity() || _M_rep()->_M_is_shared())
846  this->reserve(__len);
847  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
848  _M_rep()->_M_set_length_and_sharable(__len);
849  }
850  return *this;
851  }
852 
853  template<typename _CharT, typename _Traits, typename _Alloc>
856  append(const basic_string& __str, size_type __pos, size_type __n)
857  {
858  __str._M_check(__pos, "basic_string::append");
859  __n = __str._M_limit(__pos, __n);
860  if (__n)
861  {
862  const size_type __len = __n + this->size();
863  if (__len > this->capacity() || _M_rep()->_M_is_shared())
864  this->reserve(__len);
865  _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
866  _M_rep()->_M_set_length_and_sharable(__len);
867  }
868  return *this;
869  }
870 
871  template<typename _CharT, typename _Traits, typename _Alloc>
874  insert(size_type __pos, const _CharT* __s, size_type __n)
875  {
876  __glibcxx_requires_string_len(__s, __n);
877  _M_check(__pos, "basic_string::insert");
878  _M_check_length(size_type(0), __n, "basic_string::insert");
879  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
880  return _M_replace_safe(__pos, size_type(0), __s, __n);
881  else
882  {
883  // Work in-place.
884  const size_type __off = __s - _M_data();
885  _M_mutate(__pos, 0, __n);
886  __s = _M_data() + __off;
887  _CharT* __p = _M_data() + __pos;
888  if (__s + __n <= __p)
889  _M_copy(__p, __s, __n);
890  else if (__s >= __p)
891  _M_copy(__p, __s + __n, __n);
892  else
893  {
894  const size_type __nleft = __p - __s;
895  _M_copy(__p, __s, __nleft);
896  _M_copy(__p + __nleft, __p + __n, __n - __nleft);
897  }
898  return *this;
899  }
900  }
901 
902  template<typename _CharT, typename _Traits, typename _Alloc>
903  typename basic_string<_CharT, _Traits, _Alloc>::iterator
905  erase(iterator __first, iterator __last)
906  {
907  _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
908  && __last <= _M_iend());
909 
910  // NB: This isn't just an optimization (bail out early when
911  // there is nothing to do, really), it's also a correctness
912  // issue vs MT, see libstdc++/40518.
913  const size_type __size = __last - __first;
914  if (__size)
915  {
916  const size_type __pos = __first - _M_ibegin();
917  _M_mutate(__pos, __size, size_type(0));
918  _M_rep()->_M_set_leaked();
919  return iterator(_M_data() + __pos);
920  }
921  else
922  return __first;
923  }
924 
925  template<typename _CharT, typename _Traits, typename _Alloc>
928  replace(size_type __pos, size_type __n1, const _CharT* __s,
929  size_type __n2)
930  {
931  __glibcxx_requires_string_len(__s, __n2);
932  _M_check(__pos, "basic_string::replace");
933  __n1 = _M_limit(__pos, __n1);
934  _M_check_length(__n1, __n2, "basic_string::replace");
935  bool __left;
936  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
937  return _M_replace_safe(__pos, __n1, __s, __n2);
938  else if ((__left = __s + __n2 <= _M_data() + __pos)
939  || _M_data() + __pos + __n1 <= __s)
940  {
941  // Work in-place: non-overlapping case.
942  size_type __off = __s - _M_data();
943  __left ? __off : (__off += __n2 - __n1);
944  _M_mutate(__pos, __n1, __n2);
945  _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
946  return *this;
947  }
948  else
949  {
950  // Todo: overlapping case.
951  const basic_string __tmp(__s, __n2);
952  return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
953  }
954  }
955 
956  template<typename _CharT, typename _Traits, typename _Alloc>
957  void
959  _M_destroy(const _Alloc& __a) throw ()
960  {
961  const size_type __size = sizeof(_Rep_base) +
962  (this->_M_capacity + 1) * sizeof(_CharT);
963  _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
964  }
965 
966  template<typename _CharT, typename _Traits, typename _Alloc>
967  void
970  {
971 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
972  if (_M_rep() == &_S_empty_rep())
973  return;
974 #endif
975  if (_M_rep()->_M_is_shared())
976  _M_mutate(0, 0, 0);
977  _M_rep()->_M_set_leaked();
978  }
979 
980  template<typename _CharT, typename _Traits, typename _Alloc>
981  void
983  _M_mutate(size_type __pos, size_type __len1, size_type __len2)
984  {
985  const size_type __old_size = this->size();
986  const size_type __new_size = __old_size + __len2 - __len1;
987  const size_type __how_much = __old_size - __pos - __len1;
988 
989  if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
990  {
991  // Must reallocate.
992  const allocator_type __a = get_allocator();
993  _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
994 
995  if (__pos)
996  _M_copy(__r->_M_refdata(), _M_data(), __pos);
997  if (__how_much)
998  _M_copy(__r->_M_refdata() + __pos + __len2,
999  _M_data() + __pos + __len1, __how_much);
1000 
1001  _M_rep()->_M_dispose(__a);
1002  _M_data(__r->_M_refdata());
1003  }
1004  else if (__how_much && __len1 != __len2)
1005  {
1006  // Work in-place.
1007  _M_move(_M_data() + __pos + __len2,
1008  _M_data() + __pos + __len1, __how_much);
1009  }
1010  _M_rep()->_M_set_length_and_sharable(__new_size);
1011  }
1012 
1013  template<typename _CharT, typename _Traits, typename _Alloc>
1014  void
1016  reserve(size_type __res)
1017  {
1018  if (__res != this->capacity() || _M_rep()->_M_is_shared())
1019  {
1020  // Make sure we don't shrink below the current size
1021  if (__res < this->size())
1022  __res = this->size();
1023  const allocator_type __a = get_allocator();
1024  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
1025  _M_rep()->_M_dispose(__a);
1026  _M_data(__tmp);
1027  }
1028  }
1029 
1030  template<typename _CharT, typename _Traits, typename _Alloc>
1031  void
1034  {
1035  if (_M_rep()->_M_is_leaked())
1036  _M_rep()->_M_set_sharable();
1037  if (__s._M_rep()->_M_is_leaked())
1038  __s._M_rep()->_M_set_sharable();
1039  if (this->get_allocator() == __s.get_allocator())
1040  {
1041  _CharT* __tmp = _M_data();
1042  _M_data(__s._M_data());
1043  __s._M_data(__tmp);
1044  }
1045  // The code below can usually be optimized away.
1046  else
1047  {
1048  const basic_string __tmp1(_M_ibegin(), _M_iend(),
1049  __s.get_allocator());
1050  const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
1051  this->get_allocator());
1052  *this = __tmp2;
1053  __s = __tmp1;
1054  }
1055  }
1056 
1057  template<typename _CharT, typename _Traits, typename _Alloc>
1060  _S_create(size_type __capacity, size_type __old_capacity,
1061  const _Alloc& __alloc)
1062  {
1063  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1064  // 83. String::npos vs. string::max_size()
1065  if (__capacity > _S_max_size)
1066  __throw_length_error(__N("basic_string::_S_create"));
1067 
1068  // The standard places no restriction on allocating more memory
1069  // than is strictly needed within this layer at the moment or as
1070  // requested by an explicit application call to reserve().
1071 
1072  // Many malloc implementations perform quite poorly when an
1073  // application attempts to allocate memory in a stepwise fashion
1074  // growing each allocation size by only 1 char. Additionally,
1075  // it makes little sense to allocate less linear memory than the
1076  // natural blocking size of the malloc implementation.
1077  // Unfortunately, we would need a somewhat low-level calculation
1078  // with tuned parameters to get this perfect for any particular
1079  // malloc implementation. Fortunately, generalizations about
1080  // common features seen among implementations seems to suffice.
1081 
1082  // __pagesize need not match the actual VM page size for good
1083  // results in practice, thus we pick a common value on the low
1084  // side. __malloc_header_size is an estimate of the amount of
1085  // overhead per memory allocation (in practice seen N * sizeof
1086  // (void*) where N is 0, 2 or 4). According to folklore,
1087  // picking this value on the high side is better than
1088  // low-balling it (especially when this algorithm is used with
1089  // malloc implementations that allocate memory blocks rounded up
1090  // to a size which is a power of 2).
1091  const size_type __pagesize = 4096;
1092  const size_type __malloc_header_size = 4 * sizeof(void*);
1093 
1094  // The below implements an exponential growth policy, necessary to
1095  // meet amortized linear time requirements of the library: see
1096  // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
1097  // It's active for allocations requiring an amount of memory above
1098  // system pagesize. This is consistent with the requirements of the
1099  // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
1100  if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
1101  __capacity = 2 * __old_capacity;
1102 
1103  // NB: Need an array of char_type[__capacity], plus a terminating
1104  // null char_type() element, plus enough for the _Rep data structure.
1105  // Whew. Seemingly so needy, yet so elemental.
1106  size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1107 
1108  const size_type __adj_size = __size + __malloc_header_size;
1109  if (__adj_size > __pagesize && __capacity > __old_capacity)
1110  {
1111  const size_type __extra = __pagesize - __adj_size % __pagesize;
1112  __capacity += __extra / sizeof(_CharT);
1113  // Never allocate a string bigger than _S_max_size.
1114  if (__capacity > _S_max_size)
1115  __capacity = _S_max_size;
1116  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1117  }
1118 
1119  // NB: Might throw, but no worries about a leak, mate: _Rep()
1120  // does not throw.
1121  void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
1122  _Rep *__p = new (__place) _Rep;
1123  __p->_M_capacity = __capacity;
1124  // ABI compatibility - 3.4.x set in _S_create both
1125  // _M_refcount and _M_length. All callers of _S_create
1126  // in basic_string.tcc then set just _M_length.
1127  // In 4.0.x and later both _M_refcount and _M_length
1128  // are initialized in the callers, unfortunately we can
1129  // have 3.4.x compiled code with _S_create callers inlined
1130  // calling 4.0.x+ _S_create.
1131  __p->_M_set_sharable();
1132  return __p;
1133  }
1134 
1135  template<typename _CharT, typename _Traits, typename _Alloc>
1136  _CharT*
1138  _M_clone(const _Alloc& __alloc, size_type __res)
1139  {
1140  // Requested capacity of the clone.
1141  const size_type __requested_cap = this->_M_length + __res;
1142  _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
1143  __alloc);
1144  if (this->_M_length)
1145  _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
1146 
1147  __r->_M_set_length_and_sharable(this->_M_length);
1148  return __r->_M_refdata();
1149  }
1150 
1151  template<typename _CharT, typename _Traits, typename _Alloc>
1152  void
1154  resize(size_type __n, _CharT __c)
1155  {
1156  const size_type __size = this->size();
1157  _M_check_length(__size, __n, "basic_string::resize");
1158  if (__size < __n)
1159  this->append(__n - __size, __c);
1160  else if (__n < __size)
1161  this->erase(__n);
1162  // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
1163  }
1164 
1165  template<typename _CharT, typename _Traits, typename _Alloc>
1166  template<typename _InputIterator>
1169  _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1170  _InputIterator __k2, __false_type)
1171  {
1172  const basic_string __s(__k1, __k2);
1173  const size_type __n1 = __i2 - __i1;
1174  _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
1175  return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
1176  __s.size());
1177  }
1178 
1179  template<typename _CharT, typename _Traits, typename _Alloc>
1182  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1183  _CharT __c)
1184  {
1185  _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
1186  _M_mutate(__pos1, __n1, __n2);
1187  if (__n2)
1188  _M_assign(_M_data() + __pos1, __n2, __c);
1189  return *this;
1190  }
1191 
1192  template<typename _CharT, typename _Traits, typename _Alloc>
1195  _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1196  size_type __n2)
1197  {
1198  _M_mutate(__pos1, __n1, __n2);
1199  if (__n2)
1200  _M_copy(_M_data() + __pos1, __s, __n2);
1201  return *this;
1202  }
1203 
1204  template<typename _CharT, typename _Traits, typename _Alloc>
1205  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1207  copy(_CharT* __s, size_type __n, size_type __pos) const
1208  {
1209  _M_check(__pos, "basic_string::copy");
1210  __n = _M_limit(__pos, __n);
1211  __glibcxx_requires_string_len(__s, __n);
1212  if (__n)
1213  _M_copy(__s, _M_data() + __pos, __n);
1214  // 21.3.5.7 par 3: do not append null. (good.)
1215  return __n;
1216  }
1217 #endif // !_GLIBCXX_USE_CXX11_ABI
1218 
1219  template<typename _CharT, typename _Traits, typename _Alloc>
1221  operator+(const _CharT* __lhs,
1223  {
1224  __glibcxx_requires_string(__lhs);
1225  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1226  typedef typename __string_type::size_type __size_type;
1227  const __size_type __len = _Traits::length(__lhs);
1228  __string_type __str;
1229  __str.reserve(__len + __rhs.size());
1230  __str.append(__lhs, __len);
1231  __str.append(__rhs);
1232  return __str;
1233  }
1234 
1235  template<typename _CharT, typename _Traits, typename _Alloc>
1237  operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1238  {
1239  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1240  typedef typename __string_type::size_type __size_type;
1241  __string_type __str;
1242  const __size_type __len = __rhs.size();
1243  __str.reserve(__len + 1);
1244  __str.append(__size_type(1), __lhs);
1245  __str.append(__rhs);
1246  return __str;
1247  }
1248 
1249  template<typename _CharT, typename _Traits, typename _Alloc>
1250  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1252  find(const _CharT* __s, size_type __pos, size_type __n) const
1253  _GLIBCXX_NOEXCEPT
1254  {
1255  __glibcxx_requires_string_len(__s, __n);
1256  const size_type __size = this->size();
1257 
1258  if (__n == 0)
1259  return __pos <= __size ? __pos : npos;
1260  if (__pos >= __size)
1261  return npos;
1262 
1263  const _CharT __elem0 = __s[0];
1264  const _CharT* const __data = data();
1265  const _CharT* __first = __data + __pos;
1266  const _CharT* const __last = __data + __size;
1267  size_type __len = __size - __pos;
1268 
1269  while (__len >= __n)
1270  {
1271  // Find the first occurrence of __elem0:
1272  __first = traits_type::find(__first, __len - __n + 1, __elem0);
1273  if (!__first)
1274  return npos;
1275  // Compare the full strings from the first occurrence of __elem0.
1276  // We already know that __first[0] == __s[0] but compare them again
1277  // anyway because __s is probably aligned, which helps memcmp.
1278  if (traits_type::compare(__first, __s, __n) == 0)
1279  return __first - __data;
1280  __len = __last - ++__first;
1281  }
1282  return npos;
1283  }
1284 
1285  template<typename _CharT, typename _Traits, typename _Alloc>
1286  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1288  find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1289  {
1290  size_type __ret = npos;
1291  const size_type __size = this->size();
1292  if (__pos < __size)
1293  {
1294  const _CharT* __data = _M_data();
1295  const size_type __n = __size - __pos;
1296  const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
1297  if (__p)
1298  __ret = __p - __data;
1299  }
1300  return __ret;
1301  }
1302 
1303  template<typename _CharT, typename _Traits, typename _Alloc>
1304  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1306  rfind(const _CharT* __s, size_type __pos, size_type __n) const
1307  _GLIBCXX_NOEXCEPT
1308  {
1309  __glibcxx_requires_string_len(__s, __n);
1310  const size_type __size = this->size();
1311  if (__n <= __size)
1312  {
1313  __pos = std::min(size_type(__size - __n), __pos);
1314  const _CharT* __data = _M_data();
1315  do
1316  {
1317  if (traits_type::compare(__data + __pos, __s, __n) == 0)
1318  return __pos;
1319  }
1320  while (__pos-- > 0);
1321  }
1322  return npos;
1323  }
1324 
1325  template<typename _CharT, typename _Traits, typename _Alloc>
1326  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1328  rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1329  {
1330  size_type __size = this->size();
1331  if (__size)
1332  {
1333  if (--__size > __pos)
1334  __size = __pos;
1335  for (++__size; __size-- > 0; )
1336  if (traits_type::eq(_M_data()[__size], __c))
1337  return __size;
1338  }
1339  return npos;
1340  }
1341 
1342  template<typename _CharT, typename _Traits, typename _Alloc>
1343  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1345  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
1346  _GLIBCXX_NOEXCEPT
1347  {
1348  __glibcxx_requires_string_len(__s, __n);
1349  for (; __n && __pos < this->size(); ++__pos)
1350  {
1351  const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
1352  if (__p)
1353  return __pos;
1354  }
1355  return npos;
1356  }
1357 
1358  template<typename _CharT, typename _Traits, typename _Alloc>
1359  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1361  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
1362  _GLIBCXX_NOEXCEPT
1363  {
1364  __glibcxx_requires_string_len(__s, __n);
1365  size_type __size = this->size();
1366  if (__size && __n)
1367  {
1368  if (--__size > __pos)
1369  __size = __pos;
1370  do
1371  {
1372  if (traits_type::find(__s, __n, _M_data()[__size]))
1373  return __size;
1374  }
1375  while (__size-- != 0);
1376  }
1377  return npos;
1378  }
1379 
1380  template<typename _CharT, typename _Traits, typename _Alloc>
1381  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1383  find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1384  _GLIBCXX_NOEXCEPT
1385  {
1386  __glibcxx_requires_string_len(__s, __n);
1387  for (; __pos < this->size(); ++__pos)
1388  if (!traits_type::find(__s, __n, _M_data()[__pos]))
1389  return __pos;
1390  return npos;
1391  }
1392 
1393  template<typename _CharT, typename _Traits, typename _Alloc>
1394  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1396  find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1397  {
1398  for (; __pos < this->size(); ++__pos)
1399  if (!traits_type::eq(_M_data()[__pos], __c))
1400  return __pos;
1401  return npos;
1402  }
1403 
1404  template<typename _CharT, typename _Traits, typename _Alloc>
1405  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1407  find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1408  _GLIBCXX_NOEXCEPT
1409  {
1410  __glibcxx_requires_string_len(__s, __n);
1411  size_type __size = this->size();
1412  if (__size)
1413  {
1414  if (--__size > __pos)
1415  __size = __pos;
1416  do
1417  {
1418  if (!traits_type::find(__s, __n, _M_data()[__size]))
1419  return __size;
1420  }
1421  while (__size--);
1422  }
1423  return npos;
1424  }
1425 
1426  template<typename _CharT, typename _Traits, typename _Alloc>
1427  typename basic_string<_CharT, _Traits, _Alloc>::size_type
1429  find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1430  {
1431  size_type __size = this->size();
1432  if (__size)
1433  {
1434  if (--__size > __pos)
1435  __size = __pos;
1436  do
1437  {
1438  if (!traits_type::eq(_M_data()[__size], __c))
1439  return __size;
1440  }
1441  while (__size--);
1442  }
1443  return npos;
1444  }
1445 
1446  template<typename _CharT, typename _Traits, typename _Alloc>
1447  int
1449  compare(size_type __pos, size_type __n, const basic_string& __str) const
1450  {
1451  _M_check(__pos, "basic_string::compare");
1452  __n = _M_limit(__pos, __n);
1453  const size_type __osize = __str.size();
1454  const size_type __len = std::min(__n, __osize);
1455  int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
1456  if (!__r)
1457  __r = _S_compare(__n, __osize);
1458  return __r;
1459  }
1460 
1461  template<typename _CharT, typename _Traits, typename _Alloc>
1462  int
1464  compare(size_type __pos1, size_type __n1, const basic_string& __str,
1465  size_type __pos2, size_type __n2) const
1466  {
1467  _M_check(__pos1, "basic_string::compare");
1468  __str._M_check(__pos2, "basic_string::compare");
1469  __n1 = _M_limit(__pos1, __n1);
1470  __n2 = __str._M_limit(__pos2, __n2);
1471  const size_type __len = std::min(__n1, __n2);
1472  int __r = traits_type::compare(_M_data() + __pos1,
1473  __str.data() + __pos2, __len);
1474  if (!__r)
1475  __r = _S_compare(__n1, __n2);
1476  return __r;
1477  }
1478 
1479  template<typename _CharT, typename _Traits, typename _Alloc>
1480  int
1482  compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
1483  {
1484  __glibcxx_requires_string(__s);
1485  const size_type __size = this->size();
1486  const size_type __osize = traits_type::length(__s);
1487  const size_type __len = std::min(__size, __osize);
1488  int __r = traits_type::compare(_M_data(), __s, __len);
1489  if (!__r)
1490  __r = _S_compare(__size, __osize);
1491  return __r;
1492  }
1493 
1494  template<typename _CharT, typename _Traits, typename _Alloc>
1495  int
1497  compare(size_type __pos, size_type __n1, const _CharT* __s) const
1498  {
1499  __glibcxx_requires_string(__s);
1500  _M_check(__pos, "basic_string::compare");
1501  __n1 = _M_limit(__pos, __n1);
1502  const size_type __osize = traits_type::length(__s);
1503  const size_type __len = std::min(__n1, __osize);
1504  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1505  if (!__r)
1506  __r = _S_compare(__n1, __osize);
1507  return __r;
1508  }
1509 
1510  template<typename _CharT, typename _Traits, typename _Alloc>
1511  int
1513  compare(size_type __pos, size_type __n1, const _CharT* __s,
1514  size_type __n2) const
1515  {
1516  __glibcxx_requires_string_len(__s, __n2);
1517  _M_check(__pos, "basic_string::compare");
1518  __n1 = _M_limit(__pos, __n1);
1519  const size_type __len = std::min(__n1, __n2);
1520  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1521  if (!__r)
1522  __r = _S_compare(__n1, __n2);
1523  return __r;
1524  }
1525 
1526  // 21.3.7.9 basic_string::getline and operators
1527  template<typename _CharT, typename _Traits, typename _Alloc>
1531  {
1532  typedef basic_istream<_CharT, _Traits> __istream_type;
1533  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1534  typedef typename __istream_type::ios_base __ios_base;
1535  typedef typename __istream_type::int_type __int_type;
1536  typedef typename __string_type::size_type __size_type;
1537  typedef ctype<_CharT> __ctype_type;
1538  typedef typename __ctype_type::ctype_base __ctype_base;
1539 
1540  __size_type __extracted = 0;
1541  typename __ios_base::iostate __err = __ios_base::goodbit;
1542  typename __istream_type::sentry __cerb(__in, false);
1543  if (__cerb)
1544  {
1545  __try
1546  {
1547  // Avoid reallocation for common case.
1548  __str.erase();
1549  _CharT __buf[128];
1550  __size_type __len = 0;
1551  const streamsize __w = __in.width();
1552  const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1553  : __str.max_size();
1554  const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1555  const __int_type __eof = _Traits::eof();
1556  __int_type __c = __in.rdbuf()->sgetc();
1557 
1558  while (__extracted < __n
1559  && !_Traits::eq_int_type(__c, __eof)
1560  && !__ct.is(__ctype_base::space,
1561  _Traits::to_char_type(__c)))
1562  {
1563  if (__len == sizeof(__buf) / sizeof(_CharT))
1564  {
1565  __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1566  __len = 0;
1567  }
1568  __buf[__len++] = _Traits::to_char_type(__c);
1569  ++__extracted;
1570  __c = __in.rdbuf()->snextc();
1571  }
1572  __str.append(__buf, __len);
1573 
1574  if (_Traits::eq_int_type(__c, __eof))
1575  __err |= __ios_base::eofbit;
1576  __in.width(0);
1577  }
1578  __catch(__cxxabiv1::__forced_unwind&)
1579  {
1580  __in._M_setstate(__ios_base::badbit);
1581  __throw_exception_again;
1582  }
1583  __catch(...)
1584  {
1585  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1586  // 91. Description of operator>> and getline() for string<>
1587  // might cause endless loop
1588  __in._M_setstate(__ios_base::badbit);
1589  }
1590  }
1591  // 211. operator>>(istream&, string&) doesn't set failbit
1592  if (!__extracted)
1593  __err |= __ios_base::failbit;
1594  if (__err)
1595  __in.setstate(__err);
1596  return __in;
1597  }
1598 
1599  template<typename _CharT, typename _Traits, typename _Alloc>
1602  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1603  {
1604  typedef basic_istream<_CharT, _Traits> __istream_type;
1605  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1606  typedef typename __istream_type::ios_base __ios_base;
1607  typedef typename __istream_type::int_type __int_type;
1608  typedef typename __string_type::size_type __size_type;
1609 
1610  __size_type __extracted = 0;
1611  const __size_type __n = __str.max_size();
1612  typename __ios_base::iostate __err = __ios_base::goodbit;
1613  typename __istream_type::sentry __cerb(__in, true);
1614  if (__cerb)
1615  {
1616  __try
1617  {
1618  __str.erase();
1619  const __int_type __idelim = _Traits::to_int_type(__delim);
1620  const __int_type __eof = _Traits::eof();
1621  __int_type __c = __in.rdbuf()->sgetc();
1622 
1623  while (__extracted < __n
1624  && !_Traits::eq_int_type(__c, __eof)
1625  && !_Traits::eq_int_type(__c, __idelim))
1626  {
1627  __str += _Traits::to_char_type(__c);
1628  ++__extracted;
1629  __c = __in.rdbuf()->snextc();
1630  }
1631 
1632  if (_Traits::eq_int_type(__c, __eof))
1633  __err |= __ios_base::eofbit;
1634  else if (_Traits::eq_int_type(__c, __idelim))
1635  {
1636  ++__extracted;
1637  __in.rdbuf()->sbumpc();
1638  }
1639  else
1640  __err |= __ios_base::failbit;
1641  }
1642  __catch(__cxxabiv1::__forced_unwind&)
1643  {
1644  __in._M_setstate(__ios_base::badbit);
1645  __throw_exception_again;
1646  }
1647  __catch(...)
1648  {
1649  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1650  // 91. Description of operator>> and getline() for string<>
1651  // might cause endless loop
1652  __in._M_setstate(__ios_base::badbit);
1653  }
1654  }
1655  if (!__extracted)
1656  __err |= __ios_base::failbit;
1657  if (__err)
1658  __in.setstate(__err);
1659  return __in;
1660  }
1661 
1662  // Inhibit implicit instantiations for required instantiations,
1663  // which are defined via explicit instantiations elsewhere.
1664 #if _GLIBCXX_EXTERN_TEMPLATE > 0 && __cplusplus <= 201402L
1665  extern template class basic_string<char>;
1666  extern template
1668  operator>>(basic_istream<char>&, string&);
1669  extern template
1671  operator<<(basic_ostream<char>&, const string&);
1672  extern template
1674  getline(basic_istream<char>&, string&, char);
1675  extern template
1677  getline(basic_istream<char>&, string&);
1678 
1679 #ifdef _GLIBCXX_USE_WCHAR_T
1680  extern template class basic_string<wchar_t>;
1681  extern template
1684  extern template
1686  operator<<(basic_ostream<wchar_t>&, const wstring&);
1687  extern template
1689  getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1690  extern template
1693 #endif
1694 #endif
1695 
1696 _GLIBCXX_END_NAMESPACE_VERSION
1697 } // namespace std
1698 
1699 #endif
size_type copy(_CharT *__s, size_type __n, size_type __pos=0) const
Copy substring into C string.
size_type max_size() const noexcept
Returns the size() of the largest possible string.
Thrown as part of forced unwinding.A magic placeholder class that can be caught by reference to recog...
Definition: cxxabi_forced.h:48
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:157
streamsize width() const
Flags access.
Definition: ios_base.h:712
initializer_list
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
ISO C++ entities toplevel namespace is std.
Primary class template ctype facet.This template class defines classification and conversion function...
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
basic_string & append(const basic_string &__str)
Append a string to this string.
Managing sequences of characters and character-like objects.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:87
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:321
basic_string & erase(size_type __pos=0, size_type __n=npos)
Remove characters.
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1462
void reserve(size_type __res_arg=0)
Attempt to preallocate enough memory for specified number of characters.
void resize(size_type __n, _CharT __c)
Resizes the string to the specified number of characters.
locale getloc() const
Locale access.
Definition: ios_base.h:763
ptrdiff_t streamsize
Integral type for I/O operation counts and buffer sizes.
Definition: postypes.h:98
basic_string()
Default constructor creates an empty string.
void swap(basic_string &__s)
Swap contents with another string.
Marking input iterators.
allocator_type get_allocator() const noexcept
Return copy of allocator used to construct this string.
static const size_type npos
Value returned by various member functions when they fail.
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.
const _CharT * data() const noexcept
Return const pointer to contents.
Template class basic_istream.
Definition: iosfwd:83
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
Forward iterators support a superset of input iterator operations.