File Coverage

/usr/include/c++/5/bits/basic_string.tcc
Criterion Covered Total %
statement 0 10 0.0
branch 0 22 0.0
condition n/a
subroutine n/a
pod n/a
total 0 32 0.0


line stmt bran cond sub pod time code
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             // .
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
45              
46             namespace std _GLIBCXX_VISIBILITY(default)
47             {
48             _GLIBCXX_BEGIN_NAMESPACE_VERSION
49              
50             #if _GLIBCXX_USE_CXX11_ABI
51              
52             template
53             const typename basic_string<_CharT, _Traits, _Alloc>::size_type
54             basic_string<_CharT, _Traits, _Alloc>::npos;
55              
56             template
57             void
58             basic_string<_CharT, _Traits, _Alloc>::
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::_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
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
165             template
166             void
167             basic_string<_CharT, _Traits, _Alloc>::
168             _M_construct(_InIterator __beg, _InIterator __end,
169             std::input_iterator_tag)
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
208             template
209             void
210 0           basic_string<_CharT, _Traits, _Alloc>::
211             _M_construct(_InIterator __beg, _InIterator __end,
212             std::forward_iterator_tag)
213             {
214             // NB: Not required, but considered best practice.
215 0 0         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
    0          
    0          
216 0           std::__throw_logic_error(__N("basic_string::"
217             "_M_construct null not valid"));
218              
219 0 0         size_type __dnew = static_cast(std::distance(__beg, __end));
220              
221 0 0         if (__dnew > size_type(_S_local_capacity))
222             {
223 0 0         _M_data(_M_create(__dnew, size_type(0)));
    0          
224 0 0         _M_capacity(__dnew);
225             }
226              
227             // Check for out_of_range and length_error exceptions.
228             __try
229 0 0         { this->_S_copy_chars(_M_data(), __beg, __end); }
230             __catch(...)
231   0         {
232             _M_dispose();
233             __throw_exception_again;
234             }
235              
236 0 0         _M_set_length(__dnew);
237 0           }
238              
239             template
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
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
283             void
284             basic_string<_CharT, _Traits, _Alloc>::
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
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
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
350             void
351             basic_string<_CharT, _Traits, _Alloc>::
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
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
381             template
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
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
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
477             typename basic_string<_CharT, _Traits, _Alloc>::size_type
478             basic_string<_CharT, _Traits, _Alloc>::
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
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
498             const _CharT
499             basic_string<_CharT, _Traits, _Alloc>::
500             _Rep::_S_terminal = _CharT();
501              
502             template
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
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
519             template
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
565             template
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(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
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
613             basic_string<_CharT, _Traits, _Alloc>::
614             basic_string(const basic_string& __str)
615             : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
616             __str.get_allocator()),
617             __str.get_allocator())
618             { }
619              
620             template
621             basic_string<_CharT, _Traits, _Alloc>::
622             basic_string(const _Alloc& __a)
623             : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
624             { }
625              
626             template
627             basic_string<_CharT, _Traits, _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
637             basic_string<_CharT, _Traits, _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
649             basic_string<_CharT, _Traits, _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
656             basic_string<_CharT, _Traits, _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
663             basic_string<_CharT, _Traits, _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
670             template
671             basic_string<_CharT, _Traits, _Alloc>::
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
678             basic_string<_CharT, _Traits, _Alloc>::
679             basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
680             : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
681             { }
682             #endif
683              
684             template
685             basic_string<_CharT, _Traits, _Alloc>&
686             basic_string<_CharT, _Traits, _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
701             basic_string<_CharT, _Traits, _Alloc>&
702             basic_string<_CharT, _Traits, _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
723             basic_string<_CharT, _Traits, _Alloc>&
724             basic_string<_CharT, _Traits, _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
740             basic_string<_CharT, _Traits, _Alloc>&
741             basic_string<_CharT, _Traits, _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
767             basic_string<_CharT, _Traits, _Alloc>&
768             basic_string<_CharT, _Traits, _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
784             basic_string<_CharT, _Traits, _Alloc>&
785             basic_string<_CharT, _Traits, _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
802             basic_string<_CharT, _Traits, _Alloc>&
803             basic_string<_CharT, _Traits, _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
833             typename basic_string<_CharT, _Traits, _Alloc>::iterator
834             basic_string<_CharT, _Traits, _Alloc>::
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
856             basic_string<_CharT, _Traits, _Alloc>&
857             basic_string<_CharT, _Traits, _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
887             void
888             basic_string<_CharT, _Traits, _Alloc>::_Rep::
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(this), __size);
894             }
895              
896             template
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
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
944             void
945             basic_string<_CharT, _Traits, _Alloc>::
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
961             void
962             basic_string<_CharT, _Traits, _Alloc>::
963             swap(basic_string& __s)
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
988             typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
989             basic_string<_CharT, _Traits, _Alloc>::_Rep::
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
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
1082             void
1083             basic_string<_CharT, _Traits, _Alloc>::
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
1096             template
1097             basic_string<_CharT, _Traits, _Alloc>&
1098             basic_string<_CharT, _Traits, _Alloc>::
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
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
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
1135             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1136             basic_string<_CharT, _Traits, _Alloc>::
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
1150             basic_string<_CharT, _Traits, _Alloc>
1151             operator+(const _CharT* __lhs,
1152             const basic_string<_CharT, _Traits, _Alloc>& __rhs)
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
1166             basic_string<_CharT, _Traits, _Alloc>
1167             operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
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
1180             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1181             basic_string<_CharT, _Traits, _Alloc>::
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
1203             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1204             basic_string<_CharT, _Traits, _Alloc>::
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
1221             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1222             basic_string<_CharT, _Traits, _Alloc>::
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
1242             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1243             basic_string<_CharT, _Traits, _Alloc>::
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
1259             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1260             basic_string<_CharT, _Traits, _Alloc>::
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
1274             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1275             basic_string<_CharT, _Traits, _Alloc>::
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
1295             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1296             basic_string<_CharT, _Traits, _Alloc>::
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
1307             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1308             basic_string<_CharT, _Traits, _Alloc>::
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
1318             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1319             basic_string<_CharT, _Traits, _Alloc>::
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
1339             typename basic_string<_CharT, _Traits, _Alloc>::size_type
1340             basic_string<_CharT, _Traits, _Alloc>::
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
1359             int
1360             basic_string<_CharT, _Traits, _Alloc>::
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
1374             int
1375             basic_string<_CharT, _Traits, _Alloc>::
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
1392             int
1393             basic_string<_CharT, _Traits, _Alloc>::
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
1407             int
1408             basic_string <_CharT, _Traits, _Alloc>::
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
1423             int
1424             basic_string <_CharT, _Traits, _Alloc>::
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
1440             basic_istream<_CharT, _Traits>&
1441             operator>>(basic_istream<_CharT, _Traits>& __in,
1442             basic_string<_CharT, _Traits, _Alloc>& __str)
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
1512             basic_istream<_CharT, _Traits>&
1513             getline(basic_istream<_CharT, _Traits>& __in,
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;
1578             extern template
1579             basic_istream&
1580             operator>>(basic_istream&, string&);
1581             extern template
1582             basic_ostream&
1583             operator<<(basic_ostream&, const string&);
1584             extern template
1585             basic_istream&
1586             getline(basic_istream&, string&, char);
1587             extern template
1588             basic_istream&
1589             getline(basic_istream&, string&);
1590              
1591             #ifdef _GLIBCXX_USE_WCHAR_T
1592             extern template class basic_string;
1593             extern template
1594             basic_istream&
1595             operator>>(basic_istream&, wstring&);
1596             extern template
1597             basic_ostream&
1598             operator<<(basic_ostream&, const wstring&);
1599             extern template
1600             basic_istream&
1601             getline(basic_istream&, wstring&, wchar_t);
1602             extern template
1603             basic_istream&
1604             getline(basic_istream&, wstring&);
1605             #endif
1606             #endif
1607              
1608             _GLIBCXX_END_NAMESPACE_VERSION
1609             } // namespace std
1610              
1611             #endif