* testsuite/26_numerics/headers/cmath/hypot.cc: XFAIL on AIX.
[official-gcc.git] / libstdc++-v3 / include / bits / basic_string.tcc
blobdf1e8ddec75f730fdb20830ff93460d154e4bd79
1 // Components for manipulating sequences of characters -*- C++ -*-
3 // Copyright (C) 1997-2016 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.
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.
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.
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/>.
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  */
31 // ISO C++ 14882: 21  Strings library
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.
39 #ifndef _BASIC_STRING_TCC
40 #define _BASIC_STRING_TCC 1
42 #pragma GCC system_header
44 #include <bits/cxxabi_forced.h>
46 namespace std _GLIBCXX_VISIBILITY(default)
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
50 #if _GLIBCXX_USE_CXX11_ABI
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;
56   template<typename _CharT, typename _Traits, typename _Alloc>
57     void
58     basic_string<_CharT, _Traits, _Alloc>::
59     swap(basic_string& __s) _GLIBCXX_NOEXCEPT
60     {
61       if (this == &__s)
62         return;
64       _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
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         }
125       const size_type __tmp_length = length();
126       _M_length(__s.length());
127       __s._M_length(__tmp_length);
128     }
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"));
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         }
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     }
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,
165                    std::input_iterator_tag)
166       {
167         size_type __len = 0;
168         size_type __capacity = size_type(_S_local_capacity);
170         while (__beg != __end && __len < __capacity)
171           {
172             _M_data()[__len++] = *__beg;
173             ++__beg;
174           }
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           }
200         _M_set_length(__len);
201       }
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,
208                    std::forward_iterator_tag)
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"));
215         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
217         if (__dnew > size_type(_S_local_capacity))
218           {
219             _M_data(_M_create(__dnew, size_type(0)));
220             _M_capacity(__dnew);
221           }
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           }
232         _M_set_length(__dnew);
233       }
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         }
246       if (__n)
247         this->_S_assign(_M_data(), __n, __c);
249       _M_set_length(__n);
250     }
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();
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             }
271           if (__rsize)
272             this->_S_copy(_M_data(), __str._M_data(), __rsize);
274           _M_set_length(__rsize);
275         }
276     }
278   template<typename _CharT, typename _Traits, typename _Alloc>
279     void
280     basic_string<_CharT, _Traits, _Alloc>::
281     reserve(size_type __res)
282     {
283       // Make sure we don't shrink below the current size.
284       if (__res < length())
285         __res = length();
287       const size_type __capacity = capacity();
288       if (__res != __capacity)
289         {
290           if (__res > __capacity
291               || __res > size_type(_S_local_capacity))
292             {
293               pointer __tmp = _M_create(__res, __capacity);
294               this->_S_copy(__tmp, _M_data(), length() + 1);
295               _M_dispose();
296               _M_data(__tmp);
297               _M_capacity(__res);
298             }
299           else if (!_M_is_local())
300             {
301               this->_S_copy(_M_local_data(), _M_data(), length() + 1);
302               _M_destroy(__capacity);
303               _M_data(_M_local_data());
304             }
305         }
306     }
308   template<typename _CharT, typename _Traits, typename _Alloc>
309     void
310     basic_string<_CharT, _Traits, _Alloc>::
311     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
312               size_type __len2)
313     {
314       const size_type __how_much = length() - __pos - __len1;
316       size_type __new_capacity = length() + __len2 - __len1;
317       pointer __r = _M_create(__new_capacity, capacity());
319       if (__pos)
320         this->_S_copy(__r, _M_data(), __pos);
321       if (__s && __len2)
322         this->_S_copy(__r + __pos, __s, __len2);
323       if (__how_much)
324         this->_S_copy(__r + __pos + __len2,
325                       _M_data() + __pos + __len1, __how_much);
327       _M_dispose();
328       _M_data(__r);
329       _M_capacity(__new_capacity);
330     }
332   template<typename _CharT, typename _Traits, typename _Alloc>
333     void
334     basic_string<_CharT, _Traits, _Alloc>::
335     _M_erase(size_type __pos, size_type __n)
336     {
337       const size_type __how_much = length() - __pos - __n;
339       if (__how_much && __n)
340         this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
342       _M_set_length(length() - __n);
343     }
345   template<typename _CharT, typename _Traits, typename _Alloc>
346     void
347     basic_string<_CharT, _Traits, _Alloc>::
348     resize(size_type __n, _CharT __c)
349     {
350       const size_type __size = this->size();
351       if (__size < __n)
352         this->append(__n - __size, __c);
353       else if (__n < __size)
354         this->_M_set_length(__n);
355     }
357   template<typename _CharT, typename _Traits, typename _Alloc>
358     basic_string<_CharT, _Traits, _Alloc>&
359     basic_string<_CharT, _Traits, _Alloc>::
360     _M_append(const _CharT* __s, size_type __n)
361     {
362       const size_type __len = __n + this->size();
364       if (__len <= this->capacity())
365         {
366           if (__n)
367             this->_S_copy(this->_M_data() + this->size(), __s, __n);
368         }
369       else
370         this->_M_mutate(this->size(), size_type(0), __s, __n);
372       this->_M_set_length(__len);
373       return *this;
374     }
376   template<typename _CharT, typename _Traits, typename _Alloc>
377     template<typename _InputIterator>
378       basic_string<_CharT, _Traits, _Alloc>&
379       basic_string<_CharT, _Traits, _Alloc>::
380       _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
381                           _InputIterator __k1, _InputIterator __k2,
382                           std::__false_type)
383       {
384         const basic_string __s(__k1, __k2);
385         const size_type __n1 = __i2 - __i1;
386         return _M_replace(__i1 - begin(), __n1, __s._M_data(),
387                           __s.size());
388       }
390   template<typename _CharT, typename _Traits, typename _Alloc>
391     basic_string<_CharT, _Traits, _Alloc>&
392     basic_string<_CharT, _Traits, _Alloc>::
393     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
394                    _CharT __c)
395     {
396       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
398       const size_type __old_size = this->size();
399       const size_type __new_size = __old_size + __n2 - __n1;
401       if (__new_size <= this->capacity())
402         {
403           pointer __p = this->_M_data() + __pos1;
405           const size_type __how_much = __old_size - __pos1 - __n1;
406           if (__how_much && __n1 != __n2)
407             this->_S_move(__p + __n2, __p + __n1, __how_much);
408         }
409       else
410         this->_M_mutate(__pos1, __n1, 0, __n2);
412       if (__n2)
413         this->_S_assign(this->_M_data() + __pos1, __n2, __c);
415       this->_M_set_length(__new_size);
416       return *this;
417     }
419   template<typename _CharT, typename _Traits, typename _Alloc>
420     basic_string<_CharT, _Traits, _Alloc>&
421     basic_string<_CharT, _Traits, _Alloc>::
422     _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
423                const size_type __len2)
424     {
425       _M_check_length(__len1, __len2, "basic_string::_M_replace");
427       const size_type __old_size = this->size();
428       const size_type __new_size = __old_size + __len2 - __len1;
430       if (__new_size <= this->capacity())
431         {
432           pointer __p = this->_M_data() + __pos;
434           const size_type __how_much = __old_size - __pos - __len1;
435           if (_M_disjunct(__s))
436             {
437               if (__how_much && __len1 != __len2)
438                 this->_S_move(__p + __len2, __p + __len1, __how_much);
439               if (__len2)
440                 this->_S_copy(__p, __s, __len2);
441             }
442           else
443             {
444               // Work in-place.
445               if (__len2 && __len2 <= __len1)
446                 this->_S_move(__p, __s, __len2);
447               if (__how_much && __len1 != __len2)
448                 this->_S_move(__p + __len2, __p + __len1, __how_much);
449               if (__len2 > __len1)
450                 {
451                   if (__s + __len2 <= __p + __len1)
452                     this->_S_move(__p, __s, __len2);
453                   else if (__s >= __p + __len1)
454                     this->_S_copy(__p, __s + __len2 - __len1, __len2);
455                   else
456                     {
457                       const size_type __nleft = (__p + __len1) - __s;
458                       this->_S_move(__p, __s, __nleft);
459                       this->_S_copy(__p + __nleft, __p + __len2,
460                                     __len2 - __nleft);
461                     }
462                 }
463             }
464         }
465       else
466         this->_M_mutate(__pos, __len1, __s, __len2);
468       this->_M_set_length(__new_size);
469       return *this;
470     }
472   template<typename _CharT, typename _Traits, typename _Alloc>
473     typename basic_string<_CharT, _Traits, _Alloc>::size_type
474     basic_string<_CharT, _Traits, _Alloc>::
475     copy(_CharT* __s, size_type __n, size_type __pos) const
476     {
477       _M_check(__pos, "basic_string::copy");
478       __n = _M_limit(__pos, __n);
479       __glibcxx_requires_string_len(__s, __n);
480       if (__n)
481         _S_copy(__s, _M_data() + __pos, __n);
482       // 21.3.5.7 par 3: do not append null.  (good.)
483       return __n;
484     }
486 #else  // !_GLIBCXX_USE_CXX11_ABI
488   template<typename _CharT, typename _Traits, typename _Alloc>
489     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
490     basic_string<_CharT, _Traits, _Alloc>::
491     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
493   template<typename _CharT, typename _Traits, typename _Alloc>
494     const _CharT
495     basic_string<_CharT, _Traits, _Alloc>::
496     _Rep::_S_terminal = _CharT();
498   template<typename _CharT, typename _Traits, typename _Alloc>
499     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
500     basic_string<_CharT, _Traits, _Alloc>::npos;
502   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
503   // at static init time (before static ctors are run).
504   template<typename _CharT, typename _Traits, typename _Alloc>
505     typename basic_string<_CharT, _Traits, _Alloc>::size_type
506     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
507     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
508       sizeof(size_type)];
510   // NB: This is the special case for Input Iterators, used in
511   // istreambuf_iterators, etc.
512   // Input Iterators have a cost structure very different from
513   // pointers, calling for a different coding style.
514   template<typename _CharT, typename _Traits, typename _Alloc>
515     template<typename _InIterator>
516       _CharT*
517       basic_string<_CharT, _Traits, _Alloc>::
518       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
519                    input_iterator_tag)
520       {
521 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
522         if (__beg == __end && __a == _Alloc())
523           return _S_empty_rep()._M_refdata();
524 #endif
525         // Avoid reallocation for common case.
526         _CharT __buf[128];
527         size_type __len = 0;
528         while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
529           {
530             __buf[__len++] = *__beg;
531             ++__beg;
532           }
533         _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
534         _M_copy(__r->_M_refdata(), __buf, __len);
535         __try
536           {
537             while (__beg != __end)
538               {
539                 if (__len == __r->_M_capacity)
540                   {
541                     // Allocate more space.
542                     _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
543                     _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
544                     __r->_M_destroy(__a);
545                     __r = __another;
546                   }
547                 __r->_M_refdata()[__len++] = *__beg;
548                 ++__beg;
549               }
550           }
551         __catch(...)
552           {
553             __r->_M_destroy(__a);
554             __throw_exception_again;
555           }
556         __r->_M_set_length_and_sharable(__len);
557         return __r->_M_refdata();
558       }
560   template<typename _CharT, typename _Traits, typename _Alloc>
561     template <typename _InIterator>
562       _CharT*
563       basic_string<_CharT, _Traits, _Alloc>::
564       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
565                    forward_iterator_tag)
566       {
567 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
568         if (__beg == __end && __a == _Alloc())
569           return _S_empty_rep()._M_refdata();
570 #endif
571         // NB: Not required, but considered best practice.
572         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
573           __throw_logic_error(__N("basic_string::_S_construct null not valid"));
575         const size_type __dnew = static_cast<size_type>(std::distance(__beg,
576                                                                       __end));
577         // Check for out_of_range and length_error exceptions.
578         _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
579         __try
580           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
581         __catch(...)
582           {
583             __r->_M_destroy(__a);
584             __throw_exception_again;
585           }
586         __r->_M_set_length_and_sharable(__dnew);
587         return __r->_M_refdata();
588       }
590   template<typename _CharT, typename _Traits, typename _Alloc>
591     _CharT*
592     basic_string<_CharT, _Traits, _Alloc>::
593     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
594     {
595 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
596       if (__n == 0 && __a == _Alloc())
597         return _S_empty_rep()._M_refdata();
598 #endif
599       // Check for out_of_range and length_error exceptions.
600       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
601       if (__n)
602         _M_assign(__r->_M_refdata(), __n, __c);
604       __r->_M_set_length_and_sharable(__n);
605       return __r->_M_refdata();
606     }
608   template<typename _CharT, typename _Traits, typename _Alloc>
609     basic_string<_CharT, _Traits, _Alloc>::
610     basic_string(const basic_string& __str)
611     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
612                                           __str.get_allocator()),
613                   __str.get_allocator())
614     { }
616   template<typename _CharT, typename _Traits, typename _Alloc>
617     basic_string<_CharT, _Traits, _Alloc>::
618     basic_string(const _Alloc& __a)
619     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
620     { }
622   template<typename _CharT, typename _Traits, typename _Alloc>
623     basic_string<_CharT, _Traits, _Alloc>::
624     basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
625     : _M_dataplus(_S_construct(__str._M_data()
626                                + __str._M_check(__pos,
627                                                 "basic_string::basic_string"),
628                                __str._M_data() + __str._M_limit(__pos, npos)
629                                + __pos, __a), __a)
630     { }
632   template<typename _CharT, typename _Traits, typename _Alloc>
633     basic_string<_CharT, _Traits, _Alloc>::
634     basic_string(const basic_string& __str, size_type __pos, size_type __n)
635     : _M_dataplus(_S_construct(__str._M_data()
636                                + __str._M_check(__pos,
637                                                 "basic_string::basic_string"),
638                                __str._M_data() + __str._M_limit(__pos, __n)
639                                + __pos, _Alloc()), _Alloc())
640     { }
642   template<typename _CharT, typename _Traits, typename _Alloc>
643     basic_string<_CharT, _Traits, _Alloc>::
644     basic_string(const basic_string& __str, size_type __pos,
645                  size_type __n, const _Alloc& __a)
646     : _M_dataplus(_S_construct(__str._M_data()
647                                + __str._M_check(__pos,
648                                                 "basic_string::basic_string"),
649                                __str._M_data() + __str._M_limit(__pos, __n)
650                                + __pos, __a), __a)
651     { }
653   // TBD: DPG annotate
654   template<typename _CharT, typename _Traits, typename _Alloc>
655     basic_string<_CharT, _Traits, _Alloc>::
656     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
657     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
658     { }
660   // TBD: DPG annotate
661   template<typename _CharT, typename _Traits, typename _Alloc>
662     basic_string<_CharT, _Traits, _Alloc>::
663     basic_string(const _CharT* __s, const _Alloc& __a)
664     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
665                                __s + npos, __a), __a)
666     { }
668   template<typename _CharT, typename _Traits, typename _Alloc>
669     basic_string<_CharT, _Traits, _Alloc>::
670     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
671     : _M_dataplus(_S_construct(__n, __c, __a), __a)
672     { }
674   // TBD: DPG annotate
675   template<typename _CharT, typename _Traits, typename _Alloc>
676     template<typename _InputIterator>
677     basic_string<_CharT, _Traits, _Alloc>::
678     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
679     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
680     { }
682 #if __cplusplus >= 201103L
683   template<typename _CharT, typename _Traits, typename _Alloc>
684     basic_string<_CharT, _Traits, _Alloc>::
685     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
686     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
687     { }
688 #endif
690   template<typename _CharT, typename _Traits, typename _Alloc>
691     basic_string<_CharT, _Traits, _Alloc>&
692     basic_string<_CharT, _Traits, _Alloc>::
693     assign(const basic_string& __str)
694     {
695       if (_M_rep() != __str._M_rep())
696         {
697           // XXX MT
698           const allocator_type __a = this->get_allocator();
699           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
700           _M_rep()->_M_dispose(__a);
701           _M_data(__tmp);
702         }
703       return *this;
704     }
706   template<typename _CharT, typename _Traits, typename _Alloc>
707     basic_string<_CharT, _Traits, _Alloc>&
708     basic_string<_CharT, _Traits, _Alloc>::
709     assign(const _CharT* __s, size_type __n)
710     {
711       __glibcxx_requires_string_len(__s, __n);
712       _M_check_length(this->size(), __n, "basic_string::assign");
713       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
714         return _M_replace_safe(size_type(0), this->size(), __s, __n);
715       else
716         {
717           // Work in-place.
718           const size_type __pos = __s - _M_data();
719           if (__pos >= __n)
720             _M_copy(_M_data(), __s, __n);
721           else if (__pos)
722             _M_move(_M_data(), __s, __n);
723           _M_rep()->_M_set_length_and_sharable(__n);
724           return *this;
725         }
726      }
728   template<typename _CharT, typename _Traits, typename _Alloc>
729     basic_string<_CharT, _Traits, _Alloc>&
730     basic_string<_CharT, _Traits, _Alloc>::
731     append(size_type __n, _CharT __c)
732     {
733       if (__n)
734         {
735           _M_check_length(size_type(0), __n, "basic_string::append");     
736           const size_type __len = __n + this->size();
737           if (__len > this->capacity() || _M_rep()->_M_is_shared())
738             this->reserve(__len);
739           _M_assign(_M_data() + this->size(), __n, __c);
740           _M_rep()->_M_set_length_and_sharable(__len);
741         }
742       return *this;
743     }
745   template<typename _CharT, typename _Traits, typename _Alloc>
746     basic_string<_CharT, _Traits, _Alloc>&
747     basic_string<_CharT, _Traits, _Alloc>::
748     append(const _CharT* __s, size_type __n)
749     {
750       __glibcxx_requires_string_len(__s, __n);
751       if (__n)
752         {
753           _M_check_length(size_type(0), __n, "basic_string::append");
754           const size_type __len = __n + this->size();
755           if (__len > this->capacity() || _M_rep()->_M_is_shared())
756             {
757               if (_M_disjunct(__s))
758                 this->reserve(__len);
759               else
760                 {
761                   const size_type __off = __s - _M_data();
762                   this->reserve(__len);
763                   __s = _M_data() + __off;
764                 }
765             }
766           _M_copy(_M_data() + this->size(), __s, __n);
767           _M_rep()->_M_set_length_and_sharable(__len);
768         }
769       return *this;
770     }
772   template<typename _CharT, typename _Traits, typename _Alloc>
773     basic_string<_CharT, _Traits, _Alloc>&
774     basic_string<_CharT, _Traits, _Alloc>::
775     append(const basic_string& __str)
776     {
777       const size_type __size = __str.size();
778       if (__size)
779         {
780           const size_type __len = __size + this->size();
781           if (__len > this->capacity() || _M_rep()->_M_is_shared())
782             this->reserve(__len);
783           _M_copy(_M_data() + this->size(), __str._M_data(), __size);
784           _M_rep()->_M_set_length_and_sharable(__len);
785         }
786       return *this;
787     }    
789   template<typename _CharT, typename _Traits, typename _Alloc>
790     basic_string<_CharT, _Traits, _Alloc>&
791     basic_string<_CharT, _Traits, _Alloc>::
792     append(const basic_string& __str, size_type __pos, size_type __n)
793     {
794       __str._M_check(__pos, "basic_string::append");
795       __n = __str._M_limit(__pos, __n);
796       if (__n)
797         {
798           const size_type __len = __n + this->size();
799           if (__len > this->capacity() || _M_rep()->_M_is_shared())
800             this->reserve(__len);
801           _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
802           _M_rep()->_M_set_length_and_sharable(__len);    
803         }
804       return *this;
805     }
807    template<typename _CharT, typename _Traits, typename _Alloc>
808      basic_string<_CharT, _Traits, _Alloc>&
809      basic_string<_CharT, _Traits, _Alloc>::
810      insert(size_type __pos, const _CharT* __s, size_type __n)
811      {
812        __glibcxx_requires_string_len(__s, __n);
813        _M_check(__pos, "basic_string::insert");
814        _M_check_length(size_type(0), __n, "basic_string::insert");
815        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
816          return _M_replace_safe(__pos, size_type(0), __s, __n);
817        else
818          {
819            // Work in-place.
820            const size_type __off = __s - _M_data();
821            _M_mutate(__pos, 0, __n);
822            __s = _M_data() + __off;
823            _CharT* __p = _M_data() + __pos;
824            if (__s  + __n <= __p)
825              _M_copy(__p, __s, __n);
826            else if (__s >= __p)
827              _M_copy(__p, __s + __n, __n);
828            else
829              {
830                const size_type __nleft = __p - __s;
831                _M_copy(__p, __s, __nleft);
832                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
833              }
834            return *this;
835          }
836      }
838    template<typename _CharT, typename _Traits, typename _Alloc>
839      typename basic_string<_CharT, _Traits, _Alloc>::iterator
840      basic_string<_CharT, _Traits, _Alloc>::
841      erase(iterator __first, iterator __last)
842      {
843        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
844                                 && __last <= _M_iend());
846        // NB: This isn't just an optimization (bail out early when
847        // there is nothing to do, really), it's also a correctness
848        // issue vs MT, see libstdc++/40518.
849        const size_type __size = __last - __first;
850        if (__size)
851          {
852            const size_type __pos = __first - _M_ibegin();
853            _M_mutate(__pos, __size, size_type(0));
854            _M_rep()->_M_set_leaked();
855            return iterator(_M_data() + __pos);
856          }
857        else
858          return __first;
859      }
861    template<typename _CharT, typename _Traits, typename _Alloc>
862      basic_string<_CharT, _Traits, _Alloc>&
863      basic_string<_CharT, _Traits, _Alloc>::
864      replace(size_type __pos, size_type __n1, const _CharT* __s,
865              size_type __n2)
866      {
867        __glibcxx_requires_string_len(__s, __n2);
868        _M_check(__pos, "basic_string::replace");
869        __n1 = _M_limit(__pos, __n1);
870        _M_check_length(__n1, __n2, "basic_string::replace");
871        bool __left;
872        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
873          return _M_replace_safe(__pos, __n1, __s, __n2);
874        else if ((__left = __s + __n2 <= _M_data() + __pos)
875                 || _M_data() + __pos + __n1 <= __s)
876          {
877            // Work in-place: non-overlapping case.
878            size_type __off = __s - _M_data();
879            __left ? __off : (__off += __n2 - __n1);
880            _M_mutate(__pos, __n1, __n2);
881            _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
882            return *this;
883          }
884        else
885          {
886            // Todo: overlapping case.
887            const basic_string __tmp(__s, __n2);
888            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
889          }
890      }
892   template<typename _CharT, typename _Traits, typename _Alloc>
893     void
894     basic_string<_CharT, _Traits, _Alloc>::_Rep::
895     _M_destroy(const _Alloc& __a) throw ()
896     {
897       const size_type __size = sizeof(_Rep_base) +
898                                (this->_M_capacity + 1) * sizeof(_CharT);
899       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
900     }
902   template<typename _CharT, typename _Traits, typename _Alloc>
903     void
904     basic_string<_CharT, _Traits, _Alloc>::
905     _M_leak_hard()
906     {
907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
908       if (_M_rep() == &_S_empty_rep())
909         return;
910 #endif
911       if (_M_rep()->_M_is_shared())
912         _M_mutate(0, 0, 0);
913       _M_rep()->_M_set_leaked();
914     }
916   template<typename _CharT, typename _Traits, typename _Alloc>
917     void
918     basic_string<_CharT, _Traits, _Alloc>::
919     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
920     {
921       const size_type __old_size = this->size();
922       const size_type __new_size = __old_size + __len2 - __len1;
923       const size_type __how_much = __old_size - __pos - __len1;
925       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
926         {
927           // Must reallocate.
928           const allocator_type __a = get_allocator();
929           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
931           if (__pos)
932             _M_copy(__r->_M_refdata(), _M_data(), __pos);
933           if (__how_much)
934             _M_copy(__r->_M_refdata() + __pos + __len2,
935                     _M_data() + __pos + __len1, __how_much);
937           _M_rep()->_M_dispose(__a);
938           _M_data(__r->_M_refdata());
939         }
940       else if (__how_much && __len1 != __len2)
941         {
942           // Work in-place.
943           _M_move(_M_data() + __pos + __len2,
944                   _M_data() + __pos + __len1, __how_much);
945         }
946       _M_rep()->_M_set_length_and_sharable(__new_size);
947     }
949   template<typename _CharT, typename _Traits, typename _Alloc>
950     void
951     basic_string<_CharT, _Traits, _Alloc>::
952     reserve(size_type __res)
953     {
954       if (__res != this->capacity() || _M_rep()->_M_is_shared())
955         {
956           // Make sure we don't shrink below the current size
957           if (__res < this->size())
958             __res = this->size();
959           const allocator_type __a = get_allocator();
960           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
961           _M_rep()->_M_dispose(__a);
962           _M_data(__tmp);
963         }
964     }
966   template<typename _CharT, typename _Traits, typename _Alloc>
967     void
968     basic_string<_CharT, _Traits, _Alloc>::
969     swap(basic_string& __s)
970     {
971       if (_M_rep()->_M_is_leaked())
972         _M_rep()->_M_set_sharable();
973       if (__s._M_rep()->_M_is_leaked())
974         __s._M_rep()->_M_set_sharable();
975       if (this->get_allocator() == __s.get_allocator())
976         {
977           _CharT* __tmp = _M_data();
978           _M_data(__s._M_data());
979           __s._M_data(__tmp);
980         }
981       // The code below can usually be optimized away.
982       else
983         {
984           const basic_string __tmp1(_M_ibegin(), _M_iend(),
985                                     __s.get_allocator());
986           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
987                                     this->get_allocator());
988           *this = __tmp2;
989           __s = __tmp1;
990         }
991     }
993   template<typename _CharT, typename _Traits, typename _Alloc>
994     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
995     basic_string<_CharT, _Traits, _Alloc>::_Rep::
996     _S_create(size_type __capacity, size_type __old_capacity,
997               const _Alloc& __alloc)
998     {
999       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1000       // 83.  String::npos vs. string::max_size()
1001       if (__capacity > _S_max_size)
1002         __throw_length_error(__N("basic_string::_S_create"));
1004       // The standard places no restriction on allocating more memory
1005       // than is strictly needed within this layer at the moment or as
1006       // requested by an explicit application call to reserve().
1008       // Many malloc implementations perform quite poorly when an
1009       // application attempts to allocate memory in a stepwise fashion
1010       // growing each allocation size by only 1 char.  Additionally,
1011       // it makes little sense to allocate less linear memory than the
1012       // natural blocking size of the malloc implementation.
1013       // Unfortunately, we would need a somewhat low-level calculation
1014       // with tuned parameters to get this perfect for any particular
1015       // malloc implementation.  Fortunately, generalizations about
1016       // common features seen among implementations seems to suffice.
1018       // __pagesize need not match the actual VM page size for good
1019       // results in practice, thus we pick a common value on the low
1020       // side.  __malloc_header_size is an estimate of the amount of
1021       // overhead per memory allocation (in practice seen N * sizeof
1022       // (void*) where N is 0, 2 or 4).  According to folklore,
1023       // picking this value on the high side is better than
1024       // low-balling it (especially when this algorithm is used with
1025       // malloc implementations that allocate memory blocks rounded up
1026       // to a size which is a power of 2).
1027       const size_type __pagesize = 4096;
1028       const size_type __malloc_header_size = 4 * sizeof(void*);
1030       // The below implements an exponential growth policy, necessary to
1031       // meet amortized linear time requirements of the library: see
1032       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
1033       // It's active for allocations requiring an amount of memory above
1034       // system pagesize. This is consistent with the requirements of the
1035       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
1036       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
1037         __capacity = 2 * __old_capacity;
1039       // NB: Need an array of char_type[__capacity], plus a terminating
1040       // null char_type() element, plus enough for the _Rep data structure.
1041       // Whew. Seemingly so needy, yet so elemental.
1042       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1044       const size_type __adj_size = __size + __malloc_header_size;
1045       if (__adj_size > __pagesize && __capacity > __old_capacity)
1046         {
1047           const size_type __extra = __pagesize - __adj_size % __pagesize;
1048           __capacity += __extra / sizeof(_CharT);
1049           // Never allocate a string bigger than _S_max_size.
1050           if (__capacity > _S_max_size)
1051             __capacity = _S_max_size;
1052           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1053         }
1055       // NB: Might throw, but no worries about a leak, mate: _Rep()
1056       // does not throw.
1057       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
1058       _Rep *__p = new (__place) _Rep;
1059       __p->_M_capacity = __capacity;
1060       // ABI compatibility - 3.4.x set in _S_create both
1061       // _M_refcount and _M_length.  All callers of _S_create
1062       // in basic_string.tcc then set just _M_length.
1063       // In 4.0.x and later both _M_refcount and _M_length
1064       // are initialized in the callers, unfortunately we can
1065       // have 3.4.x compiled code with _S_create callers inlined
1066       // calling 4.0.x+ _S_create.
1067       __p->_M_set_sharable();
1068       return __p;
1069     }
1071   template<typename _CharT, typename _Traits, typename _Alloc>
1072     _CharT*
1073     basic_string<_CharT, _Traits, _Alloc>::_Rep::
1074     _M_clone(const _Alloc& __alloc, size_type __res)
1075     {
1076       // Requested capacity of the clone.
1077       const size_type __requested_cap = this->_M_length + __res;
1078       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
1079                                   __alloc);
1080       if (this->_M_length)
1081         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
1083       __r->_M_set_length_and_sharable(this->_M_length);
1084       return __r->_M_refdata();
1085     }
1087   template<typename _CharT, typename _Traits, typename _Alloc>
1088     void
1089     basic_string<_CharT, _Traits, _Alloc>::
1090     resize(size_type __n, _CharT __c)
1091     {
1092       const size_type __size = this->size();
1093       _M_check_length(__size, __n, "basic_string::resize");
1094       if (__size < __n)
1095         this->append(__n - __size, __c);
1096       else if (__n < __size)
1097         this->erase(__n);
1098       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
1099     }
1101   template<typename _CharT, typename _Traits, typename _Alloc>
1102     template<typename _InputIterator>
1103       basic_string<_CharT, _Traits, _Alloc>&
1104       basic_string<_CharT, _Traits, _Alloc>::
1105       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1106                           _InputIterator __k2, __false_type)
1107       {
1108         const basic_string __s(__k1, __k2);
1109         const size_type __n1 = __i2 - __i1;
1110         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
1111         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
1112                                __s.size());
1113       }
1115   template<typename _CharT, typename _Traits, typename _Alloc>
1116     basic_string<_CharT, _Traits, _Alloc>&
1117     basic_string<_CharT, _Traits, _Alloc>::
1118     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1119                    _CharT __c)
1120     {
1121       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
1122       _M_mutate(__pos1, __n1, __n2);
1123       if (__n2)
1124         _M_assign(_M_data() + __pos1, __n2, __c);
1125       return *this;
1126     }
1128   template<typename _CharT, typename _Traits, typename _Alloc>
1129     basic_string<_CharT, _Traits, _Alloc>&
1130     basic_string<_CharT, _Traits, _Alloc>::
1131     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1132                     size_type __n2)
1133     {
1134       _M_mutate(__pos1, __n1, __n2);
1135       if (__n2)
1136         _M_copy(_M_data() + __pos1, __s, __n2);
1137       return *this;
1138     }
1140     template<typename _CharT, typename _Traits, typename _Alloc>
1141     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1142     basic_string<_CharT, _Traits, _Alloc>::
1143     copy(_CharT* __s, size_type __n, size_type __pos) const
1144     {
1145       _M_check(__pos, "basic_string::copy");
1146       __n = _M_limit(__pos, __n);
1147       __glibcxx_requires_string_len(__s, __n);
1148       if (__n)
1149         _M_copy(__s, _M_data() + __pos, __n);
1150       // 21.3.5.7 par 3: do not append null.  (good.)
1151       return __n;
1152     }
1153 #endif  // !_GLIBCXX_USE_CXX11_ABI
1154    
1155   template<typename _CharT, typename _Traits, typename _Alloc>
1156     basic_string<_CharT, _Traits, _Alloc>
1157     operator+(const _CharT* __lhs,
1158               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1159     {
1160       __glibcxx_requires_string(__lhs);
1161       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1162       typedef typename __string_type::size_type   __size_type;
1163       const __size_type __len = _Traits::length(__lhs);
1164       __string_type __str;
1165       __str.reserve(__len + __rhs.size());
1166       __str.append(__lhs, __len);
1167       __str.append(__rhs);
1168       return __str;
1169     }
1171   template<typename _CharT, typename _Traits, typename _Alloc>
1172     basic_string<_CharT, _Traits, _Alloc>
1173     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1174     {
1175       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1176       typedef typename __string_type::size_type   __size_type;
1177       __string_type __str;
1178       const __size_type __len = __rhs.size();
1179       __str.reserve(__len + 1);
1180       __str.append(__size_type(1), __lhs);
1181       __str.append(__rhs);
1182       return __str;
1183     }
1185   template<typename _CharT, typename _Traits, typename _Alloc>
1186     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1187     basic_string<_CharT, _Traits, _Alloc>::
1188     find(const _CharT* __s, size_type __pos, size_type __n) const
1189     {
1190       __glibcxx_requires_string_len(__s, __n);
1191       const size_type __size = this->size();
1192       const _CharT* __data = _M_data();
1194       if (__n == 0)
1195         return __pos <= __size ? __pos : npos;
1197       if (__n <= __size)
1198         {
1199           for (; __pos <= __size - __n; ++__pos)
1200             if (traits_type::eq(__data[__pos], __s[0])
1201                 && traits_type::compare(__data + __pos + 1,
1202                                         __s + 1, __n - 1) == 0)
1203               return __pos;
1204         }
1205       return npos;
1206     }
1208   template<typename _CharT, typename _Traits, typename _Alloc>
1209     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1210     basic_string<_CharT, _Traits, _Alloc>::
1211     find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1212     {
1213       size_type __ret = npos;
1214       const size_type __size = this->size();
1215       if (__pos < __size)
1216         {
1217           const _CharT* __data = _M_data();
1218           const size_type __n = __size - __pos;
1219           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
1220           if (__p)
1221             __ret = __p - __data;
1222         }
1223       return __ret;
1224     }
1226   template<typename _CharT, typename _Traits, typename _Alloc>
1227     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1228     basic_string<_CharT, _Traits, _Alloc>::
1229     rfind(const _CharT* __s, size_type __pos, size_type __n) const
1230     {
1231       __glibcxx_requires_string_len(__s, __n);
1232       const size_type __size = this->size();
1233       if (__n <= __size)
1234         {
1235           __pos = std::min(size_type(__size - __n), __pos);
1236           const _CharT* __data = _M_data();
1237           do
1238             {
1239               if (traits_type::compare(__data + __pos, __s, __n) == 0)
1240                 return __pos;
1241             }
1242           while (__pos-- > 0);
1243         }
1244       return npos;
1245     }
1247   template<typename _CharT, typename _Traits, typename _Alloc>
1248     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1249     basic_string<_CharT, _Traits, _Alloc>::
1250     rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1251     {
1252       size_type __size = this->size();
1253       if (__size)
1254         {
1255           if (--__size > __pos)
1256             __size = __pos;
1257           for (++__size; __size-- > 0; )
1258             if (traits_type::eq(_M_data()[__size], __c))
1259               return __size;
1260         }
1261       return npos;
1262     }
1264   template<typename _CharT, typename _Traits, typename _Alloc>
1265     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1266     basic_string<_CharT, _Traits, _Alloc>::
1267     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
1268     {
1269       __glibcxx_requires_string_len(__s, __n);
1270       for (; __n && __pos < this->size(); ++__pos)
1271         {
1272           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
1273           if (__p)
1274             return __pos;
1275         }
1276       return npos;
1277     }
1279   template<typename _CharT, typename _Traits, typename _Alloc>
1280     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1281     basic_string<_CharT, _Traits, _Alloc>::
1282     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
1283     {
1284       __glibcxx_requires_string_len(__s, __n);
1285       size_type __size = this->size();
1286       if (__size && __n)
1287         {
1288           if (--__size > __pos)
1289             __size = __pos;
1290           do
1291             {
1292               if (traits_type::find(__s, __n, _M_data()[__size]))
1293                 return __size;
1294             }
1295           while (__size-- != 0);
1296         }
1297       return npos;
1298     }
1300   template<typename _CharT, typename _Traits, typename _Alloc>
1301     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1302     basic_string<_CharT, _Traits, _Alloc>::
1303     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1304     {
1305       __glibcxx_requires_string_len(__s, __n);
1306       for (; __pos < this->size(); ++__pos)
1307         if (!traits_type::find(__s, __n, _M_data()[__pos]))
1308           return __pos;
1309       return npos;
1310     }
1312   template<typename _CharT, typename _Traits, typename _Alloc>
1313     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1314     basic_string<_CharT, _Traits, _Alloc>::
1315     find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1316     {
1317       for (; __pos < this->size(); ++__pos)
1318         if (!traits_type::eq(_M_data()[__pos], __c))
1319           return __pos;
1320       return npos;
1321     }
1323   template<typename _CharT, typename _Traits, typename _Alloc>
1324     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1325     basic_string<_CharT, _Traits, _Alloc>::
1326     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1327     {
1328       __glibcxx_requires_string_len(__s, __n);
1329       size_type __size = this->size();
1330       if (__size)
1331         {
1332           if (--__size > __pos)
1333             __size = __pos;
1334           do
1335             {
1336               if (!traits_type::find(__s, __n, _M_data()[__size]))
1337                 return __size;
1338             }
1339           while (__size--);
1340         }
1341       return npos;
1342     }
1344   template<typename _CharT, typename _Traits, typename _Alloc>
1345     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1346     basic_string<_CharT, _Traits, _Alloc>::
1347     find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1348     {
1349       size_type __size = this->size();
1350       if (__size)
1351         {
1352           if (--__size > __pos)
1353             __size = __pos;
1354           do
1355             {
1356               if (!traits_type::eq(_M_data()[__size], __c))
1357                 return __size;
1358             }
1359           while (__size--);
1360         }
1361       return npos;
1362     }
1364   template<typename _CharT, typename _Traits, typename _Alloc>
1365     int
1366     basic_string<_CharT, _Traits, _Alloc>::
1367     compare(size_type __pos, size_type __n, const basic_string& __str) const
1368     {
1369       _M_check(__pos, "basic_string::compare");
1370       __n = _M_limit(__pos, __n);
1371       const size_type __osize = __str.size();
1372       const size_type __len = std::min(__n, __osize);
1373       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
1374       if (!__r)
1375         __r = _S_compare(__n, __osize);
1376       return __r;
1377     }
1379   template<typename _CharT, typename _Traits, typename _Alloc>
1380     int
1381     basic_string<_CharT, _Traits, _Alloc>::
1382     compare(size_type __pos1, size_type __n1, const basic_string& __str,
1383             size_type __pos2, size_type __n2) const
1384     {
1385       _M_check(__pos1, "basic_string::compare");
1386       __str._M_check(__pos2, "basic_string::compare");
1387       __n1 = _M_limit(__pos1, __n1);
1388       __n2 = __str._M_limit(__pos2, __n2);
1389       const size_type __len = std::min(__n1, __n2);
1390       int __r = traits_type::compare(_M_data() + __pos1,
1391                                      __str.data() + __pos2, __len);
1392       if (!__r)
1393         __r = _S_compare(__n1, __n2);
1394       return __r;
1395     }
1397   template<typename _CharT, typename _Traits, typename _Alloc>
1398     int
1399     basic_string<_CharT, _Traits, _Alloc>::
1400     compare(const _CharT* __s) const
1401     {
1402       __glibcxx_requires_string(__s);
1403       const size_type __size = this->size();
1404       const size_type __osize = traits_type::length(__s);
1405       const size_type __len = std::min(__size, __osize);
1406       int __r = traits_type::compare(_M_data(), __s, __len);
1407       if (!__r)
1408         __r = _S_compare(__size, __osize);
1409       return __r;
1410     }
1412   template<typename _CharT, typename _Traits, typename _Alloc>
1413     int
1414     basic_string <_CharT, _Traits, _Alloc>::
1415     compare(size_type __pos, size_type __n1, const _CharT* __s) const
1416     {
1417       __glibcxx_requires_string(__s);
1418       _M_check(__pos, "basic_string::compare");
1419       __n1 = _M_limit(__pos, __n1);
1420       const size_type __osize = traits_type::length(__s);
1421       const size_type __len = std::min(__n1, __osize);
1422       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1423       if (!__r)
1424         __r = _S_compare(__n1, __osize);
1425       return __r;
1426     }
1428   template<typename _CharT, typename _Traits, typename _Alloc>
1429     int
1430     basic_string <_CharT, _Traits, _Alloc>::
1431     compare(size_type __pos, size_type __n1, const _CharT* __s,
1432             size_type __n2) const
1433     {
1434       __glibcxx_requires_string_len(__s, __n2);
1435       _M_check(__pos, "basic_string::compare");
1436       __n1 = _M_limit(__pos, __n1);
1437       const size_type __len = std::min(__n1, __n2);
1438       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1439       if (!__r)
1440         __r = _S_compare(__n1, __n2);
1441       return __r;
1442     }
1444   // 21.3.7.9 basic_string::getline and operators
1445   template<typename _CharT, typename _Traits, typename _Alloc>
1446     basic_istream<_CharT, _Traits>&
1447     operator>>(basic_istream<_CharT, _Traits>& __in,
1448                basic_string<_CharT, _Traits, _Alloc>& __str)
1449     {
1450       typedef basic_istream<_CharT, _Traits>            __istream_type;
1451       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1452       typedef typename __istream_type::ios_base         __ios_base;
1453       typedef typename __istream_type::int_type         __int_type;
1454       typedef typename __string_type::size_type         __size_type;
1455       typedef ctype<_CharT>                             __ctype_type;
1456       typedef typename __ctype_type::ctype_base         __ctype_base;
1458       __size_type __extracted = 0;
1459       typename __ios_base::iostate __err = __ios_base::goodbit;
1460       typename __istream_type::sentry __cerb(__in, false);
1461       if (__cerb)
1462         {
1463           __try
1464             {
1465               // Avoid reallocation for common case.
1466               __str.erase();
1467               _CharT __buf[128];
1468               __size_type __len = 0;          
1469               const streamsize __w = __in.width();
1470               const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1471                                               : __str.max_size();
1472               const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1473               const __int_type __eof = _Traits::eof();
1474               __int_type __c = __in.rdbuf()->sgetc();
1476               while (__extracted < __n
1477                      && !_Traits::eq_int_type(__c, __eof)
1478                      && !__ct.is(__ctype_base::space,
1479                                  _Traits::to_char_type(__c)))
1480                 {
1481                   if (__len == sizeof(__buf) / sizeof(_CharT))
1482                     {
1483                       __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1484                       __len = 0;
1485                     }
1486                   __buf[__len++] = _Traits::to_char_type(__c);
1487                   ++__extracted;
1488                   __c = __in.rdbuf()->snextc();
1489                 }
1490               __str.append(__buf, __len);
1492               if (_Traits::eq_int_type(__c, __eof))
1493                 __err |= __ios_base::eofbit;
1494               __in.width(0);
1495             }
1496           __catch(__cxxabiv1::__forced_unwind&)
1497             {
1498               __in._M_setstate(__ios_base::badbit);
1499               __throw_exception_again;
1500             }
1501           __catch(...)
1502             {
1503               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1504               // 91. Description of operator>> and getline() for string<>
1505               // might cause endless loop
1506               __in._M_setstate(__ios_base::badbit);
1507             }
1508         }
1509       // 211.  operator>>(istream&, string&) doesn't set failbit
1510       if (!__extracted)
1511         __err |= __ios_base::failbit;
1512       if (__err)
1513         __in.setstate(__err);
1514       return __in;
1515     }
1517   template<typename _CharT, typename _Traits, typename _Alloc>
1518     basic_istream<_CharT, _Traits>&
1519     getline(basic_istream<_CharT, _Traits>& __in,
1520             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1521     {
1522       typedef basic_istream<_CharT, _Traits>            __istream_type;
1523       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1524       typedef typename __istream_type::ios_base         __ios_base;
1525       typedef typename __istream_type::int_type         __int_type;
1526       typedef typename __string_type::size_type         __size_type;
1528       __size_type __extracted = 0;
1529       const __size_type __n = __str.max_size();
1530       typename __ios_base::iostate __err = __ios_base::goodbit;
1531       typename __istream_type::sentry __cerb(__in, true);
1532       if (__cerb)
1533         {
1534           __try
1535             {
1536               __str.erase();
1537               const __int_type __idelim = _Traits::to_int_type(__delim);
1538               const __int_type __eof = _Traits::eof();
1539               __int_type __c = __in.rdbuf()->sgetc();
1541               while (__extracted < __n
1542                      && !_Traits::eq_int_type(__c, __eof)
1543                      && !_Traits::eq_int_type(__c, __idelim))
1544                 {
1545                   __str += _Traits::to_char_type(__c);
1546                   ++__extracted;
1547                   __c = __in.rdbuf()->snextc();
1548                 }
1550               if (_Traits::eq_int_type(__c, __eof))
1551                 __err |= __ios_base::eofbit;
1552               else if (_Traits::eq_int_type(__c, __idelim))
1553                 {
1554                   ++__extracted;                  
1555                   __in.rdbuf()->sbumpc();
1556                 }
1557               else
1558                 __err |= __ios_base::failbit;
1559             }
1560           __catch(__cxxabiv1::__forced_unwind&)
1561             {
1562               __in._M_setstate(__ios_base::badbit);
1563               __throw_exception_again;
1564             }
1565           __catch(...)
1566             {
1567               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1568               // 91. Description of operator>> and getline() for string<>
1569               // might cause endless loop
1570               __in._M_setstate(__ios_base::badbit);
1571             }
1572         }
1573       if (!__extracted)
1574         __err |= __ios_base::failbit;
1575       if (__err)
1576         __in.setstate(__err);
1577       return __in;
1578     }
1580   // Inhibit implicit instantiations for required instantiations,
1581   // which are defined via explicit instantiations elsewhere.
1582 #if _GLIBCXX_EXTERN_TEMPLATE > 0 && __cplusplus <= 201402L
1583   extern template class basic_string<char>;
1584   extern template
1585     basic_istream<char>&
1586     operator>>(basic_istream<char>&, string&);
1587   extern template
1588     basic_ostream<char>&
1589     operator<<(basic_ostream<char>&, const string&);
1590   extern template
1591     basic_istream<char>&
1592     getline(basic_istream<char>&, string&, char);
1593   extern template
1594     basic_istream<char>&
1595     getline(basic_istream<char>&, string&);
1597 #ifdef _GLIBCXX_USE_WCHAR_T
1598   extern template class basic_string<wchar_t>;
1599   extern template
1600     basic_istream<wchar_t>&
1601     operator>>(basic_istream<wchar_t>&, wstring&);
1602   extern template
1603     basic_ostream<wchar_t>&
1604     operator<<(basic_ostream<wchar_t>&, const wstring&);
1605   extern template
1606     basic_istream<wchar_t>&
1607     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1608   extern template
1609     basic_istream<wchar_t>&
1610     getline(basic_istream<wchar_t>&, wstring&);
1611 #endif
1612 #endif
1614 _GLIBCXX_END_NAMESPACE_VERSION
1615 } // namespace std
1617 #endif