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