OSDN Git Service

2009-12-10 Paolo Carlini <paolo.carlini@oracle.com>
[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), __end, __a); }
1592
1593       template<class _InIterator>
1594         static _CharT*
1595         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
1596         {
1597           typedef typename std::__is_integer<_InIterator>::__type _Integral;
1598           return _S_construct_aux(__beg, __end, __a, _Integral());
1599         }
1600
1601       // For Input Iterators, used in istreambuf_iterators, etc.
1602       template<class _InIterator>
1603         static _CharT*
1604          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
1605                       input_iterator_tag);
1606
1607       // For forward_iterators up to random_access_iterators, used for
1608       // string::iterator, _CharT*, etc.
1609       template<class _FwdIterator>
1610         static _CharT*
1611         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
1612                      forward_iterator_tag);
1613
1614       static _CharT*
1615       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
1616
1617     public:
1618
1619       /**
1620        *  @brief  Copy substring into C string.
1621        *  @param s  C string to copy value into.
1622        *  @param n  Number of characters to copy.
1623        *  @param pos  Index of first character to copy.
1624        *  @return  Number of characters actually copied
1625        *  @throw  std::out_of_range  If pos > size().
1626        *
1627        *  Copies up to @a n characters starting at @a pos into the C string @a
1628        *  s.  If @a pos is greater than size(), out_of_range is thrown.
1629       */
1630       size_type
1631       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
1632
1633       /**
1634        *  @brief  Swap contents with another string.
1635        *  @param s  String to swap with.
1636        *
1637        *  Exchanges the contents of this string with that of @a s in constant
1638        *  time.
1639       */
1640       void
1641       swap(basic_string& __s);
1642
1643       // String operations:
1644       /**
1645        *  @brief  Return const pointer to null-terminated contents.
1646        *
1647        *  This is a handle to internal data.  Do not modify or dire things may
1648        *  happen.
1649       */
1650       const _CharT*
1651       c_str() const
1652       { return _M_data(); }
1653
1654       /**
1655        *  @brief  Return const pointer to contents.
1656        *
1657        *  This is a handle to internal data.  Do not modify or dire things may
1658        *  happen.
1659       */
1660       const _CharT*
1661       data() const
1662       { return _M_data(); }
1663
1664       /**
1665        *  @brief  Return copy of allocator used to construct this string.
1666       */
1667       allocator_type
1668       get_allocator() const
1669       { return _M_dataplus; }
1670
1671       /**
1672        *  @brief  Find position of a C substring.
1673        *  @param s  C string to locate.
1674        *  @param pos  Index of character to search from.
1675        *  @param n  Number of characters from @a s to search for.
1676        *  @return  Index of start of first occurrence.
1677        *
1678        *  Starting from @a pos, searches forward for the first @a n characters
1679        *  in @a s within this string.  If found, returns the index where it
1680        *  begins.  If not found, returns npos.
1681       */
1682       size_type
1683       find(const _CharT* __s, size_type __pos, size_type __n) const;
1684
1685       /**
1686        *  @brief  Find position of a string.
1687        *  @param str  String to locate.
1688        *  @param pos  Index of character to search from (default 0).
1689        *  @return  Index of start of first occurrence.
1690        *
1691        *  Starting from @a pos, searches forward for value of @a str within
1692        *  this string.  If found, returns the index where it begins.  If not
1693        *  found, returns npos.
1694       */
1695       size_type
1696       find(const basic_string& __str, size_type __pos = 0) const
1697       { return this->find(__str.data(), __pos, __str.size()); }
1698
1699       /**
1700        *  @brief  Find position of a C string.
1701        *  @param s  C string to locate.
1702        *  @param pos  Index of character to search from (default 0).
1703        *  @return  Index of start of first occurrence.
1704        *
1705        *  Starting from @a pos, searches forward for the value of @a s within
1706        *  this string.  If found, returns the index where it begins.  If not
1707        *  found, returns npos.
1708       */
1709       size_type
1710       find(const _CharT* __s, size_type __pos = 0) const
1711       {
1712         __glibcxx_requires_string(__s);
1713         return this->find(__s, __pos, traits_type::length(__s));
1714       }
1715
1716       /**
1717        *  @brief  Find position of a character.
1718        *  @param c  Character to locate.
1719        *  @param pos  Index of character to search from (default 0).
1720        *  @return  Index of first occurrence.
1721        *
1722        *  Starting from @a pos, searches forward for @a c within this string.
1723        *  If found, returns the index where it was found.  If not found,
1724        *  returns npos.
1725       */
1726       size_type
1727       find(_CharT __c, size_type __pos = 0) const;
1728
1729       /**
1730        *  @brief  Find last position of a string.
1731        *  @param str  String to locate.
1732        *  @param pos  Index of character to search back from (default end).
1733        *  @return  Index of start of last occurrence.
1734        *
1735        *  Starting from @a pos, searches backward for value of @a str within
1736        *  this string.  If found, returns the index where it begins.  If not
1737        *  found, returns npos.
1738       */
1739       size_type
1740       rfind(const basic_string& __str, size_type __pos = npos) const
1741       { return this->rfind(__str.data(), __pos, __str.size()); }
1742
1743       /**
1744        *  @brief  Find last position of a C substring.
1745        *  @param s  C string to locate.
1746        *  @param pos  Index of character to search back from.
1747        *  @param n  Number of characters from s to search for.
1748        *  @return  Index of start of last occurrence.
1749        *
1750        *  Starting from @a pos, searches backward for the first @a n
1751        *  characters in @a s within this string.  If found, returns the index
1752        *  where it begins.  If not found, returns npos.
1753       */
1754       size_type
1755       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
1756
1757       /**
1758        *  @brief  Find last position of a C string.
1759        *  @param s  C string to locate.
1760        *  @param pos  Index of character to start search at (default end).
1761        *  @return  Index of start of  last occurrence.
1762        *
1763        *  Starting from @a pos, searches backward for the value of @a s within
1764        *  this string.  If found, returns the index where it begins.  If not
1765        *  found, returns npos.
1766       */
1767       size_type
1768       rfind(const _CharT* __s, size_type __pos = npos) const
1769       {
1770         __glibcxx_requires_string(__s);
1771         return this->rfind(__s, __pos, traits_type::length(__s));
1772       }
1773
1774       /**
1775        *  @brief  Find last position of a character.
1776        *  @param c  Character to locate.
1777        *  @param pos  Index of character to search back from (default end).
1778        *  @return  Index of last occurrence.
1779        *
1780        *  Starting from @a pos, searches backward for @a c within this string.
1781        *  If found, returns the index where it was found.  If not found,
1782        *  returns npos.
1783       */
1784       size_type
1785       rfind(_CharT __c, size_type __pos = npos) const;
1786
1787       /**
1788        *  @brief  Find position of a character of string.
1789        *  @param str  String containing characters to locate.
1790        *  @param pos  Index of character to search from (default 0).
1791        *  @return  Index of first occurrence.
1792        *
1793        *  Starting from @a pos, searches forward for one of the characters of
1794        *  @a str within this string.  If found, returns the index where it was
1795        *  found.  If not found, returns npos.
1796       */
1797       size_type
1798       find_first_of(const basic_string& __str, size_type __pos = 0) const
1799       { return this->find_first_of(__str.data(), __pos, __str.size()); }
1800
1801       /**
1802        *  @brief  Find position of a character of C substring.
1803        *  @param s  String containing characters to locate.
1804        *  @param pos  Index of character to search from.
1805        *  @param n  Number of characters from s to search for.
1806        *  @return  Index of first occurrence.
1807        *
1808        *  Starting from @a pos, searches forward for one of the first @a n
1809        *  characters of @a s within this string.  If found, returns the index
1810        *  where it was found.  If not found, returns npos.
1811       */
1812       size_type
1813       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
1814
1815       /**
1816        *  @brief  Find position of a character of C string.
1817        *  @param s  String containing characters to locate.
1818        *  @param pos  Index of character to search from (default 0).
1819        *  @return  Index of first occurrence.
1820        *
1821        *  Starting from @a pos, searches forward for one of the characters of
1822        *  @a s within this string.  If found, returns the index where it was
1823        *  found.  If not found, returns npos.
1824       */
1825       size_type
1826       find_first_of(const _CharT* __s, size_type __pos = 0) const
1827       {
1828         __glibcxx_requires_string(__s);
1829         return this->find_first_of(__s, __pos, traits_type::length(__s));
1830       }
1831
1832       /**
1833        *  @brief  Find position of a character.
1834        *  @param c  Character to locate.
1835        *  @param pos  Index of character to search from (default 0).
1836        *  @return  Index of first occurrence.
1837        *
1838        *  Starting from @a pos, searches forward for the character @a c within
1839        *  this string.  If found, returns the index where it was found.  If
1840        *  not found, returns npos.
1841        *
1842        *  Note: equivalent to find(c, pos).
1843       */
1844       size_type
1845       find_first_of(_CharT __c, size_type __pos = 0) const
1846       { return this->find(__c, __pos); }
1847
1848       /**
1849        *  @brief  Find last position of a character of string.
1850        *  @param str  String containing characters to locate.
1851        *  @param pos  Index of character to search back from (default end).
1852        *  @return  Index of last occurrence.
1853        *
1854        *  Starting from @a pos, searches backward for one of the characters of
1855        *  @a str within this string.  If found, returns the index where it was
1856        *  found.  If not found, returns npos.
1857       */
1858       size_type
1859       find_last_of(const basic_string& __str, size_type __pos = npos) const
1860       { return this->find_last_of(__str.data(), __pos, __str.size()); }
1861
1862       /**
1863        *  @brief  Find last position of a character of C substring.
1864        *  @param s  C string containing characters to locate.
1865        *  @param pos  Index of character to search back from.
1866        *  @param n  Number of characters from s to search for.
1867        *  @return  Index of last occurrence.
1868        *
1869        *  Starting from @a pos, searches backward for one of the first @a n
1870        *  characters of @a s within this string.  If found, returns the index
1871        *  where it was found.  If not found, returns npos.
1872       */
1873       size_type
1874       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
1875
1876       /**
1877        *  @brief  Find last position of a character of C string.
1878        *  @param s  C string containing characters to locate.
1879        *  @param pos  Index of character to search back from (default end).
1880        *  @return  Index of last occurrence.
1881        *
1882        *  Starting from @a pos, searches backward for one of the characters of
1883        *  @a s within this string.  If found, returns the index where it was
1884        *  found.  If not found, returns npos.
1885       */
1886       size_type
1887       find_last_of(const _CharT* __s, size_type __pos = npos) const
1888       {
1889         __glibcxx_requires_string(__s);
1890         return this->find_last_of(__s, __pos, traits_type::length(__s));
1891       }
1892
1893       /**
1894        *  @brief  Find last position of a character.
1895        *  @param c  Character to locate.
1896        *  @param pos  Index of character to search back from (default end).
1897        *  @return  Index of last occurrence.
1898        *
1899        *  Starting from @a pos, searches backward for @a c within this string.
1900        *  If found, returns the index where it was found.  If not found,
1901        *  returns npos.
1902        *
1903        *  Note: equivalent to rfind(c, pos).
1904       */
1905       size_type
1906       find_last_of(_CharT __c, size_type __pos = npos) const
1907       { return this->rfind(__c, __pos); }
1908
1909       /**
1910        *  @brief  Find position of a character not in string.
1911        *  @param str  String containing characters to avoid.
1912        *  @param pos  Index of character to search from (default 0).
1913        *  @return  Index of first occurrence.
1914        *
1915        *  Starting from @a pos, searches forward for a character not contained
1916        *  in @a str within this string.  If found, returns the index where it
1917        *  was found.  If not found, returns npos.
1918       */
1919       size_type
1920       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
1921       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
1922
1923       /**
1924        *  @brief  Find position of a character not in C substring.
1925        *  @param s  C string containing characters to avoid.
1926        *  @param pos  Index of character to search from.
1927        *  @param n  Number of characters from s to consider.
1928        *  @return  Index of first occurrence.
1929        *
1930        *  Starting from @a pos, searches forward for a character not contained
1931        *  in the first @a n characters of @a s within this string.  If found,
1932        *  returns the index where it was found.  If not found, returns npos.
1933       */
1934       size_type
1935       find_first_not_of(const _CharT* __s, size_type __pos,
1936                         size_type __n) const;
1937
1938       /**
1939        *  @brief  Find position of a character not in C string.
1940        *  @param s  C string containing characters to avoid.
1941        *  @param pos  Index of character to search from (default 0).
1942        *  @return  Index of first occurrence.
1943        *
1944        *  Starting from @a pos, searches forward for a character not contained
1945        *  in @a s within this string.  If found, returns the index where it
1946        *  was found.  If not found, returns npos.
1947       */
1948       size_type
1949       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
1950       {
1951         __glibcxx_requires_string(__s);
1952         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
1953       }
1954
1955       /**
1956        *  @brief  Find position of a different character.
1957        *  @param c  Character to avoid.
1958        *  @param pos  Index of character to search from (default 0).
1959        *  @return  Index of first occurrence.
1960        *
1961        *  Starting from @a pos, searches forward for a character other than @a c
1962        *  within this string.  If found, returns the index where it was found.
1963        *  If not found, returns npos.
1964       */
1965       size_type
1966       find_first_not_of(_CharT __c, size_type __pos = 0) const;
1967
1968       /**
1969        *  @brief  Find last position of a character not in string.
1970        *  @param str  String containing characters to avoid.
1971        *  @param pos  Index of character to search back from (default end).
1972        *  @return  Index of last occurrence.
1973        *
1974        *  Starting from @a pos, searches backward for a character not
1975        *  contained in @a str within this string.  If found, returns the index
1976        *  where it was found.  If not found, returns npos.
1977       */
1978       size_type
1979       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
1980       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
1981
1982       /**
1983        *  @brief  Find last position of a character not in C substring.
1984        *  @param s  C string containing characters to avoid.
1985        *  @param pos  Index of character to search back from.
1986        *  @param n  Number of characters from s to consider.
1987        *  @return  Index of last occurrence.
1988        *
1989        *  Starting from @a pos, searches backward for a character not
1990        *  contained in the first @a n characters of @a s within this string.
1991        *  If found, returns the index where it was found.  If not found,
1992        *  returns npos.
1993       */
1994       size_type
1995       find_last_not_of(const _CharT* __s, size_type __pos,
1996                        size_type __n) const;
1997       /**
1998        *  @brief  Find last position of a character not in C string.
1999        *  @param s  C string containing characters to avoid.
2000        *  @param pos  Index of character to search back from (default end).
2001        *  @return  Index of last occurrence.
2002        *
2003        *  Starting from @a pos, searches backward for a character not
2004        *  contained in @a s within this string.  If found, returns the index
2005        *  where it was found.  If not found, returns npos.
2006       */
2007       size_type
2008       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2009       {
2010         __glibcxx_requires_string(__s);
2011         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2012       }
2013
2014       /**
2015        *  @brief  Find last position of a different character.
2016        *  @param c  Character to avoid.
2017        *  @param pos  Index of character to search back from (default end).
2018        *  @return  Index of last occurrence.
2019        *
2020        *  Starting from @a pos, searches backward for a character other than
2021        *  @a c within this string.  If found, returns the index where it was
2022        *  found.  If not found, returns npos.
2023       */
2024       size_type
2025       find_last_not_of(_CharT __c, size_type __pos = npos) const;
2026
2027       /**
2028        *  @brief  Get a substring.
2029        *  @param pos  Index of first character (default 0).
2030        *  @param n  Number of characters in substring (default remainder).
2031        *  @return  The new string.
2032        *  @throw  std::out_of_range  If pos > size().
2033        *
2034        *  Construct and return a new string using the @a n characters starting
2035        *  at @a pos.  If the string is too short, use the remainder of the
2036        *  characters.  If @a pos is beyond the end of the string, out_of_range
2037        *  is thrown.
2038       */
2039       basic_string
2040       substr(size_type __pos = 0, size_type __n = npos) const
2041       { return basic_string(*this,
2042                             _M_check(__pos, "basic_string::substr"), __n); }
2043
2044       /**
2045        *  @brief  Compare to a string.
2046        *  @param str  String to compare against.
2047        *  @return  Integer < 0, 0, or > 0.
2048        *
2049        *  Returns an integer < 0 if this string is ordered before @a str, 0 if
2050        *  their values are equivalent, or > 0 if this string is ordered after
2051        *  @a str.  Determines the effective length rlen of the strings to
2052        *  compare as the smallest of size() and str.size().  The function
2053        *  then compares the two strings by calling traits::compare(data(),
2054        *  str.data(),rlen).  If the result of the comparison is nonzero returns
2055        *  it, otherwise the shorter one is ordered first.
2056       */
2057       int
2058       compare(const basic_string& __str) const
2059       {
2060         const size_type __size = this->size();
2061         const size_type __osize = __str.size();
2062         const size_type __len = std::min(__size, __osize);
2063
2064         int __r = traits_type::compare(_M_data(), __str.data(), __len);
2065         if (!__r)
2066           __r = _S_compare(__size, __osize);
2067         return __r;
2068       }
2069
2070       /**
2071        *  @brief  Compare substring to a string.
2072        *  @param pos  Index of first character of substring.
2073        *  @param n  Number of characters in substring.
2074        *  @param str  String to compare against.
2075        *  @return  Integer < 0, 0, or > 0.
2076        *
2077        *  Form the substring of this string from the @a n characters starting
2078        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2079        *  before @a str, 0 if their values are equivalent, or > 0 if the
2080        *  substring is ordered after @a str.  Determines the effective length
2081        *  rlen of the strings to compare as the smallest of the length of the
2082        *  substring and @a str.size().  The function then compares the two
2083        *  strings by calling traits::compare(substring.data(),str.data(),rlen).
2084        *  If the result of the comparison is nonzero returns it, otherwise the
2085        *  shorter one is ordered first.
2086       */
2087       int
2088       compare(size_type __pos, size_type __n, const basic_string& __str) const;
2089
2090       /**
2091        *  @brief  Compare substring to a substring.
2092        *  @param pos1  Index of first character of substring.
2093        *  @param n1  Number of characters in substring.
2094        *  @param str  String to compare against.
2095        *  @param pos2  Index of first character of substring of str.
2096        *  @param n2  Number of characters in substring of str.
2097        *  @return  Integer < 0, 0, or > 0.
2098        *
2099        *  Form the substring of this string from the @a n1 characters starting
2100        *  at @a pos1.  Form the substring of @a str from the @a n2 characters
2101        *  starting at @a pos2.  Returns an integer < 0 if this substring is
2102        *  ordered before the substring of @a str, 0 if their values are
2103        *  equivalent, or > 0 if this substring is ordered after the substring
2104        *  of @a str.  Determines the effective length rlen of the strings
2105        *  to compare as the smallest of the lengths of the substrings.  The
2106        *  function then compares the two strings by calling
2107        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2108        *  If the result of the comparison is nonzero returns it, otherwise the
2109        *  shorter one is ordered first.
2110       */
2111       int
2112       compare(size_type __pos1, size_type __n1, const basic_string& __str,
2113               size_type __pos2, size_type __n2) const;
2114
2115       /**
2116        *  @brief  Compare to a C string.
2117        *  @param s  C string to compare against.
2118        *  @return  Integer < 0, 0, or > 0.
2119        *
2120        *  Returns an integer < 0 if this string is ordered before @a s, 0 if
2121        *  their values are equivalent, or > 0 if this string is ordered after
2122        *  @a s.  Determines the effective length rlen of the strings to
2123        *  compare as the smallest of size() and the length of a string
2124        *  constructed from @a s.  The function then compares the two strings
2125        *  by calling traits::compare(data(),s,rlen).  If the result of the
2126        *  comparison is nonzero returns it, otherwise the shorter one is
2127        *  ordered first.
2128       */
2129       int
2130       compare(const _CharT* __s) const;
2131
2132       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2133       // 5 String::compare specification questionable
2134       /**
2135        *  @brief  Compare substring to a C string.
2136        *  @param pos  Index of first character of substring.
2137        *  @param n1  Number of characters in substring.
2138        *  @param s  C string to compare against.
2139        *  @return  Integer < 0, 0, or > 0.
2140        *
2141        *  Form the substring of this string from the @a n1 characters starting
2142        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2143        *  before @a s, 0 if their values are equivalent, or > 0 if the
2144        *  substring is ordered after @a s.  Determines the effective length
2145        *  rlen of the strings to compare as the smallest of the length of the 
2146        *  substring and the length of a string constructed from @a s.  The
2147        *  function then compares the two string by calling
2148        *  traits::compare(substring.data(),s,rlen).  If the result of the
2149        *  comparison is nonzero returns it, otherwise the shorter one is
2150        *  ordered first.
2151       */
2152       int
2153       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2154
2155       /**
2156        *  @brief  Compare substring against a character array.
2157        *  @param pos1  Index of first character of substring.
2158        *  @param n1  Number of characters in substring.
2159        *  @param s  character array to compare against.
2160        *  @param n2  Number of characters of s.
2161        *  @return  Integer < 0, 0, or > 0.
2162        *
2163        *  Form the substring of this string from the @a n1 characters starting
2164        *  at @a pos1.  Form a string from the first @a n2 characters of @a s.
2165        *  Returns an integer < 0 if this substring is ordered before the string
2166        *  from @a s, 0 if their values are equivalent, or > 0 if this substring
2167        *  is ordered after the string from @a s.   Determines the effective
2168        *  length rlen of the strings to compare as the smallest of the length
2169        *  of the substring and @a n2.  The function then compares the two
2170        *  strings by calling traits::compare(substring.data(),s,rlen).  If the
2171        *  result of the comparison is nonzero returns it, otherwise the shorter
2172        *  one is ordered first.
2173        *
2174        *  NB: s must have at least n2 characters, '\\0' has no special
2175        *  meaning.
2176       */
2177       int
2178       compare(size_type __pos, size_type __n1, const _CharT* __s,
2179               size_type __n2) const;
2180   };
2181
2182   template<typename _CharT, typename _Traits, typename _Alloc>
2183     inline basic_string<_CharT, _Traits, _Alloc>::
2184     basic_string()
2185 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
2186     : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2187 #else
2188     : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()) { }
2189 #endif
2190
2191   // operator+
2192   /**
2193    *  @brief  Concatenate two strings.
2194    *  @param lhs  First string.
2195    *  @param rhs  Last string.
2196    *  @return  New string with value of @a lhs followed by @a rhs.
2197    */
2198   template<typename _CharT, typename _Traits, typename _Alloc>
2199     basic_string<_CharT, _Traits, _Alloc>
2200     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2201               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2202     {
2203       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2204       __str.append(__rhs);
2205       return __str;
2206     }
2207
2208   /**
2209    *  @brief  Concatenate C string and string.
2210    *  @param lhs  First string.
2211    *  @param rhs  Last string.
2212    *  @return  New string with value of @a lhs followed by @a rhs.
2213    */
2214   template<typename _CharT, typename _Traits, typename _Alloc>
2215     basic_string<_CharT,_Traits,_Alloc>
2216     operator+(const _CharT* __lhs,
2217               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2218
2219   /**
2220    *  @brief  Concatenate character and string.
2221    *  @param lhs  First string.
2222    *  @param rhs  Last string.
2223    *  @return  New string with @a lhs followed by @a rhs.
2224    */
2225   template<typename _CharT, typename _Traits, typename _Alloc>
2226     basic_string<_CharT,_Traits,_Alloc>
2227     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2228
2229   /**
2230    *  @brief  Concatenate string and C string.
2231    *  @param lhs  First string.
2232    *  @param rhs  Last string.
2233    *  @return  New string with @a lhs followed by @a rhs.
2234    */
2235   template<typename _CharT, typename _Traits, typename _Alloc>
2236     inline basic_string<_CharT, _Traits, _Alloc>
2237     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2238              const _CharT* __rhs)
2239     {
2240       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2241       __str.append(__rhs);
2242       return __str;
2243     }
2244
2245   /**
2246    *  @brief  Concatenate string and character.
2247    *  @param lhs  First string.
2248    *  @param rhs  Last string.
2249    *  @return  New string with @a lhs followed by @a rhs.
2250    */
2251   template<typename _CharT, typename _Traits, typename _Alloc>
2252     inline basic_string<_CharT, _Traits, _Alloc>
2253     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
2254     {
2255       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
2256       typedef typename __string_type::size_type         __size_type;
2257       __string_type __str(__lhs);
2258       __str.append(__size_type(1), __rhs);
2259       return __str;
2260     }
2261
2262   // operator ==
2263   /**
2264    *  @brief  Test equivalence of two strings.
2265    *  @param lhs  First string.
2266    *  @param rhs  Second string.
2267    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
2268    */
2269   template<typename _CharT, typename _Traits, typename _Alloc>
2270     inline bool
2271     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2272                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2273     { return __lhs.compare(__rhs) == 0; }
2274
2275   template<typename _CharT>
2276     inline
2277     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
2278     operator==(const basic_string<_CharT>& __lhs,
2279                const basic_string<_CharT>& __rhs)
2280     { return (__lhs.size() == __rhs.size()
2281               && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
2282                                                     __lhs.size())); }
2283
2284   /**
2285    *  @brief  Test equivalence of C string and string.
2286    *  @param lhs  C string.
2287    *  @param rhs  String.
2288    *  @return  True if @a rhs.compare(@a lhs) == 0.  False otherwise.
2289    */
2290   template<typename _CharT, typename _Traits, typename _Alloc>
2291     inline bool
2292     operator==(const _CharT* __lhs,
2293                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2294     { return __rhs.compare(__lhs) == 0; }
2295
2296   /**
2297    *  @brief  Test equivalence of string and C string.
2298    *  @param lhs  String.
2299    *  @param rhs  C string.
2300    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
2301    */
2302   template<typename _CharT, typename _Traits, typename _Alloc>
2303     inline bool
2304     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2305                const _CharT* __rhs)
2306     { return __lhs.compare(__rhs) == 0; }
2307
2308   // operator !=
2309   /**
2310    *  @brief  Test difference of two strings.
2311    *  @param lhs  First string.
2312    *  @param rhs  Second string.
2313    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
2314    */
2315   template<typename _CharT, typename _Traits, typename _Alloc>
2316     inline bool
2317     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2318                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2319     { return !(__lhs == __rhs); }
2320
2321   /**
2322    *  @brief  Test difference of C string and string.
2323    *  @param lhs  C string.
2324    *  @param rhs  String.
2325    *  @return  True if @a rhs.compare(@a lhs) != 0.  False otherwise.
2326    */
2327   template<typename _CharT, typename _Traits, typename _Alloc>
2328     inline bool
2329     operator!=(const _CharT* __lhs,
2330                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2331     { return !(__lhs == __rhs); }
2332
2333   /**
2334    *  @brief  Test difference of string and C string.
2335    *  @param lhs  String.
2336    *  @param rhs  C string.
2337    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
2338    */
2339   template<typename _CharT, typename _Traits, typename _Alloc>
2340     inline bool
2341     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2342                const _CharT* __rhs)
2343     { return !(__lhs == __rhs); }
2344
2345   // operator <
2346   /**
2347    *  @brief  Test if string precedes string.
2348    *  @param lhs  First string.
2349    *  @param rhs  Second string.
2350    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2351    */
2352   template<typename _CharT, typename _Traits, typename _Alloc>
2353     inline bool
2354     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2355               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2356     { return __lhs.compare(__rhs) < 0; }
2357
2358   /**
2359    *  @brief  Test if string precedes C string.
2360    *  @param lhs  String.
2361    *  @param rhs  C string.
2362    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2363    */
2364   template<typename _CharT, typename _Traits, typename _Alloc>
2365     inline bool
2366     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2367               const _CharT* __rhs)
2368     { return __lhs.compare(__rhs) < 0; }
2369
2370   /**
2371    *  @brief  Test if C string precedes string.
2372    *  @param lhs  C string.
2373    *  @param rhs  String.
2374    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2375    */
2376   template<typename _CharT, typename _Traits, typename _Alloc>
2377     inline bool
2378     operator<(const _CharT* __lhs,
2379               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2380     { return __rhs.compare(__lhs) > 0; }
2381
2382   // operator >
2383   /**
2384    *  @brief  Test if string follows string.
2385    *  @param lhs  First string.
2386    *  @param rhs  Second string.
2387    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2388    */
2389   template<typename _CharT, typename _Traits, typename _Alloc>
2390     inline bool
2391     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2392               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2393     { return __lhs.compare(__rhs) > 0; }
2394
2395   /**
2396    *  @brief  Test if string follows C string.
2397    *  @param lhs  String.
2398    *  @param rhs  C string.
2399    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2400    */
2401   template<typename _CharT, typename _Traits, typename _Alloc>
2402     inline bool
2403     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2404               const _CharT* __rhs)
2405     { return __lhs.compare(__rhs) > 0; }
2406
2407   /**
2408    *  @brief  Test if C string follows string.
2409    *  @param lhs  C string.
2410    *  @param rhs  String.
2411    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2412    */
2413   template<typename _CharT, typename _Traits, typename _Alloc>
2414     inline bool
2415     operator>(const _CharT* __lhs,
2416               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2417     { return __rhs.compare(__lhs) < 0; }
2418
2419   // operator <=
2420   /**
2421    *  @brief  Test if string doesn't follow string.
2422    *  @param lhs  First string.
2423    *  @param rhs  Second string.
2424    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2425    */
2426   template<typename _CharT, typename _Traits, typename _Alloc>
2427     inline bool
2428     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2429                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2430     { return __lhs.compare(__rhs) <= 0; }
2431
2432   /**
2433    *  @brief  Test if string doesn't follow C string.
2434    *  @param lhs  String.
2435    *  @param rhs  C string.
2436    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2437    */
2438   template<typename _CharT, typename _Traits, typename _Alloc>
2439     inline bool
2440     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2441                const _CharT* __rhs)
2442     { return __lhs.compare(__rhs) <= 0; }
2443
2444   /**
2445    *  @brief  Test if C string doesn't follow string.
2446    *  @param lhs  C string.
2447    *  @param rhs  String.
2448    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2449    */
2450   template<typename _CharT, typename _Traits, typename _Alloc>
2451     inline bool
2452     operator<=(const _CharT* __lhs,
2453                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2454     { return __rhs.compare(__lhs) >= 0; }
2455
2456   // operator >=
2457   /**
2458    *  @brief  Test if string doesn't precede string.
2459    *  @param lhs  First string.
2460    *  @param rhs  Second string.
2461    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2462    */
2463   template<typename _CharT, typename _Traits, typename _Alloc>
2464     inline bool
2465     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2466                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2467     { return __lhs.compare(__rhs) >= 0; }
2468
2469   /**
2470    *  @brief  Test if string doesn't precede C string.
2471    *  @param lhs  String.
2472    *  @param rhs  C string.
2473    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2474    */
2475   template<typename _CharT, typename _Traits, typename _Alloc>
2476     inline bool
2477     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2478                const _CharT* __rhs)
2479     { return __lhs.compare(__rhs) >= 0; }
2480
2481   /**
2482    *  @brief  Test if C string doesn't precede string.
2483    *  @param lhs  C string.
2484    *  @param rhs  String.
2485    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2486    */
2487   template<typename _CharT, typename _Traits, typename _Alloc>
2488     inline bool
2489     operator>=(const _CharT* __lhs,
2490              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2491     { return __rhs.compare(__lhs) <= 0; }
2492
2493   /**
2494    *  @brief  Swap contents of two strings.
2495    *  @param lhs  First string.
2496    *  @param rhs  Second string.
2497    *
2498    *  Exchanges the contents of @a lhs and @a rhs in constant time.
2499    */
2500   template<typename _CharT, typename _Traits, typename _Alloc>
2501     inline void
2502     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
2503          basic_string<_CharT, _Traits, _Alloc>& __rhs)
2504     { __lhs.swap(__rhs); }
2505
2506   /**
2507    *  @brief  Read stream into a string.
2508    *  @param is  Input stream.
2509    *  @param str  Buffer to store into.
2510    *  @return  Reference to the input stream.
2511    *
2512    *  Stores characters from @a is into @a str until whitespace is found, the
2513    *  end of the stream is encountered, or str.max_size() is reached.  If
2514    *  is.width() is non-zero, that is the limit on the number of characters
2515    *  stored into @a str.  Any previous contents of @a str are erased.
2516    */
2517   template<typename _CharT, typename _Traits, typename _Alloc>
2518     basic_istream<_CharT, _Traits>&
2519     operator>>(basic_istream<_CharT, _Traits>& __is,
2520                basic_string<_CharT, _Traits, _Alloc>& __str);
2521
2522   template<>
2523     basic_istream<char>&
2524     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
2525
2526   /**
2527    *  @brief  Write string to a stream.
2528    *  @param os  Output stream.
2529    *  @param str  String to write out.
2530    *  @return  Reference to the output stream.
2531    *
2532    *  Output characters of @a str into os following the same rules as for
2533    *  writing a C string.
2534    */
2535   template<typename _CharT, typename _Traits, typename _Alloc>
2536     inline basic_ostream<_CharT, _Traits>&
2537     operator<<(basic_ostream<_CharT, _Traits>& __os,
2538                const basic_string<_CharT, _Traits, _Alloc>& __str)
2539     {
2540       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2541       // 586. string inserter not a formatted function
2542       return __ostream_insert(__os, __str.data(), __str.size());
2543     }
2544
2545   /**
2546    *  @brief  Read a line from stream into a string.
2547    *  @param is  Input stream.
2548    *  @param str  Buffer to store into.
2549    *  @param delim  Character marking end of line.
2550    *  @return  Reference to the input stream.
2551    *
2552    *  Stores characters from @a is into @a str until @a delim is found, the
2553    *  end of the stream is encountered, or str.max_size() is reached.  If
2554    *  is.width() is non-zero, that is the limit on the number of characters
2555    *  stored into @a str.  Any previous contents of @a str are erased.  If @a
2556    *  delim was encountered, it is extracted but not stored into @a str.
2557    */
2558   template<typename _CharT, typename _Traits, typename _Alloc>
2559     basic_istream<_CharT, _Traits>&
2560     getline(basic_istream<_CharT, _Traits>& __is,
2561             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
2562
2563   /**
2564    *  @brief  Read a line from stream into a string.
2565    *  @param is  Input stream.
2566    *  @param str  Buffer to store into.
2567    *  @return  Reference to the input stream.
2568    *
2569    *  Stores characters from is into @a str until '\n' is found, the end of
2570    *  the stream is encountered, or str.max_size() is reached.  If is.width()
2571    *  is non-zero, that is the limit on the number of characters stored into
2572    *  @a str.  Any previous contents of @a str are erased.  If end of line was
2573    *  encountered, it is extracted but not stored into @a str.
2574    */
2575   template<typename _CharT, typename _Traits, typename _Alloc>
2576     inline basic_istream<_CharT, _Traits>&
2577     getline(basic_istream<_CharT, _Traits>& __is,
2578             basic_string<_CharT, _Traits, _Alloc>& __str)
2579     { return getline(__is, __str, __is.widen('\n')); }
2580
2581   template<>
2582     basic_istream<char>&
2583     getline(basic_istream<char>& __in, basic_string<char>& __str,
2584             char __delim);
2585
2586 #ifdef _GLIBCXX_USE_WCHAR_T
2587   template<>
2588     basic_istream<wchar_t>&
2589     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
2590             wchar_t __delim);
2591 #endif  
2592
2593 _GLIBCXX_END_NAMESPACE
2594
2595 #if (defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99) \
2596      && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF))
2597
2598 #include <ext/string_conversions.h>
2599
2600 _GLIBCXX_BEGIN_NAMESPACE(std)
2601
2602   // 21.4 Numeric Conversions [string.conversions].
2603   inline int
2604   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
2605   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
2606                                         __idx, __base); }
2607
2608   inline long
2609   stol(const string& __str, size_t* __idx = 0, int __base = 10)
2610   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
2611                              __idx, __base); }
2612
2613   inline unsigned long
2614   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
2615   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
2616                              __idx, __base); }
2617
2618   inline long long
2619   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
2620   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
2621                              __idx, __base); }
2622
2623   inline unsigned long long
2624   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
2625   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
2626                              __idx, __base); }
2627
2628   // NB: strtof vs strtod.
2629   inline float
2630   stof(const string& __str, size_t* __idx = 0)
2631   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
2632
2633   inline double
2634   stod(const string& __str, size_t* __idx = 0)
2635   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
2636
2637   inline long double
2638   stold(const string& __str, size_t* __idx = 0)
2639   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
2640
2641   // NB: (v)snprintf vs sprintf.
2642
2643   // DR 1261.
2644   inline string
2645   to_string(int __val)
2646   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
2647                                            "%d", __val); }
2648
2649   inline string
2650   to_string(unsigned __val)
2651   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2652                                            4 * sizeof(unsigned),
2653                                            "%u", __val); }
2654
2655   inline string
2656   to_string(long __val)
2657   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
2658                                            "%ld", __val); }
2659
2660   inline string
2661   to_string(unsigned long __val)
2662   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2663                                            4 * sizeof(unsigned long),
2664                                            "%lu", __val); }
2665
2666   inline string
2667   to_string(long long __val)
2668   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2669                                            4 * sizeof(long long),
2670                                            "%lld", __val); }
2671
2672   inline string
2673   to_string(unsigned long long __val)
2674   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2675                                            4 * sizeof(unsigned long long),
2676                                            "%llu", __val); }
2677
2678   inline string
2679   to_string(float __val)
2680   {
2681     const int __n = 
2682       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2683     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2684                                            "%f", __val);
2685   }
2686
2687   inline string
2688   to_string(double __val)
2689   {
2690     const int __n = 
2691       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2692     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2693                                            "%f", __val);
2694   }
2695
2696   inline string
2697   to_string(long double __val)
2698   {
2699     const int __n = 
2700       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2701     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2702                                            "%Lf", __val);
2703   }
2704
2705 #ifdef _GLIBCXX_USE_WCHAR_T
2706   inline int 
2707   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
2708   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
2709                                         __idx, __base); }
2710
2711   inline long 
2712   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
2713   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
2714                              __idx, __base); }
2715
2716   inline unsigned long
2717   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
2718   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
2719                              __idx, __base); }
2720
2721   inline long long
2722   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
2723   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
2724                              __idx, __base); }
2725
2726   inline unsigned long long
2727   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
2728   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
2729                              __idx, __base); }
2730
2731   // NB: wcstof vs wcstod.
2732   inline float
2733   stof(const wstring& __str, size_t* __idx = 0)
2734   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
2735
2736   inline double
2737   stod(const wstring& __str, size_t* __idx = 0)
2738   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
2739
2740   inline long double
2741   stold(const wstring& __str, size_t* __idx = 0)
2742   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
2743
2744   // DR 1261.
2745   inline wstring
2746   to_wstring(int __val)
2747   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
2748                                             L"%d", __val); }
2749
2750   inline wstring
2751   to_wstring(unsigned __val)
2752   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2753                                             4 * sizeof(unsigned),
2754                                             L"%u", __val); }
2755
2756   inline wstring
2757   to_wstring(long __val)
2758   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
2759                                             L"%ld", __val); }
2760
2761   inline wstring
2762   to_wstring(unsigned long __val)
2763   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2764                                             4 * sizeof(unsigned long),
2765                                             L"%lu", __val); }
2766
2767   inline wstring
2768   to_wstring(long long __val)
2769   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2770                                             4 * sizeof(long long),
2771                                             L"%lld", __val); }
2772
2773   inline wstring
2774   to_wstring(unsigned long long __val)
2775   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2776                                             4 * sizeof(unsigned long long),
2777                                             L"%llu", __val); }
2778
2779   inline wstring
2780   to_wstring(float __val)
2781   {
2782     const int __n =
2783       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2784     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2785                                             L"%f", __val);
2786   }
2787
2788   inline wstring
2789   to_wstring(double __val)
2790   {
2791     const int __n =
2792       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2793     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2794                                             L"%f", __val);
2795   }
2796
2797   inline wstring
2798   to_wstring(long double __val)
2799   {
2800     const int __n =
2801       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2802     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2803                                             L"%Lf", __val);
2804   }
2805 #endif
2806
2807 _GLIBCXX_END_NAMESPACE
2808
2809 #endif
2810
2811 #endif /* _BASIC_STRING_H */