_string.h revision 9720d5f59b9c1f5d1b9ecbc9173dbcb71bd557be 
1/*
2 * Copyright (c) 1997-1999
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Copyright (c) 1999
6 * Boris Fomitchev
7 *
8 * This material is provided "as is", with absolutely no warranty expressed
9 * or implied. Any use is at your own risk.
10 *
11 * Permission to use or copy this software for any purpose is hereby granted
12 * without fee, provided the above notices are retained on all copies.
13 * Permission to modify the code and to distribute modified code is granted,
14 * provided the above notices are retained, and a notice that the code was
15 * modified is included with the above copyright notice.
16 *
17 */
18
19#ifndef _STLP_INTERNAL_STRING_H
20#define _STLP_INTERNAL_STRING_H
21
22#ifndef _STLP_INTERNAL_ALLOC_H
23#  include <stl/_alloc.h>
24#endif
25
26#ifndef _STLP_STRING_FWD_H
27#  include <stl/_string_fwd.h>
28#endif
29
30#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
31#  include <stl/_function_base.h>
32#endif
33
34#ifndef _STLP_INTERNAL_ALGOBASE_H
35#  include <stl/_algobase.h>
36#endif
37
38#ifndef _STLP_INTERNAL_ITERATOR_H
39#  include <stl/_iterator.h>
40#endif
41
42#ifndef _STLP_INTERNAL_UNINITIALIZED_H
43#  include <stl/_uninitialized.h>
44#endif
45
46#if defined (_STLP_USE_TEMPLATE_EXPRESSION)
47#  include <stl/_string_sum.h>
48#endif /* _STLP_USE_TEMPLATE_EXPRESSION */
49
50#if defined (__MWERKS__) && ! defined (_STLP_USE_OWN_NAMESPACE)
51
52// MSL implementation classes expect to see the definition of streampos
53// when this header is included. We expect this to be fixed in later MSL
54// implementations
55#  if !defined( __MSL_CPP__ ) || __MSL_CPP__ < 0x4105
56#    include <stl/msl_string.h>
57#  endif
58#endif // __MWERKS__
59
60/*
61 * Standard C++ string class.  This class has performance
62 * characteristics very much like vector<>, meaning, for example, that
63 * it does not perform reference-count or copy-on-write, and that
64 * concatenation of two strings is an O(N) operation.
65
66 * There are three reasons why basic_string is not identical to
67 * vector.
68 * First, basic_string can always stores a null character
69 * at the end (macro dependent); this makes it possible for c_str to
70 * be a fast operation.
71 * Second, the C++ standard requires basic_string to copy elements
72 * using char_traits<>::assign, char_traits<>::copy, and
73 * char_traits<>::move.  This means that all of vector<>'s low-level
74 * operations must be rewritten.  Third, basic_string<> has a lot of
75 * extra functions in its interface that are convenient but, strictly
76 * speaking, redundant.
77
78 * Additionally, the C++ standard imposes a major restriction: according
79 * to the standard, the character type _CharT must be a POD type.  This
80 * implementation weakens that restriction, and allows _CharT to be a
81 * a user-defined non-POD type.  However, _CharT must still have a
82 * default constructor.
83 */
84
85#include <stl/_string_base.h>
86
87_STLP_BEGIN_NAMESPACE
88
89// ------------------------------------------------------------
90// Class basic_string.
91
92// Class invariants:
93// (1) [start, finish) is a valid range.
94// (2) Each iterator in [start, finish) points to a valid object
95//     of type value_type.
96// (3) *finish is a valid object of type value_type; when
97//     value_type is not a POD it is value_type().
98// (4) [finish + 1, end_of_storage) is a valid range.
99// (5) Each iterator in [finish + 1, end_of_storage) points to
100//     unininitialized memory.
101
102// Note one important consequence: a string of length n must manage
103// a block of memory whose size is at least n + 1.
104
105struct _String_reserve_t {};
106
107#if defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
108#  define basic_string _STLP_NO_MEM_T_NAME(str)
109#elif defined (_STLP_DEBUG)
110#  define basic_string _STLP_NON_DBG_NAME(str)
111#endif
112
113#if defined (basic_string)
114_STLP_MOVE_TO_PRIV_NAMESPACE
115#endif
116
117template <class _CharT, class _Traits, class _Alloc>
118class basic_string : protected _STLP_PRIV _String_base<_CharT,_Alloc>
119#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (basic_string)
120                   , public __stlport_class<basic_string<_CharT, _Traits, _Alloc> >
121#endif
122{
123protected:                        // Protected members inherited from base.
124  typedef _STLP_PRIV _String_base<_CharT,_Alloc> _Base;
125  typedef basic_string<_CharT, _Traits, _Alloc> _Self;
126  // fbp : used to optimize char/wchar_t cases, and to simplify
127  // _STLP_DEF_CONST_PLCT_NEW_BUG problem workaround
128  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
129  typedef typename _IsPOD<_CharT>::_Type _Char_Is_POD;
130  typedef random_access_iterator_tag r_a_i_t;
131
132public:
133  typedef _CharT value_type;
134  typedef _Traits traits_type;
135
136  typedef value_type* pointer;
137  typedef const value_type* const_pointer;
138  typedef value_type& reference;
139  typedef const value_type& const_reference;
140  typedef typename _Base::size_type size_type;
141  typedef ptrdiff_t difference_type;
142  typedef random_access_iterator_tag _Iterator_category;
143
144  typedef const value_type* const_iterator;
145  typedef value_type*       iterator;
146
147  _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
148
149#include <stl/_string_npos.h>
150
151  typedef _String_reserve_t _Reserve_t;
152
153public:                         // Constructor, destructor, assignment.
154  typedef typename _Base::allocator_type allocator_type;
155
156  allocator_type get_allocator() const
157  { return _STLP_CONVERT_ALLOCATOR((const allocator_type&)this->_M_end_of_storage, _CharT); }
158
159#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
160  explicit basic_string(const allocator_type& __a = allocator_type())
161#else
162  basic_string()
163      : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type(), _Base::_DEFAULT_SIZE)
164  { _M_terminate_string(); }
165  explicit basic_string(const allocator_type& __a)
166#endif
167      : _STLP_PRIV _String_base<_CharT,_Alloc>(__a, _Base::_DEFAULT_SIZE)
168  { _M_terminate_string(); }
169
170#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
171  basic_string(_Reserve_t, size_t __n,
172               const allocator_type& __a = allocator_type())
173#else
174  basic_string(_Reserve_t, size_t __n)
175    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type(), __n + 1)
176  { _M_terminate_string(); }
177  basic_string(_Reserve_t, size_t __n, const allocator_type& __a)
178#endif
179    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a, __n + 1)
180  { _M_terminate_string(); }
181
182  basic_string(const _Self&);
183
184#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
185  basic_string(const _Self& __s, size_type __pos, size_type __n = npos,
186               const allocator_type& __a = allocator_type())
187#else
188  basic_string(const _Self& __s, size_type __pos)
189    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
190    if (__pos > __s.size())
191      this->_M_throw_out_of_range();
192    else
193      _M_range_initialize(__s._M_Start() + __pos, __s._M_Finish());
194  }
195  basic_string(const _Self& __s, size_type __pos, size_type __n)
196    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
197    if (__pos > __s.size())
198      this->_M_throw_out_of_range();
199    else
200      _M_range_initialize(__s._M_Start() + __pos,
201                          __s._M_Start() + __pos + (min) (__n, __s.size() - __pos));
202  }
203  basic_string(const _Self& __s, size_type __pos, size_type __n,
204               const allocator_type& __a)
205#endif
206    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a) {
207    if (__pos > __s.size())
208      this->_M_throw_out_of_range();
209    else
210      _M_range_initialize(__s._M_Start() + __pos,
211                          __s._M_Start() + __pos + (min) (__n, __s.size() - __pos));
212  }
213
214#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
215  basic_string(const _CharT* __s, size_type __n,
216               const allocator_type& __a = allocator_type())
217#else
218  basic_string(const _CharT* __s, size_type __n)
219    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
220      _STLP_FIX_LITERAL_BUG(__s)
221      _M_range_initialize(__s, __s + __n);
222    }
223  basic_string(const _CharT* __s, size_type __n, const allocator_type& __a)
224#endif
225    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a) {
226      _STLP_FIX_LITERAL_BUG(__s)
227      _M_range_initialize(__s, __s + __n);
228    }
229
230#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
231  basic_string(const _CharT* __s,
232               const allocator_type& __a = allocator_type());
233#else
234  basic_string(const _CharT* __s);
235  basic_string(const _CharT* __s, const allocator_type& __a);
236#endif
237
238#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
239  basic_string(size_type __n, _CharT __c,
240               const allocator_type& __a = allocator_type())
241#else
242  basic_string(size_type __n, _CharT __c)
243    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type(), __n + 1) {
244#  if defined (_STLP_USE_SHORT_STRING_OPTIM)
245    if (this->_M_using_static_buf()) {
246      _Traits::assign(this->_M_Start(), __n, __c);
247      this->_M_finish = this->_M_Start() + __n;
248    }
249    else
250#  endif
251    this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_Start(), __n, __c);
252    _M_terminate_string();
253  }
254  basic_string(size_type __n, _CharT __c, const allocator_type& __a)
255#endif
256    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a, __n + 1) {
257#if defined (_STLP_USE_SHORT_STRING_OPTIM)
258    if (this->_M_using_static_buf()) {
259      _Traits::assign(this->_M_Start(), __n, __c);
260      this->_M_finish = this->_M_Start() + __n;
261    }
262    else
263#endif
264    this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_Start(), __n, __c);
265    _M_terminate_string();
266  }
267
268  basic_string(__move_source<_Self> src)
269    : _STLP_PRIV _String_base<_CharT,_Alloc>(__move_source<_Base>(src.get())) {}
270
271  // Check to see if _InputIterator is an integer type.  If so, then
272  // it can't be an iterator.
273#if defined (_STLP_MEMBER_TEMPLATES) && !(defined (__MRC__) || (defined(__SC__) && !defined(__DMC__))) //*ty 04/30/2001 - mpw compilers choke on this ctor
274#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
275  template <class _InputIterator>
276  basic_string(_InputIterator __f, _InputIterator __l,
277               const allocator_type & __a _STLP_ALLOCATOR_TYPE_DFL)
278    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a) {
279    typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
280    _M_initialize_dispatch(__f, __l, _Integral());
281  }
282#    if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
283  template <class _InputIterator>
284  basic_string(_InputIterator __f, _InputIterator __l)
285    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
286    typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
287    _M_initialize_dispatch(__f, __l, _Integral());
288  }
289#    endif
290#  else
291  /* We need an additionnal constructor to build an empty string without
292   * any allocation or termination char*/
293protected:
294  struct _CalledFromWorkaround_t {};
295  basic_string(_CalledFromWorkaround_t, const allocator_type &__a)
296    : _String_base<_CharT,_Alloc>(__a) {}
297public:
298#  endif /* _STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND */
299#endif /* !__MRC__ || (__SC__ && !__DMC__) */
300
301#if !(defined (_STLP_MEMBER_TEMPLATES) && !(defined (__MRC__) || (defined (__SC__) && !defined (__DMC__)))) || \
302    !defined (_STLP_NO_METHOD_SPECIALIZATION) && !defined (_STLP_NO_EXTENSIONS) || \
303     defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
304  basic_string(const _CharT* __f, const _CharT* __l,
305               const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
306    : _STLP_PRIV _String_base<_CharT,_Alloc>(__a) {
307    _STLP_FIX_LITERAL_BUG(__f)  _STLP_FIX_LITERAL_BUG(__l)
308    _M_range_initialize(__f, __l);
309  }
310#  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
311  basic_string(const _CharT* __f, const _CharT* __l)
312    : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
313    _STLP_FIX_LITERAL_BUG(__f)  _STLP_FIX_LITERAL_BUG(__l)
314    _M_range_initialize(__f, __l);
315  }
316#  endif
317#endif /* _STLP_MEMBER_TEMPLATES */
318
319private:
320  template <class _InputIter>
321  void _M_range_initialize(_InputIter __f, _InputIter __l,
322                           const input_iterator_tag &__tag) {
323    this->_M_allocate_block();
324    _M_construct_null(this->_M_Finish());
325    _STLP_TRY {
326      _M_appendT(__f, __l, __tag);
327    }
328    _STLP_UNWIND(this->_M_destroy_range())
329  }
330
331  template <class _ForwardIter>
332  void _M_range_initialize(_ForwardIter __f, _ForwardIter __l,
333                           const forward_iterator_tag &) {
334    difference_type __n = distance(__f, __l);
335    this->_M_allocate_block(__n + 1);
336#if defined (_STLP_USE_SHORT_STRING_OPTIM)
337    if (this->_M_using_static_buf()) {
338      _M_copyT(__f, __l, this->_M_Start());
339      this->_M_finish = this->_M_Start() + __n;
340    }
341    else
342#endif /* _STLP_USE_SHORT_STRING_OPTIM */
343    this->_M_finish = uninitialized_copy(__f, __l, this->_M_Start());
344    this->_M_terminate_string();
345  }
346
347  template <class _InputIter>
348  void _M_range_initializeT(_InputIter __f, _InputIter __l) {
349    _M_range_initialize(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));
350  }
351
352  template <class _Integer>
353  void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type& /*_Integral*/) {
354    this->_M_allocate_block(__n + 1);
355#if defined (_STLP_USE_SHORT_STRING_OPTIM)
356    if (this->_M_using_static_buf()) {
357      _Traits::assign(this->_M_Start(), __n, __x);
358      this->_M_finish = this->_M_Start() + __n;
359    }
360    else
361#endif /* _STLP_USE_SHORT_STRING_OPTIM */
362    this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_Start(), __n, __x);
363    this->_M_terminate_string();
364  }
365
366  template <class _InputIter>
367  void _M_initialize_dispatch(_InputIter __f, _InputIter __l, const __false_type& /*_Integral*/) {
368    _M_range_initializeT(__f, __l);
369  }
370
371public:
372  ~basic_string()
373  { this->_M_destroy_range(); }
374
375  _Self& operator=(const _Self& __s) {
376    if (&__s != this)
377      _M_assign(__s._M_Start(), __s._M_Finish());
378    return *this;
379  }
380
381  _Self& operator=(const _CharT* __s) {
382    _STLP_FIX_LITERAL_BUG(__s)
383    return _M_assign(__s, __s + traits_type::length(__s));
384  }
385
386  _Self& operator=(_CharT __c)
387  { return assign(__STATIC_CAST(size_type,1), __c); }
388
389protected:
390
391  static _CharT _STLP_CALL _M_null()
392  { return _STLP_DEFAULT_CONSTRUCTED(_CharT); }
393
394protected:                     // Helper functions used by constructors
395                               // and elsewhere.
396  // fbp : simplify integer types (char, wchar)
397  void _M_construct_null_aux(_CharT* __p, const __false_type& /*_Is_Integral*/) const {
398#if defined (_STLP_USE_SHORT_STRING_OPTIM)
399    if (this->_M_using_static_buf())
400      _Traits::assign(*__p, _M_null());
401    else
402#endif /*_STLP_USE_SHORT_STRING_OPTIM*/
403    _STLP_STD::_Construct(__p);
404  }
405  void _M_construct_null_aux(_CharT* __p, const __true_type& /*_Is_Integral*/) const
406  { *__p = 0; }
407
408  void _M_force_construct_null(_CharT*, const __true_type& /* _Is_POD */) const
409  { /*Nothing to do*/ }
410  void _M_force_construct_null(_CharT* __p, const __false_type& /* _Is_POD */) const
411  { _M_construct_null_aux(__p, _Char_Is_Integral()); }
412
413  void _M_construct_null(_CharT* __p) const {
414    typedef __false_type _Answer;
415
416    _M_force_construct_null(__p, _Answer());
417  }
418
419protected:
420  // Helper functions used by constructors.  It is a severe error for
421  // any of them to be called anywhere except from within constructors.
422  void _M_terminate_string_aux(const __false_type& __is_integral) {
423    _STLP_TRY {
424      _M_construct_null_aux(this->_M_Finish(), __is_integral);
425    }
426    _STLP_UNWIND(this->_M_destroy_range(0,0))
427  }
428
429  void _M_terminate_string_aux(const __true_type& __is_integral)
430  { _M_construct_null_aux(this->_M_Finish(), __is_integral); }
431
432  void _M_force_terminate_string(const __true_type& /* _Is_POD */)
433  { /*Nothing to do*/ }
434  void _M_force_terminate_string(const __false_type& /* _Is_POD */)
435  { _M_terminate_string_aux(_Char_Is_Integral()); }
436
437  void _M_terminate_string() {
438    typedef __false_type _Answer;
439
440    _M_force_terminate_string(_Answer());
441  }
442
443  bool _M_inside(const _CharT* __s) const {
444    _STLP_FIX_LITERAL_BUG(__s)
445    return (__s >= this->_M_Start()) && (__s < this->_M_Finish());
446  }
447
448  void _M_range_initialize(const _CharT* __f, const _CharT* __l) {
449    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
450    ptrdiff_t __n = __l - __f;
451    this->_M_allocate_block(__n + 1);
452#if defined (_STLP_USE_SHORT_STRING_OPTIM)
453    if (this->_M_using_static_buf()) {
454      _M_copy(__f, __l, this->_M_Start());
455      this->_M_finish = this->_M_Start() + __n;
456    }
457    else
458#endif /* _STLP_USE_SHORT_STRING_OPTIM */
459    this->_M_finish = uninitialized_copy(__f, __l, this->_M_Start());
460    _M_terminate_string();
461  }
462
463public:                         // Iterators.
464  iterator begin()             { return this->_M_Start(); }
465  iterator end()               { return this->_M_Finish(); }
466  const_iterator begin() const { return this->_M_Start(); }
467  const_iterator end()   const { return this->_M_Finish(); }
468
469  reverse_iterator rbegin()
470    { return reverse_iterator(this->_M_Finish()); }
471  reverse_iterator rend()
472    { return reverse_iterator(this->_M_Start()); }
473  const_reverse_iterator rbegin() const
474    { return const_reverse_iterator(this->_M_Finish()); }
475  const_reverse_iterator rend()   const
476    { return const_reverse_iterator(this->_M_Start()); }
477
478public:                         // Size, capacity, etc.
479  size_type size() const { return this->_M_Finish() - this->_M_Start(); }
480  size_type length() const { return size(); }
481  size_t max_size() const { return _Base::max_size(); }
482
483  void resize(size_type __n, _CharT __c) {
484    if (__n <= size())
485      erase(begin() + __n, end());
486    else
487      append(__n - size(), __c);
488  }
489
490  void resize(size_type __n) { resize(__n, _M_null()); }
491
492  void reserve(size_type = 0);
493
494  size_type capacity() const
495  { return (this->_M_end_of_storage._M_data - this->_M_Start()) - 1; }
496
497  void clear() {
498    if (!empty()) {
499      _Traits::assign(*(this->_M_Start()), _M_null());
500      this->_M_destroy_range(1);
501      this->_M_finish = this->_M_Start();
502    }
503  }
504
505  bool empty() const { return this->_M_Start() == this->_M_Finish(); }
506
507public:                         // Element access.
508
509  const_reference operator[](size_type __n) const
510  { return *(this->_M_Start() + __n); }
511  reference operator[](size_type __n)
512  { return *(this->_M_Start() + __n); }
513
514  const_reference at(size_type __n) const {
515    if (__n >= size())
516      this->_M_throw_out_of_range();
517    return *(this->_M_Start() + __n);
518  }
519
520  reference at(size_type __n) {
521    if (__n >= size())
522      this->_M_throw_out_of_range();
523    return *(this->_M_Start() + __n);
524  }
525
526public:                         // Append, operator+=, push_back.
527
528  _Self& operator+=(const _Self& __s) { return append(__s); }
529  _Self& operator+=(const _CharT* __s) { _STLP_FIX_LITERAL_BUG(__s) return append(__s); }
530  _Self& operator+=(_CharT __c) { push_back(__c); return *this; }
531
532#if defined (_STLP_MEMBER_TEMPLATES)
533#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
534private: // Helper functions for append.
535  template <class _InputIter>
536  _Self& _M_appendT(_InputIter __first, _InputIter __last,
537                    const input_iterator_tag &) {
538    for ( ; __first != __last ; ++__first)
539      push_back(*__first);
540    return *this;
541  }
542
543  template <class _ForwardIter>
544  _Self& _M_appendT(_ForwardIter __first, _ForwardIter __last,
545                    const forward_iterator_tag &) {
546    if (__first != __last) {
547      const size_type __old_size = this->size();
548      difference_type __n = distance(__first, __last);
549      if (__STATIC_CAST(size_type,__n) > this->max_size() || __old_size > this->max_size() - __STATIC_CAST(size_type,__n))
550        this->_M_throw_length_error();
551      if (__old_size + __n > this->capacity()) {
552        size_type __len = __old_size + (max)(__old_size, __STATIC_CAST(size_type,__n)) + 1;
553        pointer __new_start = this->_M_end_of_storage.allocate(__len, __len);
554        pointer __new_finish = __new_start;
555        _STLP_TRY {
556          __new_finish = uninitialized_copy(this->_M_Start(), this->_M_Finish(), __new_start);
557          __new_finish = uninitialized_copy(__first, __last, __new_finish);
558          _M_construct_null(__new_finish);
559        }
560        _STLP_UNWIND((_STLP_STD::_Destroy_Range(__new_start,__new_finish),
561          this->_M_end_of_storage.deallocate(__new_start, __len)))
562          this->_M_destroy_range();
563        this->_M_deallocate_block();
564        this->_M_reset(__new_start, __new_finish, __new_start + __len);
565      }
566      else {
567        _ForwardIter __f1 = __first;
568        ++__f1;
569#if defined (_STLP_USE_SHORT_STRING_OPTIM)
570        if (this->_M_using_static_buf())
571          _M_copyT(__f1, __last, this->_M_Finish() + 1);
572        else
573#endif /* _STLP_USE_SHORT_STRING_OPTIM */
574          uninitialized_copy(__f1, __last, this->_M_Finish() + 1);
575        _STLP_TRY {
576          _M_construct_null(this->_M_Finish() + __n);
577        }
578        _STLP_UNWIND(this->_M_destroy_ptr_range(this->_M_Finish() + 1, this->_M_Finish() + __n))
579        _Traits::assign(*this->_M_finish, *__first);
580        this->_M_finish += __n;
581      }
582    }
583    return *this;
584  }
585
586  template <class _Integer>
587  _Self& _M_append_dispatch(_Integer __n, _Integer __x, const __true_type& /*Integral*/)
588  { return append((size_type) __n, (_CharT) __x); }
589
590  template <class _InputIter>
591  _Self& _M_append_dispatch(_InputIter __f, _InputIter __l, const __false_type& /*Integral*/)
592  { return _M_appendT(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter)); }
593
594public:
595  // Check to see if _InputIterator is an integer type.  If so, then
596  // it can't be an iterator.
597  template <class _InputIter>
598  _Self& append(_InputIter __first, _InputIter __last) {
599    typedef typename _IsIntegral<_InputIter>::_Ret _Integral;
600    return _M_append_dispatch(__first, __last, _Integral());
601  }
602#  endif
603#endif
604
605protected:
606  _Self& _M_append(const _CharT* __first, const _CharT* __last);
607
608public:
609#if !defined (_STLP_MEMBER_TEMPLATES) || \
610    !defined (_STLP_NO_METHOD_SPECIALIZATION) && !defined (_STLP_NO_EXTENSIONS)
611#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
612  _Self& append(const _CharT* __first, const _CharT* __last) {
613    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
614    return _M_append(__first, __last);
615  }
616#  endif
617#endif
618
619  _Self& append(const _Self& __s)
620  { return _M_append(__s._M_Start(), __s._M_Finish()); }
621
622  _Self& append(const _Self& __s,
623                size_type __pos, size_type __n) {
624    if (__pos > __s.size())
625      this->_M_throw_out_of_range();
626    return _M_append(__s._M_Start() + __pos,
627                     __s._M_Start() + __pos + (min) (__n, __s.size() - __pos));
628  }
629
630  _Self& append(const _CharT* __s, size_type __n)
631  { _STLP_FIX_LITERAL_BUG(__s) return _M_append(__s, __s+__n); }
632  _Self& append(const _CharT* __s)
633  { _STLP_FIX_LITERAL_BUG(__s) return _M_append(__s, __s + traits_type::length(__s)); }
634  _Self& append(size_type __n, _CharT __c);
635
636public:
637  void push_back(_CharT __c) {
638    if (this->_M_Finish() + 1 == this->_M_end_of_storage._M_data)
639      reserve(size() + (max)(size(), __STATIC_CAST(size_type,1)));
640    _M_construct_null(this->_M_Finish() + 1);
641    _Traits::assign(*(this->_M_Finish()), __c);
642    ++this->_M_finish;
643  }
644
645  void pop_back() {
646    _Traits::assign(*(this->_M_Finish() - 1), _M_null());
647    this->_M_destroy_back();
648    --this->_M_finish;
649  }
650
651public:                         // Assign
652  _Self& assign(const _Self& __s)
653  { return _M_assign(__s._M_Start(), __s._M_Finish()); }
654
655  _Self& assign(const _Self& __s,
656                size_type __pos, size_type __n) {
657    if (__pos > __s.size())
658      this->_M_throw_out_of_range();
659    return _M_assign(__s._M_Start() + __pos,
660                     __s._M_Start() + __pos + (min) (__n, __s.size() - __pos));
661  }
662
663  _Self& assign(const _CharT* __s, size_type __n)
664  { _STLP_FIX_LITERAL_BUG(__s) return _M_assign(__s, __s + __n); }
665
666  _Self& assign(const _CharT* __s)
667  { _STLP_FIX_LITERAL_BUG(__s) return _M_assign(__s, __s + _Traits::length(__s)); }
668
669  _Self& assign(size_type __n, _CharT __c);
670
671#if defined (_STLP_MEMBER_TEMPLATES)
672#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
673private:                        // Helper functions for assign.
674  template <class _Integer>
675  _Self& _M_assign_dispatch(_Integer __n, _Integer __x, const __true_type& /*_Integral*/)
676  { return assign((size_type) __n, (_CharT) __x); }
677
678  template <class _InputIter>
679  _Self& _M_assign_dispatch(_InputIter __f, _InputIter __l, const __false_type& /*_Integral*/) {
680    pointer __cur = this->_M_Start();
681    while (__f != __l && __cur != this->_M_Finish()) {
682      _Traits::assign(*__cur, *__f);
683      ++__f;
684      ++__cur;
685    }
686    if (__f == __l)
687      erase(__cur, this->end());
688    else
689      _M_appendT(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));
690    return *this;
691  }
692
693public:
694  // Check to see if _InputIterator is an integer type.  If so, then
695  // it can't be an iterator.
696  template <class _InputIter>
697  _Self& assign(_InputIter __first, _InputIter __last) {
698    typedef typename _IsIntegral<_InputIter>::_Ret _Integral;
699    return _M_assign_dispatch(__first, __last, _Integral());
700  }
701#  endif
702#endif
703
704protected:
705  _Self& _M_assign(const _CharT* __f, const _CharT* __l);
706
707public:
708
709#if !defined (_STLP_MEMBER_TEMPLATES) || \
710    !defined (_STLP_NO_METHOD_SPECIALIZATION) && !defined (_STLP_NO_EXTENSIONS)
711#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
712  _Self& assign(const _CharT* __f, const _CharT* __l) {
713    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
714    return _M_assign(__f, __l);
715  }
716#  endif
717#endif
718
719public:                         // Insert
720
721  _Self& insert(size_type __pos, const _Self& __s) {
722    if (__pos > size())
723      this->_M_throw_out_of_range();
724    if (size() > max_size() - __s.size())
725      this->_M_throw_length_error();
726    _M_insert(begin() + __pos, __s._M_Start(), __s._M_Finish(), &__s == this);
727    return *this;
728  }
729
730  _Self& insert(size_type __pos, const _Self& __s,
731                size_type __beg, size_type __n) {
732    if (__pos > size() || __beg > __s.size())
733      this->_M_throw_out_of_range();
734    size_type __len = (min) (__n, __s.size() - __beg);
735    if (size() > max_size() - __len)
736      this->_M_throw_length_error();
737    _M_insert(begin() + __pos,
738              __s._M_Start() + __beg, __s._M_Start() + __beg + __len, &__s == this);
739    return *this;
740  }
741  _Self& insert(size_type __pos, const _CharT* __s, size_type __n) {
742    _STLP_FIX_LITERAL_BUG(__s)
743    if (__pos > size())
744      this->_M_throw_out_of_range();
745    if (size() > max_size() - __n)
746      this->_M_throw_length_error();
747    _M_insert(begin() + __pos, __s, __s + __n, _M_inside(__s));
748    return *this;
749  }
750
751  _Self& insert(size_type __pos, const _CharT* __s) {
752    _STLP_FIX_LITERAL_BUG(__s)
753    if (__pos > size())
754      this->_M_throw_out_of_range();
755    size_type __len = _Traits::length(__s);
756    if (size() > max_size() - __len)
757      this->_M_throw_length_error();
758    _M_insert(this->_M_Start() + __pos, __s, __s + __len, _M_inside(__s));
759    return *this;
760  }
761
762  _Self& insert(size_type __pos, size_type __n, _CharT __c) {
763    if (__pos > size())
764      this->_M_throw_out_of_range();
765    if (size() > max_size() - __n)
766      this->_M_throw_length_error();
767    insert(begin() + __pos, __n, __c);
768    return *this;
769  }
770
771  iterator insert(iterator __p, _CharT __c) {
772    _STLP_FIX_LITERAL_BUG(__p)
773    if (__p == end()) {
774      push_back(__c);
775      return this->_M_Finish() - 1;
776    }
777    else
778      return _M_insert_aux(__p, __c);
779  }
780
781  void insert(iterator __p, size_t __n, _CharT __c);
782
783protected:  // Helper functions for insert.
784
785  void _M_insert(iterator __p, const _CharT* __first, const _CharT* __last, bool __self_ref);
786
787  pointer _M_insert_aux(pointer, _CharT);
788
789  void _M_copy(const _CharT* __f, const _CharT* __l, _CharT* __res) {
790    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
791    _STLP_FIX_LITERAL_BUG(__res)
792    _Traits::copy(__res, __f, __l - __f);
793  }
794
795  void _M_move(const _CharT* __f, const _CharT* __l, _CharT* __res) {
796    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
797    _Traits::move(__res, __f, __l - __f);
798  }
799
800#if defined (_STLP_MEMBER_TEMPLATES)
801#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
802  template <class _ForwardIter>
803  void _M_insert_overflow(iterator __pos, _ForwardIter __first, _ForwardIter __last,
804                          difference_type __n) {
805    const size_type __old_size = this->size();
806    size_type __len = __old_size + (max)(__old_size, __STATIC_CAST(size_type,__n)) + 1;
807    pointer __new_start = this->_M_end_of_storage.allocate(__len, __len);
808    pointer __new_finish = __new_start;
809    _STLP_TRY {
810      __new_finish = uninitialized_copy(this->_M_Start(), __pos, __new_start);
811      __new_finish = uninitialized_copy(__first, __last, __new_finish);
812      __new_finish = uninitialized_copy(__pos, this->_M_Finish(), __new_finish);
813      _M_construct_null(__new_finish);
814    }
815    _STLP_UNWIND((_STLP_STD::_Destroy_Range(__new_start,__new_finish),
816                  this->_M_end_of_storage.deallocate(__new_start, __len)))
817    this->_M_destroy_range();
818    this->_M_deallocate_block();
819    this->_M_reset(__new_start, __new_finish, __new_start + __len);
820  }
821
822  template <class _InputIter>
823  void _M_insertT(iterator __p, _InputIter __first, _InputIter __last,
824                  const input_iterator_tag &) {
825    for ( ; __first != __last; ++__first) {
826      __p = insert(__p, *__first);
827      ++__p;
828    }
829  }
830
831  template <class _ForwardIter>
832  void _M_insertT(iterator __pos, _ForwardIter __first, _ForwardIter __last,
833                  const forward_iterator_tag &) {
834    if (__first != __last) {
835      difference_type __n = distance(__first, __last);
836      if (this->_M_end_of_storage._M_data - this->_M_finish >= __n + 1) {
837        const difference_type __elems_after = this->_M_finish - __pos;
838        if (__elems_after >= __n) {
839#    if defined (_STLP_USE_SHORT_STRING_OPTIM)
840          if (this->_M_using_static_buf())
841            _M_copy((this->_M_Finish() - __n) + 1, this->_M_Finish() + 1, this->_M_Finish() + 1);
842          else
843#    endif /* _STLP_USE_SHORT_STRING_OPTIM */
844          uninitialized_copy((this->_M_Finish() - __n) + 1, this->_M_Finish() + 1, this->_M_Finish() + 1);
845          this->_M_finish += __n;
846          _Traits::move(__pos + __n, __pos, (__elems_after - __n) + 1);
847          _M_copyT(__first, __last, __pos);
848        }
849        else {
850          pointer __old_finish = this->_M_Finish();
851          _ForwardIter __mid = __first;
852          advance(__mid, __elems_after + 1);
853#    if defined (_STLP_USE_SHORT_STRING_OPTIM)
854          if (this->_M_using_static_buf())
855            _M_copyT(__mid, __last, this->_M_Finish() + 1);
856          else
857#    endif /* _STLP_USE_SHORT_STRING_OPTIM */
858          uninitialized_copy(__mid, __last, this->_M_Finish() + 1);
859          this->_M_finish += __n - __elems_after;
860          _STLP_TRY {
861#    if defined (_STLP_USE_SHORT_STRING_OPTIM)
862            if (this->_M_using_static_buf())
863              _M_copy(__pos, __old_finish + 1, this->_M_Finish());
864            else
865#    endif /* _STLP_USE_SHORT_STRING_OPTIM */
866            uninitialized_copy(__pos, __old_finish + 1, this->_M_Finish());
867            this->_M_finish += __elems_after;
868          }
869          _STLP_UNWIND((this->_M_destroy_ptr_range(__old_finish + 1, this->_M_Finish()),
870                        this->_M_finish = __old_finish))
871          _M_copyT(__first, __mid, __pos);
872        }
873      }
874      else {
875        _M_insert_overflow(__pos, __first, __last, __n);
876      }
877    }
878  }
879
880  template <class _Integer>
881  void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x,
882                          const __true_type& /*Integral*/) {
883    insert(__p, (size_type) __n, (_CharT) __x);
884  }
885
886  template <class _InputIter>
887  void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last,
888                          const __false_type& /*Integral*/) {
889    _STLP_FIX_LITERAL_BUG(__p)
890    /*
891     * Within the basic_string implementation we are only going to check for
892     * self referencing if iterators are string iterators or _CharT pointers.
893     * A user could encapsulate those iterator within their own iterator interface
894     * and in this case lead to a bad behavior, this is a known limitation.
895     */
896    typedef typename _AreSameUnCVTypes<_InputIter, iterator>::_Ret _IsIterator;
897    typedef typename _AreSameUnCVTypes<_InputIter, const_iterator>::_Ret _IsConstIterator;
898    typedef typename _Lor2<_IsIterator, _IsConstIterator>::_Ret _CheckInside;
899    _M_insert_aux(__p, __first, __last, _CheckInside());
900  }
901
902  template <class _RandomIter>
903  void _M_insert_aux (iterator __p, _RandomIter __first, _RandomIter __last,
904                      const __true_type& /*_CheckInside*/) {
905    _STLP_FIX_LITERAL_BUG(__p)
906    _M_insert(__p, &(*__first), &(*__last), _M_inside(&(*__first)));
907  }
908
909  template<class _InputIter>
910  void _M_insert_aux (iterator __p, _InputIter __first, _InputIter __last,
911                      const __false_type& /*_CheckInside*/) {
912    _STLP_FIX_LITERAL_BUG(__p)
913    _M_insertT(__p, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
914  }
915
916  template <class _InputIterator>
917  void _M_copyT(_InputIterator __first, _InputIterator __last, pointer __result) {
918    _STLP_FIX_LITERAL_BUG(__result)
919    for ( ; __first != __last; ++__first, ++__result)
920      _Traits::assign(*__result, *__first);
921  }
922
923#    if !defined (_STLP_NO_METHOD_SPECIALIZATION)
924  void _M_copyT(const _CharT* __f, const _CharT* __l, _CharT* __res) {
925    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
926    _STLP_FIX_LITERAL_BUG(__res)
927    _Traits::copy(__res, __f, __l - __f);
928  }
929#    endif
930
931public:
932  // Check to see if _InputIterator is an integer type.  If so, then
933  // it can't be an iterator.
934  template <class _InputIter>
935  void insert(iterator __p, _InputIter __first, _InputIter __last) {
936    typedef typename _IsIntegral<_InputIter>::_Ret _Integral;
937    _M_insert_dispatch(__p, __first, __last, _Integral());
938  }
939#  endif
940#endif
941
942public:
943
944#if !defined (_STLP_MEMBER_TEMPLATES) || \
945    !defined (_STLP_NO_METHOD_SPECIALIZATION) && !defined (_STLP_NO_EXTENSIONS)
946  void insert(iterator __p, const _CharT* __f, const _CharT* __l) {
947    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
948    _M_insert(__p, __f, __l, _M_inside(__f));
949  }
950#endif
951
952public:                         // Erase.
953
954  _Self& erase(size_type __pos = 0, size_type __n = npos) {
955    if (__pos > size())
956      this->_M_throw_out_of_range();
957    erase(begin() + __pos, begin() + __pos + (min) (__n, size() - __pos));
958    return *this;
959  }
960
961  iterator erase(iterator __pos) {
962    // The move includes the terminating _CharT().
963    _Traits::move(__pos, __pos + 1, this->_M_Finish() - __pos);
964    this->_M_destroy_back();
965    --this->_M_finish;
966    return __pos;
967  }
968
969  iterator erase(iterator __first, iterator __last) {
970    if (__first != __last) {
971      // The move includes the terminating _CharT().
972      traits_type::move(__first, __last, (this->_M_Finish() - __last) + 1);
973      pointer __new_finish = this->_M_Finish() - (__last - __first);
974      this->_M_destroy_ptr_range(__new_finish + 1, this->_M_Finish() + 1);
975      this->_M_finish = __new_finish;
976    }
977    return __first;
978  }
979
980public:                         // Replace.  (Conceptually equivalent
981                                // to erase followed by insert.)
982  _Self& replace(size_type __pos, size_type __n, const _Self& __s) {
983    if (__pos > size())
984      this->_M_throw_out_of_range();
985    const size_type __len = (min) (__n, size() - __pos);
986    if (size() - __len >= max_size() - __s.size())
987      this->_M_throw_length_error();
988    return _M_replace(begin() + __pos, begin() + __pos + __len,
989                      __s._M_Start(), __s._M_Finish(), &__s == this);
990  }
991
992  _Self& replace(size_type __pos1, size_type __n1, const _Self& __s,
993                 size_type __pos2, size_type __n2) {
994    if (__pos1 > size() || __pos2 > __s.size())
995      this->_M_throw_out_of_range();
996    const size_type __len1 = (min) (__n1, size() - __pos1);
997    const size_type __len2 = (min) (__n2, __s.size() - __pos2);
998    if (size() - __len1 >= max_size() - __len2)
999      this->_M_throw_length_error();
1000    return _M_replace(begin() + __pos1, begin() + __pos1 + __len1,
1001                      __s._M_Start() + __pos2, __s._M_Start() + __pos2 + __len2, &__s == this);
1002  }
1003
1004  _Self& replace(size_type __pos, size_type __n1,
1005                 const _CharT* __s, size_type __n2) {
1006    _STLP_FIX_LITERAL_BUG(__s)
1007    if (__pos > size())
1008      this->_M_throw_out_of_range();
1009    const size_type __len = (min) (__n1, size() - __pos);
1010    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
1011      this->_M_throw_length_error();
1012    return _M_replace(begin() + __pos, begin() + __pos + __len,
1013                      __s, __s + __n2, _M_inside(__s));
1014  }
1015
1016  _Self& replace(size_type __pos, size_type __n1, const _CharT* __s) {
1017    _STLP_FIX_LITERAL_BUG(__s)
1018    if (__pos > size())
1019      this->_M_throw_out_of_range();
1020    const size_type __len = (min) (__n1, size() - __pos);
1021    const size_type __n2 = _Traits::length(__s);
1022    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
1023      this->_M_throw_length_error();
1024    return _M_replace(begin() + __pos, begin() + __pos + __len,
1025                      __s, __s + _Traits::length(__s), _M_inside(__s));
1026  }
1027
1028  _Self& replace(size_type __pos, size_type __n1,
1029                 size_type __n2, _CharT __c) {
1030    if (__pos > size())
1031      this->_M_throw_out_of_range();
1032    const size_type __len = (min) (__n1, size() - __pos);
1033    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
1034      this->_M_throw_length_error();
1035    return replace(begin() + __pos, begin() + __pos + __len, __n2, __c);
1036  }
1037
1038  _Self& replace(iterator __first, iterator __last, const _Self& __s) {
1039    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
1040    return _M_replace(__first, __last, __s._M_Start(), __s._M_Finish(), &__s == this);
1041  }
1042
1043  _Self& replace(iterator __first, iterator __last,
1044                 const _CharT* __s, size_type __n) {
1045    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
1046    _STLP_FIX_LITERAL_BUG(__s)
1047    return _M_replace(__first, __last, __s, __s + __n, _M_inside(__s));
1048  }
1049
1050  _Self& replace(iterator __first, iterator __last,
1051                 const _CharT* __s) {
1052    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
1053    _STLP_FIX_LITERAL_BUG(__s)
1054    return _M_replace(__first, __last, __s, __s + _Traits::length(__s), _M_inside(__s));
1055  }
1056
1057  _Self& replace(iterator __first, iterator __last, size_type __n, _CharT __c);
1058
1059protected:                        // Helper functions for replace.
1060  _Self& _M_replace(iterator __first, iterator __last,
1061                    const _CharT* __f, const _CharT* __l, bool __self_ref);
1062
1063public:
1064#if defined (_STLP_MEMBER_TEMPLATES)
1065#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
1066  template <class _Integer>
1067  _Self& _M_replace_dispatch(iterator __first, iterator __last,
1068                             _Integer __n, _Integer __x, const __true_type& /*IsIntegral*/) {
1069    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1070    return replace(__first, __last, (size_type) __n, (_CharT) __x);
1071  }
1072
1073  template <class _InputIter>
1074  _Self& _M_replace_dispatch(iterator __first, iterator __last,
1075                             _InputIter __f, _InputIter __l, const __false_type& /*IsIntegral*/) {
1076    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1077    typedef typename _AreSameUnCVTypes<_InputIter, iterator>::_Ret _IsIterator;
1078    typedef typename _AreSameUnCVTypes<_InputIter, const_iterator>::_Ret _IsConstIterator;
1079    typedef typename _Lor2<_IsIterator, _IsConstIterator>::_Ret _CheckInside;
1080    return _M_replace_aux(__first, __last, __f, __l, _CheckInside());
1081  }
1082
1083  template <class _RandomIter>
1084  _Self& _M_replace_aux(iterator __first, iterator __last,
1085                        _RandomIter __f, _RandomIter __l, __true_type const& /*_CheckInside*/) {
1086    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1087    return _M_replace(__first, __last, &(*__f), &(*__l), _M_inside(&(*__f)));
1088  }
1089
1090  template <class _InputIter>
1091  _Self& _M_replace_aux(iterator __first, iterator __last,
1092                     _InputIter __f, _InputIter __l, __false_type const& /*_CheckInside*/) {
1093    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1094    return _M_replaceT(__first, __last, __f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));
1095  }
1096
1097  template <class _InputIter>
1098  _Self& _M_replaceT(iterator __first, iterator __last,
1099                     _InputIter __f, _InputIter __l, const input_iterator_tag&__ite_tag) {
1100    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1101    for ( ; __first != __last && __f != __l; ++__first, ++__f)
1102      _Traits::assign(*__first, *__f);
1103    if (__f == __l)
1104      erase(__first, __last);
1105    else
1106      _M_insertT(__last, __f, __l, __ite_tag);
1107    return *this;
1108  }
1109
1110  template <class _ForwardIter>
1111  _Self& _M_replaceT(iterator __first, iterator __last,
1112                     _ForwardIter __f, _ForwardIter __l, const forward_iterator_tag &__ite_tag) {
1113    _STLP_FIX_LITERAL_BUG(__first) _STLP_FIX_LITERAL_BUG(__last)
1114    difference_type __n = distance(__f, __l);
1115    const difference_type __len = __last - __first;
1116    if (__len >= __n) {
1117      _M_copyT(__f, __l, __first);
1118      erase(__first + __n, __last);
1119    }
1120    else {
1121      _ForwardIter __m = __f;
1122      advance(__m, __len);
1123      _M_copyT(__f, __m, __first);
1124      _M_insertT(__last, __m, __l, __ite_tag);
1125    }
1126    return *this;
1127  }
1128
1129public:
1130  // Check to see if _InputIter is an integer type.  If so, then
1131  // it can't be an iterator.
1132  template <class _InputIter>
1133  _Self& replace(iterator __first, iterator __last,
1134                 _InputIter __f, _InputIter __l) {
1135    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
1136    typedef typename _IsIntegral<_InputIter>::_Ret _Integral;
1137    return _M_replace_dispatch(__first, __last, __f, __l,  _Integral());
1138  }
1139
1140#  endif
1141#endif
1142
1143#if !defined (_STLP_MEMBER_TEMPLATES) || \
1144    !defined (_STLP_NO_METHOD_SPECIALIZATION) && !defined (_STLP_NO_EXTENSIONS)
1145#  if !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
1146  _Self& replace(iterator __first, iterator __last,
1147                 const _CharT* __f, const _CharT* __l) {
1148    _STLP_FIX_LITERAL_BUG(__first)_STLP_FIX_LITERAL_BUG(__last)
1149    _STLP_FIX_LITERAL_BUG(__f) _STLP_FIX_LITERAL_BUG(__l)
1150    return _M_replace(__first, __last, __f, __l, _M_inside(__f));
1151  }
1152#  endif
1153#endif
1154
1155public:                         // Other modifier member functions.
1156
1157  size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const {
1158    _STLP_FIX_LITERAL_BUG(__s)
1159    if (__pos > size())
1160      this->_M_throw_out_of_range();
1161    const size_type __len = (min) (__n, size() - __pos);
1162    _Traits::copy(__s, this->_M_Start() + __pos, __len);
1163    return __len;
1164  }
1165
1166  void swap(_Self& __s) {
1167    this->_M_Swap(__s);
1168  }
1169
1170public:                         // Conversion to C string.
1171
1172  const _CharT* c_str() const { return this->_M_Start(); }
1173  const _CharT* data()  const { return this->_M_Start(); }
1174
1175public:                         // find.
1176
1177  size_type find(const _Self& __s, size_type __pos = 0) const
1178    { return find(__s._M_Start(), __pos, __s.size()); }
1179
1180  size_type find(const _CharT* __s, size_type __pos = 0) const
1181    { _STLP_FIX_LITERAL_BUG(__s) return find(__s, __pos, _Traits::length(__s)); }
1182
1183  size_type find(const _CharT* __s, size_type __pos, size_type __n) const;
1184
1185  // WIE: Versant schema compiler 5.2.2 ICE workaround
1186  size_type find(_CharT __c) const { return find(__c, 0); }
1187  size_type find(_CharT __c, size_type __pos /* = 0 */) const;
1188
1189public:                         // rfind.
1190
1191  size_type rfind(const _Self& __s, size_type __pos = npos) const
1192    { return rfind(__s._M_Start(), __pos, __s.size()); }
1193
1194  size_type rfind(const _CharT* __s, size_type __pos = npos) const
1195    { _STLP_FIX_LITERAL_BUG(__s) return rfind(__s, __pos, _Traits::length(__s)); }
1196
1197  size_type rfind(const _CharT* __s, size_type __pos, size_type __n) const;
1198  size_type rfind(_CharT __c, size_type __pos = npos) const;
1199
1200public:                         // find_first_of
1201
1202  size_type find_first_of(const _Self& __s, size_type __pos = 0) const
1203    { return find_first_of(__s._M_Start(), __pos, __s.size()); }
1204
1205  size_type find_first_of(const _CharT* __s, size_type __pos = 0) const
1206    { _STLP_FIX_LITERAL_BUG(__s) return find_first_of(__s, __pos, _Traits::length(__s)); }
1207
1208  size_type find_first_of(const _CharT* __s, size_type __pos,
1209                          size_type __n) const;
1210
1211  size_type find_first_of(_CharT __c, size_type __pos = 0) const
1212    { return find(__c, __pos); }
1213
1214public:                         // find_last_of
1215
1216  size_type find_last_of(const _Self& __s,
1217                         size_type __pos = npos) const
1218    { return find_last_of(__s._M_Start(), __pos, __s.size()); }
1219
1220  size_type find_last_of(const _CharT* __s, size_type __pos = npos) const
1221    { _STLP_FIX_LITERAL_BUG(__s) return find_last_of(__s, __pos, _Traits::length(__s)); }
1222
1223  size_type find_last_of(const _CharT* __s, size_type __pos,
1224                         size_type __n) const;
1225
1226  size_type find_last_of(_CharT __c, size_type __pos = npos) const {
1227    return rfind(__c, __pos);
1228  }
1229
1230public:                         // find_first_not_of
1231
1232  size_type find_first_not_of(const _Self& __s,
1233                              size_type __pos = 0) const
1234    { return find_first_not_of(__s._M_Start(), __pos, __s.size()); }
1235
1236  size_type find_first_not_of(const _CharT* __s, size_type __pos = 0) const
1237  { _STLP_FIX_LITERAL_BUG(__s) return find_first_not_of(__s, __pos, _Traits::length(__s)); }
1238
1239  size_type find_first_not_of(const _CharT* __s, size_type __pos,
1240                              size_type __n) const;
1241
1242  size_type find_first_not_of(_CharT __c, size_type __pos = 0) const;
1243
1244public:                         // find_last_not_of
1245
1246  size_type find_last_not_of(const _Self& __s,
1247                             size_type __pos = npos) const
1248  { return find_last_not_of(__s._M_Start(), __pos, __s.size()); }
1249
1250  size_type find_last_not_of(const _CharT* __s, size_type __pos = npos) const
1251    { _STLP_FIX_LITERAL_BUG(__s) return find_last_not_of(__s, __pos, _Traits::length(__s)); }
1252
1253  size_type find_last_not_of(const _CharT* __s, size_type __pos,
1254                             size_type __n) const;
1255
1256  size_type find_last_not_of(_CharT __c, size_type __pos = npos) const;
1257
1258public:                         // Substring.
1259  _Self substr(size_type __pos = 0, size_type __n = npos) const
1260  { return _Self(*this, __pos, __n, get_allocator()); }
1261
1262public:                         // Compare
1263  int compare(const _Self& __s) const
1264  { return _M_compare(this->_M_Start(), this->_M_Finish(), __s._M_Start(), __s._M_Finish()); }
1265
1266  int compare(size_type __pos1, size_type __n1,
1267              const _Self& __s) const {
1268    if (__pos1 > size())
1269      this->_M_throw_out_of_range();
1270    return _M_compare(this->_M_Start() + __pos1,
1271                      this->_M_Start() + __pos1 + (min) (__n1, size() - __pos1),
1272                      __s._M_Start(), __s._M_Finish());
1273  }
1274
1275  int compare(size_type __pos1, size_type __n1,
1276              const _Self& __s,
1277              size_type __pos2, size_type __n2) const {
1278    if (__pos1 > size() || __pos2 > __s.size())
1279      this->_M_throw_out_of_range();
1280    return _M_compare(this->_M_Start() + __pos1,
1281                      this->_M_Start() + __pos1 + (min) (__n1, size() - __pos1),
1282                      __s._M_Start() + __pos2,
1283                      __s._M_Start() + __pos2 + (min) (__n2, __s.size() - __pos2));
1284  }
1285
1286  int compare(const _CharT* __s) const {
1287    _STLP_FIX_LITERAL_BUG(__s)
1288    return _M_compare(this->_M_Start(), this->_M_Finish(), __s, __s + _Traits::length(__s));
1289  }
1290
1291  int compare(size_type __pos1, size_type __n1, const _CharT* __s) const {
1292    _STLP_FIX_LITERAL_BUG(__s)
1293    if (__pos1 > size())
1294      this->_M_throw_out_of_range();
1295    return _M_compare(this->_M_Start() + __pos1,
1296                      this->_M_Start() + __pos1 + (min) (__n1, size() - __pos1),
1297                      __s, __s + _Traits::length(__s));
1298  }
1299
1300  int compare(size_type __pos1, size_type __n1, const _CharT* __s,
1301              size_type __n2) const {
1302    _STLP_FIX_LITERAL_BUG(__s)
1303    if (__pos1 > size())
1304      this->_M_throw_out_of_range();
1305    return _M_compare(this->_M_Start() + __pos1,
1306                      this->_M_Start() + __pos1 + (min) (__n1, size() - __pos1),
1307                      __s, __s + __n2);
1308  }
1309
1310public:                        // Helper functions for compare.
1311
1312  static int _STLP_CALL _M_compare(const _CharT* __f1, const _CharT* __l1,
1313                                   const _CharT* __f2, const _CharT* __l2) {
1314    const ptrdiff_t __n1 = __l1 - __f1;
1315    const ptrdiff_t __n2 = __l2 - __f2;
1316    const int cmp = _Traits::compare(__f1, __f2, (min) (__n1, __n2));
1317    return cmp != 0 ? cmp : (__n1 < __n2 ? -1 : (__n1 > __n2 ? 1 : 0));
1318  }
1319#if defined (_STLP_USE_TEMPLATE_EXPRESSION) && !defined (_STLP_DEBUG) && !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
1320#  define _STLP_STRING_SUM_BASE(__reserve, __size, __alloc) _STLP_PRIV _String_base<_CharT,_Alloc>(__alloc, __size + 1)
1321#  include <stl/_string_sum_methods.h>
1322#  undef _STLP_STRING_SUM_BASE
1323#endif /* _STLP_USE_TEMPLATE_EXPRESSION */
1324};
1325
1326#if !defined (_STLP_STATIC_CONST_INIT_BUG)
1327#  if defined (__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ == 96)
1328template <class _CharT, class _Traits, class _Alloc>
1329const size_t basic_string<_CharT, _Traits, _Alloc>::npos = ~(size_t) 0;
1330#  endif
1331#endif
1332
1333#if defined (_STLP_USE_TEMPLATE_EXPORT)
1334_STLP_EXPORT_TEMPLATE_CLASS basic_string<char, char_traits<char>, allocator<char> >;
1335#  if defined (_STLP_HAS_WCHAR_T)
1336_STLP_EXPORT_TEMPLATE_CLASS basic_string<wchar_t, char_traits<wchar_t>, allocator<wchar_t> >;
1337#  endif
1338#endif /* _STLP_USE_TEMPLATE_EXPORT */
1339
1340#if defined (basic_string)
1341_STLP_MOVE_TO_STD_NAMESPACE
1342#  undef basic_string
1343#endif
1344
1345_STLP_END_NAMESPACE
1346
1347#if defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
1348#  include <stl/_string_workaround.h>
1349#endif
1350
1351#if defined (_STLP_DEBUG)
1352#  include <stl/debug/_string.h>
1353#endif
1354
1355_STLP_BEGIN_NAMESPACE
1356
1357// ------------------------------------------------------------
1358// Non-member functions.
1359// Swap.
1360#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
1361template <class _CharT, class _Traits, class _Alloc>
1362inline void _STLP_CALL
1363swap(basic_string<_CharT,_Traits,_Alloc>& __x,
1364     basic_string<_CharT,_Traits,_Alloc>& __y)
1365{ __x.swap(__y); }
1366#endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
1367
1368#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1369template <class _CharT, class _Traits, class _Alloc>
1370struct __move_traits<basic_string<_CharT, _Traits, _Alloc> > {
1371  typedef __stlp_movable implemented;
1372  //Completness depends on the allocator:
1373  typedef typename __move_traits<_Alloc>::complete complete;
1374};
1375/*#else
1376 * There is no need to specialize for string and wstring in this case
1377 * as the default __move_traits will already tell that string is movable
1378 * but not complete. We cannot define it as complete as nothing guaranty
1379 * that the STLport user hasn't specialized std::allocator for char or
1380 * wchar_t.
1381 */
1382#endif
1383
1384_STLP_MOVE_TO_PRIV_NAMESPACE
1385
1386template <class _CharT, class _Traits, class _Alloc>
1387void _STLP_CALL _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s,
1388                               _CharT* __buf, size_t __n);
1389
1390#if defined(_STLP_USE_WIDE_INTERFACE)
1391// A couple of functions to transfer between ASCII/Unicode
1392wstring __ASCIIToWide(const char *ascii);
1393string __WideToASCII(const wchar_t *wide);
1394#endif
1395
1396inline const char* _STLP_CALL
1397__get_c_string(const string& __str) { return __str.c_str(); }
1398
1399_STLP_MOVE_TO_STD_NAMESPACE
1400
1401_STLP_END_NAMESPACE
1402
1403#include <stl/_string_operators.h>
1404
1405#if defined(_STLP_USE_NO_IOSTREAMS) || \
1406    (defined (_STLP_EXPOSE_STREAM_IMPLEMENTATION) && !defined (_STLP_LINK_TIME_INSTANTIATION))
1407#  include <stl/_string.c>
1408#endif
1409
1410#endif /* _STLP_INTERNAL_STRING_H */
1411
1412/*
1413 * Local Variables:
1414 * mode:C++
1415 * End:
1416 */
1417