OSDN Git Service

b022c3060535e0f745c8b063a3d8c2888eedf49a
[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, 2010
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 @a 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 <em>empty string</em> _Rep object already @a 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       basic_string()
423 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
424       : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
425 #else
426       : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
427 #endif
428
429       /**
430        *  @brief  Construct an empty string using allocator @a a.
431        */
432       explicit
433       basic_string(const _Alloc& __a);
434
435       // NB: per LWG issue 42, semantics different from IS:
436       /**
437        *  @brief  Construct string with copy of value of @a str.
438        *  @param  str  Source string.
439        */
440       basic_string(const basic_string& __str);
441       /**
442        *  @brief  Construct string as copy of a substring.
443        *  @param  str  Source string.
444        *  @param  pos  Index of first character to copy from.
445        *  @param  n  Number of characters to copy (default remainder).
446        */
447       basic_string(const basic_string& __str, size_type __pos,
448                    size_type __n = npos);
449       /**
450        *  @brief  Construct string as copy of a substring.
451        *  @param  str  Source string.
452        *  @param  pos  Index of first character to copy from.
453        *  @param  n  Number of characters to copy.
454        *  @param  a  Allocator to use.
455        */
456       basic_string(const basic_string& __str, size_type __pos,
457                    size_type __n, const _Alloc& __a);
458
459       /**
460        *  @brief  Construct string initialized by a character array.
461        *  @param  s  Source character array.
462        *  @param  n  Number of characters to copy.
463        *  @param  a  Allocator to use (default is default allocator).
464        *
465        *  NB: @a s must have at least @a n characters, &apos;\\0&apos;
466        *  has no special meaning.
467        */
468       basic_string(const _CharT* __s, size_type __n,
469                    const _Alloc& __a = _Alloc());
470       /**
471        *  @brief  Construct string as copy of a C string.
472        *  @param  s  Source C string.
473        *  @param  a  Allocator to use (default is default allocator).
474        */
475       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
476       /**
477        *  @brief  Construct string as multiple characters.
478        *  @param  n  Number of characters.
479        *  @param  c  Character to use.
480        *  @param  a  Allocator to use (default is default allocator).
481        */
482       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
483
484 #ifdef __GXX_EXPERIMENTAL_CXX0X__
485       /**
486        *  @brief  Move construct string.
487        *  @param  str  Source string.
488        *
489        *  The newly-created string contains the exact contents of @a str.
490        *  @a str is a valid, but unspecified string.
491        **/
492       basic_string(basic_string&& __str)
493       : _M_dataplus(__str._M_dataplus)
494       {
495 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING   
496         __str._M_data(_S_empty_rep()._M_refdata());
497 #else
498         __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
499 #endif
500       }
501
502       /**
503        *  @brief  Construct string from an initializer list.
504        *  @param  l  std::initializer_list of characters.
505        *  @param  a  Allocator to use (default is default allocator).
506        */
507       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
508 #endif // __GXX_EXPERIMENTAL_CXX0X__
509
510       /**
511        *  @brief  Construct string as copy of a range.
512        *  @param  beg  Start of range.
513        *  @param  end  End of range.
514        *  @param  a  Allocator to use (default is default allocator).
515        */
516       template<class _InputIterator>
517         basic_string(_InputIterator __beg, _InputIterator __end,
518                      const _Alloc& __a = _Alloc());
519
520       /**
521        *  @brief  Destroy the string instance.
522        */
523       ~basic_string()
524       { _M_rep()->_M_dispose(this->get_allocator()); }
525
526       /**
527        *  @brief  Assign the value of @a str to this string.
528        *  @param  str  Source string.
529        */
530       basic_string&
531       operator=(const basic_string& __str) 
532       { return this->assign(__str); }
533
534       /**
535        *  @brief  Copy contents of @a s into this string.
536        *  @param  s  Source null-terminated string.
537        */
538       basic_string&
539       operator=(const _CharT* __s) 
540       { return this->assign(__s); }
541
542       /**
543        *  @brief  Set value to string of length 1.
544        *  @param  c  Source character.
545        *
546        *  Assigning to a character makes this string length 1 and
547        *  (*this)[0] == @a c.
548        */
549       basic_string&
550       operator=(_CharT __c) 
551       { 
552         this->assign(1, __c); 
553         return *this;
554       }
555
556 #ifdef __GXX_EXPERIMENTAL_CXX0X__
557       /**
558        *  @brief  Move assign the value of @a str to this string.
559        *  @param  str  Source string.
560        *
561        *  The contents of @a str are moved into this string (without copying).
562        *  @a str is a valid, but unspecified string.
563        **/
564       basic_string&
565       operator=(basic_string&& __str)
566       {
567         // NB: DR 1204.
568         this->swap(__str);
569         return *this;
570       }
571
572       /**
573        *  @brief  Set value to string constructed from initializer list.
574        *  @param  l  std::initializer_list.
575        */
576       basic_string&
577       operator=(initializer_list<_CharT> __l)
578       {
579         this->assign(__l.begin(), __l.size());
580         return *this;
581       }
582 #endif // __GXX_EXPERIMENTAL_CXX0X__
583
584       // Iterators:
585       /**
586        *  Returns a read/write iterator that points to the first character in
587        *  the %string.  Unshares the string.
588        */
589       iterator
590       begin()
591       {
592         _M_leak();
593         return iterator(_M_data());
594       }
595
596       /**
597        *  Returns a read-only (constant) iterator that points to the first
598        *  character in the %string.
599        */
600       const_iterator
601       begin() const
602       { return const_iterator(_M_data()); }
603
604       /**
605        *  Returns a read/write iterator that points one past the last
606        *  character in the %string.  Unshares the string.
607        */
608       iterator
609       end()
610       {
611         _M_leak();
612         return iterator(_M_data() + this->size());
613       }
614
615       /**
616        *  Returns a read-only (constant) iterator that points one past the
617        *  last character in the %string.
618        */
619       const_iterator
620       end() const
621       { return const_iterator(_M_data() + this->size()); }
622
623       /**
624        *  Returns a read/write reverse iterator that points to the last
625        *  character in the %string.  Iteration is done in reverse element
626        *  order.  Unshares the string.
627        */
628       reverse_iterator
629       rbegin()
630       { return reverse_iterator(this->end()); }
631
632       /**
633        *  Returns a read-only (constant) reverse iterator that points
634        *  to the last character in the %string.  Iteration is done in
635        *  reverse element order.
636        */
637       const_reverse_iterator
638       rbegin() const
639       { return const_reverse_iterator(this->end()); }
640
641       /**
642        *  Returns a read/write reverse iterator that points to one before the
643        *  first character in the %string.  Iteration is done in reverse
644        *  element order.  Unshares the string.
645        */
646       reverse_iterator
647       rend()
648       { return reverse_iterator(this->begin()); }
649
650       /**
651        *  Returns a read-only (constant) reverse iterator that points
652        *  to one before the first character in the %string.  Iteration
653        *  is done in reverse element order.
654        */
655       const_reverse_iterator
656       rend() const
657       { return const_reverse_iterator(this->begin()); }
658
659 #ifdef __GXX_EXPERIMENTAL_CXX0X__
660       /**
661        *  Returns a read-only (constant) iterator that points to the first
662        *  character in the %string.
663        */
664       const_iterator
665       cbegin() const
666       { return const_iterator(this->_M_data()); }
667
668       /**
669        *  Returns a read-only (constant) iterator that points one past the
670        *  last character in the %string.
671        */
672       const_iterator
673       cend() const
674       { return const_iterator(this->_M_data() + this->size()); }
675
676       /**
677        *  Returns a read-only (constant) reverse iterator that points
678        *  to the last character in the %string.  Iteration is done in
679        *  reverse element order.
680        */
681       const_reverse_iterator
682       crbegin() const
683       { return const_reverse_iterator(this->end()); }
684
685       /**
686        *  Returns a read-only (constant) reverse iterator that points
687        *  to one before the first character in the %string.  Iteration
688        *  is done in reverse element order.
689        */
690       const_reverse_iterator
691       crend() const
692       { return const_reverse_iterator(this->begin()); }
693 #endif
694
695     public:
696       // Capacity:
697       ///  Returns the number of characters in the string, not including any
698       ///  null-termination.
699       size_type
700       size() const
701       { return _M_rep()->_M_length; }
702
703       ///  Returns the number of characters in the string, not including any
704       ///  null-termination.
705       size_type
706       length() const
707       { return _M_rep()->_M_length; }
708
709       ///  Returns the size() of the largest possible %string.
710       size_type
711       max_size() const
712       { return _Rep::_S_max_size; }
713
714       /**
715        *  @brief  Resizes the %string to the specified number of characters.
716        *  @param  n  Number of characters the %string should contain.
717        *  @param  c  Character to fill any new elements.
718        *
719        *  This function will %resize the %string to the specified
720        *  number of characters.  If the number is smaller than the
721        *  %string's current size the %string is truncated, otherwise
722        *  the %string is extended and new elements are set to @a c.
723        */
724       void
725       resize(size_type __n, _CharT __c);
726
727       /**
728        *  @brief  Resizes the %string to the specified number of characters.
729        *  @param  n  Number of characters the %string should contain.
730        *
731        *  This function will resize the %string to the specified length.  If
732        *  the new size is smaller than the %string's current size the %string
733        *  is truncated, otherwise the %string is extended and new characters
734        *  are default-constructed.  For basic types such as char, this means
735        *  setting them to 0.
736        */
737       void
738       resize(size_type __n)
739       { this->resize(__n, _CharT()); }
740
741 #ifdef __GXX_EXPERIMENTAL_CXX0X__
742       ///  A non-binding request to reduce capacity() to size().
743       void
744       shrink_to_fit()
745       {
746         __try
747           { reserve(0); }
748         __catch(...)
749           { }
750       }
751 #endif
752
753       /**
754        *  Returns the total number of characters that the %string can hold
755        *  before needing to allocate more memory.
756        */
757       size_type
758       capacity() const
759       { return _M_rep()->_M_capacity; }
760
761       /**
762        *  @brief  Attempt to preallocate enough memory for specified number of
763        *          characters.
764        *  @param  res_arg  Number of characters required.
765        *  @throw  std::length_error  If @a res_arg exceeds @c max_size().
766        *
767        *  This function attempts to reserve enough memory for the
768        *  %string to hold the specified number of characters.  If the
769        *  number requested is more than max_size(), length_error is
770        *  thrown.
771        *
772        *  The advantage of this function is that if optimal code is a
773        *  necessity and the user can determine the string length that will be
774        *  required, the user can reserve the memory in %advance, and thus
775        *  prevent a possible reallocation of memory and copying of %string
776        *  data.
777        */
778       void
779       reserve(size_type __res_arg = 0);
780
781       /**
782        *  Erases the string, making it empty.
783        */
784       void
785       clear()
786       { _M_mutate(0, this->size(), 0); }
787
788       /**
789        *  Returns true if the %string is empty.  Equivalent to 
790        *  <code>*this == ""</code>.
791        */
792       bool
793       empty() const
794       { return this->size() == 0; }
795
796       // Element access:
797       /**
798        *  @brief  Subscript access to the data contained in the %string.
799        *  @param  pos  The index of the character to access.
800        *  @return  Read-only (constant) reference to the character.
801        *
802        *  This operator allows for easy, array-style, data access.
803        *  Note that data access with this operator is unchecked and
804        *  out_of_range lookups are not defined. (For checked lookups
805        *  see at().)
806        */
807       const_reference
808       operator[] (size_type __pos) const
809       {
810         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
811         return _M_data()[__pos];
812       }
813
814       /**
815        *  @brief  Subscript access to the data contained in the %string.
816        *  @param  pos  The index of the character to access.
817        *  @return  Read/write reference to the character.
818        *
819        *  This operator allows for easy, array-style, data access.
820        *  Note that data access with this operator is unchecked and
821        *  out_of_range lookups are not defined. (For checked lookups
822        *  see at().)  Unshares the string.
823        */
824       reference
825       operator[](size_type __pos)
826       {
827         // allow pos == size() as v3 extension:
828         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
829         // but be strict in pedantic mode:
830         _GLIBCXX_DEBUG_PEDASSERT(__pos < size());
831         _M_leak();
832         return _M_data()[__pos];
833       }
834
835       /**
836        *  @brief  Provides access to the data contained in the %string.
837        *  @param n The index of the character to access.
838        *  @return  Read-only (const) reference to the character.
839        *  @throw  std::out_of_range  If @a n is an invalid index.
840        *
841        *  This function provides for safer data access.  The parameter is
842        *  first checked that it is in the range of the string.  The function
843        *  throws out_of_range if the check fails.
844        */
845       const_reference
846       at(size_type __n) const
847       {
848         if (__n >= this->size())
849           __throw_out_of_range(__N("basic_string::at"));
850         return _M_data()[__n];
851       }
852
853       /**
854        *  @brief  Provides access to the data contained in the %string.
855        *  @param n The index of the character to access.
856        *  @return  Read/write reference to the character.
857        *  @throw  std::out_of_range  If @a n is an invalid index.
858        *
859        *  This function provides for safer data access.  The parameter is
860        *  first checked that it is in the range of the string.  The function
861        *  throws out_of_range if the check fails.  Success results in
862        *  unsharing the string.
863        */
864       reference
865       at(size_type __n)
866       {
867         if (__n >= size())
868           __throw_out_of_range(__N("basic_string::at"));
869         _M_leak();
870         return _M_data()[__n];
871       }
872
873       // Modifiers:
874       /**
875        *  @brief  Append a string to this string.
876        *  @param str  The string to append.
877        *  @return  Reference to this string.
878        */
879       basic_string&
880       operator+=(const basic_string& __str)
881       { return this->append(__str); }
882
883       /**
884        *  @brief  Append a C string.
885        *  @param s  The C string to append.
886        *  @return  Reference to this string.
887        */
888       basic_string&
889       operator+=(const _CharT* __s)
890       { return this->append(__s); }
891
892       /**
893        *  @brief  Append a character.
894        *  @param c  The character to append.
895        *  @return  Reference to this string.
896        */
897       basic_string&
898       operator+=(_CharT __c)
899       { 
900         this->push_back(__c);
901         return *this;
902       }
903
904 #ifdef __GXX_EXPERIMENTAL_CXX0X__
905       /**
906        *  @brief  Append an initializer_list of characters.
907        *  @param l  The initializer_list of characters to be appended.
908        *  @return  Reference to this string.
909        */
910       basic_string&
911       operator+=(initializer_list<_CharT> __l)
912       { return this->append(__l.begin(), __l.size()); }
913 #endif // __GXX_EXPERIMENTAL_CXX0X__
914
915       /**
916        *  @brief  Append a string to this string.
917        *  @param str  The string to append.
918        *  @return  Reference to this string.
919        */
920       basic_string&
921       append(const basic_string& __str);
922
923       /**
924        *  @brief  Append a substring.
925        *  @param str  The string to append.
926        *  @param pos  Index of the first character of str to append.
927        *  @param n  The number of characters to append.
928        *  @return  Reference to this string.
929        *  @throw  std::out_of_range if @a pos is not a valid index.
930        *
931        *  This function appends @a n characters from @a str starting at @a pos
932        *  to this string.  If @a n is is larger than the number of available
933        *  characters in @a str, the remainder of @a str is appended.
934        */
935       basic_string&
936       append(const basic_string& __str, size_type __pos, size_type __n);
937
938       /**
939        *  @brief  Append a C substring.
940        *  @param s  The C string to append.
941        *  @param n  The number of characters to append.
942        *  @return  Reference to this string.
943        */
944       basic_string&
945       append(const _CharT* __s, size_type __n);
946
947       /**
948        *  @brief  Append a C string.
949        *  @param s  The C string to append.
950        *  @return  Reference to this string.
951        */
952       basic_string&
953       append(const _CharT* __s)
954       {
955         __glibcxx_requires_string(__s);
956         return this->append(__s, traits_type::length(__s));
957       }
958
959       /**
960        *  @brief  Append multiple characters.
961        *  @param n  The number of characters to append.
962        *  @param c  The character to use.
963        *  @return  Reference to this string.
964        *
965        *  Appends n copies of c to this string.
966        */
967       basic_string&
968       append(size_type __n, _CharT __c);
969
970 #ifdef __GXX_EXPERIMENTAL_CXX0X__
971       /**
972        *  @brief  Append an initializer_list of characters.
973        *  @param l  The initializer_list of characters to append.
974        *  @return  Reference to this string.
975        */
976       basic_string&
977       append(initializer_list<_CharT> __l)
978       { return this->append(__l.begin(), __l.size()); }
979 #endif // __GXX_EXPERIMENTAL_CXX0X__
980
981       /**
982        *  @brief  Append a range of characters.
983        *  @param first  Iterator referencing the first character to append.
984        *  @param last  Iterator marking the end of the range.
985        *  @return  Reference to this string.
986        *
987        *  Appends characters in the range [first,last) to this string.
988        */
989       template<class _InputIterator>
990         basic_string&
991         append(_InputIterator __first, _InputIterator __last)
992         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
993
994       /**
995        *  @brief  Append a single character.
996        *  @param c  Character to append.
997        */
998       void
999       push_back(_CharT __c)
1000       { 
1001         const size_type __len = 1 + this->size();
1002         if (__len > this->capacity() || _M_rep()->_M_is_shared())
1003           this->reserve(__len);
1004         traits_type::assign(_M_data()[this->size()], __c);
1005         _M_rep()->_M_set_length_and_sharable(__len);
1006       }
1007
1008       /**
1009        *  @brief  Set value to contents of another string.
1010        *  @param  str  Source string to use.
1011        *  @return  Reference to this string.
1012        */
1013       basic_string&
1014       assign(const basic_string& __str);
1015
1016 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1017       /**
1018        *  @brief  Set value to contents of another string.
1019        *  @param  str  Source string to use.
1020        *  @return  Reference to this string.
1021        *
1022        *  This function sets this string to the exact contents of @a str.
1023        *  @a str is a valid, but unspecified string.
1024        */
1025       basic_string&
1026       assign(basic_string&& __str)
1027       {
1028         this->swap(__str);
1029         return *this;
1030       }
1031 #endif // __GXX_EXPERIMENTAL_CXX0X__
1032
1033       /**
1034        *  @brief  Set value to a substring of a string.
1035        *  @param str  The string to use.
1036        *  @param pos  Index of the first character of str.
1037        *  @param n  Number of characters to use.
1038        *  @return  Reference to this string.
1039        *  @throw  std::out_of_range if @a pos is not a valid index.
1040        *
1041        *  This function sets this string to the substring of @a str consisting
1042        *  of @a n characters at @a pos.  If @a n is is larger than the number
1043        *  of available characters in @a str, the remainder of @a str is used.
1044        */
1045       basic_string&
1046       assign(const basic_string& __str, size_type __pos, size_type __n)
1047       { return this->assign(__str._M_data()
1048                             + __str._M_check(__pos, "basic_string::assign"),
1049                             __str._M_limit(__pos, __n)); }
1050
1051       /**
1052        *  @brief  Set value to a C substring.
1053        *  @param s  The C string to use.
1054        *  @param n  Number of characters to use.
1055        *  @return  Reference to this string.
1056        *
1057        *  This function sets the value of this string to the first @a n
1058        *  characters of @a s.  If @a n is is larger than the number of
1059        *  available characters in @a s, the remainder of @a s is used.
1060        */
1061       basic_string&
1062       assign(const _CharT* __s, size_type __n);
1063
1064       /**
1065        *  @brief  Set value to contents of a C string.
1066        *  @param s  The C string to use.
1067        *  @return  Reference to this string.
1068        *
1069        *  This function sets the value of this string to the value of @a s.
1070        *  The data is copied, so there is no dependence on @a s once the
1071        *  function returns.
1072        */
1073       basic_string&
1074       assign(const _CharT* __s)
1075       {
1076         __glibcxx_requires_string(__s);
1077         return this->assign(__s, traits_type::length(__s));
1078       }
1079
1080       /**
1081        *  @brief  Set value to multiple characters.
1082        *  @param n  Length of the resulting string.
1083        *  @param c  The character to use.
1084        *  @return  Reference to this string.
1085        *
1086        *  This function sets the value of this string to @a n copies of
1087        *  character @a c.
1088        */
1089       basic_string&
1090       assign(size_type __n, _CharT __c)
1091       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
1092
1093       /**
1094        *  @brief  Set value to a range of characters.
1095        *  @param first  Iterator referencing the first character to append.
1096        *  @param last  Iterator marking the end of the range.
1097        *  @return  Reference to this string.
1098        *
1099        *  Sets value of string to characters in the range [first,last).
1100       */
1101       template<class _InputIterator>
1102         basic_string&
1103         assign(_InputIterator __first, _InputIterator __last)
1104         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
1105
1106 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1107       /**
1108        *  @brief  Set value to an initializer_list of characters.
1109        *  @param l  The initializer_list of characters to assign.
1110        *  @return  Reference to this string.
1111        */
1112       basic_string&
1113       assign(initializer_list<_CharT> __l)
1114       { return this->assign(__l.begin(), __l.size()); }
1115 #endif // __GXX_EXPERIMENTAL_CXX0X__
1116
1117       /**
1118        *  @brief  Insert multiple characters.
1119        *  @param p  Iterator referencing location in string to insert at.
1120        *  @param n  Number of characters to insert
1121        *  @param c  The character to insert.
1122        *  @throw  std::length_error  If new length exceeds @c max_size().
1123        *
1124        *  Inserts @a n copies of character @a c starting at the position
1125        *  referenced by iterator @a p.  If adding characters causes the length
1126        *  to exceed max_size(), length_error is thrown.  The value of the
1127        *  string doesn't change if an error is thrown.
1128       */
1129       void
1130       insert(iterator __p, size_type __n, _CharT __c)
1131       { this->replace(__p, __p, __n, __c);  }
1132
1133       /**
1134        *  @brief  Insert a range of characters.
1135        *  @param p  Iterator referencing location in string to insert at.
1136        *  @param beg  Start of range.
1137        *  @param end  End of range.
1138        *  @throw  std::length_error  If new length exceeds @c max_size().
1139        *
1140        *  Inserts characters in range [beg,end).  If adding characters causes
1141        *  the length to exceed max_size(), length_error is thrown.  The value
1142        *  of the string doesn't change if an error is thrown.
1143       */
1144       template<class _InputIterator>
1145         void
1146         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
1147         { this->replace(__p, __p, __beg, __end); }
1148
1149 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1150       /**
1151        *  @brief  Insert an initializer_list of characters.
1152        *  @param p  Iterator referencing location in string to insert at.
1153        *  @param l  The initializer_list of characters to insert.
1154        *  @throw  std::length_error  If new length exceeds @c max_size().
1155        */
1156       void
1157       insert(iterator __p, initializer_list<_CharT> __l)
1158       {
1159         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
1160         this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
1161       }
1162 #endif // __GXX_EXPERIMENTAL_CXX0X__
1163
1164       /**
1165        *  @brief  Insert value of a string.
1166        *  @param pos1  Iterator referencing location in string to insert at.
1167        *  @param str  The string to insert.
1168        *  @return  Reference to this string.
1169        *  @throw  std::length_error  If new length exceeds @c max_size().
1170        *
1171        *  Inserts value of @a str starting at @a pos1.  If adding characters
1172        *  causes the length to exceed max_size(), length_error is thrown.  The
1173        *  value of the string doesn't change if an error is thrown.
1174       */
1175       basic_string&
1176       insert(size_type __pos1, const basic_string& __str)
1177       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
1178
1179       /**
1180        *  @brief  Insert a substring.
1181        *  @param pos1  Iterator referencing location in string to insert at.
1182        *  @param str  The string to insert.
1183        *  @param pos2  Start of characters in str to insert.
1184        *  @param n  Number of characters to insert.
1185        *  @return  Reference to this string.
1186        *  @throw  std::length_error  If new length exceeds @c max_size().
1187        *  @throw  std::out_of_range  If @a pos1 > size() or
1188        *  @a pos2 > @a str.size().
1189        *
1190        *  Starting at @a pos1, insert @a n character of @a str beginning with
1191        *  @a pos2.  If adding characters causes the length to exceed
1192        *  max_size(), length_error is thrown.  If @a pos1 is beyond the end of
1193        *  this string or @a pos2 is beyond the end of @a str, out_of_range is
1194        *  thrown.  The value of the string doesn't change if an error is
1195        *  thrown.
1196       */
1197       basic_string&
1198       insert(size_type __pos1, const basic_string& __str,
1199              size_type __pos2, size_type __n)
1200       { return this->insert(__pos1, __str._M_data()
1201                             + __str._M_check(__pos2, "basic_string::insert"),
1202                             __str._M_limit(__pos2, __n)); }
1203
1204       /**
1205        *  @brief  Insert a C substring.
1206        *  @param pos  Iterator referencing location in string to insert at.
1207        *  @param s  The C string to insert.
1208        *  @param n  The number of characters to insert.
1209        *  @return  Reference to this string.
1210        *  @throw  std::length_error  If new length exceeds @c max_size().
1211        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1212        *  string.
1213        *
1214        *  Inserts the first @a n characters of @a s starting at @a pos.  If
1215        *  adding characters causes the length to exceed max_size(),
1216        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
1217        *  thrown.  The value of the string doesn't change if an error is
1218        *  thrown.
1219       */
1220       basic_string&
1221       insert(size_type __pos, const _CharT* __s, size_type __n);
1222
1223       /**
1224        *  @brief  Insert a C string.
1225        *  @param pos  Iterator referencing location in string to insert at.
1226        *  @param s  The C string to insert.
1227        *  @return  Reference to this string.
1228        *  @throw  std::length_error  If new length exceeds @c max_size().
1229        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1230        *  string.
1231        *
1232        *  Inserts the first @a n characters of @a s starting at @a pos.  If
1233        *  adding characters causes the length to exceed max_size(),
1234        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
1235        *  thrown.  The value of the string doesn't change if an error is
1236        *  thrown.
1237       */
1238       basic_string&
1239       insert(size_type __pos, const _CharT* __s)
1240       {
1241         __glibcxx_requires_string(__s);
1242         return this->insert(__pos, __s, traits_type::length(__s));
1243       }
1244
1245       /**
1246        *  @brief  Insert multiple characters.
1247        *  @param pos  Index in string to insert at.
1248        *  @param n  Number of characters to insert
1249        *  @param c  The character to insert.
1250        *  @return  Reference to this string.
1251        *  @throw  std::length_error  If new length exceeds @c max_size().
1252        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1253        *  string.
1254        *
1255        *  Inserts @a n copies of character @a c starting at index @a pos.  If
1256        *  adding characters causes the length to exceed max_size(),
1257        *  length_error is thrown.  If @a pos > length(), out_of_range is
1258        *  thrown.  The value of the string doesn't change if an error is
1259        *  thrown.
1260       */
1261       basic_string&
1262       insert(size_type __pos, size_type __n, _CharT __c)
1263       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
1264                               size_type(0), __n, __c); }
1265
1266       /**
1267        *  @brief  Insert one character.
1268        *  @param p  Iterator referencing position in string to insert at.
1269        *  @param c  The character to insert.
1270        *  @return  Iterator referencing newly inserted char.
1271        *  @throw  std::length_error  If new length exceeds @c max_size().
1272        *
1273        *  Inserts character @a c at position referenced by @a p.  If adding
1274        *  character causes the length to exceed max_size(), length_error is
1275        *  thrown.  If @a p is beyond end of string, out_of_range is thrown.
1276        *  The value of the string doesn't change if an error is thrown.
1277       */
1278       iterator
1279       insert(iterator __p, _CharT __c)
1280       {
1281         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
1282         const size_type __pos = __p - _M_ibegin();
1283         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
1284         _M_rep()->_M_set_leaked();
1285         return iterator(_M_data() + __pos);
1286       }
1287
1288       /**
1289        *  @brief  Remove characters.
1290        *  @param pos  Index of first character to remove (default 0).
1291        *  @param n  Number of characters to remove (default remainder).
1292        *  @return  Reference to this string.
1293        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1294        *  string.
1295        *
1296        *  Removes @a n characters from this string starting at @a pos.  The
1297        *  length of the string is reduced by @a n.  If there are < @a n
1298        *  characters to remove, the remainder of the string is truncated.  If
1299        *  @a p is beyond end of string, out_of_range is thrown.  The value of
1300        *  the string doesn't change if an error is thrown.
1301       */
1302       basic_string&
1303       erase(size_type __pos = 0, size_type __n = npos)
1304       { 
1305         _M_mutate(_M_check(__pos, "basic_string::erase"),
1306                   _M_limit(__pos, __n), size_type(0));
1307         return *this;
1308       }
1309
1310       /**
1311        *  @brief  Remove one character.
1312        *  @param position  Iterator referencing the character to remove.
1313        *  @return  iterator referencing same location after removal.
1314        *
1315        *  Removes the character at @a position from this string. The value
1316        *  of the string doesn't change if an error is thrown.
1317       */
1318       iterator
1319       erase(iterator __position)
1320       {
1321         _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
1322                                  && __position < _M_iend());
1323         const size_type __pos = __position - _M_ibegin();
1324         _M_mutate(__pos, size_type(1), size_type(0));
1325         _M_rep()->_M_set_leaked();
1326         return iterator(_M_data() + __pos);
1327       }
1328
1329       /**
1330        *  @brief  Remove a range of characters.
1331        *  @param first  Iterator referencing the first character to remove.
1332        *  @param last  Iterator referencing the end of the range.
1333        *  @return  Iterator referencing location of first after removal.
1334        *
1335        *  Removes the characters in the range [first,last) from this string.
1336        *  The value of the string doesn't change if an error is thrown.
1337       */
1338       iterator
1339       erase(iterator __first, iterator __last);
1340  
1341       /**
1342        *  @brief  Replace characters with value from another string.
1343        *  @param pos  Index of first character to replace.
1344        *  @param n  Number of characters to be replaced.
1345        *  @param str  String to insert.
1346        *  @return  Reference to this string.
1347        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1348        *  string.
1349        *  @throw  std::length_error  If new length exceeds @c max_size().
1350        *
1351        *  Removes the characters in the range [pos,pos+n) from this string.
1352        *  In place, the value of @a str is inserted.  If @a pos is beyond end
1353        *  of string, out_of_range is thrown.  If the length of the result
1354        *  exceeds max_size(), length_error is thrown.  The value of the string
1355        *  doesn't change if an error is thrown.
1356       */
1357       basic_string&
1358       replace(size_type __pos, size_type __n, const basic_string& __str)
1359       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
1360
1361       /**
1362        *  @brief  Replace characters with value from another string.
1363        *  @param pos1  Index of first character to replace.
1364        *  @param n1  Number of characters to be replaced.
1365        *  @param str  String to insert.
1366        *  @param pos2  Index of first character of str to use.
1367        *  @param n2  Number of characters from str to use.
1368        *  @return  Reference to this string.
1369        *  @throw  std::out_of_range  If @a pos1 > size() or @a pos2 >
1370        *  str.size().
1371        *  @throw  std::length_error  If new length exceeds @c max_size().
1372        *
1373        *  Removes the characters in the range [pos1,pos1 + n) from this
1374        *  string.  In place, the value of @a str is inserted.  If @a pos is
1375        *  beyond end of string, out_of_range is thrown.  If the length of the
1376        *  result exceeds max_size(), length_error is thrown.  The value of the
1377        *  string doesn't change if an error is thrown.
1378       */
1379       basic_string&
1380       replace(size_type __pos1, size_type __n1, const basic_string& __str,
1381               size_type __pos2, size_type __n2)
1382       { return this->replace(__pos1, __n1, __str._M_data()
1383                              + __str._M_check(__pos2, "basic_string::replace"),
1384                              __str._M_limit(__pos2, __n2)); }
1385
1386       /**
1387        *  @brief  Replace characters with value of a C substring.
1388        *  @param pos  Index of first character to replace.
1389        *  @param n1  Number of characters to be replaced.
1390        *  @param s  C string to insert.
1391        *  @param n2  Number of characters from @a s to use.
1392        *  @return  Reference to this string.
1393        *  @throw  std::out_of_range  If @a pos1 > size().
1394        *  @throw  std::length_error  If new length exceeds @c max_size().
1395        *
1396        *  Removes the characters in the range [pos,pos + n1) from this string.
1397        *  In place, the first @a n2 characters of @a s are inserted, or all
1398        *  of @a s if @a n2 is too large.  If @a pos is beyond end of string,
1399        *  out_of_range is thrown.  If the length of result exceeds max_size(),
1400        *  length_error is thrown.  The value of the string doesn't change if
1401        *  an error is thrown.
1402       */
1403       basic_string&
1404       replace(size_type __pos, size_type __n1, const _CharT* __s,
1405               size_type __n2);
1406
1407       /**
1408        *  @brief  Replace characters with value of a C string.
1409        *  @param pos  Index of first character to replace.
1410        *  @param n1  Number of characters to be replaced.
1411        *  @param s  C string to insert.
1412        *  @return  Reference to this string.
1413        *  @throw  std::out_of_range  If @a pos > size().
1414        *  @throw  std::length_error  If new length exceeds @c max_size().
1415        *
1416        *  Removes the characters in the range [pos,pos + n1) from this string.
1417        *  In place, the characters of @a s are inserted.  If @a pos is beyond
1418        *  end of string, out_of_range is thrown.  If the length of result
1419        *  exceeds max_size(), length_error is thrown.  The value of the string
1420        *  doesn't change if an error is thrown.
1421       */
1422       basic_string&
1423       replace(size_type __pos, size_type __n1, const _CharT* __s)
1424       {
1425         __glibcxx_requires_string(__s);
1426         return this->replace(__pos, __n1, __s, traits_type::length(__s));
1427       }
1428
1429       /**
1430        *  @brief  Replace characters with multiple characters.
1431        *  @param pos  Index of first character to replace.
1432        *  @param n1  Number of characters to be replaced.
1433        *  @param n2  Number of characters to insert.
1434        *  @param c  Character to insert.
1435        *  @return  Reference to this string.
1436        *  @throw  std::out_of_range  If @a pos > size().
1437        *  @throw  std::length_error  If new length exceeds @c max_size().
1438        *
1439        *  Removes the characters in the range [pos,pos + n1) from this string.
1440        *  In place, @a n2 copies of @a c are inserted.  If @a pos is beyond
1441        *  end of string, out_of_range is thrown.  If the length of result
1442        *  exceeds max_size(), length_error is thrown.  The value of the string
1443        *  doesn't change if an error is thrown.
1444       */
1445       basic_string&
1446       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
1447       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
1448                               _M_limit(__pos, __n1), __n2, __c); }
1449
1450       /**
1451        *  @brief  Replace range of characters with string.
1452        *  @param i1  Iterator referencing start of range to replace.
1453        *  @param i2  Iterator referencing end of range to replace.
1454        *  @param str  String value to insert.
1455        *  @return  Reference to this string.
1456        *  @throw  std::length_error  If new length exceeds @c max_size().
1457        *
1458        *  Removes the characters in the range [i1,i2).  In place, the value of
1459        *  @a str is inserted.  If the length of result exceeds max_size(),
1460        *  length_error is thrown.  The value of the string doesn't change if
1461        *  an error is thrown.
1462       */
1463       basic_string&
1464       replace(iterator __i1, iterator __i2, const basic_string& __str)
1465       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
1466
1467       /**
1468        *  @brief  Replace range of characters with C substring.
1469        *  @param i1  Iterator referencing start of range to replace.
1470        *  @param i2  Iterator referencing end of range to replace.
1471        *  @param s  C string value to insert.
1472        *  @param n  Number of characters from s to insert.
1473        *  @return  Reference to this string.
1474        *  @throw  std::length_error  If new length exceeds @c max_size().
1475        *
1476        *  Removes the characters in the range [i1,i2).  In place, the first @a
1477        *  n characters of @a s are inserted.  If the length of result exceeds
1478        *  max_size(), length_error is thrown.  The value of the string doesn't
1479        *  change if an error is thrown.
1480       */
1481       basic_string&
1482       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
1483       {
1484         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1485                                  && __i2 <= _M_iend());
1486         return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
1487       }
1488
1489       /**
1490        *  @brief  Replace range of characters with C string.
1491        *  @param i1  Iterator referencing start of range to replace.
1492        *  @param i2  Iterator referencing end of range to replace.
1493        *  @param s  C string value to insert.
1494        *  @return  Reference to this string.
1495        *  @throw  std::length_error  If new length exceeds @c max_size().
1496        *
1497        *  Removes the characters in the range [i1,i2).  In place, the
1498        *  characters of @a s are inserted.  If the length of result exceeds
1499        *  max_size(), length_error is thrown.  The value of the string doesn't
1500        *  change if an error is thrown.
1501       */
1502       basic_string&
1503       replace(iterator __i1, iterator __i2, const _CharT* __s)
1504       {
1505         __glibcxx_requires_string(__s);
1506         return this->replace(__i1, __i2, __s, traits_type::length(__s));
1507       }
1508
1509       /**
1510        *  @brief  Replace range of characters with multiple characters
1511        *  @param i1  Iterator referencing start of range to replace.
1512        *  @param i2  Iterator referencing end of range to replace.
1513        *  @param n  Number of characters to insert.
1514        *  @param c  Character to insert.
1515        *  @return  Reference to this string.
1516        *  @throw  std::length_error  If new length exceeds @c max_size().
1517        *
1518        *  Removes the characters in the range [i1,i2).  In place, @a n copies
1519        *  of @a c are inserted.  If the length of result exceeds max_size(),
1520        *  length_error is thrown.  The value of the string doesn't change if
1521        *  an error is thrown.
1522       */
1523       basic_string&
1524       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
1525       {
1526         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1527                                  && __i2 <= _M_iend());
1528         return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
1529       }
1530
1531       /**
1532        *  @brief  Replace range of characters with range.
1533        *  @param i1  Iterator referencing start of range to replace.
1534        *  @param i2  Iterator referencing end of range to replace.
1535        *  @param k1  Iterator referencing start of range to insert.
1536        *  @param k2  Iterator referencing end of range to insert.
1537        *  @return  Reference to this string.
1538        *  @throw  std::length_error  If new length exceeds @c max_size().
1539        *
1540        *  Removes the characters in the range [i1,i2).  In place, characters
1541        *  in the range [k1,k2) are inserted.  If the length of result exceeds
1542        *  max_size(), length_error is thrown.  The value of the string doesn't
1543        *  change if an error is thrown.
1544       */
1545       template<class _InputIterator>
1546         basic_string&
1547         replace(iterator __i1, iterator __i2,
1548                 _InputIterator __k1, _InputIterator __k2)
1549         {
1550           _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1551                                    && __i2 <= _M_iend());
1552           __glibcxx_requires_valid_range(__k1, __k2);
1553           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1554           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
1555         }
1556
1557       // Specializations for the common case of pointer and iterator:
1558       // useful to avoid the overhead of temporary buffering in _M_replace.
1559       basic_string&
1560       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
1561       {
1562         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1563                                  && __i2 <= _M_iend());
1564         __glibcxx_requires_valid_range(__k1, __k2);
1565         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1566                              __k1, __k2 - __k1);
1567       }
1568
1569       basic_string&
1570       replace(iterator __i1, iterator __i2,
1571               const _CharT* __k1, const _CharT* __k2)
1572       {
1573         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1574                                  && __i2 <= _M_iend());
1575         __glibcxx_requires_valid_range(__k1, __k2);
1576         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1577                              __k1, __k2 - __k1);
1578       }
1579
1580       basic_string&
1581       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
1582       {
1583         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1584                                  && __i2 <= _M_iend());
1585         __glibcxx_requires_valid_range(__k1, __k2);
1586         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1587                              __k1.base(), __k2 - __k1);
1588       }
1589
1590       basic_string&
1591       replace(iterator __i1, iterator __i2,
1592               const_iterator __k1, const_iterator __k2)
1593       {
1594         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
1595                                  && __i2 <= _M_iend());
1596         __glibcxx_requires_valid_range(__k1, __k2);
1597         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
1598                              __k1.base(), __k2 - __k1);
1599       }
1600       
1601 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1602       /**
1603        *  @brief  Replace range of characters with initializer_list.
1604        *  @param i1  Iterator referencing start of range to replace.
1605        *  @param i2  Iterator referencing end of range to replace.
1606        *  @param l  The initializer_list of characters to insert.
1607        *  @return  Reference to this string.
1608        *  @throw  std::length_error  If new length exceeds @c max_size().
1609        *
1610        *  Removes the characters in the range [i1,i2).  In place, characters
1611        *  in the range [k1,k2) are inserted.  If the length of result exceeds
1612        *  max_size(), length_error is thrown.  The value of the string doesn't
1613        *  change if an error is thrown.
1614       */
1615       basic_string& replace(iterator __i1, iterator __i2,
1616                             initializer_list<_CharT> __l)
1617       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
1618 #endif // __GXX_EXPERIMENTAL_CXX0X__
1619
1620     private:
1621       template<class _Integer>
1622         basic_string&
1623         _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
1624                             _Integer __val, __true_type)
1625         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
1626
1627       template<class _InputIterator>
1628         basic_string&
1629         _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1630                             _InputIterator __k2, __false_type);
1631
1632       basic_string&
1633       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1634                      _CharT __c);
1635
1636       basic_string&
1637       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1638                       size_type __n2);
1639
1640       // _S_construct_aux is used to implement the 21.3.1 para 15 which
1641       // requires special behaviour if _InIter is an integral type
1642       template<class _InIterator>
1643         static _CharT*
1644         _S_construct_aux(_InIterator __beg, _InIterator __end,
1645                          const _Alloc& __a, __false_type)
1646         {
1647           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
1648           return _S_construct(__beg, __end, __a, _Tag());
1649         }
1650
1651       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1652       // 438. Ambiguity in the "do the right thing" clause
1653       template<class _Integer>
1654         static _CharT*
1655         _S_construct_aux(_Integer __beg, _Integer __end,
1656                          const _Alloc& __a, __true_type)
1657         { return _S_construct_aux_2(static_cast<size_type>(__beg),
1658                                     __end, __a); }
1659
1660       static _CharT*
1661       _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
1662       { return _S_construct(__req, __c, __a); }
1663
1664       template<class _InIterator>
1665         static _CharT*
1666         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
1667         {
1668           typedef typename std::__is_integer<_InIterator>::__type _Integral;
1669           return _S_construct_aux(__beg, __end, __a, _Integral());
1670         }
1671
1672       // For Input Iterators, used in istreambuf_iterators, etc.
1673       template<class _InIterator>
1674         static _CharT*
1675          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
1676                       input_iterator_tag);
1677
1678       // For forward_iterators up to random_access_iterators, used for
1679       // string::iterator, _CharT*, etc.
1680       template<class _FwdIterator>
1681         static _CharT*
1682         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
1683                      forward_iterator_tag);
1684
1685       static _CharT*
1686       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
1687
1688     public:
1689
1690       /**
1691        *  @brief  Copy substring into C string.
1692        *  @param s  C string to copy value into.
1693        *  @param n  Number of characters to copy.
1694        *  @param pos  Index of first character to copy.
1695        *  @return  Number of characters actually copied
1696        *  @throw  std::out_of_range  If pos > size().
1697        *
1698        *  Copies up to @a n characters starting at @a pos into the C string @a
1699        *  s.  If @a pos is greater than size(), out_of_range is thrown.
1700       */
1701       size_type
1702       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
1703
1704       /**
1705        *  @brief  Swap contents with another string.
1706        *  @param s  String to swap with.
1707        *
1708        *  Exchanges the contents of this string with that of @a s in constant
1709        *  time.
1710       */
1711       void
1712       swap(basic_string& __s);
1713
1714       // String operations:
1715       /**
1716        *  @brief  Return const pointer to null-terminated contents.
1717        *
1718        *  This is a handle to internal data.  Do not modify or dire things may
1719        *  happen.
1720       */
1721       const _CharT*
1722       c_str() const
1723       { return _M_data(); }
1724
1725       /**
1726        *  @brief  Return const pointer to contents.
1727        *
1728        *  This is a handle to internal data.  Do not modify or dire things may
1729        *  happen.
1730       */
1731       const _CharT*
1732       data() const
1733       { return _M_data(); }
1734
1735       /**
1736        *  @brief  Return copy of allocator used to construct this string.
1737       */
1738       allocator_type
1739       get_allocator() const
1740       { return _M_dataplus; }
1741
1742       /**
1743        *  @brief  Find position of a C substring.
1744        *  @param s  C string to locate.
1745        *  @param pos  Index of character to search from.
1746        *  @param n  Number of characters from @a s to search for.
1747        *  @return  Index of start of first occurrence.
1748        *
1749        *  Starting from @a pos, searches forward for the first @a n characters
1750        *  in @a s within this string.  If found, returns the index where it
1751        *  begins.  If not found, returns npos.
1752       */
1753       size_type
1754       find(const _CharT* __s, size_type __pos, size_type __n) const;
1755
1756       /**
1757        *  @brief  Find position of a string.
1758        *  @param str  String to locate.
1759        *  @param pos  Index of character to search from (default 0).
1760        *  @return  Index of start of first occurrence.
1761        *
1762        *  Starting from @a pos, searches forward for value of @a str within
1763        *  this string.  If found, returns the index where it begins.  If not
1764        *  found, returns npos.
1765       */
1766       size_type
1767       find(const basic_string& __str, size_type __pos = 0) const
1768       { return this->find(__str.data(), __pos, __str.size()); }
1769
1770       /**
1771        *  @brief  Find position of a C string.
1772        *  @param s  C string to locate.
1773        *  @param pos  Index of character to search from (default 0).
1774        *  @return  Index of start of first occurrence.
1775        *
1776        *  Starting from @a pos, searches forward for the value of @a s within
1777        *  this string.  If found, returns the index where it begins.  If not
1778        *  found, returns npos.
1779       */
1780       size_type
1781       find(const _CharT* __s, size_type __pos = 0) const
1782       {
1783         __glibcxx_requires_string(__s);
1784         return this->find(__s, __pos, traits_type::length(__s));
1785       }
1786
1787       /**
1788        *  @brief  Find position of a character.
1789        *  @param c  Character 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 @a c within this string.
1794        *  If found, returns the index where it was found.  If not found,
1795        *  returns npos.
1796       */
1797       size_type
1798       find(_CharT __c, size_type __pos = 0) const;
1799
1800       /**
1801        *  @brief  Find last position of a string.
1802        *  @param str  String to locate.
1803        *  @param pos  Index of character to search back from (default end).
1804        *  @return  Index of start of last occurrence.
1805        *
1806        *  Starting from @a pos, searches backward for value of @a str within
1807        *  this string.  If found, returns the index where it begins.  If not
1808        *  found, returns npos.
1809       */
1810       size_type
1811       rfind(const basic_string& __str, size_type __pos = npos) const
1812       { return this->rfind(__str.data(), __pos, __str.size()); }
1813
1814       /**
1815        *  @brief  Find last position of a C substring.
1816        *  @param s  C string to locate.
1817        *  @param pos  Index of character to search back from.
1818        *  @param n  Number of characters from s to search for.
1819        *  @return  Index of start of last occurrence.
1820        *
1821        *  Starting from @a pos, searches backward for the first @a n
1822        *  characters in @a s within this string.  If found, returns the index
1823        *  where it begins.  If not found, returns npos.
1824       */
1825       size_type
1826       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
1827
1828       /**
1829        *  @brief  Find last position of a C string.
1830        *  @param s  C string to locate.
1831        *  @param pos  Index of character to start search at (default end).
1832        *  @return  Index of start of  last occurrence.
1833        *
1834        *  Starting from @a pos, searches backward for the value of @a s within
1835        *  this string.  If found, returns the index where it begins.  If not
1836        *  found, returns npos.
1837       */
1838       size_type
1839       rfind(const _CharT* __s, size_type __pos = npos) const
1840       {
1841         __glibcxx_requires_string(__s);
1842         return this->rfind(__s, __pos, traits_type::length(__s));
1843       }
1844
1845       /**
1846        *  @brief  Find last position of a character.
1847        *  @param c  Character to locate.
1848        *  @param pos  Index of character to search back from (default end).
1849        *  @return  Index of last occurrence.
1850        *
1851        *  Starting from @a pos, searches backward for @a c within this string.
1852        *  If found, returns the index where it was found.  If not found,
1853        *  returns npos.
1854       */
1855       size_type
1856       rfind(_CharT __c, size_type __pos = npos) const;
1857
1858       /**
1859        *  @brief  Find position of a character of string.
1860        *  @param str  String containing characters to locate.
1861        *  @param pos  Index of character to search from (default 0).
1862        *  @return  Index of first occurrence.
1863        *
1864        *  Starting from @a pos, searches forward for one of the characters of
1865        *  @a str within this string.  If found, returns the index where it was
1866        *  found.  If not found, returns npos.
1867       */
1868       size_type
1869       find_first_of(const basic_string& __str, size_type __pos = 0) const
1870       { return this->find_first_of(__str.data(), __pos, __str.size()); }
1871
1872       /**
1873        *  @brief  Find position of a character of C substring.
1874        *  @param s  String containing characters to locate.
1875        *  @param pos  Index of character to search from.
1876        *  @param n  Number of characters from s to search for.
1877        *  @return  Index of first occurrence.
1878        *
1879        *  Starting from @a pos, searches forward for one of the first @a n
1880        *  characters of @a s within this string.  If found, returns the index
1881        *  where it was found.  If not found, returns npos.
1882       */
1883       size_type
1884       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
1885
1886       /**
1887        *  @brief  Find position of a character of C string.
1888        *  @param s  String containing characters to locate.
1889        *  @param pos  Index of character to search from (default 0).
1890        *  @return  Index of first occurrence.
1891        *
1892        *  Starting from @a pos, searches forward for one of the characters of
1893        *  @a s within this string.  If found, returns the index where it was
1894        *  found.  If not found, returns npos.
1895       */
1896       size_type
1897       find_first_of(const _CharT* __s, size_type __pos = 0) const
1898       {
1899         __glibcxx_requires_string(__s);
1900         return this->find_first_of(__s, __pos, traits_type::length(__s));
1901       }
1902
1903       /**
1904        *  @brief  Find position of a character.
1905        *  @param c  Character to locate.
1906        *  @param pos  Index of character to search from (default 0).
1907        *  @return  Index of first occurrence.
1908        *
1909        *  Starting from @a pos, searches forward for the character @a c within
1910        *  this string.  If found, returns the index where it was found.  If
1911        *  not found, returns npos.
1912        *
1913        *  Note: equivalent to find(c, pos).
1914       */
1915       size_type
1916       find_first_of(_CharT __c, size_type __pos = 0) const
1917       { return this->find(__c, __pos); }
1918
1919       /**
1920        *  @brief  Find last position of a character of string.
1921        *  @param str  String containing characters to locate.
1922        *  @param pos  Index of character to search back from (default end).
1923        *  @return  Index of last occurrence.
1924        *
1925        *  Starting from @a pos, searches backward for one of the characters of
1926        *  @a str within this string.  If found, returns the index where it was
1927        *  found.  If not found, returns npos.
1928       */
1929       size_type
1930       find_last_of(const basic_string& __str, size_type __pos = npos) const
1931       { return this->find_last_of(__str.data(), __pos, __str.size()); }
1932
1933       /**
1934        *  @brief  Find last position of a character of C substring.
1935        *  @param s  C string containing characters to locate.
1936        *  @param pos  Index of character to search back from.
1937        *  @param n  Number of characters from s to search for.
1938        *  @return  Index of last occurrence.
1939        *
1940        *  Starting from @a pos, searches backward for one of the first @a n
1941        *  characters of @a s within this string.  If found, returns the index
1942        *  where it was found.  If not found, returns npos.
1943       */
1944       size_type
1945       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
1946
1947       /**
1948        *  @brief  Find last position of a character of C string.
1949        *  @param s  C string containing characters to locate.
1950        *  @param pos  Index of character to search back from (default end).
1951        *  @return  Index of last occurrence.
1952        *
1953        *  Starting from @a pos, searches backward for one of the characters of
1954        *  @a s within this string.  If found, returns the index where it was
1955        *  found.  If not found, returns npos.
1956       */
1957       size_type
1958       find_last_of(const _CharT* __s, size_type __pos = npos) const
1959       {
1960         __glibcxx_requires_string(__s);
1961         return this->find_last_of(__s, __pos, traits_type::length(__s));
1962       }
1963
1964       /**
1965        *  @brief  Find last position of a character.
1966        *  @param c  Character to locate.
1967        *  @param pos  Index of character to search back from (default end).
1968        *  @return  Index of last occurrence.
1969        *
1970        *  Starting from @a pos, searches backward for @a c within this string.
1971        *  If found, returns the index where it was found.  If not found,
1972        *  returns npos.
1973        *
1974        *  Note: equivalent to rfind(c, pos).
1975       */
1976       size_type
1977       find_last_of(_CharT __c, size_type __pos = npos) const
1978       { return this->rfind(__c, __pos); }
1979
1980       /**
1981        *  @brief  Find position of a character not in string.
1982        *  @param str  String containing characters to avoid.
1983        *  @param pos  Index of character to search from (default 0).
1984        *  @return  Index of first occurrence.
1985        *
1986        *  Starting from @a pos, searches forward for a character not contained
1987        *  in @a str within this string.  If found, returns the index where it
1988        *  was found.  If not found, returns npos.
1989       */
1990       size_type
1991       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
1992       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
1993
1994       /**
1995        *  @brief  Find position of a character not in C substring.
1996        *  @param s  C string containing characters to avoid.
1997        *  @param pos  Index of character to search from.
1998        *  @param n  Number of characters from s to consider.
1999        *  @return  Index of first occurrence.
2000        *
2001        *  Starting from @a pos, searches forward for a character not contained
2002        *  in the first @a n characters of @a s within this string.  If found,
2003        *  returns the index where it was found.  If not found, returns npos.
2004       */
2005       size_type
2006       find_first_not_of(const _CharT* __s, size_type __pos,
2007                         size_type __n) const;
2008
2009       /**
2010        *  @brief  Find position of a character not in C string.
2011        *  @param s  C string containing characters to avoid.
2012        *  @param pos  Index of character to search from (default 0).
2013        *  @return  Index of first occurrence.
2014        *
2015        *  Starting from @a pos, searches forward for a character not contained
2016        *  in @a s within this string.  If found, returns the index where it
2017        *  was found.  If not found, returns npos.
2018       */
2019       size_type
2020       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
2021       {
2022         __glibcxx_requires_string(__s);
2023         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
2024       }
2025
2026       /**
2027        *  @brief  Find position of a different character.
2028        *  @param c  Character to avoid.
2029        *  @param pos  Index of character to search from (default 0).
2030        *  @return  Index of first occurrence.
2031        *
2032        *  Starting from @a pos, searches forward for a character other than @a c
2033        *  within this string.  If found, returns the index where it was found.
2034        *  If not found, returns npos.
2035       */
2036       size_type
2037       find_first_not_of(_CharT __c, size_type __pos = 0) const;
2038
2039       /**
2040        *  @brief  Find last position of a character not in string.
2041        *  @param str  String containing characters to avoid.
2042        *  @param pos  Index of character to search back from (default end).
2043        *  @return  Index of last occurrence.
2044        *
2045        *  Starting from @a pos, searches backward for a character not
2046        *  contained in @a str within this string.  If found, returns the index
2047        *  where it was found.  If not found, returns npos.
2048       */
2049       size_type
2050       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
2051       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
2052
2053       /**
2054        *  @brief  Find last position of a character not in C substring.
2055        *  @param s  C string containing characters to avoid.
2056        *  @param pos  Index of character to search back from.
2057        *  @param n  Number of characters from s to consider.
2058        *  @return  Index of last occurrence.
2059        *
2060        *  Starting from @a pos, searches backward for a character not
2061        *  contained in the first @a n characters of @a s within this string.
2062        *  If found, returns the index where it was found.  If not found,
2063        *  returns npos.
2064       */
2065       size_type
2066       find_last_not_of(const _CharT* __s, size_type __pos,
2067                        size_type __n) const;
2068       /**
2069        *  @brief  Find last position of a character not in C string.
2070        *  @param s  C string containing characters to avoid.
2071        *  @param pos  Index of character to search back from (default end).
2072        *  @return  Index of last occurrence.
2073        *
2074        *  Starting from @a pos, searches backward for a character not
2075        *  contained in @a s within this string.  If found, returns the index
2076        *  where it was found.  If not found, returns npos.
2077       */
2078       size_type
2079       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2080       {
2081         __glibcxx_requires_string(__s);
2082         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2083       }
2084
2085       /**
2086        *  @brief  Find last position of a different character.
2087        *  @param c  Character to avoid.
2088        *  @param pos  Index of character to search back from (default end).
2089        *  @return  Index of last occurrence.
2090        *
2091        *  Starting from @a pos, searches backward for a character other than
2092        *  @a c within this string.  If found, returns the index where it was
2093        *  found.  If not found, returns npos.
2094       */
2095       size_type
2096       find_last_not_of(_CharT __c, size_type __pos = npos) const;
2097
2098       /**
2099        *  @brief  Get a substring.
2100        *  @param pos  Index of first character (default 0).
2101        *  @param n  Number of characters in substring (default remainder).
2102        *  @return  The new string.
2103        *  @throw  std::out_of_range  If pos > size().
2104        *
2105        *  Construct and return a new string using the @a n characters starting
2106        *  at @a pos.  If the string is too short, use the remainder of the
2107        *  characters.  If @a pos is beyond the end of the string, out_of_range
2108        *  is thrown.
2109       */
2110       basic_string
2111       substr(size_type __pos = 0, size_type __n = npos) const
2112       { return basic_string(*this,
2113                             _M_check(__pos, "basic_string::substr"), __n); }
2114
2115       /**
2116        *  @brief  Compare to a string.
2117        *  @param str  String to compare against.
2118        *  @return  Integer < 0, 0, or > 0.
2119        *
2120        *  Returns an integer < 0 if this string is ordered before @a str, 0 if
2121        *  their values are equivalent, or > 0 if this string is ordered after
2122        *  @a str.  Determines the effective length rlen of the strings to
2123        *  compare as the smallest of size() and str.size().  The function
2124        *  then compares the two strings by calling traits::compare(data(),
2125        *  str.data(),rlen).  If the result of the comparison is nonzero returns
2126        *  it, otherwise the shorter one is ordered first.
2127       */
2128       int
2129       compare(const basic_string& __str) const
2130       {
2131         const size_type __size = this->size();
2132         const size_type __osize = __str.size();
2133         const size_type __len = std::min(__size, __osize);
2134
2135         int __r = traits_type::compare(_M_data(), __str.data(), __len);
2136         if (!__r)
2137           __r = _S_compare(__size, __osize);
2138         return __r;
2139       }
2140
2141       /**
2142        *  @brief  Compare substring to a string.
2143        *  @param pos  Index of first character of substring.
2144        *  @param n  Number of characters in substring.
2145        *  @param str  String to compare against.
2146        *  @return  Integer < 0, 0, or > 0.
2147        *
2148        *  Form the substring of this string from the @a n characters starting
2149        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2150        *  before @a str, 0 if their values are equivalent, or > 0 if the
2151        *  substring is ordered after @a str.  Determines the effective length
2152        *  rlen of the strings to compare as the smallest of the length of the
2153        *  substring and @a str.size().  The function then compares the two
2154        *  strings by calling traits::compare(substring.data(),str.data(),rlen).
2155        *  If the result of the comparison is nonzero returns it, otherwise the
2156        *  shorter one is ordered first.
2157       */
2158       int
2159       compare(size_type __pos, size_type __n, const basic_string& __str) const;
2160
2161       /**
2162        *  @brief  Compare substring to a substring.
2163        *  @param pos1  Index of first character of substring.
2164        *  @param n1  Number of characters in substring.
2165        *  @param str  String to compare against.
2166        *  @param pos2  Index of first character of substring of str.
2167        *  @param n2  Number of characters in substring of str.
2168        *  @return  Integer < 0, 0, or > 0.
2169        *
2170        *  Form the substring of this string from the @a n1 characters starting
2171        *  at @a pos1.  Form the substring of @a str from the @a n2 characters
2172        *  starting at @a pos2.  Returns an integer < 0 if this substring is
2173        *  ordered before the substring of @a str, 0 if their values are
2174        *  equivalent, or > 0 if this substring is ordered after the substring
2175        *  of @a str.  Determines the effective length rlen of the strings
2176        *  to compare as the smallest of the lengths of the substrings.  The
2177        *  function then compares the two strings by calling
2178        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2179        *  If the result of the comparison is nonzero returns it, otherwise the
2180        *  shorter one is ordered first.
2181       */
2182       int
2183       compare(size_type __pos1, size_type __n1, const basic_string& __str,
2184               size_type __pos2, size_type __n2) const;
2185
2186       /**
2187        *  @brief  Compare to a C string.
2188        *  @param s  C string to compare against.
2189        *  @return  Integer < 0, 0, or > 0.
2190        *
2191        *  Returns an integer < 0 if this string is ordered before @a s, 0 if
2192        *  their values are equivalent, or > 0 if this string is ordered after
2193        *  @a s.  Determines the effective length rlen of the strings to
2194        *  compare as the smallest of size() and the length of a string
2195        *  constructed from @a s.  The function then compares the two strings
2196        *  by calling traits::compare(data(),s,rlen).  If the result of the
2197        *  comparison is nonzero returns it, otherwise the shorter one is
2198        *  ordered first.
2199       */
2200       int
2201       compare(const _CharT* __s) const;
2202
2203       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2204       // 5 String::compare specification questionable
2205       /**
2206        *  @brief  Compare substring to a C string.
2207        *  @param pos  Index of first character of substring.
2208        *  @param n1  Number of characters in substring.
2209        *  @param s  C string to compare against.
2210        *  @return  Integer < 0, 0, or > 0.
2211        *
2212        *  Form the substring of this string from the @a n1 characters starting
2213        *  at @a pos.  Returns an integer < 0 if the substring is ordered
2214        *  before @a s, 0 if their values are equivalent, or > 0 if the
2215        *  substring is ordered after @a s.  Determines the effective length
2216        *  rlen of the strings to compare as the smallest of the length of the 
2217        *  substring and the length of a string constructed from @a s.  The
2218        *  function then compares the two string by calling
2219        *  traits::compare(substring.data(),s,rlen).  If the result of the
2220        *  comparison is nonzero returns it, otherwise the shorter one is
2221        *  ordered first.
2222       */
2223       int
2224       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2225
2226       /**
2227        *  @brief  Compare substring against a character array.
2228        *  @param pos1  Index of first character of substring.
2229        *  @param n1  Number of characters in substring.
2230        *  @param s  character array to compare against.
2231        *  @param n2  Number of characters of s.
2232        *  @return  Integer < 0, 0, or > 0.
2233        *
2234        *  Form the substring of this string from the @a n1 characters starting
2235        *  at @a pos1.  Form a string from the first @a n2 characters of @a s.
2236        *  Returns an integer < 0 if this substring is ordered before the string
2237        *  from @a s, 0 if their values are equivalent, or > 0 if this substring
2238        *  is ordered after the string from @a s.   Determines the effective
2239        *  length rlen of the strings to compare as the smallest of the length
2240        *  of the substring and @a n2.  The function then compares the two
2241        *  strings by calling traits::compare(substring.data(),s,rlen).  If the
2242        *  result of the comparison is nonzero returns it, otherwise the shorter
2243        *  one is ordered first.
2244        *
2245        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
2246        *  no special meaning.
2247       */
2248       int
2249       compare(size_type __pos, size_type __n1, const _CharT* __s,
2250               size_type __n2) const;
2251   };
2252
2253   // operator+
2254   /**
2255    *  @brief  Concatenate two strings.
2256    *  @param lhs  First string.
2257    *  @param rhs  Last string.
2258    *  @return  New string with value of @a lhs followed by @a rhs.
2259    */
2260   template<typename _CharT, typename _Traits, typename _Alloc>
2261     basic_string<_CharT, _Traits, _Alloc>
2262     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2263               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2264     {
2265       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2266       __str.append(__rhs);
2267       return __str;
2268     }
2269
2270   /**
2271    *  @brief  Concatenate C string and string.
2272    *  @param lhs  First string.
2273    *  @param rhs  Last string.
2274    *  @return  New string with value of @a lhs followed by @a rhs.
2275    */
2276   template<typename _CharT, typename _Traits, typename _Alloc>
2277     basic_string<_CharT,_Traits,_Alloc>
2278     operator+(const _CharT* __lhs,
2279               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2280
2281   /**
2282    *  @brief  Concatenate character and string.
2283    *  @param lhs  First string.
2284    *  @param rhs  Last string.
2285    *  @return  New string with @a lhs followed by @a rhs.
2286    */
2287   template<typename _CharT, typename _Traits, typename _Alloc>
2288     basic_string<_CharT,_Traits,_Alloc>
2289     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
2290
2291   /**
2292    *  @brief  Concatenate string and C string.
2293    *  @param lhs  First string.
2294    *  @param rhs  Last string.
2295    *  @return  New string with @a lhs followed by @a rhs.
2296    */
2297   template<typename _CharT, typename _Traits, typename _Alloc>
2298     inline basic_string<_CharT, _Traits, _Alloc>
2299     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2300              const _CharT* __rhs)
2301     {
2302       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
2303       __str.append(__rhs);
2304       return __str;
2305     }
2306
2307   /**
2308    *  @brief  Concatenate string and character.
2309    *  @param lhs  First string.
2310    *  @param rhs  Last string.
2311    *  @return  New string with @a lhs followed by @a rhs.
2312    */
2313   template<typename _CharT, typename _Traits, typename _Alloc>
2314     inline basic_string<_CharT, _Traits, _Alloc>
2315     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
2316     {
2317       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
2318       typedef typename __string_type::size_type         __size_type;
2319       __string_type __str(__lhs);
2320       __str.append(__size_type(1), __rhs);
2321       return __str;
2322     }
2323
2324   // operator ==
2325   /**
2326    *  @brief  Test equivalence of two strings.
2327    *  @param lhs  First string.
2328    *  @param rhs  Second string.
2329    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
2330    */
2331   template<typename _CharT, typename _Traits, typename _Alloc>
2332     inline bool
2333     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2334                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2335     { return __lhs.compare(__rhs) == 0; }
2336
2337   template<typename _CharT>
2338     inline
2339     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
2340     operator==(const basic_string<_CharT>& __lhs,
2341                const basic_string<_CharT>& __rhs)
2342     { return (__lhs.size() == __rhs.size()
2343               && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
2344                                                     __lhs.size())); }
2345
2346   /**
2347    *  @brief  Test equivalence of C string and string.
2348    *  @param lhs  C string.
2349    *  @param rhs  String.
2350    *  @return  True if @a rhs.compare(@a lhs) == 0.  False otherwise.
2351    */
2352   template<typename _CharT, typename _Traits, typename _Alloc>
2353     inline bool
2354     operator==(const _CharT* __lhs,
2355                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2356     { return __rhs.compare(__lhs) == 0; }
2357
2358   /**
2359    *  @brief  Test equivalence of string and C string.
2360    *  @param lhs  String.
2361    *  @param rhs  C string.
2362    *  @return  True if @a lhs.compare(@a rhs) == 0.  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   // operator !=
2371   /**
2372    *  @brief  Test difference of two strings.
2373    *  @param lhs  First string.
2374    *  @param rhs  Second string.
2375    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
2376    */
2377   template<typename _CharT, typename _Traits, typename _Alloc>
2378     inline bool
2379     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2380                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2381     { return !(__lhs == __rhs); }
2382
2383   /**
2384    *  @brief  Test difference of C string and string.
2385    *  @param lhs  C string.
2386    *  @param rhs  String.
2387    *  @return  True if @a rhs.compare(@a lhs) != 0.  False otherwise.
2388    */
2389   template<typename _CharT, typename _Traits, typename _Alloc>
2390     inline bool
2391     operator!=(const _CharT* __lhs,
2392                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2393     { return !(__lhs == __rhs); }
2394
2395   /**
2396    *  @brief  Test difference of string and C string.
2397    *  @param lhs  String.
2398    *  @param rhs  C string.
2399    *  @return  True if @a lhs.compare(@a rhs) != 0.  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 == __rhs); }
2406
2407   // operator <
2408   /**
2409    *  @brief  Test if string precedes string.
2410    *  @param lhs  First string.
2411    *  @param rhs  Second string.
2412    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2413    */
2414   template<typename _CharT, typename _Traits, typename _Alloc>
2415     inline bool
2416     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2417               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2418     { return __lhs.compare(__rhs) < 0; }
2419
2420   /**
2421    *  @brief  Test if string precedes C string.
2422    *  @param lhs  String.
2423    *  @param rhs  C string.
2424    *  @return  True if @a lhs precedes @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 _CharT* __rhs)
2430     { return __lhs.compare(__rhs) < 0; }
2431
2432   /**
2433    *  @brief  Test if C string precedes string.
2434    *  @param lhs  C string.
2435    *  @param rhs  String.
2436    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
2437    */
2438   template<typename _CharT, typename _Traits, typename _Alloc>
2439     inline bool
2440     operator<(const _CharT* __lhs,
2441               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2442     { return __rhs.compare(__lhs) > 0; }
2443
2444   // operator >
2445   /**
2446    *  @brief  Test if string follows string.
2447    *  @param lhs  First string.
2448    *  @param rhs  Second string.
2449    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2450    */
2451   template<typename _CharT, typename _Traits, typename _Alloc>
2452     inline bool
2453     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2454               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2455     { return __lhs.compare(__rhs) > 0; }
2456
2457   /**
2458    *  @brief  Test if string follows C string.
2459    *  @param lhs  String.
2460    *  @param rhs  C string.
2461    *  @return  True if @a lhs follows @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 _CharT* __rhs)
2467     { return __lhs.compare(__rhs) > 0; }
2468
2469   /**
2470    *  @brief  Test if C string follows string.
2471    *  @param lhs  C string.
2472    *  @param rhs  String.
2473    *  @return  True if @a lhs follows @a rhs.  False otherwise.
2474    */
2475   template<typename _CharT, typename _Traits, typename _Alloc>
2476     inline bool
2477     operator>(const _CharT* __lhs,
2478               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2479     { return __rhs.compare(__lhs) < 0; }
2480
2481   // operator <=
2482   /**
2483    *  @brief  Test if string doesn't follow string.
2484    *  @param lhs  First string.
2485    *  @param rhs  Second string.
2486    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2487    */
2488   template<typename _CharT, typename _Traits, typename _Alloc>
2489     inline bool
2490     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2491                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2492     { return __lhs.compare(__rhs) <= 0; }
2493
2494   /**
2495    *  @brief  Test if string doesn't follow C string.
2496    *  @param lhs  String.
2497    *  @param rhs  C string.
2498    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2499    */
2500   template<typename _CharT, typename _Traits, typename _Alloc>
2501     inline bool
2502     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2503                const _CharT* __rhs)
2504     { return __lhs.compare(__rhs) <= 0; }
2505
2506   /**
2507    *  @brief  Test if C string doesn't follow string.
2508    *  @param lhs  C string.
2509    *  @param rhs  String.
2510    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
2511    */
2512   template<typename _CharT, typename _Traits, typename _Alloc>
2513     inline bool
2514     operator<=(const _CharT* __lhs,
2515                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2516     { return __rhs.compare(__lhs) >= 0; }
2517
2518   // operator >=
2519   /**
2520    *  @brief  Test if string doesn't precede string.
2521    *  @param lhs  First string.
2522    *  @param rhs  Second string.
2523    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2524    */
2525   template<typename _CharT, typename _Traits, typename _Alloc>
2526     inline bool
2527     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2528                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2529     { return __lhs.compare(__rhs) >= 0; }
2530
2531   /**
2532    *  @brief  Test if string doesn't precede C string.
2533    *  @param lhs  String.
2534    *  @param rhs  C string.
2535    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2536    */
2537   template<typename _CharT, typename _Traits, typename _Alloc>
2538     inline bool
2539     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
2540                const _CharT* __rhs)
2541     { return __lhs.compare(__rhs) >= 0; }
2542
2543   /**
2544    *  @brief  Test if C string doesn't precede string.
2545    *  @param lhs  C string.
2546    *  @param rhs  String.
2547    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
2548    */
2549   template<typename _CharT, typename _Traits, typename _Alloc>
2550     inline bool
2551     operator>=(const _CharT* __lhs,
2552              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
2553     { return __rhs.compare(__lhs) <= 0; }
2554
2555   /**
2556    *  @brief  Swap contents of two strings.
2557    *  @param lhs  First string.
2558    *  @param rhs  Second string.
2559    *
2560    *  Exchanges the contents of @a lhs and @a rhs in constant time.
2561    */
2562   template<typename _CharT, typename _Traits, typename _Alloc>
2563     inline void
2564     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
2565          basic_string<_CharT, _Traits, _Alloc>& __rhs)
2566     { __lhs.swap(__rhs); }
2567
2568   /**
2569    *  @brief  Read stream into a string.
2570    *  @param is  Input stream.
2571    *  @param str  Buffer to store into.
2572    *  @return  Reference to the input stream.
2573    *
2574    *  Stores characters from @a is into @a str until whitespace is found, the
2575    *  end of the stream is encountered, or str.max_size() is reached.  If
2576    *  is.width() is non-zero, that is the limit on the number of characters
2577    *  stored into @a str.  Any previous contents of @a str are erased.
2578    */
2579   template<typename _CharT, typename _Traits, typename _Alloc>
2580     basic_istream<_CharT, _Traits>&
2581     operator>>(basic_istream<_CharT, _Traits>& __is,
2582                basic_string<_CharT, _Traits, _Alloc>& __str);
2583
2584   template<>
2585     basic_istream<char>&
2586     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
2587
2588   /**
2589    *  @brief  Write string to a stream.
2590    *  @param os  Output stream.
2591    *  @param str  String to write out.
2592    *  @return  Reference to the output stream.
2593    *
2594    *  Output characters of @a str into os following the same rules as for
2595    *  writing a C string.
2596    */
2597   template<typename _CharT, typename _Traits, typename _Alloc>
2598     inline basic_ostream<_CharT, _Traits>&
2599     operator<<(basic_ostream<_CharT, _Traits>& __os,
2600                const basic_string<_CharT, _Traits, _Alloc>& __str)
2601     {
2602       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2603       // 586. string inserter not a formatted function
2604       return __ostream_insert(__os, __str.data(), __str.size());
2605     }
2606
2607   /**
2608    *  @brief  Read a line from stream into a string.
2609    *  @param is  Input stream.
2610    *  @param str  Buffer to store into.
2611    *  @param delim  Character marking end of line.
2612    *  @return  Reference to the input stream.
2613    *
2614    *  Stores characters from @a is into @a str until @a delim is found, the
2615    *  end of the stream is encountered, or str.max_size() is reached.  If
2616    *  is.width() is non-zero, that is the limit on the number of characters
2617    *  stored into @a str.  Any previous contents of @a str are erased.  If @a
2618    *  delim was encountered, it is extracted but not stored into @a str.
2619    */
2620   template<typename _CharT, typename _Traits, typename _Alloc>
2621     basic_istream<_CharT, _Traits>&
2622     getline(basic_istream<_CharT, _Traits>& __is,
2623             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
2624
2625   /**
2626    *  @brief  Read a line from stream into a string.
2627    *  @param is  Input stream.
2628    *  @param str  Buffer to store into.
2629    *  @return  Reference to the input stream.
2630    *
2631    *  Stores characters from is into @a str until &apos;\n&apos; is
2632    *  found, the end of the stream is encountered, or str.max_size()
2633    *  is reached.  If is.width() is non-zero, that is the limit on the
2634    *  number of characters stored into @a str.  Any previous contents
2635    *  of @a str are erased.  If end of line was encountered, it is
2636    *  extracted but not stored into @a str.
2637    */
2638   template<typename _CharT, typename _Traits, typename _Alloc>
2639     inline basic_istream<_CharT, _Traits>&
2640     getline(basic_istream<_CharT, _Traits>& __is,
2641             basic_string<_CharT, _Traits, _Alloc>& __str)
2642     { return getline(__is, __str, __is.widen('\n')); }
2643
2644   template<>
2645     basic_istream<char>&
2646     getline(basic_istream<char>& __in, basic_string<char>& __str,
2647             char __delim);
2648
2649 #ifdef _GLIBCXX_USE_WCHAR_T
2650   template<>
2651     basic_istream<wchar_t>&
2652     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
2653             wchar_t __delim);
2654 #endif  
2655
2656 _GLIBCXX_END_NAMESPACE
2657
2658 #if (defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99) \
2659      && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF))
2660
2661 #include <ext/string_conversions.h>
2662
2663 _GLIBCXX_BEGIN_NAMESPACE(std)
2664
2665   // 21.4 Numeric Conversions [string.conversions].
2666   inline int
2667   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
2668   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
2669                                         __idx, __base); }
2670
2671   inline long
2672   stol(const string& __str, size_t* __idx = 0, int __base = 10)
2673   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
2674                              __idx, __base); }
2675
2676   inline unsigned long
2677   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
2678   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
2679                              __idx, __base); }
2680
2681   inline long long
2682   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
2683   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
2684                              __idx, __base); }
2685
2686   inline unsigned long long
2687   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
2688   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
2689                              __idx, __base); }
2690
2691   // NB: strtof vs strtod.
2692   inline float
2693   stof(const string& __str, size_t* __idx = 0)
2694   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
2695
2696   inline double
2697   stod(const string& __str, size_t* __idx = 0)
2698   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
2699
2700   inline long double
2701   stold(const string& __str, size_t* __idx = 0)
2702   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
2703
2704   // NB: (v)snprintf vs sprintf.
2705
2706   // DR 1261.
2707   inline string
2708   to_string(int __val)
2709   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
2710                                            "%d", __val); }
2711
2712   inline string
2713   to_string(unsigned __val)
2714   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2715                                            4 * sizeof(unsigned),
2716                                            "%u", __val); }
2717
2718   inline string
2719   to_string(long __val)
2720   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
2721                                            "%ld", __val); }
2722
2723   inline string
2724   to_string(unsigned long __val)
2725   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2726                                            4 * sizeof(unsigned long),
2727                                            "%lu", __val); }
2728
2729   inline string
2730   to_string(long long __val)
2731   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2732                                            4 * sizeof(long long),
2733                                            "%lld", __val); }
2734
2735   inline string
2736   to_string(unsigned long long __val)
2737   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
2738                                            4 * sizeof(unsigned long long),
2739                                            "%llu", __val); }
2740
2741   inline string
2742   to_string(float __val)
2743   {
2744     const int __n = 
2745       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2746     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2747                                            "%f", __val);
2748   }
2749
2750   inline string
2751   to_string(double __val)
2752   {
2753     const int __n = 
2754       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2755     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2756                                            "%f", __val);
2757   }
2758
2759   inline string
2760   to_string(long double __val)
2761   {
2762     const int __n = 
2763       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2764     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
2765                                            "%Lf", __val);
2766   }
2767
2768 #ifdef _GLIBCXX_USE_WCHAR_T
2769   inline int 
2770   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
2771   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
2772                                         __idx, __base); }
2773
2774   inline long 
2775   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
2776   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
2777                              __idx, __base); }
2778
2779   inline unsigned long
2780   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
2781   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
2782                              __idx, __base); }
2783
2784   inline long long
2785   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
2786   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
2787                              __idx, __base); }
2788
2789   inline unsigned long long
2790   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
2791   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
2792                              __idx, __base); }
2793
2794   // NB: wcstof vs wcstod.
2795   inline float
2796   stof(const wstring& __str, size_t* __idx = 0)
2797   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
2798
2799   inline double
2800   stod(const wstring& __str, size_t* __idx = 0)
2801   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
2802
2803   inline long double
2804   stold(const wstring& __str, size_t* __idx = 0)
2805   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
2806
2807   // DR 1261.
2808   inline wstring
2809   to_wstring(int __val)
2810   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
2811                                             L"%d", __val); }
2812
2813   inline wstring
2814   to_wstring(unsigned __val)
2815   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2816                                             4 * sizeof(unsigned),
2817                                             L"%u", __val); }
2818
2819   inline wstring
2820   to_wstring(long __val)
2821   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
2822                                             L"%ld", __val); }
2823
2824   inline wstring
2825   to_wstring(unsigned long __val)
2826   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2827                                             4 * sizeof(unsigned long),
2828                                             L"%lu", __val); }
2829
2830   inline wstring
2831   to_wstring(long long __val)
2832   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2833                                             4 * sizeof(long long),
2834                                             L"%lld", __val); }
2835
2836   inline wstring
2837   to_wstring(unsigned long long __val)
2838   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
2839                                             4 * sizeof(unsigned long long),
2840                                             L"%llu", __val); }
2841
2842   inline wstring
2843   to_wstring(float __val)
2844   {
2845     const int __n =
2846       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
2847     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2848                                             L"%f", __val);
2849   }
2850
2851   inline wstring
2852   to_wstring(double __val)
2853   {
2854     const int __n =
2855       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
2856     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2857                                             L"%f", __val);
2858   }
2859
2860   inline wstring
2861   to_wstring(long double __val)
2862   {
2863     const int __n =
2864       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
2865     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
2866                                             L"%Lf", __val);
2867   }
2868 #endif
2869
2870 _GLIBCXX_END_NAMESPACE
2871
2872 #endif /* __GXX_EXPERIMENTAL_CXX0X__ && _GLIBCXX_USE_C99 ... */
2873
2874 #ifdef __GXX_EXPERIMENTAL_CXX0X__
2875
2876 #include <bits/functional_hash.h>
2877
2878 _GLIBCXX_BEGIN_NAMESPACE(std)
2879
2880   // DR 1182.
2881
2882 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
2883   /// std::hash specialization for string.
2884   template<>
2885     struct hash<string>
2886     : public std::unary_function<string, size_t>
2887     {
2888       size_t
2889       operator()(const string& __s) const
2890       { return std::_Fnv_hash::hash(__s.data(), __s.length()); }
2891     };
2892
2893 #ifdef _GLIBCXX_USE_WCHAR_T
2894   /// std::hash specialization for wstring.
2895   template<>
2896     struct hash<wstring>
2897     : public std::unary_function<wstring, size_t>
2898     {
2899       size_t
2900       operator()(const wstring& __s) const
2901       { return std::_Fnv_hash::hash(__s.data(),
2902                                     __s.length() * sizeof(wchar_t)); }
2903     };
2904 #endif
2905 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
2906
2907 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
2908   /// std::hash specialization for u16string.
2909   template<>
2910     struct hash<u16string>
2911     : public std::unary_function<u16string, size_t>
2912     {
2913       size_t
2914       operator()(const u16string& __s) const
2915       { return std::_Fnv_hash::hash(__s.data(),
2916                                     __s.length() * sizeof(char16_t)); }
2917     };
2918
2919   /// std::hash specialization for u32string.
2920   template<>
2921     struct hash<u32string>
2922     : public std::unary_function<u32string, size_t>
2923     {
2924       size_t
2925       operator()(const u32string& __s) const
2926       { return std::_Fnv_hash::hash(__s.data(),
2927                                     __s.length() * sizeof(char32_t)); }
2928     };
2929 #endif
2930
2931 _GLIBCXX_END_NAMESPACE
2932
2933 #endif /* __GXX_EXPERIMENTAL_CXX0X__ */
2934
2935 #endif /* _BASIC_STRING_H */