OSDN Git Service

a574bf62f8789490d5090116d0a9d200e6ee5e76
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / basic_string.h
1 // Components for manipulating sequences of characters -*- C++ -*-
2
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
4 // 2006, 2007, 2008, 2009
5 // Free Software Foundation, Inc.
6 //
7 // This file is part of the GNU ISO C++ Library.  This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
11 // any later version.
12
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 // GNU General Public License for more details.
17
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
21
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
25 // <http://www.gnu.org/licenses/>.
26
27 /** @file basic_string.h
28  *  This is an internal header file, included by other library headers.
29  *  You should not attempt to use it directly.
30  */
31
32 //
33 // ISO C++ 14882: 21 Strings library
34 //
35
36 #ifndef _BASIC_STRING_H
37 #define _BASIC_STRING_H 1
38
39 #pragma GCC system_header
40
41 #include <ext/atomicity.h>
42 #include <debug/debug.h>
43 #include <initializer_list>
44
45 _GLIBCXX_BEGIN_NAMESPACE(std)
46
47   /**
48    *  @class basic_string basic_string.h <string>
49    *  @brief  Managing sequences of characters and character-like objects.
50    *
51    *  @ingroup sequences
52    *
53    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
54    *  <a href="tables.html#66">reversible container</a>, and a
55    *  <a href="tables.html#67">sequence</a>.  Of the
56    *  <a href="tables.html#68">optional sequence requirements</a>, only
57    *  @c push_back, @c at, and array access are supported.
58    *
59    *  @doctodo
60    *
61    *
62    *  Documentation?  What's that?
63    *  Nathan Myers <ncm@cantrip.org>.
64    *
65    *  A string looks like this:
66    *
67    *  @code
68    *                                        [_Rep]
69    *                                        _M_length
70    *   [basic_string<char_type>]            _M_capacity
71    *   _M_dataplus                          _M_refcount
72    *   _M_p ---------------->               unnamed array of char_type
73    *  @endcode
74    *
75    *  Where the _M_p points to the first character in the string, and
76    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
77    *  pointer to the header.
78    *
79    *  This approach has the enormous advantage that a string object
80    *  requires only one allocation.  All the ugliness is confined
81    *  within a single pair of inline functions, which each compile to
82    *  a single "add" instruction: _Rep::_M_data(), and
83    *  string::_M_rep(); and the allocation function which gets a
84    *  block of raw bytes and with room enough and constructs a _Rep
85    *  object at the front.
86    *
87    *  The reason you want _M_data pointing to the character array and
88    *  not the _Rep is so that the debugger can see the string
89    *  contents. (Probably we should add a non-inline member to get
90    *  the _Rep for the debugger to use, so users can check the actual
91    *  string length.)
92    *
93    *  Note that the _Rep object is a POD so that you can have a
94    *  static "empty string" _Rep object already "constructed" before
95    *  static constructors have run.  The reference-count encoding is
96    *  chosen so that a 0 indicates one reference, so you never try to
97    *  destroy the empty-string _Rep object.
98    *
99    *  All but the last paragraph is considered pretty conventional
100    *  for a C++ string implementation.
101   */
102   // 21.3  Template class basic_string
103   template<typename _CharT, typename _Traits, typename _Alloc>
104     class basic_string
105     {
106       typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
107
108       // Types:
109     public:
110       typedef _Traits                                       traits_type;
111       typedef typename _Traits::char_type                   value_type;
112       typedef _Alloc                                        allocator_type;
113       typedef typename _CharT_alloc_type::size_type         size_type;
114       typedef typename _CharT_alloc_type::difference_type   difference_type;
115       typedef typename _CharT_alloc_type::reference         reference;
116       typedef typename _CharT_alloc_type::const_reference   const_reference;
117       typedef typename _CharT_alloc_type::pointer           pointer;
118       typedef typename _CharT_alloc_type::const_pointer     const_pointer;
119       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
120       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
121                                                             const_iterator;
122       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
123       typedef std::reverse_iterator<iterator>               reverse_iterator;
124
125     private:
126       // _Rep: string representation
127       //   Invariants:
128       //   1. String really contains _M_length + 1 characters: due to 21.3.4
129       //      must be kept null-terminated.
130       //   2. _M_capacity >= _M_length
131       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
132       //   3. _M_refcount has three states:
133       //      -1: leaked, one reference, no ref-copies allowed, non-const.
134       //       0: one reference, non-const.
135       //     n>0: n + 1 references, operations require a lock, const.
136       //   4. All fields==0 is an empty string, given the extra storage
137       //      beyond-the-end for a null terminator; thus, the shared
138       //      empty string representation needs no constructor.
139
140       struct _Rep_base
141       {
142         size_type               _M_length;
143         size_type               _M_capacity;
144         _Atomic_word            _M_refcount;
145       };
146
147       struct _Rep : _Rep_base
148       {
149         // Types:
150         typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
151
152         // (Public) Data members:
153
154         // The maximum number of individual char_type elements of an
155         // individual string is determined by _S_max_size. This is the
156         // value that will be returned by max_size().  (Whereas npos
157         // is the maximum number of bytes the allocator can allocate.)
158         // If one was to divvy up the theoretical largest size string,
159         // with a terminating character and m _CharT elements, it'd
160         // look like this:
161         // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
162         // Solving for m:
163         // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
164         // In addition, this implementation quarters this amount.
165         static const size_type  _S_max_size;
166         static const _CharT     _S_terminal;
167
168         // The following storage is init'd to 0 by the linker, resulting
169         // (carefully) in an empty string with one reference.
170         static size_type _S_empty_rep_storage[];
171
172         static _Rep&
173         _S_empty_rep()
174         { 
175           // NB: Mild hack to avoid strict-aliasing warnings.  Note that
176           // _S_empty_rep_storage is never modified and the punning should
177           // be reasonably safe in this case.
178           void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
179           return *reinterpret_cast<_Rep*>(__p);
180         }
181
182         bool
183         _M_is_leaked() const
184         { return this->_M_refcount < 0; }
185
186         bool
187         _M_is_shared() const
188         { return this->_M_refcount > 0; }
189
190         void
191         _M_set_leaked()
192         { this->_M_refcount = -1; }
193
194         void
195         _M_set_sharable()
196         { this->_M_refcount = 0; }
197
198         void
199         _M_set_length_and_sharable(size_type __n)
200         {
201 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
202           if (__builtin_expect(this != &_S_empty_rep(), false))
203 #endif
204             {
205               this->_M_set_sharable();  // One reference.
206               this->_M_length = __n;
207               traits_type::assign(this->_M_refdata()[__n], _S_terminal);
208               // grrr. (per 21.3.4)
209               // You cannot leave those LWG people alone for a second.
210             }
211         }
212
213         _CharT*
214         _M_refdata() throw()
215         { return reinterpret_cast<_CharT*>(this + 1); }
216
217         _CharT*
218         _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
219         {
220           return (!_M_is_leaked() && __alloc1 == __alloc2)
221                   ? _M_refcopy() : _M_clone(__alloc1);
222         }
223
224         // Create & Destroy
225         static _Rep*
226         _S_create(size_type, size_type, const _Alloc&);
227
228         void
229         _M_dispose(const _Alloc& __a)
230         {
231 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
232           if (__builtin_expect(this != &_S_empty_rep(), false))
233 #endif
234             if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
235                                                        -1) <= 0)
236               _M_destroy(__a);
237         }  // XXX MT
238
239         void
240         _M_destroy(const _Alloc&) throw();
241
242         _CharT*
243         _M_refcopy() throw()
244         {
245 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
246           if (__builtin_expect(this != &_S_empty_rep(), false))
247 #endif
248             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
249           return _M_refdata();
250         }  // XXX MT
251
252         _CharT*
253         _M_clone(const _Alloc&, size_type __res = 0);
254       };
255
256       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
257       struct _Alloc_hider : _Alloc
258       {
259         _Alloc_hider(_CharT* __dat, const _Alloc& __a)
260         : _Alloc(__a), _M_p(__dat) { }
261
262         _CharT* _M_p; // The actual data.
263       };
264
265     public:
266       // Data Members (public):
267       // NB: This is an unsigned type, and thus represents the maximum
268       // size that the allocator can hold.
269       ///  Value returned by various member functions when they fail.
270       static const size_type    npos = static_cast<size_type>(-1);
271
272     private:
273       // Data Members (private):
274       mutable _Alloc_hider      _M_dataplus;
275
276       _CharT*
277       _M_data() const
278       { return  _M_dataplus._M_p; }
279
280       _CharT*
281       _M_data(_CharT* __p)
282       { return (_M_dataplus._M_p = __p); }
283
284       _Rep*
285       _M_rep() const
286       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
287
288       // For the internal use we have functions similar to `begin'/`end'
289       // but they do not call _M_leak.
290       iterator
291       _M_ibegin() const
292       { return iterator(_M_data()); }
293
294       iterator
295       _M_iend() const
296       { return iterator(_M_data() + this->size()); }
297
298       void
299       _M_leak()    // for use in begin() & non-const op[]
300       {
301         if (!_M_rep()->_M_is_leaked())
302           _M_leak_hard();
303       }
304
305       size_type
306       _M_check(size_type __pos, const char* __s) const
307       {
308         if (__pos > this->size())
309           __throw_out_of_range(__N(__s));
310         return __pos;
311       }
312
313       void
314       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
315       {
316         if (this->max_size() - (this->size() - __n1) < __n2)
317           __throw_length_error(__N(__s));
318       }
319
320       // NB: _M_limit doesn't check for a bad __pos value.
321       size_type
322       _M_limit(size_type __pos, size_type __off) const
323       {
324         const bool __testoff =  __off < this->size() - __pos;
325         return __testoff ? __off : this->size() - __pos;
326       }
327
328       // True if _Rep and source do not overlap.
329       bool
330       _M_disjunct(const _CharT* __s) const
331       {
332         return (less<const _CharT*>()(__s, _M_data())
333                 || less<const _CharT*>()(_M_data() + this->size(), __s));
334       }
335
336       // When __n = 1 way faster than the general multichar
337       // traits_type::copy/move/assign.
338       static void
339       _M_copy(_CharT* __d, const _CharT* __s, size_type __n)
340       {
341         if (__n == 1)
342           traits_type::assign(*__d, *__s);
343         else
344           traits_type::copy(__d, __s, __n);
345       }
346
347       static void
348       _M_move(_CharT* __d, const _CharT* __s, size_type __n)
349       {
350         if (__n == 1)
351           traits_type::assign(*__d, *__s);
352         else
353           traits_type::move(__d, __s, __n);       
354       }
355
356       static void
357       _M_assign(_CharT* __d, size_type __n, _CharT __c)
358       {
359         if (__n == 1)
360           traits_type::assign(*__d, __c);
361         else
362           traits_type::assign(__d, __n, __c);     
363       }
364
365       // _S_copy_chars is a separate template to permit specialization
366       // to optimize for the common case of pointers as iterators.
367       template<class _Iterator>
368         static void
369         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
370         {
371           for (; __k1 != __k2; ++__k1, ++__p)
372             traits_type::assign(*__p, *__k1); // These types are off.
373         }
374
375       static void
376       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
377       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
378
379       static void
380       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
381       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
382
383       static void
384       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
385       { _M_copy(__p, __k1, __k2 - __k1); }
386
387       static void
388       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
389       { _M_copy(__p, __k1, __k2 - __k1); }
390
391       static int
392       _S_compare(size_type __n1, size_type __n2)
393       {
394         const difference_type __d = difference_type(__n1 - __n2);
395
396         if (__d > __gnu_cxx::__numeric_traits<int>::__max)
397           return __gnu_cxx::__numeric_traits<int>::__max;
398         else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
399           return __gnu_cxx::__numeric_traits<int>::__min;
400         else
401           return int(__d);
402       }
403
404       void
405       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
406
407       void
408       _M_leak_hard();
409
410       static _Rep&
411       _S_empty_rep()
412       { return _Rep::_S_empty_rep(); }
413
414     public:
415       // Construct/copy/destroy:
416       // NB: We overload ctors in some cases instead of using default
417       // arguments, per 17.4.4.4 para. 2 item 2.
418
419       /**
420        *  @brief  Default constructor creates an empty string.
421        */
422       inline
423       basic_string();
424
425       /**
426        *  @brief  Construct an empty string using allocator @a a.
427        */
428       explicit
429       basic_string(const _Alloc& __a);
430
431       // NB: per LWG issue 42, semantics different from IS:
432       /**
433        *  @brief  Construct string with copy of value of @a str.
434        *  @param  str  Source string.
435        */
436       basic_string(const basic_string& __str);
437       /**
438        *  @brief  Construct string as copy of a substring.
439        *  @param  str  Source string.
440        *  @param  pos  Index of first character to copy from.
441        *  @param  n  Number of characters to copy (default remainder).
442        */
443       basic_string(const basic_string& __str, size_type __pos,
444                    size_type __n = npos);
445       /**
446        *  @brief  Construct string as copy of a substring.
447        *  @param  str  Source string.
448        *  @param  pos  Index of first character to copy from.
449        *  @param  n  Number of characters to copy.
450        *  @param  a  Allocator to use.
451        */
452       basic_string(const basic_string& __str, size_type __pos,
453                    size_type __n, const _Alloc& __a);
454
455       /**
456        *  @brief  Construct string initialized by a character array.
457        *  @param  s  Source character array.
458        *  @param  n  Number of characters to copy.
459        *  @param  a  Allocator to use (default is default allocator).
460        *
461        *  NB: @a s must have at least @a n characters, '\\0' has no special
462        *  meaning.
463        */
464       basic_string(const _CharT* __s, size_type __n,
465                    const _Alloc& __a = _Alloc());
466       /**
467        *  @brief  Construct string as copy of a C string.
468        *  @param  s  Source C string.
469        *  @param  a  Allocator to use (default is default allocator).
470        */
471       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
472       /**
473        *  @brief  Construct string as multiple characters.
474        *  @param  n  Number of characters.
475        *  @param  c  Character to use.
476        *  @param  a  Allocator to use (default is default allocator).
477        */
478       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
479
480 #ifdef __GXX_EXPERIMENTAL_CXX0X__
481       /**
482        *  @brief  Construct string from an initializer list.
483        *  @param  l  std::initializer_list of characters.
484        *  @param  a  Allocator to use (default is default allocator).
485        */
486       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
487 #endif // __GXX_EXPERIMENTAL_CXX0X__
488
489       /**
490        *  @brief  Construct string as copy of a range.
491        *  @param  beg  Start of range.
492        *  @param  end  End of range.
493        *  @param  a  Allocator to use (default is default allocator).
494        */
495       template<class _InputIterator>
496         basic_string(_InputIterator __beg, _InputIterator __end,
497                      const _Alloc& __a = _Alloc());
498
499       /**
500        *  @brief  Destroy the string instance.
501        */
502       ~basic_string()
503       { _M_rep()->_M_dispose(this->get_allocator()); }
504
505       /**
506        *  @brief  Assign the value of @a str to this string.
507        *  @param  str  Source string.
508        */
509       basic_string&
510       operator=(const basic_string& __str) 
511       { return this->assign(__str); }
512
513       /**
514        *  @brief  Copy contents of @a s into this string.
515        *  @param  s  Source null-terminated string.
516        */
517       basic_string&
518       operator=(const _CharT* __s) 
519       { return this->assign(__s); }
520
521       /**
522        *  @brief  Set value to string of length 1.
523        *  @param  c  Source character.
524        *
525        *  Assigning to a character makes this string length 1 and
526        *  (*this)[0] == @a c.
527        */
528       basic_string&
529       operator=(_CharT __c) 
530       { 
531         this->assign(1, __c); 
532         return *this;
533       }
534
535 #ifdef __GXX_EXPERIMENTAL_CXX0X__
536       /**
537        *  @brief  Set value to string constructed from initializer list.
538        *  @param  l  std::initializer_list.
539        */
540       basic_string&
541       operator=(initializer_list<_CharT> __l)
542       {
543         this->assign(__l.begin(), __l.size());
544         return *this;
545       }
546 #endif // __GXX_EXPERIMENTAL_CXX0X__
547
548       // Iterators:
549       /**
550        *  Returns a read/write iterator that points to the first character in
551        *  the %string.  Unshares the string.
552        */
553       iterator
554       begin()
555       {
556         _M_leak();
557         return iterator(_M_data());
558       }
559
560       /**
561        *  Returns a read-only (constant) iterator that points to the first
562        *  character in the %string.
563        */
564       const_iterator
565       begin() const
566       { return const_iterator(_M_data()); }
567
568       /**
569        *  Returns a read/write iterator that points one past the last
570        *  character in the %string.  Unshares the string.
571        */
572       iterator
573       end()
574       {
575         _M_leak();
576         return iterator(_M_data() + this->size());
577       }
578
579       /**
580        *  Returns a read-only (constant) iterator that points one past the
581        *  last character in the %string.
582        */
583       const_iterator
584       end() const
585       { return const_iterator(_M_data() + this->size()); }
586
587       /**
588        *  Returns a read/write reverse iterator that points to the last
589        *  character in the %string.  Iteration is done in reverse element
590        *  order.  Unshares the string.
591        */
592       reverse_iterator
593       rbegin()
594       { return reverse_iterator(this->end()); }
595
596       /**
597        *  Returns a read-only (constant) reverse iterator that points
598        *  to the last character in the %string.  Iteration is done in
599        *  reverse element order.
600        */
601       const_reverse_iterator
602       rbegin() const
603       { return const_reverse_iterator(this->end()); }
604
605       /**
606        *  Returns a read/write reverse iterator that points to one before the
607        *  first character in the %string.  Iteration is done in reverse
608        *  element order.  Unshares the string.
609        */
610       reverse_iterator
611       rend()
612       { return reverse_iterator(this->begin()); }
613
614       /**
615        *  Returns a read-only (constant) reverse iterator that points
616        *  to one before the first character in the %string.  Iteration
617        *  is done in reverse element order.
618        */
619       const_reverse_iterator
620       rend() const
621       { return const_reverse_iterator(this->begin()); }
622
623 #ifdef __GXX_EXPERIMENTAL_CXX0X__
624       /**
625        *  Returns a read-only (constant) iterator that points to the first
626        *  character in the %string.
627        */
628       const_iterator
629       cbegin() const
630       { return const_iterator(this->_M_data()); }
631
632       /**
633        *  Returns a read-only (constant) iterator that points one past the
634        *  last character in the %string.
635        */
636       const_iterator
637       cend() const
638       { return const_iterator(this->_M_data() + this->size()); }
639
640       /**
641        *  Returns a read-only (constant) reverse iterator that points
642        *  to the last character in the %string.  Iteration is done in
643        *  reverse element order.
644        */
645       const_reverse_iterator
646       crbegin() const
647       { return const_reverse_iterator(this->end()); }
648
649       /**
650        *  Returns a read-only (constant) reverse iterator that points
651        *  to one before the first character in the %string.  Iteration
652        *  is done in reverse element order.
653        */
654       const_reverse_iterator
655       crend() const
656       { return const_reverse_iterator(this->begin()); }
657 #endif
658
659     public:
660       // Capacity:
661       ///  Returns the number of characters in the string, not including any
662       ///  null-termination.
663       size_type
664       size() const
665       { return _M_rep()->_M_length; }
666
667       ///  Returns the number of characters in the string, not including any
668       ///  null-termination.
669       size_type
670       length() const
671       { return _M_rep()->_M_length; }
672
673       /// Returns the size() of the largest possible %string.
674       size_type
675       max_size() const
676       { return _Rep::_S_max_size; }
677
678       /**
679        *  @brief  Resizes the %string to the specified number of characters.
680        *  @param  n  Number of characters the %string should contain.
681        *  @param  c  Character to fill any new elements.
682        *
683        *  This function will %resize the %string to the specified
684        *  number of characters.  If the number is smaller than the
685        *  %string's current size the %string is truncated, otherwise
686        *  the %string is extended and new elements are set to @a c.
687        */
688       void
689       resize(size_type __n, _CharT __c);
690
691       /**
692        *  @brief  Resizes the %string to the specified number of characters.
693        *  @param  n  Number of characters the %string should contain.
694        *
695        *  This function will resize the %string to the specified length.  If
696        *  the new size is smaller than the %string's current size the %string
697        *  is truncated, otherwise the %string is extended and new characters
698        *  are default-constructed.  For basic types such as char, this means
699        *  setting them to 0.
700        */
701       void
702       resize(size_type __n)
703       { this->resize(__n, _CharT()); }
704
705       /**
706        *  Returns the total number of characters that the %string can hold
707        *  before needing to allocate more memory.
708        */
709       size_type
710       capacity() const
711       { return _M_rep()->_M_capacity; }
712
713       /**
714        *  @brief  Attempt to preallocate enough memory for specified number of
715        *          characters.
716        *  @param  res_arg  Number of characters required.
717        *  @throw  std::length_error  If @a res_arg exceeds @c max_size().
718        *
719        *  This function attempts to reserve enough memory for the
720        *  %string to hold the specified number of characters.  If the
721        *  number requested is more than max_size(), length_error is
722        *  thrown.
723        *
724        *  The advantage of this function is that if optimal code is a
725        *  necessity and the user can determine the string length that will be
726        *  required, the user can reserve the memory in %advance, and thus
727        *  prevent a possible reallocation of memory and copying of %string
728        *  data.
729        */
730       void
731       reserve(size_type __res_arg = 0);
732
733       /**
734        *  Erases the string, making it empty.
735        */
736       void
737       clear()
738       { _M_mutate(0, this->size(), 0); }
739
740       /**
741        *  Returns true if the %string is empty.  Equivalent to *this == "".
742        */
743       bool
744       empty() const
745       { return this->size() == 0; }
746
747       // Element access:
748       /**
749        *  @brief  Subscript access to the data contained in the %string.
750        *  @param  pos  The index of the character to access.
751        *  @return  Read-only (constant) reference to the character.
752        *
753        *  This operator allows for easy, array-style, data access.
754        *  Note that data access with this operator is unchecked and
755        *  out_of_range lookups are not defined. (For checked lookups
756        *  see at().)
757        */
758       const_reference
759       operator[] (size_type __pos) const
760       {
761         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
762         return _M_data()[__pos];
763       }
764
765       /**
766        *  @brief  Subscript access to the data contained in the %string.
767        *  @param  pos  The index of the character to access.
768        *  @return  Read/write reference to the character.
769        *
770        *  This operator allows for easy, array-style, data access.
771        *  Note that data access with this operator is unchecked and
772        *  out_of_range lookups are not defined. (For checked lookups
773        *  see at().)  Unshares the string.
774        */
775       reference
776       operator[](size_type __pos)
777       {
778         // allow pos == size() as v3 extension:
779         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
780         // but be strict in pedantic mode:
781         _GLIBCXX_DEBUG_PEDASSERT(__pos < size());
782         _M_leak();
783         return _M_data()[__pos];
784       }
785
786       /**
787        *  @brief  Provides access to the data contained in the %string.
788        *  @param n The index of the character to access.
789        *  @return  Read-only (const) reference to the character.
790        *  @throw  std::out_of_range  If @a n is an invalid index.
791        *
792        *  This function provides for safer data access.  The parameter is
793        *  first checked that it is in the range of the string.  The function
794        *  throws out_of_range if the check fails.
795        */
796       const_reference
797       at(size_type __n) const
798       {
799         if (__n >= this->size())
800           __throw_out_of_range(__N("basic_string::at"));
801         return _M_data()[__n];
802       }
803
804       /**
805        *  @brief  Provides access to the data contained in the %string.
806        *  @param n The index of the character to access.
807        *  @return  Read/write reference to the character.
808        *  @throw  std::out_of_range  If @a n is an invalid index.
809        *
810        *  This function provides for safer data access.  The parameter is
811        *  first checked that it is in the range of the string.  The function
812        *  throws out_of_range if the check fails.  Success results in
813        *  unsharing the string.
814        */
815       reference
816       at(size_type __n)
817       {
818         if (__n >= size())
819           __throw_out_of_range(__N("basic_string::at"));
820         _M_leak();
821         return _M_data()[__n];
822       }
823
824       // Modifiers:
825       /**
826        *  @brief  Append a string to this string.
827        *  @param str  The string to append.
828        *  @return  Reference to this string.
829        */
830       basic_string&
831       operator+=(const basic_string& __str)
832       { return this->append(__str); }
833
834       /**
835        *  @brief  Append a C string.
836        *  @param s  The C string to append.
837        *  @return  Reference to this string.
838        */
839       basic_string&
840       operator+=(const _CharT* __s)
841       { return this->append(__s); }
842
843       /**
844        *  @brief  Append a character.
845        *  @param c  The character to append.
846        *  @return  Reference to this string.
847        */
848       basic_string&
849       operator+=(_CharT __c)
850       { 
851         this->push_back(__c);
852         return *this;
853       }
854
855 #ifdef __GXX_EXPERIMENTAL_CXX0X__
856       /**
857        *  @brief  Append an initializer_list of characters.
858        *  @param l  The initializer_list of characters to be appended.
859        *  @return  Reference to this string.
860        */
861       basic_string&
862       operator+=(initializer_list<_CharT> __l)
863       { return this->append(__l.begin(), __l.size()); }
864 #endif // __GXX_EXPERIMENTAL_CXX0X__
865
866       /**
867        *  @brief  Append a string to this string.
868        *  @param str  The string to append.
869        *  @return  Reference to this string.
870        */
871       basic_string&
872       append(const basic_string& __str);
873
874       /**
875        *  @brief  Append a substring.
876        *  @param str  The string to append.
877        *  @param pos  Index of the first character of str to append.
878        *  @param n  The number of characters to append.
879        *  @return  Reference to this string.
880        *  @throw  std::out_of_range if @a pos is not a valid index.
881        *
882        *  This function appends @a n characters from @a str starting at @a pos
883        *  to this string.  If @a n is is larger than the number of available
884        *  characters in @a str, the remainder of @a str is appended.
885        */
886       basic_string&
887       append(const basic_string& __str, size_type __pos, size_type __n);
888
889       /**
890        *  @brief  Append a C substring.
891        *  @param s  The C string to append.
892        *  @param n  The number of characters to append.
893        *  @return  Reference to this string.
894        */
895       basic_string&
896       append(const _CharT* __s, size_type __n);
897
898       /**
899        *  @brief  Append a C string.
900        *  @param s  The C string to append.
901        *  @return  Reference to this string.
902        */
903       basic_string&
904       append(const _CharT* __s)
905       {
906         __glibcxx_requires_string(__s);
907         return this->append(__s, traits_type::length(__s));
908       }
909
910       /**
911        *  @brief  Append multiple characters.
912        *  @param n  The number of characters to append.
913        *  @param c  The character to use.
914        *  @return  Reference to this string.
915        *
916        *  Appends n copies of c to this string.
917        */
918       basic_string&
919       append(size_type __n, _CharT __c);
920
921 #ifdef __GXX_EXPERIMENTAL_CXX0X__
922       /**
923        *  @brief  Append an initializer_list of characters.
924        *  @param l  The initializer_list of characters to append.
925        *  @return  Reference to this string.
926        */
927       basic_string&
928       append(initializer_list<_CharT> __l)
929       { return this->append(__l.begin(), __l.size()); }
930 #endif // __GXX_EXPERIMENTAL_CXX0X__
931
932       /**
933        *  @brief  Append a range of characters.
934        *  @param first  Iterator referencing the first character to append.
935        *  @param last  Iterator marking the end of the range.
936        *  @return  Reference to this string.
937        *
938        *  Appends characters in the range [first,last) to this string.
939        */
940       template<class _InputIterator>
941         basic_string&
942         append(_InputIterator __first, _InputIterator __last)
943         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
944
945       /**
946        *  @brief  Append a single character.
947        *  @param c  Character to append.
948        */
949       void
950       push_back(_CharT __c)
951       { 
952         const size_type __len = 1 + this->size();
953         if (__len > this->capacity() || _M_rep()->_M_is_shared())
954           this->reserve(__len);
955         traits_type::assign(_M_data()[this->size()], __c);
956         _M_rep()->_M_set_length_and_sharable(__len);
957       }
958
959       /**
960        *  @brief  Set value to contents of another string.
961        *  @param  str  Source string to use.
962        *  @return  Reference to this string.
963        */
964       basic_string&
965       assign(const basic_string& __str);
966
967       /**
968        *  @brief  Set value to a substring of a string.
969        *  @param str  The string to use.
970        *  @param pos  Index of the first character of str.
971        *  @param n  Number of characters to use.
972        *  @return  Reference to this string.
973        *  @throw  std::out_of_range if @a pos is not a valid index.
974        *
975        *  This function sets this string to the substring of @a str consisting
976        *  of @a n characters at @a pos.  If @a n is is larger than the number
977        *  of available characters in @a str, the remainder of @a str is used.
978        */
979       basic_string&
980       assign(const basic_string& __str, size_type __pos, size_type __n)
981       { return this->assign(__str._M_data()
982                             + __str._M_check(__pos, "basic_string::assign"),
983                             __str._M_limit(__pos, __n)); }
984
985       /**
986        *  @brief  Set value to a C substring.
987        *  @param s  The C string to use.
988        *  @param n  Number of characters to use.
989        *  @return  Reference to this string.
990        *
991        *  This function sets the value of this string to the first @a n
992        *  characters of @a s.  If @a n is is larger than the number of
993        *  available characters in @a s, the remainder of @a s is used.
994        */
995       basic_string&
996       assign(const _CharT* __s, size_type __n);
997
998       /**
999        *  @brief  Set value to contents of a C string.
1000        *  @param s  The C string to use.
1001        *  @return  Reference to this string.
1002        *
1003        *  This function sets the value of this string to the value of @a s.
1004        *  The data is copied, so there is no dependence on @a s once the
1005        *  function returns.
1006        */
1007       basic_string&
1008       assign(const _CharT* __s)
1009       {
1010         __glibcxx_requires_string(__s);
1011         return this->assign(__s, traits_type::length(__s));
1012       }
1013
1014       /**
1015        *  @brief  Set value to multiple characters.
1016        *  @param n  Length of the resulting string.
1017        *  @param c  The character to use.
1018        *  @return  Reference to this string.
1019        *
1020        *  This function sets the value of this string to @a n copies of
1021        *  character @a c.
1022        */
1023       basic_string&
1024       assign(size_type __n, _CharT __c)
1025       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
1026
1027       /**
1028        *  @brief  Set value to a range of characters.
1029        *  @param first  Iterator referencing the first character to append.
1030        *  @param last  Iterator marking the end of the range.
1031        *  @return  Reference to this string.
1032        *
1033        *  Sets value of string to characters in the range [first,last).
1034       */
1035       template<class _InputIterator>
1036         basic_string&
1037         assign(_InputIterator __first, _InputIterator __last)
1038         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
1039
1040 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1041       /**
1042        *  @brief  Set value to an initializer_list of characters.
1043        *  @param l  The initializer_list of characters to assign.
1044        *  @return  Reference to this string.
1045        */
1046       basic_string&
1047       assign(initializer_list<_CharT> __l)
1048       { return this->assign(__l.begin(), __l.size()); }
1049 #endif // __GXX_EXPERIMENTAL_CXX0X__
1050
1051       /**
1052        *  @brief  Insert multiple characters.
1053        *  @param p  Iterator referencing location in string to insert at.
1054        *  @param n  Number of characters to insert
1055        *  @param c  The character to insert.
1056        *  @throw  std::length_error  If new length exceeds @c max_size().
1057        *
1058        *  Inserts @a n copies of character @a c starting at the position
1059        *  referenced by iterator @a p.  If adding characters causes the length
1060        *  to exceed max_size(), length_error is thrown.  The value of the
1061        *  string doesn't change if an error is thrown.
1062       */
1063       void
1064       insert(iterator __p, size_type __n, _CharT __c)
1065       { this->replace(__p, __p, __n, __c);  }
1066
1067       /**
1068        *  @brief  Insert a range of characters.
1069        *  @param p  Iterator referencing location in string to insert at.
1070        *  @param beg  Start of range.
1071        *  @param end  End of range.
1072        *  @throw  std::length_error  If new length exceeds @c max_size().
1073        *
1074        *  Inserts characters in range [beg,end).  If adding characters causes
1075        *  the length to exceed max_size(), length_error is thrown.  The value
1076        *  of the string doesn't change if an error is thrown.
1077       */
1078       template<class _InputIterator>
1079         void
1080         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
1081         { this->replace(__p, __p, __beg, __end); }
1082
1083 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1084       /**
1085        *  @brief  Insert an initializer_list of characters.
1086        *  @param p  Iterator referencing location in string to insert at.
1087        *  @param l  The initializer_list of characters to insert.
1088        *  @throw  std::length_error  If new length exceeds @c max_size().
1089        */
1090       void
1091       insert(iterator __p, initializer_list<_CharT> __l)
1092       {
1093         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
1094         this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
1095       }
1096 #endif // __GXX_EXPERIMENTAL_CXX0X__
1097
1098       /**
1099        *  @brief  Insert value of a string.
1100        *  @param pos1  Iterator referencing location in string to insert at.
1101        *  @param str  The string to insert.
1102        *  @return  Reference to this string.
1103        *  @throw  std::length_error  If new length exceeds @c max_size().
1104        *
1105        *  Inserts value of @a str starting at @a pos1.  If adding characters
1106        *  causes the length to exceed max_size(), length_error is thrown.  The
1107        *  value of the string doesn't change if an error is thrown.
1108       */
1109       basic_string&
1110       insert(size_type __pos1, const basic_string& __str)
1111       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
1112
1113       /**
1114        *  @brief  Insert a substring.
1115        *  @param pos1  Iterator referencing location in string to insert at.
1116        *  @param str  The string to insert.
1117        *  @param pos2  Start of characters in str to insert.
1118        *  @param n  Number of characters to insert.
1119        *  @return  Reference to this string.
1120        *  @throw  std::length_error  If new length exceeds @c max_size().
1121        *  @throw  std::out_of_range  If @a pos1 > size() or
1122        *  @a pos2 > @a str.size().
1123        *
1124        *  Starting at @a pos1, insert @a n character of @a str beginning with
1125        *  @a pos2.  If adding characters causes the length to exceed
1126        *  max_size(), length_error is thrown.  If @a pos1 is beyond the end of
1127        *  this string or @a pos2 is beyond the end of @a str, out_of_range is
1128        *  thrown.  The value of the string doesn't change if an error is
1129        *  thrown.
1130       */
1131       basic_string&
1132       insert(size_type __pos1, const basic_string& __str,
1133              size_type __pos2, size_type __n)
1134       { return this->insert(__pos1, __str._M_data()
1135                             + __str._M_check(__pos2, "basic_string::insert"),
1136                             __str._M_limit(__pos2, __n)); }
1137
1138       /**
1139        *  @brief  Insert a C substring.
1140        *  @param pos  Iterator referencing location in string to insert at.
1141        *  @param s  The C string to insert.
1142        *  @param n  The number of characters to insert.
1143        *  @return  Reference to this string.
1144        *  @throw  std::length_error  If new length exceeds @c max_size().
1145        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1146        *  string.
1147        *
1148        *  Inserts the first @a n characters of @a s starting at @a pos.  If
1149        *  adding characters causes the length to exceed max_size(),
1150        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
1151        *  thrown.  The value of the string doesn't change if an error is
1152        *  thrown.
1153       */
1154       basic_string&
1155       insert(size_type __pos, const _CharT* __s, size_type __n);
1156
1157       /**
1158        *  @brief  Insert a C string.
1159        *  @param pos  Iterator referencing location in string to insert at.
1160        *  @param s  The C string to insert.
1161        *  @return  Reference to this string.
1162        *  @throw  std::length_error  If new length exceeds @c max_size().
1163        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1164        *  string.
1165        *
1166        *  Inserts the first @a n characters of @a s starting at @a pos.  If
1167        *  adding characters causes the length to exceed max_size(),
1168        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
1169        *  thrown.  The value of the string doesn't change if an error is
1170        *  thrown.
1171       */
1172       basic_string&
1173       insert(size_type __pos, const _CharT* __s)
1174       {
1175         __glibcxx_requires_string(__s);
1176         return this->insert(__pos, __s, traits_type::length(__s));
1177       }
1178
1179       /**
1180        *  @brief  Insert multiple characters.
1181        *  @param pos  Index in string to insert at.
1182        *  @param n  Number of characters to insert
1183        *  @param c  The character to insert.
1184        *  @return  Reference to this string.
1185        *  @throw  std::length_error  If new length exceeds @c max_size().
1186        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1187        *  string.
1188        *
1189        *  Inserts @a n copies of character @a c starting at index @a pos.  If
1190        *  adding characters causes the length to exceed max_size(),
1191        *  length_error is thrown.  If @a pos > length(), out_of_range is
1192        *  thrown.  The value of the string doesn't change if an error is
1193        *  thrown.
1194       */
1195       basic_string&
1196       insert(size_type __pos, size_type __n, _CharT __c)
1197       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
1198                               size_type(0), __n, __c); }
1199
1200       /**
1201        *  @brief  Insert one character.
1202        *  @param p  Iterator referencing position in string to insert at.
1203        *  @param c  The character to insert.
1204        *  @return  Iterator referencing newly inserted char.
1205        *  @throw  std::length_error  If new length exceeds @c max_size().
1206        *
1207        *  Inserts character @a c at position referenced by @a p.  If adding
1208        *  character causes the length to exceed max_size(), length_error is
1209        *  thrown.  If @a p is beyond end of string, out_of_range is thrown.
1210        *  The value of the string doesn't change if an error is thrown.
1211       */
1212       iterator
1213       insert(iterator __p, _CharT __c)
1214       {
1215         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
1216         const size_type __pos = __p - _M_ibegin();
1217         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
1218         _M_rep()->_M_set_leaked();
1219         return iterator(_M_data() + __pos);
1220       }
1221
1222       /**
1223        *  @brief  Remove characters.
1224        *  @param pos  Index of first character to remove (default 0).
1225        *  @param n  Number of characters to remove (default remainder).
1226        *  @return  Reference to this string.
1227        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1228        *  string.
1229        *
1230        *  Removes @a n characters from this string starting at @a pos.  The
1231        *  length of the string is reduced by @a n.  If there are < @a n
1232        *  characters to remove, the remainder of the string is truncated.  If
1233        *  @a p is beyond end of string, out_of_range is thrown.  The value of
1234        *  the string doesn't change if an error is thrown.
1235       */
1236       basic_string&
1237       erase(size_type __pos = 0, size_type __n = npos)
1238       { 
1239         _M_mutate(_M_check(__pos, "basic_string::erase"),
1240                   _M_limit(__pos, __n), size_type(0));
1241         return *this;
1242       }
1243
1244       /**
1245        *  @brief  Remove one character.
1246        *  @param position  Iterator referencing the character to remove.
1247        *  @return  iterator referencing same location after removal.
1248        *
1249        *  Removes the character at @a position from this string. The value
1250        *  of the string doesn't change if an error is thrown.
1251       */
1252       iterator
1253       erase(iterator __position)
1254       {
1255         _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
1256                                  && __position < _M_iend());
1257         const size_type __pos = __position - _M_ibegin();
1258         _M_mutate(__pos, size_type(1), size_type(0));
1259         _M_rep()->_M_set_leaked();
1260         return iterator(_M_data() + __pos);
1261       }
1262
1263       /**
1264        *  @brief  Remove a range of characters.
1265        *  @param first  Iterator referencing the first character to remove.
1266        *  @param last  Iterator referencing the end of the range.
1267        *  @return  Iterator referencing location of first after removal.
1268        *
1269        *  Removes the characters in the range [first,last) from this string.
1270        *  The value of the string doesn't change if an error is thrown.
1271       */
1272       iterator
1273       erase(iterator __first, iterator __last);
1274  
1275       /**
1276        *  @brief  Replace characters with value from another string.
1277        *  @param pos  Index of first character to replace.
1278        *  @param n  Number of characters to be replaced.
1279        *  @param str  String to insert.
1280        *  @return  Reference to this string.
1281        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1282        *  string.
1283        *  @throw  std::length_error  If new length exceeds @c max_size().
1284        *
1285        *  Removes the characters in the range [pos,pos+n) from this string.
1286        *  In place, the value of @a str is inserted.  If @a pos is beyond end
1287        *  of string, out_of_range is thrown.  If the length of the result
1288        *  exceeds max_size(), length_error is thrown.  The value of the string
1289        *  doesn't change if an error is thrown.
1290       */
1291       basic_string&
1292       replace(size_type __pos, size_type __n, const basic_string& __str)
1293       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
1294
1295       /**
1296        *  @brief  Replace characters with value from another string.
1297        *  @param pos1  Index of first character to replace.
1298        *  @param n1  Number of characters to be replaced.
1299        *  @param str  String to insert.
1300        *  @param pos2  Index of first character of str to use.
1301        *  @param n2  Number of characters from str to use.
1302        *  @return  Reference to this string.
1303        *  @throw  std::out_of_range  If @a pos1 > size() or @a pos2 >
1304        *  str.size().
1305        *  @throw  std::length_error  If new length exceeds @c max_size().
1306        *
1307        *  Removes the characters in the range [pos1,pos1 + n) from this
1308        *  string.  In place, the value of @a str is inserted.  If @a pos is
1309        *  beyond end of string, out_of_range is thrown.  If the length of the
1310        *  result exceeds max_size(), length_error is thrown.  The value of the
1311        *  string doesn't change if an error is thrown.
1312       */
1313       basic_string&
1314       replace(size_type __pos1, size_type __n1, const basic_string& __str,
1315               size_type __pos2, size_type __n2)
1316       { return this->replace(__pos1, __n1, __str._M_data()
1317                              + __str._M_check(__pos2, "basic_string::replace"),
1318                              __str._M_limit(__pos2, __n2)); }
1319
1320       /**
1321        *  @brief  Replace characters with value of a C substring.
1322        *  @param pos  Index of first character to replace.
1323        *  @param n1  Number of characters to be replaced.
1324        *  @param s  C string to insert.
1325        *  @param n2  Number of characters from @a s to use.
1326        *  @return  Reference to this string.
1327        *  @throw  std::out_of_range  If @a pos1 > size().
1328        *  @throw  std::length_error  If new length exceeds @c max_size().
1329        *
1330        *  Removes the characters in the range [pos,pos + n1) from this string.
1331        *  In place, the first @a n2 characters of @a s are inserted, or all
1332        *  of @a s if @a n2 is too large.  If @a pos is beyond end of string,
1333        *  out_of_range is thrown.  If the length of result exceeds max_size(),
1334        *  length_error is thrown.  The value of the string doesn't change if
1335        *  an error is thrown.
1336       */
1337       basic_string&
1338       replace(size_type __pos, size_type __n1, const _CharT* __s,
1339               size_type __n2);
1340
1341       /**
1342        *  @brief  Replace characters with value of a C string.
1343        *  @param pos  Index of first character to replace.
1344        *  @param n1  Number of characters to be replaced.
1345        *  @param s  C string to insert.
1346        *  @return  Reference to this string.
1347        *  @throw  std::out_of_range  If @a pos > size().
1348        *  @throw  std::length_error  If new length exceeds @c max_size().
1349        *
1350        *  Removes the characters in the range [pos,pos + n1) from this string.
1351        *  In place, the first @a n characters of @a s are inserted.  If @a
1352        *  pos is beyond end of string, out_of_range is thrown.  If the length
1353        *  of result exceeds max_size(), length_error is thrown.  The value of
1354        *  the string doesn't change if an error is thrown.
1355       */
1356       basic_string&
1357       replace(size_type __pos, size_type __n1, const _CharT* __s)
1358       {
1359         __glibcxx_requires_string(__s);
1360         return this->replace(__pos, __n1, __s, traits_type::length(__s));
1361       }
1362
1363       /**
1364        *  @brief  Replace characters with multiple characters.
1365        *  @param pos  Index of first character to replace.
1366        *  @param n1  Number of characters to be replaced.
1367        *  @param n2  Number of characters to insert.
1368        *  @param c  Character to insert.
1369        *  @return  Reference to this string.
1370        *  @throw  std::out_of_range  If @a pos > size().
1371        *  @throw  std::length_error  If new length exceeds @c max_size().
1372        *
1373        *  Removes the characters in the range [pos,pos + n1) from this string.
1374        *  In place, @a n2 copies of @a c are inserted.  If @a pos is beyond
1375        *  end of string, out_of_range is thrown.  If the length of result
1376        *  exceeds max_size(), length_error is thrown.  The value of the string
1377        *  doesn't change if an error is thrown.
1378       */
1379       basic_string&
1380       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
1381       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
1382                               _M_limit(__pos, __n1), __n2, __c); }
1383
1384       /**
1385        *  @brief  Replace range of characters with string.
1386        *  @param i1  Iterator referencing start of range to replace.
1387        *  @param i2  Iterator referencing end of range to replace.
1388        *  @param str  String value to insert.
1389        *  @return  Reference to this string.
1390        *  @throw  std::length_error  If new length exceeds @c max_size().
1391        *
1392        *  Removes the characters in the range [i1,i2).  In place, the value of
1393        *  @a str is inserted.  If the length of result exceeds max_size(),
1394        *  length_error is thrown.  The value of the string doesn't change if
1395        *  an error is thrown.
1396       */
1397       basic_string&
1398       replace(iterator __i1, iterator __i2, const basic_string& __str)
1399       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
1400
1401       /**
1402        *  @brief  Replace range of characters with C substring.
1403        *  @param i1  Iterator referencing start of range to replace.
1404        *  @param i2  Iterator referencing end of range to replace.
1405        *  @param s  C string value to insert.
1406        *  @param n  Number of characters from s to insert.
1407        *  @return  Reference to this string.
1408        *  @throw  std::length_error  If new length exceeds @c max_size().
1409        *
1410        *  Removes the characters in the range [i1,i2).  In place, the first @a
1411        *  n characters of @a s are inserted.  If the length of result exceeds
1412        *  max_size(), length_error is thrown.  The value of the string doesn't
1413        *  change if an error is thrown.
1414       */
1415       basic_string&
1416       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
1417       {
1418         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1419                                  && __i2 <= _M_iend());
1420         return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
1421       }
1422
1423       /**
1424        *  @brief  Replace range of characters with C string.
1425        *  @param i1  Iterator referencing start of range to replace.
1426        *  @param i2  Iterator referencing end of range to replace.
1427        *  @param s  C string value to insert.
1428        *  @return  Reference to this string.
1429        *  @throw  std::length_error  If new length exceeds @c max_size().
1430        *
1431        *  Removes the characters in the range [i1,i2).  In place, the
1432        *  characters of @a s are inserted.  If the length of result exceeds
1433        *  max_size(), length_error is thrown.  The value of the string doesn't
1434        *  change if an error is thrown.
1435       */
1436       basic_string&
1437       replace(iterator __i1, iterator __i2, const _CharT* __s)
1438       {
1439         __glibcxx_requires_string(__s);
1440         return this->replace(__i1, __i2, __s, traits_type::length(__s));
1441       }
1442
1443       /**
1444        *  @brief  Replace range of characters with multiple characters
1445        *  @param i1  Iterator referencing start of range to replace.
1446        *  @param i2  Iterator referencing end of range to replace.
1447        *  @param n  Number of characters to insert.
1448        *  @param c  Character to insert.
1449        *  @return  Reference to this string.
1450        *  @throw  std::length_error  If new length exceeds @c max_size().
1451        *
1452        *  Removes the characters in the range [i1,i2).  In place, @a n copies
1453        *  of @a c are inserted.  If the length of result exceeds max_size(),
1454        *  length_error is thrown.  The value of the string doesn't change if
1455        *  an error is thrown.
1456       */
1457       basic_string&
1458       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
1459       {
1460         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1461                                  && __i2 <= _M_iend());
1462         return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
1463       }
1464
1465       /**
1466        *  @brief  Replace range of characters with range.
1467        *  @param i1  Iterator referencing start of range to replace.
1468        *  @param i2  Iterator referencing end of range to replace.
1469        *  @param k1  Iterator referencing start of range to insert.
1470        *  @param k2  Iterator referencing end of range to insert.
1471        *  @return  Reference to this string.
1472        *  @throw  std::length_error  If new length exceeds @c max_size().
1473        *
1474        *  Removes the characters in the range [i1,i2).  In place, characters
1475        *  in the range [k1,k2) are inserted.  If the length of result exceeds
1476        *  max_size(), length_error is thrown.  The value of the string doesn't
1477        *  change if an error is thrown.
1478       */
1479       template<class _InputIterator>
1480         basic_string&
1481         replace(iterator __i1, iterator __i2,
1482                 _InputIterator __k1, _InputIterator __k2)
1483         {
1484           _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1485                                    && __i2 <= _M_iend());
1486           __glibcxx_requires_valid_range(__k1, __k2);
1487           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1488           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
1489         }
1490
1491       // Specializations for the common case of pointer and iterator:
1492       // useful to avoid the overhead of temporary buffering in _M_replace.
1493       basic_string&
1494       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
1495       {
1496         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1497                                  && __i2 <= _M_iend());
1498         __glibcxx_requires_valid_range(__k1, __k2);
1499         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1500                              __k1, __k2 - __k1);
1501       }
1502
1503       basic_string&
1504       replace(iterator __i1, iterator __i2,
1505               const _CharT* __k1, const _CharT* __k2)
1506       {
1507         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1508                                  && __i2 <= _M_iend());
1509         __glibcxx_requires_valid_range(__k1, __k2);
1510         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1511                              __k1, __k2 - __k1);
1512       }
1513
1514       basic_string&
1515       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
1516       {
1517         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1518                                  && __i2 <= _M_iend());
1519         __glibcxx_requires_valid_range(__k1, __k2);
1520         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1521                              __k1.base(), __k2 - __k1);
1522       }
1523
1524       basic_string&
1525       replace(iterator __i1, iterator __i2,
1526               const_iterator __k1, const_iterator __k2)
1527       {
1528         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1529                                  && __i2 <= _M_iend());
1530         __glibcxx_requires_valid_range(__k1, __k2);
1531         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1532                              __k1.base(), __k2 - __k1);
1533       }
1534       
1535 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1536       /**
1537        *  @brief  Replace range of characters with initializer_list.
1538        *  @param i1  Iterator referencing start of range to replace.
1539        *  @param i2  Iterator referencing end of range to replace.
1540        *  @param l  The initializer_list of characters to insert.
1541        *  @return  Reference to this string.
1542        *  @throw  std::length_error  If new length exceeds @c max_size().
1543        *
1544        *  Removes the characters in the range [i1,i2).  In place, characters
1545        *  in the range [k1,k2) are inserted.  If the length of result exceeds
1546        *  max_size(), length_error is thrown.  The value of the string doesn't
1547        *  change if an error is thrown.
1548       */
1549       basic_string& replace(iterator __i1, iterator __i2,
1550                             initializer_list<_CharT> __l)
1551       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
1552 #endif // __GXX_EXPERIMENTAL_CXX0X__
1553
1554     private:
1555       template<class _Integer>
1556         basic_string&
1557         _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
1558                             _Integer __val, __true_type)
1559         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
1560
1561       template<class _InputIterator>
1562         basic_string&
1563         _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1564                             _InputIterator __k2, __false_type);
1565
1566       basic_string&
1567       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1568                      _CharT __c);
1569
1570       basic_string&
1571       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1572                       size_type __n2);
1573
1574       // _S_construct_aux is used to implement the 21.3.1 para 15 which
1575       // requires special behaviour if _InIter is an integral type
1576       template<class _InIterator>
1577         static _CharT*
1578         _S_construct_aux(_InIterator __beg, _InIterator __end,
1579                          const _Alloc& __a, __false_type)
1580         {
1581           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
1582           return _S_construct(__beg, __end, __a, _Tag());
1583         }
1584
1585       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1586       // 438. Ambiguity in the "do the right thing" clause
1587       template<class _Integer>
1588         static _CharT*
1589         _S_construct_aux(_Integer __beg, _Integer __end,
1590                          const _Alloc& __a, __true_type)
1591         { return _S_construct(static_cast<size_type>(__beg),
1592                               static_cast<value_type>(__end), __a); }
1593
1594       template<class _InIterator>
1595         static _CharT*
1596         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
1597         {
1598           typedef typename std::__is_integer<_InIterator>::__type _Integral;
1599           return _S_construct_aux(__beg, __end, __a, _Integral());
1600         }
1601
1602       // For Input Iterators, used in istreambuf_iterators, etc.
1603       template<class _InIterator>
1604         static _CharT*
1605          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
1606                       input_iterator_tag);
1607
1608       // For forward_iterators up to random_access_iterators, used for
1609       // string::iterator, _CharT*, etc.
1610       template<class _FwdIterator>
1611         static _CharT*
1612         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
1613                      forward_iterator_tag);
1614
1615       static _CharT*
1616       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
1617
1618     public:
1619
1620       /**
1621        *  @brief  Copy substring into C string.
1622        *  @param s  C string to copy value into.
1623        *  @param n  Number of characters to copy.
1624        *  @param pos  Index of first character to copy.
1625        *  @return  Number of characters actually copied
1626        *  @throw  std::out_of_range  If pos > size().
1627        *
1628        *  Copies up to @a n characters starting at @a pos into the C string @a
1629        *  s.  If @a pos is greater than size(), out_of_range is thrown.
1630       */
1631       size_type
1632       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
1633
1634       /**
1635        *  @brief  Swap contents with another string.
1636        *  @param s  String to swap with.
1637        *
1638        *  Exchanges the contents of this string with that of @a s in constant
1639        *  time.
1640       */
1641       void
1642       swap(basic_string& __s);
1643
1644       // String operations:
1645       /**
1646        *  @brief  Return const pointer to null-terminated contents.
1647        *
1648        *  This is a handle to internal data.  Do not modify or dire things may
1649        *  happen.
1650       */
1651       const _CharT*
1652       c_str() const
1653       { return _M_data(); }
1654
1655       /**
1656        *  @brief  Return const pointer to contents.
1657        *
1658        *  This is a handle to internal data.  Do not modify or dire things may
1659        *  happen.
1660       */
1661       const _CharT*
1662       data() const
1663       { return _M_data(); }
1664
1665       /**
1666        *  @brief  Return copy of allocator used to construct this string.
1667       */
1668       allocator_type
1669       get_allocator() const
1670       { return _M_dataplus; }
1671
1672       /**
1673        *  @brief  Find position of a C substring.
1674        *  @param s  C string to locate.
1675        *  @param pos  Index of character to search from.
1676        *  @param n  Number of characters from @a s to search for.
1677        *  @return  Index of start of first occurrence.
1678        *
1679        *  Starting from @a pos, searches forward for the first @a n characters
1680        *  in @a s within this string.  If found, returns the index where it
1681        *  begins.  If not found, returns npos.
1682       */
1683       size_type
1684       find(const _CharT* __s, size_type __pos, size_type __n) const;
1685
1686       /**
1687        *  @brief  Find position of a string.
1688        *  @param str  String to locate.
1689        *  @param pos  Index of character to search from (default 0).
1690        *  @return  Index of start of first occurrence.
1691        *
1692        *  Starting from @a pos, searches forward for value of @a str within
1693        *  this string.  If found, returns the index where it begins.  If not
1694        *  found, returns npos.
1695       */
1696       size_type
1697       find(const basic_string& __str, size_type __pos = 0) const
1698       { return this->find(__str.data(), __pos, __str.size()); }
1699
1700       /**
1701        *  @brief  Find position of a C string.
1702        *  @param s  C string to locate.
1703        *  @param pos  Index of character to search from (default 0).
1704        *  @return  Index of start of first occurrence.
1705        *
1706        *  Starting from @a pos, searches forward for the value of @a s within
1707        *  this string.  If found, returns the index where it begins.  If not
1708        *  found, returns npos.
1709       */
1710       size_type
1711       find(const _CharT* __s, size_type __pos = 0) const
1712       {
1713         __glibcxx_requires_string(__s);
1714         return this->find(__s, __pos, traits_type::length(__s));
1715       }
1716
1717       /**
1718        *  @brief  Find position of a character.
1719        *  @param c  Character to locate.
1720        *  @param pos  Index of character to search from (default 0).
1721        *  @return  Index of first occurrence.
1722        *
1723        *  Starting from @a pos, searches forward for @a c within this string.
1724        *  If found, returns the index where it was found.  If not found,
1725        *  returns npos.
1726       */
1727       size_type
1728       find(_CharT __c, size_type __pos = 0) const;
1729
1730       /**
1731        *  @brief  Find last position of a string.
1732        *  @param str  String to locate.
1733        *  @param pos  Index of character to search back from (default end).
1734        *  @return  Index of start of last occurrence.
1735        *
1736        *  Starting from @a pos, searches backward for value of @a str within
1737        *  this string.  If found, returns the index where it begins.  If not
1738        *  found, returns npos.
1739       */
1740       size_type
1741       rfind(const basic_string& __str, size_type __pos = npos) const
1742       { return this->rfind(__str.data(), __pos, __str.size()); }
1743
1744       /**
1745        *  @brief  Find last position of a C substring.
1746        *  @param s  C string to locate.
1747        *  @param pos  Index of character to search back from.
1748        *  @param n  Number of characters from s to search for.
1749        *  @return  Index of start of last occurrence.
1750        *
1751        *  Starting from @a pos, searches backward for the first @a n
1752        *  characters in @a s within this string.  If found, returns the index
1753        *  where it begins.  If not found, returns npos.
1754       */
1755       size_type
1756       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
1757
1758       /**
1759        *  @brief  Find last position of a C string.
1760        *  @param s  C string to locate.
1761        *  @param pos  Index of character to start search at (default end).
1762        *  @return  Index of start of  last occurrence.
1763        *
1764        *  Starting from @a pos, searches backward for the value of @a s within
1765        *  this string.  If found, returns the index where it begins.  If not
1766        *  found, returns npos.
1767       */
1768       size_type
1769       rfind(const _CharT* __s, size_type __pos = npos) const
1770       {
1771         __glibcxx_requires_string(__s);
1772         return this->rfind(__s, __pos, traits_type::length(__s));
1773       }
1774
1775       /**
1776        *  @brief  Find last position of a character.
1777        *  @param c  Character to locate.
1778        *  @param pos  Index of character to search back from (default end).
1779        *  @return  Index of last occurrence.
1780        *
1781        *  Starting from @a pos, searches backward for @a c within this string.
1782        *  If found, returns the index where it was found.  If not found,
1783        *  returns npos.
1784       */
1785       size_type
1786       rfind(_CharT __c, size_type __pos = npos) const;
1787
1788       /**
1789        *  @brief  Find position of a character of string.
1790        *  @param str  String containing characters to locate.
1791        *  @param pos  Index of character to search from (default 0).
1792        *  @return  Index of first occurrence.
1793        *
1794        *  Starting from @a pos, searches forward for one of the characters of
1795        *  @a str within this string.  If found, returns the index where it was
1796        *  found.  If not found, returns npos.
1797       */
1798       size_type
1799       find_first_of(const basic_string& __str, size_type __pos = 0) const
1800       { return this->find_first_of(__str.data(), __pos, __str.size()); }
1801
1802       /**
1803        *  @brief  Find position of a character of C substring.
1804        *  @param s  String containing characters to locate.
1805        *  @param pos  Index of character to search from.
1806        *  @param n  Number of characters from s to search for.
1807        *  @return  Index of first occurrence.
1808        *
1809        *  Starting from @a pos, searches forward for one of the first @a n
1810        *  characters of @a s within this string.  If found, returns the index
1811        *  where it was found.  If not found, returns npos.
1812       */
1813       size_type
1814       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
1815
1816       /**
1817        *  @brief  Find position of a character of C string.
1818        *  @param s  String containing characters to locate.
1819        *  @param pos  Index of character to search from (default 0).
1820        *  @return  Index of first occurrence.
1821        *
1822        *  Starting from @a pos, searches forward for one of the characters of
1823        *  @a s within this string.  If found, returns the index where it was
1824        *  found.  If not found, returns npos.
1825       */
1826       size_type
1827       find_first_of(const _CharT* __s, size_type __pos = 0) const
1828       {
1829         __glibcxx_requires_string(__s);
1830         return this->find_first_of(__s, __pos, traits_type::length(__s));
1831       }
1832
1833       /**
1834        *  @brief  Find position of a character.
1835        *  @param c  Character to locate.
1836        *  @param pos  Index of character to search from (default 0).
1837        *  @return  Index of first occurrence.
1838        *
1839        *  Starting from @a pos, searches forward for the character @a c within
1840        *  this string.  If found, returns the index where it was found.  If
1841        *  not found, returns npos.
1842        *
1843        *  Note: equivalent to find(c, pos).
1844       */
1845       size_type
1846       find_first_of(_CharT __c, size_type __pos = 0) const
1847       { return this->find(__c, __pos); }
1848
1849       /**
1850        *  @brief  Find last position of a character of string.
1851        *  @param str  String containing characters to locate.
1852        *  @param pos  Index of character to search back from (default end).
1853        *  @return  Index of last occurrence.
1854        *
1855        *  Starting from @a pos, searches backward for one of the characters of
1856        *  @a str within this string.  If found, returns the index where it was
1857        *  found.  If not found, returns npos.
1858       */
1859       size_type
1860       find_last_of(const basic_string& __str, size_type __pos = npos) const
1861       { return this->find_last_of(__str.data(), __pos, __str.size()); }
1862
1863       /**
1864        *  @brief  Find last position of a character of C substring.
1865        *  @param s  C string containing characters to locate.
1866        *  @param pos  Index of character to search back from.
1867        *  @param n  Number of characters from s to search for.
1868        *  @return  Index of last occurrence.
1869        *
1870        *  Starting from @a pos, searches backward for one of the first @a n
1871        *  characters of @a s within this string.  If found, returns the index
1872        *  where it was found.  If not found, returns npos.
1873       */
1874       size_type
1875       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
1876
1877       /**
1878        *  @brief  Find last position of a character of C string.
1879        *  @param s  C string containing characters to locate.
1880        *  @param pos  Index of character to search back from (default end).
1881        *  @return  Index of last occurrence.
1882        *
1883        *  Starting from @a pos, searches backward for one of the characters of
1884        *  @a s within this string.  If found, returns the index where it was
1885        *  found.  If not found, returns npos.
1886       */
1887       size_type
1888       find_last_of(const _CharT* __s, size_type __pos = npos) const
1889       {
1890         __glibcxx_requires_string(__s);
1891         return this->find_last_of(__s, __pos, traits_type::length(__s));
1892       }
1893
1894       /**
1895        *  @brief  Find last position of a character.
1896        *  @param c  Character to locate.
1897        *  @param pos  Index of character to search back from (default end).
1898        *  @return  Index of last occurrence.
1899        *
1900        *  Starting from @a pos, searches backward for @a c within this string.
1901        *  If found, returns the index where it was found.  If not found,
1902        *  returns npos.
1903        *
1904        *  Note: equivalent to rfind(c, pos).
1905       */
1906       size_type
1907       find_last_of(_CharT __c, size_type __pos = npos) const
1908       { return this->rfind(__c, __pos); }
1909
1910       /**
1911        *  @brief  Find position of a character not in string.
1912        *  @param str  String containing characters to avoid.
1913        *  @param pos  Index of character to search from (default 0).
1914        *  @return  Index of first occurrence.
1915        *
1916        *  Starting from @a pos, searches forward for a character not contained
1917        *  in @a str within this string.  If found, returns the index where it
1918        *  was found.  If not found, returns npos.
1919       */
1920       size_type
1921       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
1922       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
1923
1924       /**
1925        *  @brief  Find position of a character not in C substring.
1926        *  @param s  C string containing characters to avoid.
1927        *  @param pos  Index of character to search from.
1928        *  @param n  Number of characters from s to consider.
1929        *  @return  Index of first occurrence.
1930        *
1931        *  Starting from @a pos, searches forward for a character not contained
1932        *  in the first @a n characters of @a s within this string.  If found,
1933        *  returns the index where it was found.  If not found, returns npos.
1934       */
1935       size_type
1936       find_first_not_of(const _CharT* __s, size_type __pos,
1937                         size_type __n) const;
1938
1939       /**
1940        *  @brief  Find position of a character not in C string.
1941        *  @param s  C string containing characters to avoid.
1942        *  @param pos  Index of character to search from (default 0).
1943        *  @return  Index of first occurrence.
1944        *
1945        *  Starting from @a pos, searches forward for a character not contained
1946        *  in @a s within this string.  If found, returns the index where it
1947        *  was found.  If not found, returns npos.
1948       */
1949       size_type
1950       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
1951       {
1952         __glibcxx_requires_string(__s);
1953         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
1954       }
1955
1956       /**
1957        *  @brief  Find position of a different character.
1958        *  @param c  Character to avoid.
1959        *  @param pos  Index of character to search from (default 0).
1960        *  @return  Index of first occurrence.
1961        *
1962        *  Starting from @a pos, searches forward for a character other than @a c
1963        *  within this string.  If found, returns the index where it was found.
1964        *  If not found, returns npos.
1965       */
1966       size_type
1967       find_first_not_of(_CharT __c, size_type __pos = 0) const;
1968
1969       /**
1970        *  @brief  Find last position of a character not in string.
1971        *  @param str  String containing characters to avoid.
1972        *  @param pos  Index of character to search back from (default end).
1973        *  @return  Index of last occurrence.
1974        *
1975        *  Starting from @a pos, searches backward for a character not
1976        *  contained in @a str within this string.  If found, returns the index
1977        *  where it was found.  If not found, returns npos.
1978       */
1979       size_type
1980       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
1981       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
1982
1983       /**
1984        *  @brief  Find last position of a character not in C substring.
1985        *  @param s  C string containing characters to avoid.
1986        *  @param pos  Index of character to search back from.
1987        *  @param n  Number of characters from s to consider.
1988        *  @return  Index of last occurrence.
1989        *
1990        *  Starting from @a pos, searches backward for a character not
1991        *  contained in the first @a n characters of @a s within this string.
1992        *  If found, returns the index where it was found.  If not found,
1993        *  returns npos.
1994       */
1995       size_type
1996       find_last_not_of(const _CharT* __s, size_type __pos,
1997                        size_type __n) const;
1998       /**
1999        *  @brief  Find last position of a character not in C string.
2000        *  @param s  C string containing characters to avoid.
2001        *  @param pos  Index of character to search back from (default end).
2002        *  @return  Index of last occurrence.
2003        *
2004        *  Starting from @a pos, searches backward for a character not
2005        *  contained in @a s within this string.  If found, returns the index
2006        *  where it was found.  If not found, returns npos.
2007       */
2008       size_type
2009       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2010       {
2011         __glibcxx_requires_string(__s);
2012         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2013       }
2014
2015       /**
2016        *  @brief  Find last position of a different character.
2017        *  @param c  Character to avoid.
2018        *  @param pos  Index of character to search back from (default end).
2019        *  @return  Index of last occurrence.
2020        *
2021        *  Starting from @a pos, searches backward for a character other than
2022        *  @a c within this string.  If found, returns the index where it was
2023        *  found.  If not found, returns npos.
2024       */
2025       size_type
2026       find_last_not_of(_CharT __c, size_type __pos = npos) const;
2027
2028       /**
2029        *  @brief  Get a substring.
2030        *  @param pos  Index of first character (default 0).
2031        *  @param n  Number of characters in substring (default remainder).
2032        *  @return  The new string.
2033        *  @throw  std::out_of_range  If pos > size().
2034        *
2035        *  Construct and return a new string using the @a n characters starting
2036        *  at @a pos.  If the string is too short, use the remainder of the
2037        *  characters.  If @a pos is beyond the end of the string, out_of_range
2038        *  is thrown.
2039       */
2040       basic_string
2041       substr(size_type __pos = 0, size_type __n = npos) const
2042       { return basic_string(*this,
2043                             _M_check(__pos, "basic_string::substr"), __n); }
2044
2045       /**
2046        *  @brief  Compare to a string.
2047        *  @param str  String to compare against.
2048        *  @return  Integer < 0, 0, or > 0.
2049        *
2050        *  Returns an integer < 0 if this string is ordered before @a str, 0 if
2051        *  their values are equivalent, or > 0 if this string is ordered after
2052        *  @a str.  Determines the effective length rlen of the strings to
2053        *  compare as the smallest of size() and str.size().  The function
2054        *  then compares the two strings by calling traits::compare(data(),
2055        *  str.data(),rlen).  If the result of the comparison is nonzero returns
2056        *  it, otherwise the shorter one is ordered first.
2057       */
2058       int
2059       compare(const basic_string& __str) const
2060       {
2061         const size_type __size = this->size();
2062         const size_type __osize = __str.size();
2063         const size_type __len = std::min(__size, __osize);
2064
2065         int __r = traits_type::compare(_M_data(), __str.data(), __len);
2066         if (!__r)
2067           __r = _S_compare(__size, __osize);
2068         return __r;
2069       }
2070
2071       /**
2072        *  @brief  Compare substring to a string.
2073        *  @param pos  Index of first character of substring.
2074        *  @param n  Number of characters in substring.
2075        *  @param str  String to compare against.
2076        *  @return  Integer < 0, 0, or > 0.
2077        *
2078        *  Form the substring of this string from the @a n characters starting
2079        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2080        *  before @a str, 0 if their values are equivalent, or > 0 if the
2081        *  substring is ordered after @a str.  Determines the effective length
2082        *  rlen of the strings to compare as the smallest of the length of the
2083        *  substring and @a str.size().  The function then compares the two
2084        *  strings by calling traits::compare(substring.data(),str.data(),rlen).
2085        *  If the result of the comparison is nonzero returns it, otherwise the
2086        *  shorter one is ordered first.
2087       */
2088       int
2089       compare(size_type __pos, size_type __n, const basic_string& __str) const;
2090
2091       /**
2092        *  @brief  Compare substring to a substring.
2093        *  @param pos1  Index of first character of substring.
2094        *  @param n1  Number of characters in substring.
2095        *  @param str  String to compare against.
2096        *  @param pos2  Index of first character of substring of str.
2097        *  @param n2  Number of characters in substring of str.
2098        *  @return  Integer < 0, 0, or > 0.
2099        *
2100        *  Form the substring of this string from the @a n1 characters starting
2101        *  at @a pos1.  Form the substring of @a str from the @a n2 characters
2102        *  starting at @a pos2.  Returns an integer < 0 if this substring is
2103        *  ordered before the substring of @a str, 0 if their values are
2104        *  equivalent, or > 0 if this substring is ordered after the substring
2105        *  of @a str.  Determines the effective length rlen of the strings
2106        *  to compare as the smallest of the lengths of the substrings.  The
2107        *  function then compares the two strings by calling
2108        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2109        *  If the result of the comparison is nonzero returns it, otherwise the
2110        *  shorter one is ordered first.
2111       */
2112       int
2113       compare(size_type __pos1, size_type __n1, const basic_string& __str,
2114               size_type __pos2, size_type __n2) const;
2115
2116       /**
2117        *  @brief  Compare to a C string.
2118        *  @param s  C string to compare against.
2119        *  @return  Integer < 0, 0, or > 0.
2120        *
2121        *  Returns an integer < 0 if this string is ordered before @a s, 0 if
2122        *  their values are equivalent, or > 0 if this string is ordered after
2123        *  @a s.  Determines the effective length rlen of the strings to
2124        *  compare as the smallest of size() and the length of a string
2125        *  constructed from @a s.  The function then compares the two strings
2126        *  by calling traits::compare(data(),s,rlen).  If the result of the
2127        *  comparison is nonzero returns it, otherwise the shorter one is
2128        *  ordered first.
2129       */
2130       int
2131       compare(const _CharT* __s) const;
2132
2133       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2134       // 5 String::compare specification questionable
2135       /**
2136        *  @brief  Compare substring to a C string.
2137        *  @param pos  Index of first character of substring.
2138        *  @param n1  Number of characters in substring.
2139        *  @param s  C string to compare against.
2140        *  @return  Integer < 0, 0, or > 0.
2141        *
2142        *  Form the substring of this string from the @a n1 characters starting
2143        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2144        *  before @a s, 0 if their values are equivalent, or > 0 if the
2145        *  substring is ordered after @a s.  Determines the effective length
2146        *  rlen of the strings to compare as the smallest of the length of the 
2147        *  substring and the length of a string constructed from @a s.  The
2148        *  function then compares the two string by calling
2149        *  traits::compare(substring.data(),s,rlen).  If the result of the
2150        *  comparison is nonzero returns it, otherwise the shorter one is
2151        *  ordered first.
2152       */
2153       int
2154       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2155
2156       /**
2157        *  @brief  Compare substring against a character array.
2158        *  @param pos1  Index of first character of substring.
2159        *  @param n1  Number of characters in substring.
2160        *  @param s  character array to compare against.
2161        *  @param n2  Number of characters of s.
2162        *  @return  Integer < 0, 0, or > 0.
2163        *
2164        *  Form the substring of this string from the @a n1 characters starting
2165        *  at @a pos1.  Form a string from the first @a n2 characters of @a s.
2166        *  Returns an integer < 0 if this substring is ordered before the string
2167        *  from @a s, 0 if their values are equivalent, or > 0 if this substring
2168        *  is ordered after the string from @a s.   Determines the effective
2169        *  length rlen of the strings to compare as the smallest of the length
2170        *  of the substring and @a n2.  The function then compares the two
2171        *  strings by calling traits::compare(substring.data(),s,rlen).  If the
2172        *  result of the comparison is nonzero returns it, otherwise the shorter
2173        *  one is ordered first.
2174        *
2175        *  NB: s must have at least n2 characters, '\\0' has no special
2176        *  meaning.
2177       */
2178       int
2179       compare(size_type __pos, size_type __n1, const _CharT* __s,
2180               size_type __n2) const;
2181   };
2182
2183   template<typename _CharT, typename _Traits, typename _Alloc>
2184     inline basic_string<_CharT, _Traits, _Alloc>::
2185     basic_string()
2186 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
2187     : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2188 #else
2189     : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()) { }
2190 #endif
2191
2192   // operator+
2193   /**
2194    *  @brief  Concatenate two strings.
2195    *  @param lhs  First string.
2196    *  @param rhs  Last string.
2197    *  @return  New string with value of @a lhs followed by @a rhs.
2198    */
2199   template<typename _CharT, typename _Traits, typename _Alloc>
2200     basic_string<_CharT, _Traits, _Alloc>
2201     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2202               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2203     {
2204       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2205       __str.append(__rhs);
2206       return __str;
2207     }
2208
2209   /**
2210    *  @brief  Concatenate C string and string.
2211    *  @param lhs  First string.
2212    *  @param rhs  Last string.
2213    *  @return  New string with value of @a lhs followed by @a rhs.
2214    */
2215   template<typename _CharT, typename _Traits, typename _Alloc>
2216     basic_string<_CharT,_Traits,_Alloc>
2217     operator+(const _CharT* __lhs,
2218               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2219
2220   /**
2221    *  @brief  Concatenate character and string.
2222    *  @param lhs  First string.
2223    *  @param rhs  Last string.
2224    *  @return  New string with @a lhs followed by @a rhs.
2225    */
2226   template<typename _CharT, typename _Traits, typename _Alloc>
2227     basic_string<_CharT,_Traits,_Alloc>
2228     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2229
2230   /**
2231    *  @brief  Concatenate string and C string.
2232    *  @param lhs  First string.
2233    *  @param rhs  Last string.
2234    *  @return  New string with @a lhs followed by @a rhs.
2235    */
2236   template<typename _CharT, typename _Traits, typename _Alloc>
2237     inline basic_string<_CharT, _Traits, _Alloc>
2238     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2239              const _CharT* __rhs)
2240     {
2241       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2242       __str.append(__rhs);
2243       return __str;
2244     }
2245
2246   /**
2247    *  @brief  Concatenate string and character.
2248    *  @param lhs  First string.
2249    *  @param rhs  Last string.
2250    *  @return  New string with @a lhs followed by @a rhs.
2251    */
2252   template<typename _CharT, typename _Traits, typename _Alloc>
2253     inline basic_string<_CharT, _Traits, _Alloc>
2254     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
2255     {
2256       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
2257       typedef typename __string_type::size_type         __size_type;
2258       __string_type __str(__lhs);
2259       __str.append(__size_type(1), __rhs);
2260       return __str;
2261     }
2262
2263   // operator ==
2264   /**
2265    *  @brief  Test equivalence of two strings.
2266    *  @param lhs  First string.
2267    *  @param rhs  Second string.
2268    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
2269    */
2270   template<typename _CharT, typename _Traits, typename _Alloc>
2271     inline bool
2272     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2273                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2274     { return __lhs.compare(__rhs) == 0; }
2275
2276   template<typename _CharT>
2277     inline
2278     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
2279     operator==(const basic_string<_CharT>& __lhs,
2280                const basic_string<_CharT>& __rhs)
2281     { return (__lhs.size() == __rhs.size()
2282               && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
2283                                                     __lhs.size())); }
2284
2285   /**
2286    *  @brief  Test equivalence of C string and string.
2287    *  @param lhs  C string.
2288    *  @param rhs  String.
2289    *  @return  True if @a rhs.compare(@a lhs) == 0.  False otherwise.
2290    */
2291   template<typename _CharT, typename _Traits, typename _Alloc>
2292     inline bool
2293     operator==(const _CharT* __lhs,
2294                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2295     { return __rhs.compare(__lhs) == 0; }
2296
2297   /**
2298    *  @brief  Test equivalence of string and C string.
2299    *  @param lhs  String.
2300    *  @param rhs  C string.
2301    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
2302    */
2303   template<typename _CharT, typename _Traits, typename _Alloc>
2304     inline bool
2305     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2306                const _CharT* __rhs)
2307     { return __lhs.compare(__rhs) == 0; }
2308
2309   // operator !=
2310   /**
2311    *  @brief  Test difference of two strings.
2312    *  @param lhs  First string.
2313    *  @param rhs  Second string.
2314    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
2315    */
2316   template<typename _CharT, typename _Traits, typename _Alloc>
2317     inline bool
2318     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2319                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2320     { return !(__lhs == __rhs); }
2321
2322   /**
2323    *  @brief  Test difference of C string and string.
2324    *  @param lhs  C string.
2325    *  @param rhs  String.
2326    *  @return  True if @a rhs.compare(@a lhs) != 0.  False otherwise.
2327    */
2328   template<typename _CharT, typename _Traits, typename _Alloc>
2329     inline bool
2330     operator!=(const _CharT* __lhs,
2331                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2332     { return !(__lhs == __rhs); }
2333
2334   /**
2335    *  @brief  Test difference of string and C string.
2336    *  @param lhs  String.
2337    *  @param rhs  C string.
2338    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
2339    */
2340   template<typename _CharT, typename _Traits, typename _Alloc>
2341     inline bool
2342     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2343                const _CharT* __rhs)
2344     { return !(__lhs == __rhs); }
2345
2346   // operator <
2347   /**
2348    *  @brief  Test if string precedes string.
2349    *  @param lhs  First string.
2350    *  @param rhs  Second string.
2351    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2352    */
2353   template<typename _CharT, typename _Traits, typename _Alloc>
2354     inline bool
2355     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2356               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2357     { return __lhs.compare(__rhs) < 0; }
2358
2359   /**
2360    *  @brief  Test if string precedes C string.
2361    *  @param lhs  String.
2362    *  @param rhs  C string.
2363    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2364    */
2365   template<typename _CharT, typename _Traits, typename _Alloc>
2366     inline bool
2367     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2368               const _CharT* __rhs)
2369     { return __lhs.compare(__rhs) < 0; }
2370
2371   /**
2372    *  @brief  Test if C string precedes string.
2373    *  @param lhs  C string.
2374    *  @param rhs  String.
2375    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2376    */
2377   template<typename _CharT, typename _Traits, typename _Alloc>
2378     inline bool
2379     operator<(const _CharT* __lhs,
2380               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2381     { return __rhs.compare(__lhs) > 0; }
2382
2383   // operator >
2384   /**
2385    *  @brief  Test if string follows string.
2386    *  @param lhs  First string.
2387    *  @param rhs  Second string.
2388    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2389    */
2390   template<typename _CharT, typename _Traits, typename _Alloc>
2391     inline bool
2392     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2393               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2394     { return __lhs.compare(__rhs) > 0; }
2395
2396   /**
2397    *  @brief  Test if string follows C string.
2398    *  @param lhs  String.
2399    *  @param rhs  C string.
2400    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2401    */
2402   template<typename _CharT, typename _Traits, typename _Alloc>
2403     inline bool
2404     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2405               const _CharT* __rhs)
2406     { return __lhs.compare(__rhs) > 0; }
2407
2408   /**
2409    *  @brief  Test if C string follows string.
2410    *  @param lhs  C string.
2411    *  @param rhs  String.
2412    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2413    */
2414   template<typename _CharT, typename _Traits, typename _Alloc>
2415     inline bool
2416     operator>(const _CharT* __lhs,
2417               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2418     { return __rhs.compare(__lhs) < 0; }
2419
2420   // operator <=
2421   /**
2422    *  @brief  Test if string doesn't follow string.
2423    *  @param lhs  First string.
2424    *  @param rhs  Second string.
2425    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2426    */
2427   template<typename _CharT, typename _Traits, typename _Alloc>
2428     inline bool
2429     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2430                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2431     { return __lhs.compare(__rhs) <= 0; }
2432
2433   /**
2434    *  @brief  Test if string doesn't follow C string.
2435    *  @param lhs  String.
2436    *  @param rhs  C string.
2437    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2438    */
2439   template<typename _CharT, typename _Traits, typename _Alloc>
2440     inline bool
2441     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2442                const _CharT* __rhs)
2443     { return __lhs.compare(__rhs) <= 0; }
2444
2445   /**
2446    *  @brief  Test if C string doesn't follow string.
2447    *  @param lhs  C string.
2448    *  @param rhs  String.
2449    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2450    */
2451   template<typename _CharT, typename _Traits, typename _Alloc>
2452     inline bool
2453     operator<=(const _CharT* __lhs,
2454                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2455     { return __rhs.compare(__lhs) >= 0; }
2456
2457   // operator >=
2458   /**
2459    *  @brief  Test if string doesn't precede string.
2460    *  @param lhs  First string.
2461    *  @param rhs  Second string.
2462    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2463    */
2464   template<typename _CharT, typename _Traits, typename _Alloc>
2465     inline bool
2466     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2467                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2468     { return __lhs.compare(__rhs) >= 0; }
2469
2470   /**
2471    *  @brief  Test if string doesn't precede C string.
2472    *  @param lhs  String.
2473    *  @param rhs  C string.
2474    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2475    */
2476   template<typename _CharT, typename _Traits, typename _Alloc>
2477     inline bool
2478     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2479                const _CharT* __rhs)
2480     { return __lhs.compare(__rhs) >= 0; }
2481
2482   /**
2483    *  @brief  Test if C string doesn't precede string.
2484    *  @param lhs  C string.
2485    *  @param rhs  String.
2486    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2487    */
2488   template<typename _CharT, typename _Traits, typename _Alloc>
2489     inline bool
2490     operator>=(const _CharT* __lhs,
2491              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2492     { return __rhs.compare(__lhs) <= 0; }
2493
2494   /**
2495    *  @brief  Swap contents of two strings.
2496    *  @param lhs  First string.
2497    *  @param rhs  Second string.
2498    *
2499    *  Exchanges the contents of @a lhs and @a rhs in constant time.
2500    */
2501   template<typename _CharT, typename _Traits, typename _Alloc>
2502     inline void
2503     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
2504          basic_string<_CharT, _Traits, _Alloc>& __rhs)
2505     { __lhs.swap(__rhs); }
2506
2507   /**
2508    *  @brief  Read stream into a string.
2509    *  @param is  Input stream.
2510    *  @param str  Buffer to store into.
2511    *  @return  Reference to the input stream.
2512    *
2513    *  Stores characters from @a is into @a str until whitespace is found, the
2514    *  end of the stream is encountered, or str.max_size() is reached.  If
2515    *  is.width() is non-zero, that is the limit on the number of characters
2516    *  stored into @a str.  Any previous contents of @a str are erased.
2517    */
2518   template<typename _CharT, typename _Traits, typename _Alloc>
2519     basic_istream<_CharT, _Traits>&
2520     operator>>(basic_istream<_CharT, _Traits>& __is,
2521                basic_string<_CharT, _Traits, _Alloc>& __str);
2522
2523   template<>
2524     basic_istream<char>&
2525     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
2526
2527   /**
2528    *  @brief  Write string to a stream.
2529    *  @param os  Output stream.
2530    *  @param str  String to write out.
2531    *  @return  Reference to the output stream.
2532    *
2533    *  Output characters of @a str into os following the same rules as for
2534    *  writing a C string.
2535    */
2536   template<typename _CharT, typename _Traits, typename _Alloc>
2537     inline basic_ostream<_CharT, _Traits>&
2538     operator<<(basic_ostream<_CharT, _Traits>& __os,
2539                const basic_string<_CharT, _Traits, _Alloc>& __str)
2540     {
2541       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2542       // 586. string inserter not a formatted function
2543       return __ostream_insert(__os, __str.data(), __str.size());
2544     }
2545
2546   /**
2547    *  @brief  Read a line from stream into a string.
2548    *  @param is  Input stream.
2549    *  @param str  Buffer to store into.
2550    *  @param delim  Character marking end of line.
2551    *  @return  Reference to the input stream.
2552    *
2553    *  Stores characters from @a is into @a str until @a delim is found, the
2554    *  end of the stream is encountered, or str.max_size() is reached.  If
2555    *  is.width() is non-zero, that is the limit on the number of characters
2556    *  stored into @a str.  Any previous contents of @a str are erased.  If @a
2557    *  delim was encountered, it is extracted but not stored into @a str.
2558    */
2559   template<typename _CharT, typename _Traits, typename _Alloc>
2560     basic_istream<_CharT, _Traits>&
2561     getline(basic_istream<_CharT, _Traits>& __is,
2562             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
2563
2564   /**
2565    *  @brief  Read a line from stream into a string.
2566    *  @param is  Input stream.
2567    *  @param str  Buffer to store into.
2568    *  @return  Reference to the input stream.
2569    *
2570    *  Stores characters from is into @a str until '\n' is found, the end of
2571    *  the stream is encountered, or str.max_size() is reached.  If is.width()
2572    *  is non-zero, that is the limit on the number of characters stored into
2573    *  @a str.  Any previous contents of @a str are erased.  If end of line was
2574    *  encountered, it is extracted but not stored into @a str.
2575    */
2576   template<typename _CharT, typename _Traits, typename _Alloc>
2577     inline basic_istream<_CharT, _Traits>&
2578     getline(basic_istream<_CharT, _Traits>& __is,
2579             basic_string<_CharT, _Traits, _Alloc>& __str)
2580     { return getline(__is, __str, __is.widen('\n')); }
2581
2582   template<>
2583     basic_istream<char>&
2584     getline(basic_istream<char>& __in, basic_string<char>& __str,
2585             char __delim);
2586
2587 #ifdef _GLIBCXX_USE_WCHAR_T
2588   template<>
2589     basic_istream<wchar_t>&
2590     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
2591             wchar_t __delim);
2592 #endif  
2593
2594 _GLIBCXX_END_NAMESPACE
2595
2596 #if (defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99) \
2597      && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF))
2598
2599 #include <ext/string_conversions.h>
2600
2601 _GLIBCXX_BEGIN_NAMESPACE(std)
2602
2603   // 21.4 Numeric Conversions [string.conversions].
2604   inline int
2605   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
2606   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
2607                                         __idx, __base); }
2608
2609   inline long
2610   stol(const string& __str, size_t* __idx = 0, int __base = 10)
2611   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
2612                              __idx, __base); }
2613
2614   inline unsigned long
2615   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
2616   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
2617                              __idx, __base); }
2618
2619   inline long long
2620   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
2621   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
2622                              __idx, __base); }
2623
2624   inline unsigned long long
2625   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
2626   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
2627                              __idx, __base); }
2628
2629   // NB: strtof vs strtod.
2630   inline float
2631   stof(const string& __str, size_t* __idx = 0)
2632   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
2633
2634   inline double
2635   stod(const string& __str, size_t* __idx = 0)
2636   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
2637
2638   inline long double
2639   stold(const string& __str, size_t* __idx = 0)
2640   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
2641
2642   // NB: (v)snprintf vs sprintf.
2643
2644   // DR 1261.
2645   inline string
2646   to_string(int __val)
2647   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
2648                                            "%d", __val); }
2649
2650   inline string
2651   to_string(unsigned __val)
2652   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2653                                            4 * sizeof(unsigned),
2654                                            "%u", __val); }
2655
2656   inline string
2657   to_string(long __val)
2658   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
2659                                            "%ld", __val); }
2660
2661   inline string
2662   to_string(unsigned long __val)
2663   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2664                                            4 * sizeof(unsigned long),
2665                                            "%lu", __val); }
2666
2667   inline string
2668   to_string(long long __val)
2669   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2670                                            4 * sizeof(long long),
2671                                            "%lld", __val); }
2672
2673   inline string
2674   to_string(unsigned long long __val)
2675   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2676                                            4 * sizeof(unsigned long long),
2677                                            "%llu", __val); }
2678
2679   inline string
2680   to_string(float __val)
2681   {
2682     const int __n = 
2683       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2684     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2685                                            "%f", __val);
2686   }
2687
2688   inline string
2689   to_string(double __val)
2690   {
2691     const int __n = 
2692       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2693     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2694                                            "%f", __val);
2695   }
2696
2697   inline string
2698   to_string(long double __val)
2699   {
2700     const int __n = 
2701       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2702     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2703                                            "%Lf", __val);
2704   }
2705
2706 #ifdef _GLIBCXX_USE_WCHAR_T
2707   inline int 
2708   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
2709   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
2710                                         __idx, __base); }
2711
2712   inline long 
2713   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
2714   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
2715                              __idx, __base); }
2716
2717   inline unsigned long
2718   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
2719   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
2720                              __idx, __base); }
2721
2722   inline long long
2723   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
2724   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
2725                              __idx, __base); }
2726
2727   inline unsigned long long
2728   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
2729   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
2730                              __idx, __base); }
2731
2732   // NB: wcstof vs wcstod.
2733   inline float
2734   stof(const wstring& __str, size_t* __idx = 0)
2735   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
2736
2737   inline double
2738   stod(const wstring& __str, size_t* __idx = 0)
2739   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
2740
2741   inline long double
2742   stold(const wstring& __str, size_t* __idx = 0)
2743   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
2744
2745   // DR 1261.
2746   inline wstring
2747   to_wstring(int __val)
2748   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
2749                                             L"%d", __val); }
2750
2751   inline wstring
2752   to_wstring(unsigned __val)
2753   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2754                                             4 * sizeof(unsigned),
2755                                             L"%u", __val); }
2756
2757   inline wstring
2758   to_wstring(long __val)
2759   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
2760                                             L"%ld", __val); }
2761
2762   inline wstring
2763   to_wstring(unsigned long __val)
2764   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2765                                             4 * sizeof(unsigned long),
2766                                             L"%lu", __val); }
2767
2768   inline wstring
2769   to_wstring(long long __val)
2770   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2771                                             4 * sizeof(long long),
2772                                             L"%lld", __val); }
2773
2774   inline wstring
2775   to_wstring(unsigned long long __val)
2776   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2777                                             4 * sizeof(unsigned long long),
2778                                             L"%llu", __val); }
2779
2780   inline wstring
2781   to_wstring(float __val)
2782   {
2783     const int __n =
2784       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2785     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2786                                             L"%f", __val);
2787   }
2788
2789   inline wstring
2790   to_wstring(double __val)
2791   {
2792     const int __n =
2793       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2794     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2795                                             L"%f", __val);
2796   }
2797
2798   inline wstring
2799   to_wstring(long double __val)
2800   {
2801     const int __n =
2802       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2803     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2804                                             L"%Lf", __val);
2805   }
2806 #endif
2807
2808 _GLIBCXX_END_NAMESPACE
2809
2810 #endif
2811
2812 #endif /* _BASIC_STRING_H */