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