xref: /openbsd-src/gnu/lib/libstdc++/libstdc++/include/bits/basic_string.h (revision 03a78d155d6fff5698289342b62759a75b20d130)
1*03a78d15Sespie // Components for manipulating sequences of characters -*- C++ -*-
2*03a78d15Sespie 
3*03a78d15Sespie // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
4*03a78d15Sespie // Free Software Foundation, Inc.
5*03a78d15Sespie //
6*03a78d15Sespie // This file is part of the GNU ISO C++ Library.  This library is free
7*03a78d15Sespie // software; you can redistribute it and/or modify it under the
8*03a78d15Sespie // terms of the GNU General Public License as published by the
9*03a78d15Sespie // Free Software Foundation; either version 2, or (at your option)
10*03a78d15Sespie // any later version.
11*03a78d15Sespie 
12*03a78d15Sespie // This library is distributed in the hope that it will be useful,
13*03a78d15Sespie // but WITHOUT ANY WARRANTY; without even the implied warranty of
14*03a78d15Sespie // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15*03a78d15Sespie // GNU General Public License for more details.
16*03a78d15Sespie 
17*03a78d15Sespie // You should have received a copy of the GNU General Public License along
18*03a78d15Sespie // with this library; see the file COPYING.  If not, write to the Free
19*03a78d15Sespie // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
20*03a78d15Sespie // USA.
21*03a78d15Sespie 
22*03a78d15Sespie // As a special exception, you may use this file as part of a free software
23*03a78d15Sespie // library without restriction.  Specifically, if other files instantiate
24*03a78d15Sespie // templates or use macros or inline functions from this file, or you compile
25*03a78d15Sespie // this file and link it with other files to produce an executable, this
26*03a78d15Sespie // file does not by itself cause the resulting executable to be covered by
27*03a78d15Sespie // the GNU General Public License.  This exception does not however
28*03a78d15Sespie // invalidate any other reasons why the executable file might be covered by
29*03a78d15Sespie // the GNU General Public License.
30*03a78d15Sespie 
31*03a78d15Sespie //
32*03a78d15Sespie // ISO C++ 14882: 21 Strings library
33*03a78d15Sespie //
34*03a78d15Sespie 
35*03a78d15Sespie /** @file basic_string.h
36*03a78d15Sespie  *  This is an internal header file, included by other library headers.
37*03a78d15Sespie  *  You should not attempt to use it directly.
38*03a78d15Sespie  */
39*03a78d15Sespie 
40*03a78d15Sespie #ifndef _CPP_BITS_STRING_H
41*03a78d15Sespie #define _CPP_BITS_STRING_H        1
42*03a78d15Sespie 
43*03a78d15Sespie #pragma GCC system_header
44*03a78d15Sespie 
45*03a78d15Sespie #include <bits/atomicity.h>
46*03a78d15Sespie 
47*03a78d15Sespie namespace std
48*03a78d15Sespie {
49*03a78d15Sespie   /**
50*03a78d15Sespie    *  @class basic_string basic_string.h <string>
51*03a78d15Sespie    *  @brief  Managing sequences of characters and character-like objects.
52*03a78d15Sespie    *
53*03a78d15Sespie    *  @ingroup Containers
54*03a78d15Sespie    *  @ingroup Sequences
55*03a78d15Sespie    *
56*03a78d15Sespie    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
57*03a78d15Sespie    *  <a href="tables.html#66">reversible container</a>, and a
58*03a78d15Sespie    *  <a href="tables.html#67">sequence</a>.  Of the
59*03a78d15Sespie    *  <a href="tables.html#68">optional sequence requirements</a>, only
60*03a78d15Sespie    *  @c push_back, @c at, and array access are supported.
61*03a78d15Sespie    *
62*03a78d15Sespie    *  @doctodo
63*03a78d15Sespie    *
64*03a78d15Sespie    *
65*03a78d15Sespie    *  @if maint
66*03a78d15Sespie    *  Documentation?  What's that?
67*03a78d15Sespie    *  Nathan Myers <ncm@cantrip.org>.
68*03a78d15Sespie    *
69*03a78d15Sespie    *  A string looks like this:
70*03a78d15Sespie    *
71*03a78d15Sespie    *  @code
72*03a78d15Sespie    *                                        [_Rep]
73*03a78d15Sespie    *                                        _M_length
74*03a78d15Sespie    *   [basic_string<char_type>]            _M_capacity
75*03a78d15Sespie    *   _M_dataplus                          _M_state
76*03a78d15Sespie    *   _M_p ---------------->               unnamed array of char_type
77*03a78d15Sespie    *  @endcode
78*03a78d15Sespie    *
79*03a78d15Sespie    *  Where the _M_p points to the first character in the string, and
80*03a78d15Sespie    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
81*03a78d15Sespie    *  pointer to the header.
82*03a78d15Sespie    *
83*03a78d15Sespie    *  This approach has the enormous advantage that a string object
84*03a78d15Sespie    *  requires only one allocation.  All the ugliness is confined
85*03a78d15Sespie    *  within a single pair of inline functions, which each compile to
86*03a78d15Sespie    *  a single "add" instruction: _Rep::_M_data(), and
87*03a78d15Sespie    *  string::_M_rep(); and the allocation function which gets a
88*03a78d15Sespie    *  block of raw bytes and with room enough and constructs a _Rep
89*03a78d15Sespie    *  object at the front.
90*03a78d15Sespie    *
91*03a78d15Sespie    *  The reason you want _M_data pointing to the character array and
92*03a78d15Sespie    *  not the _Rep is so that the debugger can see the string
93*03a78d15Sespie    *  contents. (Probably we should add a non-inline member to get
94*03a78d15Sespie    *  the _Rep for the debugger to use, so users can check the actual
95*03a78d15Sespie    *  string length.)
96*03a78d15Sespie    *
97*03a78d15Sespie    *  Note that the _Rep object is a POD so that you can have a
98*03a78d15Sespie    *  static "empty string" _Rep object already "constructed" before
99*03a78d15Sespie    *  static constructors have run.  The reference-count encoding is
100*03a78d15Sespie    *  chosen so that a 0 indicates one reference, so you never try to
101*03a78d15Sespie    *  destroy the empty-string _Rep object.
102*03a78d15Sespie    *
103*03a78d15Sespie    *  All but the last paragraph is considered pretty conventional
104*03a78d15Sespie    *  for a C++ string implementation.
105*03a78d15Sespie    *  @endif
106*03a78d15Sespie   */
107*03a78d15Sespie   // 21.3  Template class basic_string
108*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
109*03a78d15Sespie     class basic_string
110*03a78d15Sespie     {
111*03a78d15Sespie       // Types:
112*03a78d15Sespie     public:
113*03a78d15Sespie       typedef _Traits 					    traits_type;
114*03a78d15Sespie       typedef typename _Traits::char_type 		    value_type;
115*03a78d15Sespie       typedef _Alloc 					    allocator_type;
116*03a78d15Sespie       typedef typename _Alloc::size_type 		    size_type;
117*03a78d15Sespie       typedef typename _Alloc::difference_type 		    difference_type;
118*03a78d15Sespie       typedef typename _Alloc::reference 		    reference;
119*03a78d15Sespie       typedef typename _Alloc::const_reference 		    const_reference;
120*03a78d15Sespie       typedef typename _Alloc::pointer 			    pointer;
121*03a78d15Sespie       typedef typename _Alloc::const_pointer 	   	    const_pointer;
122*03a78d15Sespie       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
123*03a78d15Sespie       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
124*03a78d15Sespie                                                             const_iterator;
125*03a78d15Sespie       typedef std::reverse_iterator<const_iterator> 	const_reverse_iterator;
126*03a78d15Sespie       typedef std::reverse_iterator<iterator> 		    reverse_iterator;
127*03a78d15Sespie 
128*03a78d15Sespie     private:
129*03a78d15Sespie       // _Rep: string representation
130*03a78d15Sespie       //   Invariants:
131*03a78d15Sespie       //   1. String really contains _M_length + 1 characters; last is set
132*03a78d15Sespie       //      to 0 only on call to c_str().  We avoid instantiating
133*03a78d15Sespie       //      _CharT() where the interface does not require it.
134*03a78d15Sespie       //   2. _M_capacity >= _M_length
135*03a78d15Sespie       //      Allocated memory is always _M_capacity + (1 * sizeof(_CharT)).
136*03a78d15Sespie       //   3. _M_references has three states:
137*03a78d15Sespie       //      -1: leaked, one reference, no ref-copies allowed, non-const.
138*03a78d15Sespie       //       0: one reference, non-const.
139*03a78d15Sespie       //     n>0: n + 1 references, operations require a lock, const.
140*03a78d15Sespie       //   4. All fields==0 is an empty string, given the extra storage
141*03a78d15Sespie       //      beyond-the-end for a null terminator; thus, the shared
142*03a78d15Sespie       //      empty string representation needs no constructor.
143*03a78d15Sespie       struct _Rep
144*03a78d15Sespie       {
145*03a78d15Sespie 	// Types:
146*03a78d15Sespie 	typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
147*03a78d15Sespie 
148*03a78d15Sespie 	// (Public) Data members:
149*03a78d15Sespie 
150*03a78d15Sespie 	// The maximum number of individual char_type elements of an
151*03a78d15Sespie 	// individual string is determined by _S_max_size. This is the
152*03a78d15Sespie 	// value that will be returned by max_size().  (Whereas npos
153*03a78d15Sespie 	// is the maximum number of bytes the allocator can allocate.)
154*03a78d15Sespie 	// If one was to divvy up the theoretical largest size string,
155*03a78d15Sespie 	// with a terminating character and m _CharT elements, it'd
156*03a78d15Sespie 	// look like this:
157*03a78d15Sespie 	// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
158*03a78d15Sespie 	// Solving for m:
159*03a78d15Sespie 	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
160*03a78d15Sespie 	// In addition, this implementation quarters this ammount.
161*03a78d15Sespie 	static const size_type 	_S_max_size;
162*03a78d15Sespie 	static const _CharT 	_S_terminal;
163*03a78d15Sespie 
164*03a78d15Sespie 	size_type 		_M_length;
165*03a78d15Sespie 	size_type 		_M_capacity;
166*03a78d15Sespie 	_Atomic_word		_M_references;
167*03a78d15Sespie 
168*03a78d15Sespie         bool
_M_is_leaked_Rep169*03a78d15Sespie 	_M_is_leaked() const
170*03a78d15Sespie         { return _M_references < 0; }
171*03a78d15Sespie 
172*03a78d15Sespie         bool
_M_is_shared_Rep173*03a78d15Sespie 	_M_is_shared() const
174*03a78d15Sespie         { return _M_references > 0; }
175*03a78d15Sespie 
176*03a78d15Sespie         void
_M_set_leaked_Rep177*03a78d15Sespie 	_M_set_leaked()
178*03a78d15Sespie         { _M_references = -1; }
179*03a78d15Sespie 
180*03a78d15Sespie         void
_M_set_sharable_Rep181*03a78d15Sespie 	_M_set_sharable()
182*03a78d15Sespie         { _M_references = 0; }
183*03a78d15Sespie 
184*03a78d15Sespie 	_CharT*
_M_refdata_Rep185*03a78d15Sespie 	_M_refdata() throw()
186*03a78d15Sespie 	{ return reinterpret_cast<_CharT*>(this + 1); }
187*03a78d15Sespie 
188*03a78d15Sespie 	_CharT&
throw_Rep189*03a78d15Sespie 	operator[](size_t __s) throw()
190*03a78d15Sespie 	{ return _M_refdata() [__s]; }
191*03a78d15Sespie 
192*03a78d15Sespie 	_CharT*
_M_grab_Rep193*03a78d15Sespie 	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
194*03a78d15Sespie 	{
195*03a78d15Sespie 	  return (!_M_is_leaked() && __alloc1 == __alloc2)
196*03a78d15Sespie 	          ? _M_refcopy() : _M_clone(__alloc1);
197*03a78d15Sespie 	}
198*03a78d15Sespie 
199*03a78d15Sespie 	// Create & Destroy
200*03a78d15Sespie 	static _Rep*
201*03a78d15Sespie 	_S_create(size_t, const _Alloc&);
202*03a78d15Sespie 
203*03a78d15Sespie 	void
_M_dispose_Rep204*03a78d15Sespie 	_M_dispose(const _Alloc& __a)
205*03a78d15Sespie 	{
206*03a78d15Sespie 	  if (__exchange_and_add(&_M_references, -1) <= 0)
207*03a78d15Sespie 	    _M_destroy(__a);
208*03a78d15Sespie 	}  // XXX MT
209*03a78d15Sespie 
210*03a78d15Sespie 	void
211*03a78d15Sespie 	_M_destroy(const _Alloc&) throw();
212*03a78d15Sespie 
213*03a78d15Sespie 	_CharT*
_M_refcopy_Rep214*03a78d15Sespie 	_M_refcopy() throw()
215*03a78d15Sespie 	{
216*03a78d15Sespie 	  __atomic_add(&_M_references, 1);
217*03a78d15Sespie 	  return _M_refdata();
218*03a78d15Sespie 	}  // XXX MT
219*03a78d15Sespie 
220*03a78d15Sespie 	_CharT*
221*03a78d15Sespie 	_M_clone(const _Alloc&, size_type __res = 0);
222*03a78d15Sespie       };
223*03a78d15Sespie 
224*03a78d15Sespie       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
225*03a78d15Sespie       struct _Alloc_hider : _Alloc
226*03a78d15Sespie       {
_Alloc_hider_Alloc_hider227*03a78d15Sespie 	_Alloc_hider(_CharT* __dat, const _Alloc& __a)
228*03a78d15Sespie 	: _Alloc(__a), _M_p(__dat) { }
229*03a78d15Sespie 
230*03a78d15Sespie 	_CharT* _M_p; // The actual data.
231*03a78d15Sespie       };
232*03a78d15Sespie 
233*03a78d15Sespie     public:
234*03a78d15Sespie       // Data Members (public):
235*03a78d15Sespie       // NB: This is an unsigned type, and thus represents the maximum
236*03a78d15Sespie       // size that the allocator can hold.
237*03a78d15Sespie       static const size_type 	npos = static_cast<size_type>(-1);
238*03a78d15Sespie 
239*03a78d15Sespie     private:
240*03a78d15Sespie       // Data Members (private):
241*03a78d15Sespie       mutable _Alloc_hider 	_M_dataplus;
242*03a78d15Sespie 
243*03a78d15Sespie       // The following storage is init'd to 0 by the linker, resulting
244*03a78d15Sespie       // (carefully) in an empty string with one reference.
245*03a78d15Sespie       static size_type _S_empty_rep_storage[(sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
246*03a78d15Sespie 
247*03a78d15Sespie       _CharT*
_M_data()248*03a78d15Sespie       _M_data() const
249*03a78d15Sespie       { return  _M_dataplus._M_p; }
250*03a78d15Sespie 
251*03a78d15Sespie       _CharT*
_M_data(_CharT * __p)252*03a78d15Sespie       _M_data(_CharT* __p)
253*03a78d15Sespie       { return (_M_dataplus._M_p = __p); }
254*03a78d15Sespie 
255*03a78d15Sespie       _Rep*
_M_rep()256*03a78d15Sespie       _M_rep() const
257*03a78d15Sespie       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
258*03a78d15Sespie 
259*03a78d15Sespie       // For the internal use we have functions similar to `begin'/`end'
260*03a78d15Sespie       // but they do not call _M_leak.
261*03a78d15Sespie       iterator
_M_ibegin()262*03a78d15Sespie       _M_ibegin() const { return iterator(_M_data()); }
263*03a78d15Sespie 
264*03a78d15Sespie       iterator
_M_iend()265*03a78d15Sespie       _M_iend() const { return iterator(_M_data() + this->size()); }
266*03a78d15Sespie 
267*03a78d15Sespie       void
_M_leak()268*03a78d15Sespie       _M_leak()    // for use in begin() & non-const op[]
269*03a78d15Sespie       {
270*03a78d15Sespie 	if (!_M_rep()->_M_is_leaked())
271*03a78d15Sespie 	  _M_leak_hard();
272*03a78d15Sespie       }
273*03a78d15Sespie 
274*03a78d15Sespie       iterator
_M_check(size_type __pos)275*03a78d15Sespie       _M_check(size_type __pos) const
276*03a78d15Sespie       {
277*03a78d15Sespie 	if (__pos > this->size())
278*03a78d15Sespie 	  __throw_out_of_range("basic_string::_M_check");
279*03a78d15Sespie 	return _M_ibegin() + __pos;
280*03a78d15Sespie       }
281*03a78d15Sespie 
282*03a78d15Sespie       // NB: _M_fold doesn't check for a bad __pos1 value.
283*03a78d15Sespie       iterator
_M_fold(size_type __pos,size_type __off)284*03a78d15Sespie       _M_fold(size_type __pos, size_type __off) const
285*03a78d15Sespie       {
286*03a78d15Sespie 	bool __testoff =  __off < this->size() - __pos;
287*03a78d15Sespie 	size_type __newoff = __testoff ? __off : this->size() - __pos;
288*03a78d15Sespie 	return (_M_ibegin() + __pos + __newoff);
289*03a78d15Sespie       }
290*03a78d15Sespie 
291*03a78d15Sespie       // _S_copy_chars is a separate template to permit specialization
292*03a78d15Sespie       // to optimize for the common case of pointers as iterators.
293*03a78d15Sespie       template<class _Iterator>
294*03a78d15Sespie         static void
_S_copy_chars(_CharT * __p,_Iterator __k1,_Iterator __k2)295*03a78d15Sespie         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
296*03a78d15Sespie         {
297*03a78d15Sespie 	  for (; __k1 != __k2; ++__k1, ++__p)
298*03a78d15Sespie 	    traits_type::assign(*__p, *__k1); // These types are off.
299*03a78d15Sespie 	}
300*03a78d15Sespie 
301*03a78d15Sespie       static void
_S_copy_chars(_CharT * __p,iterator __k1,iterator __k2)302*03a78d15Sespie       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
303*03a78d15Sespie       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
304*03a78d15Sespie 
305*03a78d15Sespie       static void
_S_copy_chars(_CharT * __p,const_iterator __k1,const_iterator __k2)306*03a78d15Sespie       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
307*03a78d15Sespie       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
308*03a78d15Sespie 
309*03a78d15Sespie       static void
_S_copy_chars(_CharT * __p,_CharT * __k1,_CharT * __k2)310*03a78d15Sespie       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
311*03a78d15Sespie       { traits_type::copy(__p, __k1, __k2 - __k1); }
312*03a78d15Sespie 
313*03a78d15Sespie       static void
_S_copy_chars(_CharT * __p,const _CharT * __k1,const _CharT * __k2)314*03a78d15Sespie       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
315*03a78d15Sespie       { traits_type::copy(__p, __k1, __k2 - __k1); }
316*03a78d15Sespie 
317*03a78d15Sespie       void
318*03a78d15Sespie       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
319*03a78d15Sespie 
320*03a78d15Sespie       void
321*03a78d15Sespie       _M_leak_hard();
322*03a78d15Sespie 
323*03a78d15Sespie       static _Rep&
_S_empty_rep()324*03a78d15Sespie       _S_empty_rep()
325*03a78d15Sespie       { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
326*03a78d15Sespie 
327*03a78d15Sespie     public:
328*03a78d15Sespie       // Construct/copy/destroy:
329*03a78d15Sespie       // NB: We overload ctors in some cases instead of using default
330*03a78d15Sespie       // arguments, per 17.4.4.4 para. 2 item 2.
331*03a78d15Sespie 
332*03a78d15Sespie       inline
333*03a78d15Sespie       basic_string();
334*03a78d15Sespie 
335*03a78d15Sespie       explicit
336*03a78d15Sespie       basic_string(const _Alloc& __a);
337*03a78d15Sespie 
338*03a78d15Sespie       // NB: per LWG issue 42, semantics different from IS:
339*03a78d15Sespie       basic_string(const basic_string& __str);
340*03a78d15Sespie       basic_string(const basic_string& __str, size_type __pos,
341*03a78d15Sespie 		   size_type __n = npos);
342*03a78d15Sespie       basic_string(const basic_string& __str, size_type __pos,
343*03a78d15Sespie 		   size_type __n, const _Alloc& __a);
344*03a78d15Sespie 
345*03a78d15Sespie       basic_string(const _CharT* __s, size_type __n,
346*03a78d15Sespie 		   const _Alloc& __a = _Alloc());
347*03a78d15Sespie       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
348*03a78d15Sespie       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
349*03a78d15Sespie 
350*03a78d15Sespie       template<class _InputIterator>
351*03a78d15Sespie         basic_string(_InputIterator __beg, _InputIterator __end,
352*03a78d15Sespie 		     const _Alloc& __a = _Alloc());
353*03a78d15Sespie 
~basic_string()354*03a78d15Sespie       ~basic_string()
355*03a78d15Sespie       { _M_rep()->_M_dispose(this->get_allocator()); }
356*03a78d15Sespie 
357*03a78d15Sespie       basic_string&
358*03a78d15Sespie       operator=(const basic_string& __str) { return this->assign(__str); }
359*03a78d15Sespie 
360*03a78d15Sespie       basic_string&
361*03a78d15Sespie       operator=(const _CharT* __s) { return this->assign(__s); }
362*03a78d15Sespie 
363*03a78d15Sespie       basic_string&
364*03a78d15Sespie       operator=(_CharT __c) { return this->assign(1, __c); }
365*03a78d15Sespie 
366*03a78d15Sespie       // Iterators:
367*03a78d15Sespie       iterator
begin()368*03a78d15Sespie       begin()
369*03a78d15Sespie       {
370*03a78d15Sespie 	_M_leak();
371*03a78d15Sespie 	return iterator(_M_data());
372*03a78d15Sespie       }
373*03a78d15Sespie 
374*03a78d15Sespie       const_iterator
begin()375*03a78d15Sespie       begin() const
376*03a78d15Sespie       { return const_iterator(_M_data()); }
377*03a78d15Sespie 
378*03a78d15Sespie       iterator
end()379*03a78d15Sespie       end()
380*03a78d15Sespie       {
381*03a78d15Sespie          _M_leak();
382*03a78d15Sespie 	 return iterator(_M_data() + this->size());
383*03a78d15Sespie       }
384*03a78d15Sespie 
385*03a78d15Sespie       const_iterator
end()386*03a78d15Sespie       end() const
387*03a78d15Sespie       { return const_iterator(_M_data() + this->size()); }
388*03a78d15Sespie 
389*03a78d15Sespie       reverse_iterator
rbegin()390*03a78d15Sespie       rbegin()
391*03a78d15Sespie       { return reverse_iterator(this->end()); }
392*03a78d15Sespie 
393*03a78d15Sespie       const_reverse_iterator
rbegin()394*03a78d15Sespie       rbegin() const
395*03a78d15Sespie       { return const_reverse_iterator(this->end()); }
396*03a78d15Sespie 
397*03a78d15Sespie       reverse_iterator
rend()398*03a78d15Sespie       rend()
399*03a78d15Sespie       { return reverse_iterator(this->begin()); }
400*03a78d15Sespie 
401*03a78d15Sespie       const_reverse_iterator
rend()402*03a78d15Sespie       rend() const
403*03a78d15Sespie       { return const_reverse_iterator(this->begin()); }
404*03a78d15Sespie 
405*03a78d15Sespie     public:
406*03a78d15Sespie       // Capacity:
407*03a78d15Sespie       size_type
size()408*03a78d15Sespie       size() const { return _M_rep()->_M_length; }
409*03a78d15Sespie 
410*03a78d15Sespie       size_type
length()411*03a78d15Sespie       length() const { return _M_rep()->_M_length; }
412*03a78d15Sespie 
413*03a78d15Sespie       size_type
max_size()414*03a78d15Sespie       max_size() const { return _Rep::_S_max_size; }
415*03a78d15Sespie 
416*03a78d15Sespie       void
417*03a78d15Sespie       resize(size_type __n, _CharT __c);
418*03a78d15Sespie 
419*03a78d15Sespie       void
resize(size_type __n)420*03a78d15Sespie       resize(size_type __n) { this->resize(__n, _CharT()); }
421*03a78d15Sespie 
422*03a78d15Sespie       size_type
capacity()423*03a78d15Sespie       capacity() const { return _M_rep()->_M_capacity; }
424*03a78d15Sespie 
425*03a78d15Sespie       void
426*03a78d15Sespie       reserve(size_type __res_arg = 0);
427*03a78d15Sespie 
428*03a78d15Sespie       void
clear()429*03a78d15Sespie       clear() { _M_mutate(0, this->size(), 0); }
430*03a78d15Sespie 
431*03a78d15Sespie       bool
empty()432*03a78d15Sespie       empty() const { return this->size() == 0; }
433*03a78d15Sespie 
434*03a78d15Sespie       // Element access:
435*03a78d15Sespie       const_reference
436*03a78d15Sespie       operator[] (size_type __pos) const
437*03a78d15Sespie       { return _M_data()[__pos]; }
438*03a78d15Sespie 
439*03a78d15Sespie       reference
440*03a78d15Sespie       operator[](size_type __pos)
441*03a78d15Sespie       {
442*03a78d15Sespie 	_M_leak();
443*03a78d15Sespie 	return _M_data()[__pos];
444*03a78d15Sespie       }
445*03a78d15Sespie 
446*03a78d15Sespie       const_reference
at(size_type __n)447*03a78d15Sespie       at(size_type __n) const
448*03a78d15Sespie       {
449*03a78d15Sespie 	if (__n >= this->size())
450*03a78d15Sespie 	  __throw_out_of_range("basic_string::at");
451*03a78d15Sespie 	return _M_data()[__n];
452*03a78d15Sespie       }
453*03a78d15Sespie 
454*03a78d15Sespie       reference
at(size_type __n)455*03a78d15Sespie       at(size_type __n)
456*03a78d15Sespie       {
457*03a78d15Sespie 	if (__n >= size())
458*03a78d15Sespie 	  __throw_out_of_range("basic_string::at");
459*03a78d15Sespie 	_M_leak();
460*03a78d15Sespie 	return _M_data()[__n];
461*03a78d15Sespie       }
462*03a78d15Sespie 
463*03a78d15Sespie       // Modifiers:
464*03a78d15Sespie       basic_string&
465*03a78d15Sespie       operator+=(const basic_string& __str) { return this->append(__str); }
466*03a78d15Sespie 
467*03a78d15Sespie       basic_string&
468*03a78d15Sespie       operator+=(const _CharT* __s) { return this->append(__s); }
469*03a78d15Sespie 
470*03a78d15Sespie       basic_string&
471*03a78d15Sespie       operator+=(_CharT __c) { return this->append(size_type(1), __c); }
472*03a78d15Sespie 
473*03a78d15Sespie       basic_string&
474*03a78d15Sespie       append(const basic_string& __str);
475*03a78d15Sespie 
476*03a78d15Sespie       basic_string&
477*03a78d15Sespie       append(const basic_string& __str, size_type __pos, size_type __n);
478*03a78d15Sespie 
479*03a78d15Sespie       basic_string&
480*03a78d15Sespie       append(const _CharT* __s, size_type __n);
481*03a78d15Sespie 
482*03a78d15Sespie       basic_string&
append(const _CharT * __s)483*03a78d15Sespie       append(const _CharT* __s)
484*03a78d15Sespie       { return this->append(__s, traits_type::length(__s)); }
485*03a78d15Sespie 
486*03a78d15Sespie       basic_string&
487*03a78d15Sespie       append(size_type __n, _CharT __c);
488*03a78d15Sespie 
489*03a78d15Sespie       template<class _InputIterator>
490*03a78d15Sespie         basic_string&
append(_InputIterator __first,_InputIterator __last)491*03a78d15Sespie         append(_InputIterator __first, _InputIterator __last)
492*03a78d15Sespie         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
493*03a78d15Sespie 
494*03a78d15Sespie       void
push_back(_CharT __c)495*03a78d15Sespie       push_back(_CharT __c)
496*03a78d15Sespie       { this->replace(_M_iend(), _M_iend(), 1, __c); }
497*03a78d15Sespie 
498*03a78d15Sespie       basic_string&
499*03a78d15Sespie       assign(const basic_string& __str);
500*03a78d15Sespie 
501*03a78d15Sespie       basic_string&
502*03a78d15Sespie       assign(const basic_string& __str, size_type __pos, size_type __n);
503*03a78d15Sespie 
504*03a78d15Sespie       basic_string&
505*03a78d15Sespie       assign(const _CharT* __s, size_type __n);
506*03a78d15Sespie 
507*03a78d15Sespie       basic_string&
assign(const _CharT * __s)508*03a78d15Sespie       assign(const _CharT* __s)
509*03a78d15Sespie       { return this->assign(__s, traits_type::length(__s)); }
510*03a78d15Sespie 
511*03a78d15Sespie       basic_string&
assign(size_type __n,_CharT __c)512*03a78d15Sespie       assign(size_type __n, _CharT __c)
513*03a78d15Sespie       { return this->replace(_M_ibegin(), _M_iend(), __n, __c); }
514*03a78d15Sespie 
515*03a78d15Sespie       template<class _InputIterator>
516*03a78d15Sespie         basic_string&
assign(_InputIterator __first,_InputIterator __last)517*03a78d15Sespie         assign(_InputIterator __first, _InputIterator __last)
518*03a78d15Sespie         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
519*03a78d15Sespie 
520*03a78d15Sespie       void
insert(iterator __p,size_type __n,_CharT __c)521*03a78d15Sespie       insert(iterator __p, size_type __n, _CharT __c)
522*03a78d15Sespie       {	this->replace(__p, __p, __n, __c);  }
523*03a78d15Sespie 
524*03a78d15Sespie       template<class _InputIterator>
insert(iterator __p,_InputIterator __beg,_InputIterator __end)525*03a78d15Sespie         void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
526*03a78d15Sespie         { this->replace(__p, __p, __beg, __end); }
527*03a78d15Sespie 
528*03a78d15Sespie       basic_string&
insert(size_type __pos1,const basic_string & __str)529*03a78d15Sespie       insert(size_type __pos1, const basic_string& __str)
530*03a78d15Sespie       { return this->insert(__pos1, __str, 0, __str.size()); }
531*03a78d15Sespie 
532*03a78d15Sespie       basic_string&
533*03a78d15Sespie       insert(size_type __pos1, const basic_string& __str,
534*03a78d15Sespie 	     size_type __pos2, size_type __n);
535*03a78d15Sespie 
536*03a78d15Sespie       basic_string&
537*03a78d15Sespie       insert(size_type __pos, const _CharT* __s, size_type __n);
538*03a78d15Sespie 
539*03a78d15Sespie       basic_string&
insert(size_type __pos,const _CharT * __s)540*03a78d15Sespie       insert(size_type __pos, const _CharT* __s)
541*03a78d15Sespie       { return this->insert(__pos, __s, traits_type::length(__s)); }
542*03a78d15Sespie 
543*03a78d15Sespie       basic_string&
insert(size_type __pos,size_type __n,_CharT __c)544*03a78d15Sespie       insert(size_type __pos, size_type __n, _CharT __c)
545*03a78d15Sespie       {
546*03a78d15Sespie 	this->insert(_M_check(__pos), __n, __c);
547*03a78d15Sespie 	return *this;
548*03a78d15Sespie       }
549*03a78d15Sespie 
550*03a78d15Sespie       iterator
551*03a78d15Sespie       insert(iterator __p, _CharT __c = _CharT())
552*03a78d15Sespie       {
553*03a78d15Sespie 	size_type __pos = __p - _M_ibegin();
554*03a78d15Sespie 	this->insert(_M_check(__pos), size_type(1), __c);
555*03a78d15Sespie 	_M_rep()->_M_set_leaked();
556*03a78d15Sespie  	return this->_M_ibegin() + __pos;
557*03a78d15Sespie       }
558*03a78d15Sespie 
559*03a78d15Sespie       basic_string&
560*03a78d15Sespie       erase(size_type __pos = 0, size_type __n = npos)
561*03a78d15Sespie       {
562*03a78d15Sespie 	return this->replace(_M_check(__pos), _M_fold(__pos, __n),
563*03a78d15Sespie 			     _M_data(), _M_data());
564*03a78d15Sespie       }
565*03a78d15Sespie 
566*03a78d15Sespie       iterator
erase(iterator __position)567*03a78d15Sespie       erase(iterator __position)
568*03a78d15Sespie       {
569*03a78d15Sespie 	size_type __i = __position - _M_ibegin();
570*03a78d15Sespie         this->replace(__position, __position + 1, _M_data(), _M_data());
571*03a78d15Sespie 	_M_rep()->_M_set_leaked();
572*03a78d15Sespie 	return _M_ibegin() + __i;
573*03a78d15Sespie       }
574*03a78d15Sespie 
575*03a78d15Sespie       iterator
erase(iterator __first,iterator __last)576*03a78d15Sespie       erase(iterator __first, iterator __last)
577*03a78d15Sespie       {
578*03a78d15Sespie         size_type __i = __first - _M_ibegin();
579*03a78d15Sespie 	this->replace(__first, __last, _M_data(), _M_data());
580*03a78d15Sespie 	_M_rep()->_M_set_leaked();
581*03a78d15Sespie        return _M_ibegin() + __i;
582*03a78d15Sespie       }
583*03a78d15Sespie 
584*03a78d15Sespie       basic_string&
replace(size_type __pos,size_type __n,const basic_string & __str)585*03a78d15Sespie       replace(size_type __pos, size_type __n, const basic_string& __str)
586*03a78d15Sespie       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
587*03a78d15Sespie 
588*03a78d15Sespie       basic_string&
589*03a78d15Sespie       replace(size_type __pos1, size_type __n1, const basic_string& __str,
590*03a78d15Sespie 	      size_type __pos2, size_type __n2);
591*03a78d15Sespie 
592*03a78d15Sespie       basic_string&
593*03a78d15Sespie       replace(size_type __pos, size_type __n1, const _CharT* __s,
594*03a78d15Sespie 	      size_type __n2);
595*03a78d15Sespie 
596*03a78d15Sespie       basic_string&
replace(size_type __pos,size_type __n1,const _CharT * __s)597*03a78d15Sespie       replace(size_type __pos, size_type __n1, const _CharT* __s)
598*03a78d15Sespie       { return this->replace(__pos, __n1, __s, traits_type::length(__s)); }
599*03a78d15Sespie 
600*03a78d15Sespie       basic_string&
replace(size_type __pos,size_type __n1,size_type __n2,_CharT __c)601*03a78d15Sespie       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
602*03a78d15Sespie       { return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c); }
603*03a78d15Sespie 
604*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,const basic_string & __str)605*03a78d15Sespie       replace(iterator __i1, iterator __i2, const basic_string& __str)
606*03a78d15Sespie       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
607*03a78d15Sespie 
608*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,const _CharT * __s,size_type __n)609*03a78d15Sespie       replace(iterator __i1, iterator __i2,
610*03a78d15Sespie                            const _CharT* __s, size_type __n)
611*03a78d15Sespie       { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n); }
612*03a78d15Sespie 
613*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,const _CharT * __s)614*03a78d15Sespie       replace(iterator __i1, iterator __i2, const _CharT* __s)
615*03a78d15Sespie       { return this->replace(__i1, __i2, __s, traits_type::length(__s)); }
616*03a78d15Sespie 
617*03a78d15Sespie       basic_string&
618*03a78d15Sespie       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c);
619*03a78d15Sespie 
620*03a78d15Sespie       template<class _InputIterator>
621*03a78d15Sespie         basic_string&
replace(iterator __i1,iterator __i2,_InputIterator __k1,_InputIterator __k2)622*03a78d15Sespie         replace(iterator __i1, iterator __i2,
623*03a78d15Sespie 		_InputIterator __k1, _InputIterator __k2)
624*03a78d15Sespie         { return _M_replace(__i1, __i2, __k1, __k2,
625*03a78d15Sespie 	     typename iterator_traits<_InputIterator>::iterator_category()); }
626*03a78d15Sespie 
627*03a78d15Sespie       // Specializations for the common case of pointer and iterator:
628*03a78d15Sespie       // useful to avoid the overhead of temporary buffering in _M_replace.
629*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,_CharT * __k1,_CharT * __k2)630*03a78d15Sespie       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
631*03a78d15Sespie         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
632*03a78d15Sespie 			       __k1, __k2 - __k1); }
633*03a78d15Sespie 
634*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,const _CharT * __k1,const _CharT * __k2)635*03a78d15Sespie       replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2)
636*03a78d15Sespie         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
637*03a78d15Sespie 			       __k1, __k2 - __k1); }
638*03a78d15Sespie 
639*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,iterator __k1,iterator __k2)640*03a78d15Sespie       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
641*03a78d15Sespie         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
642*03a78d15Sespie 			       __k1.base(), __k2 - __k1);
643*03a78d15Sespie 	}
644*03a78d15Sespie 
645*03a78d15Sespie       basic_string&
replace(iterator __i1,iterator __i2,const_iterator __k1,const_iterator __k2)646*03a78d15Sespie       replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2)
647*03a78d15Sespie         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
648*03a78d15Sespie 			       __k1.base(), __k2 - __k1);
649*03a78d15Sespie 	}
650*03a78d15Sespie 
651*03a78d15Sespie     private:
652*03a78d15Sespie       template<class _InputIterator>
653*03a78d15Sespie         basic_string&
654*03a78d15Sespie         _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
655*03a78d15Sespie 		   _InputIterator __k2, input_iterator_tag);
656*03a78d15Sespie 
657*03a78d15Sespie       template<class _ForwardIterator>
658*03a78d15Sespie         basic_string&
659*03a78d15Sespie         _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1,
660*03a78d15Sespie 		   _ForwardIterator __k2);
661*03a78d15Sespie 
662*03a78d15Sespie       // _S_construct_aux is used to implement the 21.3.1 para 15 which
663*03a78d15Sespie       // requires special behaviour if _InIter is an integral type
664*03a78d15Sespie       template<class _InIter>
665*03a78d15Sespie         static _CharT*
_S_construct_aux(_InIter __beg,_InIter __end,const _Alloc & __a,__false_type)666*03a78d15Sespie         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
667*03a78d15Sespie 			 __false_type)
668*03a78d15Sespie 	{
669*03a78d15Sespie           typedef typename iterator_traits<_InIter>::iterator_category _Tag;
670*03a78d15Sespie           return _S_construct(__beg, __end, __a, _Tag());
671*03a78d15Sespie 	}
672*03a78d15Sespie 
673*03a78d15Sespie       template<class _InIter>
674*03a78d15Sespie         static _CharT*
_S_construct_aux(_InIter __beg,_InIter __end,const _Alloc & __a,__true_type)675*03a78d15Sespie         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
676*03a78d15Sespie 			 __true_type)
677*03a78d15Sespie 	{
678*03a78d15Sespie 	  return _S_construct(static_cast<size_type>(__beg),
679*03a78d15Sespie 			      static_cast<value_type>(__end), __a);
680*03a78d15Sespie 	}
681*03a78d15Sespie 
682*03a78d15Sespie       template<class _InIter>
683*03a78d15Sespie         static _CharT*
_S_construct(_InIter __beg,_InIter __end,const _Alloc & __a)684*03a78d15Sespie         _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a)
685*03a78d15Sespie 	{
686*03a78d15Sespie 	  typedef typename _Is_integer<_InIter>::_Integral _Integral;
687*03a78d15Sespie 	  return _S_construct_aux(__beg, __end, __a, _Integral());
688*03a78d15Sespie         }
689*03a78d15Sespie 
690*03a78d15Sespie       // For Input Iterators, used in istreambuf_iterators, etc.
691*03a78d15Sespie       template<class _InIter>
692*03a78d15Sespie         static _CharT*
693*03a78d15Sespie          _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
694*03a78d15Sespie 		      input_iterator_tag);
695*03a78d15Sespie 
696*03a78d15Sespie       // For forward_iterators up to random_access_iterators, used for
697*03a78d15Sespie       // string::iterator, _CharT*, etc.
698*03a78d15Sespie       template<class _FwdIter>
699*03a78d15Sespie         static _CharT*
700*03a78d15Sespie         _S_construct(_FwdIter __beg, _FwdIter __end, const _Alloc& __a,
701*03a78d15Sespie 		     forward_iterator_tag);
702*03a78d15Sespie 
703*03a78d15Sespie       static _CharT*
704*03a78d15Sespie       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
705*03a78d15Sespie 
706*03a78d15Sespie     public:
707*03a78d15Sespie 
708*03a78d15Sespie       size_type
709*03a78d15Sespie       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
710*03a78d15Sespie 
711*03a78d15Sespie       void
712*03a78d15Sespie       swap(basic_string<_CharT, _Traits, _Alloc>& __s);
713*03a78d15Sespie 
714*03a78d15Sespie       // String operations:
715*03a78d15Sespie       const _CharT*
c_str()716*03a78d15Sespie       c_str() const
717*03a78d15Sespie       {
718*03a78d15Sespie 	// MT: This assumes concurrent writes are OK.
719*03a78d15Sespie 	size_type __n = this->size();
720*03a78d15Sespie 	traits_type::assign(_M_data()[__n], _Rep::_S_terminal);
721*03a78d15Sespie         return _M_data();
722*03a78d15Sespie       }
723*03a78d15Sespie 
724*03a78d15Sespie       const _CharT*
data()725*03a78d15Sespie       data() const { return _M_data(); }
726*03a78d15Sespie 
727*03a78d15Sespie       allocator_type
get_allocator()728*03a78d15Sespie       get_allocator() const { return _M_dataplus; }
729*03a78d15Sespie 
730*03a78d15Sespie       size_type
731*03a78d15Sespie       find(const _CharT* __s, size_type __pos, size_type __n) const;
732*03a78d15Sespie 
733*03a78d15Sespie       size_type
734*03a78d15Sespie       find(const basic_string& __str, size_type __pos = 0) const
735*03a78d15Sespie       { return this->find(__str.data(), __pos, __str.size()); }
736*03a78d15Sespie 
737*03a78d15Sespie       size_type
738*03a78d15Sespie       find(const _CharT* __s, size_type __pos = 0) const
739*03a78d15Sespie       { return this->find(__s, __pos, traits_type::length(__s)); }
740*03a78d15Sespie 
741*03a78d15Sespie       size_type
742*03a78d15Sespie       find(_CharT __c, size_type __pos = 0) const;
743*03a78d15Sespie 
744*03a78d15Sespie       size_type
745*03a78d15Sespie       rfind(const basic_string& __str, size_type __pos = npos) const
746*03a78d15Sespie       { return this->rfind(__str.data(), __pos, __str.size()); }
747*03a78d15Sespie 
748*03a78d15Sespie       size_type
749*03a78d15Sespie       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
750*03a78d15Sespie 
751*03a78d15Sespie       size_type
752*03a78d15Sespie       rfind(const _CharT* __s, size_type __pos = npos) const
753*03a78d15Sespie       { return this->rfind(__s, __pos, traits_type::length(__s)); }
754*03a78d15Sespie 
755*03a78d15Sespie       size_type
756*03a78d15Sespie       rfind(_CharT __c, size_type __pos = npos) const;
757*03a78d15Sespie 
758*03a78d15Sespie       size_type
759*03a78d15Sespie       find_first_of(const basic_string& __str, size_type __pos = 0) const
760*03a78d15Sespie       { return this->find_first_of(__str.data(), __pos, __str.size()); }
761*03a78d15Sespie 
762*03a78d15Sespie       size_type
763*03a78d15Sespie       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
764*03a78d15Sespie 
765*03a78d15Sespie       size_type
766*03a78d15Sespie       find_first_of(const _CharT* __s, size_type __pos = 0) const
767*03a78d15Sespie       { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
768*03a78d15Sespie 
769*03a78d15Sespie       size_type
770*03a78d15Sespie       find_first_of(_CharT __c, size_type __pos = 0) const
771*03a78d15Sespie       { return this->find(__c, __pos); }
772*03a78d15Sespie 
773*03a78d15Sespie       size_type
774*03a78d15Sespie       find_last_of(const basic_string& __str, size_type __pos = npos) const
775*03a78d15Sespie       { return this->find_last_of(__str.data(), __pos, __str.size()); }
776*03a78d15Sespie 
777*03a78d15Sespie       size_type
778*03a78d15Sespie       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
779*03a78d15Sespie 
780*03a78d15Sespie       size_type
781*03a78d15Sespie       find_last_of(const _CharT* __s, size_type __pos = npos) const
782*03a78d15Sespie       { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
783*03a78d15Sespie 
784*03a78d15Sespie       size_type
785*03a78d15Sespie       find_last_of(_CharT __c, size_type __pos = npos) const
786*03a78d15Sespie       { return this->rfind(__c, __pos); }
787*03a78d15Sespie 
788*03a78d15Sespie       size_type
789*03a78d15Sespie       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
790*03a78d15Sespie       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
791*03a78d15Sespie 
792*03a78d15Sespie       size_type
793*03a78d15Sespie       find_first_not_of(const _CharT* __s, size_type __pos,
794*03a78d15Sespie 			size_type __n) const;
795*03a78d15Sespie 
796*03a78d15Sespie       size_type
797*03a78d15Sespie       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
798*03a78d15Sespie       { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
799*03a78d15Sespie 
800*03a78d15Sespie       size_type
801*03a78d15Sespie       find_first_not_of(_CharT __c, size_type __pos = 0) const;
802*03a78d15Sespie 
803*03a78d15Sespie       size_type
804*03a78d15Sespie       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
805*03a78d15Sespie       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
806*03a78d15Sespie 
807*03a78d15Sespie       size_type
808*03a78d15Sespie       find_last_not_of(const _CharT* __s, size_type __pos,
809*03a78d15Sespie 		       size_type __n) const;
810*03a78d15Sespie       size_type
811*03a78d15Sespie       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
812*03a78d15Sespie       { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
813*03a78d15Sespie 
814*03a78d15Sespie       size_type
815*03a78d15Sespie       find_last_not_of(_CharT __c, size_type __pos = npos) const;
816*03a78d15Sespie 
817*03a78d15Sespie       basic_string
818*03a78d15Sespie       substr(size_type __pos = 0, size_type __n = npos) const
819*03a78d15Sespie       {
820*03a78d15Sespie 	if (__pos > this->size())
821*03a78d15Sespie 	  __throw_out_of_range("basic_string::substr");
822*03a78d15Sespie 	return basic_string(*this, __pos, __n);
823*03a78d15Sespie       }
824*03a78d15Sespie 
825*03a78d15Sespie       int
compare(const basic_string & __str)826*03a78d15Sespie       compare(const basic_string& __str) const
827*03a78d15Sespie       {
828*03a78d15Sespie 	size_type __size = this->size();
829*03a78d15Sespie 	size_type __osize = __str.size();
830*03a78d15Sespie 	size_type __len = std::min(__size, __osize);
831*03a78d15Sespie 
832*03a78d15Sespie 	int __r = traits_type::compare(_M_data(), __str.data(), __len);
833*03a78d15Sespie 	if (!__r)
834*03a78d15Sespie 	  __r =  __size - __osize;
835*03a78d15Sespie 	return __r;
836*03a78d15Sespie       }
837*03a78d15Sespie 
838*03a78d15Sespie       int
839*03a78d15Sespie       compare(size_type __pos, size_type __n, const basic_string& __str) const;
840*03a78d15Sespie 
841*03a78d15Sespie       int
842*03a78d15Sespie       compare(size_type __pos1, size_type __n1, const basic_string& __str,
843*03a78d15Sespie 	      size_type __pos2, size_type __n2) const;
844*03a78d15Sespie 
845*03a78d15Sespie       int
846*03a78d15Sespie       compare(const _CharT* __s) const;
847*03a78d15Sespie 
848*03a78d15Sespie       // _GLIBCPP_RESOLVE_LIB_DEFECTS
849*03a78d15Sespie       // 5 String::compare specification questionable
850*03a78d15Sespie       int
851*03a78d15Sespie       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
852*03a78d15Sespie 
853*03a78d15Sespie       int
854*03a78d15Sespie       compare(size_type __pos, size_type __n1, const _CharT* __s,
855*03a78d15Sespie 	      size_type __n2) const;
856*03a78d15Sespie   };
857*03a78d15Sespie 
858*03a78d15Sespie 
859*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
860*03a78d15Sespie     inline basic_string<_CharT, _Traits, _Alloc>::
basic_string()861*03a78d15Sespie     basic_string()
862*03a78d15Sespie     : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
863*03a78d15Sespie 
864*03a78d15Sespie   // operator+
865*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
866*03a78d15Sespie     basic_string<_CharT, _Traits, _Alloc>
867*03a78d15Sespie     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
868*03a78d15Sespie 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
869*03a78d15Sespie     {
870*03a78d15Sespie       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
871*03a78d15Sespie       __str.append(__rhs);
872*03a78d15Sespie       return __str;
873*03a78d15Sespie     }
874*03a78d15Sespie 
875*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
876*03a78d15Sespie     basic_string<_CharT,_Traits,_Alloc>
877*03a78d15Sespie     operator+(const _CharT* __lhs,
878*03a78d15Sespie 	      const basic_string<_CharT,_Traits,_Alloc>& __rhs);
879*03a78d15Sespie 
880*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
881*03a78d15Sespie     basic_string<_CharT,_Traits,_Alloc>
882*03a78d15Sespie     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
883*03a78d15Sespie 
884*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
885*03a78d15Sespie     inline basic_string<_CharT, _Traits, _Alloc>
886*03a78d15Sespie     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
887*03a78d15Sespie 	     const _CharT* __rhs)
888*03a78d15Sespie     {
889*03a78d15Sespie       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
890*03a78d15Sespie       __str.append(__rhs);
891*03a78d15Sespie       return __str;
892*03a78d15Sespie     }
893*03a78d15Sespie 
894*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
895*03a78d15Sespie     inline basic_string<_CharT, _Traits, _Alloc>
896*03a78d15Sespie     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
897*03a78d15Sespie     {
898*03a78d15Sespie       typedef basic_string<_CharT, _Traits, _Alloc> 	__string_type;
899*03a78d15Sespie       typedef typename __string_type::size_type		__size_type;
900*03a78d15Sespie       __string_type __str(__lhs);
901*03a78d15Sespie       __str.append(__size_type(1), __rhs);
902*03a78d15Sespie       return __str;
903*03a78d15Sespie     }
904*03a78d15Sespie 
905*03a78d15Sespie   // operator ==
906*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
907*03a78d15Sespie     inline bool
908*03a78d15Sespie     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
909*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
910*03a78d15Sespie     { return __lhs.compare(__rhs) == 0; }
911*03a78d15Sespie 
912*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
913*03a78d15Sespie     inline bool
914*03a78d15Sespie     operator==(const _CharT* __lhs,
915*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
916*03a78d15Sespie     { return __rhs.compare(__lhs) == 0; }
917*03a78d15Sespie 
918*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
919*03a78d15Sespie     inline bool
920*03a78d15Sespie     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
921*03a78d15Sespie 	       const _CharT* __rhs)
922*03a78d15Sespie     { return __lhs.compare(__rhs) == 0; }
923*03a78d15Sespie 
924*03a78d15Sespie   // operator !=
925*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
926*03a78d15Sespie     inline bool
927*03a78d15Sespie     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
928*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
929*03a78d15Sespie     { return __rhs.compare(__lhs) != 0; }
930*03a78d15Sespie 
931*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
932*03a78d15Sespie     inline bool
933*03a78d15Sespie     operator!=(const _CharT* __lhs,
934*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
935*03a78d15Sespie     { return __rhs.compare(__lhs) != 0; }
936*03a78d15Sespie 
937*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
938*03a78d15Sespie     inline bool
939*03a78d15Sespie     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
940*03a78d15Sespie 	       const _CharT* __rhs)
941*03a78d15Sespie     { return __lhs.compare(__rhs) != 0; }
942*03a78d15Sespie 
943*03a78d15Sespie   // operator <
944*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
945*03a78d15Sespie     inline bool
946*03a78d15Sespie     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
947*03a78d15Sespie 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
948*03a78d15Sespie     { return __lhs.compare(__rhs) < 0; }
949*03a78d15Sespie 
950*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
951*03a78d15Sespie     inline bool
952*03a78d15Sespie     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
953*03a78d15Sespie 	      const _CharT* __rhs)
954*03a78d15Sespie     { return __lhs.compare(__rhs) < 0; }
955*03a78d15Sespie 
956*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
957*03a78d15Sespie     inline bool
958*03a78d15Sespie     operator<(const _CharT* __lhs,
959*03a78d15Sespie 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
960*03a78d15Sespie     { return __rhs.compare(__lhs) > 0; }
961*03a78d15Sespie 
962*03a78d15Sespie   // operator >
963*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
964*03a78d15Sespie     inline bool
965*03a78d15Sespie     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
966*03a78d15Sespie 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
967*03a78d15Sespie     { return __lhs.compare(__rhs) > 0; }
968*03a78d15Sespie 
969*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
970*03a78d15Sespie     inline bool
971*03a78d15Sespie     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
972*03a78d15Sespie 	      const _CharT* __rhs)
973*03a78d15Sespie     { return __lhs.compare(__rhs) > 0; }
974*03a78d15Sespie 
975*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
976*03a78d15Sespie     inline bool
977*03a78d15Sespie     operator>(const _CharT* __lhs,
978*03a78d15Sespie 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
979*03a78d15Sespie     { return __rhs.compare(__lhs) < 0; }
980*03a78d15Sespie 
981*03a78d15Sespie   // operator <=
982*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
983*03a78d15Sespie     inline bool
984*03a78d15Sespie     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
985*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
986*03a78d15Sespie     { return __lhs.compare(__rhs) <= 0; }
987*03a78d15Sespie 
988*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
989*03a78d15Sespie     inline bool
990*03a78d15Sespie     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
991*03a78d15Sespie 	       const _CharT* __rhs)
992*03a78d15Sespie     { return __lhs.compare(__rhs) <= 0; }
993*03a78d15Sespie 
994*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
995*03a78d15Sespie     inline bool
996*03a78d15Sespie     operator<=(const _CharT* __lhs,
997*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
998*03a78d15Sespie   { return __rhs.compare(__lhs) >= 0; }
999*03a78d15Sespie 
1000*03a78d15Sespie   // operator >=
1001*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1002*03a78d15Sespie     inline bool
1003*03a78d15Sespie     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1004*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1005*03a78d15Sespie     { return __lhs.compare(__rhs) >= 0; }
1006*03a78d15Sespie 
1007*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1008*03a78d15Sespie     inline bool
1009*03a78d15Sespie     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1010*03a78d15Sespie 	       const _CharT* __rhs)
1011*03a78d15Sespie     { return __lhs.compare(__rhs) >= 0; }
1012*03a78d15Sespie 
1013*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1014*03a78d15Sespie     inline bool
1015*03a78d15Sespie     operator>=(const _CharT* __lhs,
1016*03a78d15Sespie 	     const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1017*03a78d15Sespie     { return __rhs.compare(__lhs) <= 0; }
1018*03a78d15Sespie 
1019*03a78d15Sespie 
1020*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1021*03a78d15Sespie     inline void
swap(basic_string<_CharT,_Traits,_Alloc> & __lhs,basic_string<_CharT,_Traits,_Alloc> & __rhs)1022*03a78d15Sespie     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
1023*03a78d15Sespie 	 basic_string<_CharT, _Traits, _Alloc>& __rhs)
1024*03a78d15Sespie     { __lhs.swap(__rhs); }
1025*03a78d15Sespie 
1026*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1027*03a78d15Sespie     basic_istream<_CharT, _Traits>&
1028*03a78d15Sespie     operator>>(basic_istream<_CharT, _Traits>& __is,
1029*03a78d15Sespie 	       basic_string<_CharT, _Traits, _Alloc>& __str);
1030*03a78d15Sespie 
1031*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1032*03a78d15Sespie     basic_ostream<_CharT, _Traits>&
1033*03a78d15Sespie     operator<<(basic_ostream<_CharT, _Traits>& __os,
1034*03a78d15Sespie 	       const basic_string<_CharT, _Traits, _Alloc>& __str);
1035*03a78d15Sespie 
1036*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1037*03a78d15Sespie     basic_istream<_CharT,_Traits>&
1038*03a78d15Sespie     getline(basic_istream<_CharT, _Traits>& __is,
1039*03a78d15Sespie 	    basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
1040*03a78d15Sespie 
1041*03a78d15Sespie   template<typename _CharT, typename _Traits, typename _Alloc>
1042*03a78d15Sespie     inline basic_istream<_CharT,_Traits>&
1043*03a78d15Sespie     getline(basic_istream<_CharT, _Traits>& __is,
1044*03a78d15Sespie 	    basic_string<_CharT, _Traits, _Alloc>& __str);
1045*03a78d15Sespie } // namespace std
1046*03a78d15Sespie 
1047*03a78d15Sespie #endif /* _CPP_BITS_STRING_H */
1048