include/c++/stl/stl/_string.h

   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
 105 struct _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
 117 template <class _CharT, class _Traits, class _Alloc>
 118 class 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 {
 123 protected:                        // 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
 132 public:
 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
 153 public:                         // 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*/
 293 protected:
 294   struct _CalledFromWorkaround_t {};
 295   basic_string(_CalledFromWorkaround_t, const allocator_type &__a)
 296     : _String_base<_CharT,_Alloc>(__a) {}
 297 public:
 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
 319 private:
 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
 371 public:
 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
 389 protected:
 390
 391   static _CharT _STLP_CALL _M_null()
 392   { return _STLP_DEFAULT_CONSTRUCTED(_CharT); }
 393
 394 protected:                     // 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
 419 protected:
 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
 463 public:                         // 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
 478 public:                         // 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
 507 public:                         // 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
 526 public:                         // 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)
 534 private: // 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
 594 public:
 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
 605 protected:
 606   _Self& _M_append(const _CharT* __first, const _CharT* __last);
 607
 608 public:
 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
 636 public:
 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
 651 public:                         // 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)
 673 private:                        // 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
 693 public:
 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
 704 protected:
 705   _Self& _M_assign(const _CharT* __f, const _CharT* __l);
 706
 707 public:
 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
 719 public:                         // 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
 783 protected:  // 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
 931 public:
 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
 942 public:
 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
 952 public:                         // 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
 980 public:                         // 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
1059 protected:                        // Helper functions for replace.
1060   _Self& _M_replace(iterator __first, iterator __last,
1061                     const _CharT* __f, const _CharT* __l, bool __self_ref);
1062
1063 public:
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
1129 public:
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
1155 public:                         // 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
1170 public:                         // 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
1175 public:                         // 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
1189 public:                         // 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
1200 public:                         // 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
1214 public:                         // 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
1230 public:                         // 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
1244 public:                         // 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
1258 public:                         // Substring.
1259   _Self substr(size_type __pos = 0, size_type __n = npos) const
1260   { return _Self(*this, __pos, __n, get_allocator()); }
1261
1262 public:                         // 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
1310 public:                        // 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)
1328 template <class _CharT, class _Traits, class _Alloc>
1329 const 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)
1361 template <class _CharT, class _Traits, class _Alloc>
1362 inline void _STLP_CALL
1363 swap(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)
1369 template <class _CharT, class _Traits, class _Alloc>
1370 struct __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
1386 template <class _CharT, class _Traits, class _Alloc>
1387 void _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
1392 wstring __ASCIIToWide(const char *ascii);
1393 string __WideToASCII(const wchar_t *wide);
1394 #endif
1395
1396 inline 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  */