2 * Copyright (c) 1997,1998
3 * Silicon Graphics Computer Systems, Inc.
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation. Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose. It is provided "as is" without express or implied warranty.
14 #ifndef __SGI_STL_STRING
15 #define __SGI_STL_STRING
18 #include <stdexcept> // Includes stl_string_fwd.h and stl_config.h
19 #include <char_traits.h> // This header name is an extension.
25 // Standard C++ string class. This class has performance
26 // characteristics very much like vector<>, meaning, for example, that
27 // it does not perform reference-count or copy-on-write, and that
28 // concatenation of two strings is an O(N) operation.
30 // There are three reasons why basic_string is not identical to
31 // vector. First, basic_string always stores a null character at the
32 // end; this makes it possible for c_str to be a fast operation.
33 // Second, the C++ standard requires basic_string to copy elements
34 // using char_traits<>::assign, char_traits<>::copy, and
35 // char_traits<>::move. This means that all of vector<>'s low-level
36 // operations must be rewritten. Third, basic_string<> has a lot of
37 // extra functions in its interface that are convenient but, strictly
38 // speaking, redundant.
40 // Additionally, the C++ standard imposes a major restriction: according
41 // to the standard, the character type _CharT must be a POD type. This
42 // implementation weakens that restriction, and allows _CharT to be a
43 // a user-defined non-POD type. However, _CharT must still have a
44 // default constructor.
48 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
53 // Helper classes that turn char_traits into function objects.
55 template <class _Traits>
57 : public binary_function<typename _Traits::char_type,
58 typename _Traits::char_type,
61 bool operator()(const typename _Traits::char_type& __x,
62 const typename _Traits::char_type& __y) const
63 { return _Traits::eq(__x, __y); }
66 template <class _Traits>
68 : public binary_function<typename _Traits::char_type,
69 typename _Traits::char_type,
72 bool operator()(const typename _Traits::char_type& __x,
73 const typename _Traits::char_type& __y) const
74 { return _Traits::lt(__x, __y); }
77 template <class _Traits>
78 struct _Not_within_traits
79 : public unary_function<typename _Traits::char_type, bool>
81 typedef const typename _Traits::char_type* _Pointer;
82 const _Pointer _M_first;
83 const _Pointer _M_last;
85 _Not_within_traits(_Pointer __f, _Pointer __l)
86 : _M_first(__f), _M_last(__l) {}
88 bool operator()(const typename _Traits::char_type& __x) const {
89 return find_if(_M_first, _M_last,
90 bind1st(_Eq_traits<_Traits>(), __x)) == _M_last;
94 // ------------------------------------------------------------
95 // Class _String_base.
97 // _String_base is a helper class that makes it it easier to write an
98 // exception-safe version of basic_string. The constructor allocates,
99 // but does not initialize, a block of memory. The destructor
100 // deallocates, but does not destroy elements within, a block of
101 // memory. The destructor assumes that _M_start either is null, or else
102 // points to a block of memory that was allocated using _String_base's
103 // allocator and whose size is _M_end_of_storage - _M_start.
105 // Additionally, _String_base encapsulates the difference between
106 // old SGI-style allocators and standard-conforming allocators.
108 #ifdef __STL_USE_STD_ALLOCATORS
110 // General base class.
111 template <class _Tp, class _Alloc, bool _S_instanceless>
112 class _String_alloc_base {
114 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
115 allocator_type get_allocator() const { return _M_data_allocator; }
117 _String_alloc_base(const allocator_type& __a)
118 : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
122 _Tp* _M_allocate(size_t __n)
123 { return _M_data_allocator.allocate(__n); }
124 void _M_deallocate(_Tp* __p, size_t __n) {
126 _M_data_allocator.deallocate(__p, __n);
130 allocator_type _M_data_allocator;
134 _Tp* _M_end_of_storage;
137 // Specialization for instanceless allocators.
138 template <class _Tp, class _Alloc>
139 class _String_alloc_base<_Tp,_Alloc,true> {
141 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
142 allocator_type get_allocator() const { return allocator_type(); }
144 _String_alloc_base(const allocator_type&)
145 : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
148 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Alloc_type;
149 _Tp* _M_allocate(size_t __n)
150 { return _Alloc_type::allocate(__n); }
151 void _M_deallocate(_Tp* __p, size_t __n)
152 { _Alloc_type::deallocate(__p, __n); }
157 _Tp* _M_end_of_storage;
160 template <class _Tp, class _Alloc>
162 : public _String_alloc_base<_Tp, _Alloc,
163 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
166 typedef _String_alloc_base<_Tp, _Alloc,
167 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
169 typedef typename _Base::allocator_type allocator_type;
171 void _M_allocate_block(size_t __n) {
172 if (__n <= max_size()) {
173 _M_start = _M_allocate(__n);
174 _M_finish = _M_start;
175 _M_end_of_storage = _M_start + __n;
178 _M_throw_length_error();
181 void _M_deallocate_block()
182 { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
184 size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
186 _String_base(const allocator_type& __a) : _Base(__a) { }
188 _String_base(const allocator_type& __a, size_t __n) : _Base(__a)
189 { _M_allocate_block(__n); }
191 ~_String_base() { _M_deallocate_block(); }
193 void _M_throw_length_error() const;
194 void _M_throw_out_of_range() const;
197 #else /* __STL_USE_STD_ALLOCATORS */
199 template <class _Tp, class _Alloc> class _String_base {
201 typedef simple_alloc<_Tp, _Alloc> _Alloc_type;
202 typedef _Alloc allocator_type;
203 allocator_type get_allocator() const { return allocator_type(); }
207 _Tp* _M_end_of_storage;
208 // Precondition: 0 < __n <= max_size().
210 _Tp* _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); }
211 void _M_deallocate(_Tp* __p, size_t __n) {
213 _Alloc_type::deallocate(__p, __n);
216 void _M_allocate_block(size_t __n) {
217 if (__n <= max_size()) {
218 _M_start = _M_allocate(__n);
219 _M_finish = _M_start;
220 _M_end_of_storage = _M_start + __n;
223 _M_throw_length_error();
226 void _M_deallocate_block()
227 { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
229 size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
231 _String_base(const allocator_type&)
232 : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
234 _String_base(const allocator_type&, size_t __n)
235 : _M_start(0), _M_finish(0), _M_end_of_storage(0)
236 { _M_allocate_block(__n); }
238 ~_String_base() { _M_deallocate_block(); }
240 void _M_throw_length_error() const;
241 void _M_throw_out_of_range() const;
244 #endif /* __STL_USE_STD_ALLOCATORS */
246 template <class _Tp, class _Alloc>
247 void _String_base<_Tp,_Alloc>::_M_throw_length_error() const {
248 __STL_THROW(length_error("basic_string"));
251 template <class _Tp, class _Alloc>
252 void _String_base<_Tp, _Alloc>::_M_throw_out_of_range() const {
253 __STL_THROW(out_of_range("basic_string"));
256 // ------------------------------------------------------------
257 // Class basic_string.
260 // (1) [start, finish) is a valid range.
261 // (2) Each iterator in [start, finish) points to a valid object
262 // of type value_type.
263 // (3) *finish is a valid object of type value_type; in particular,
264 // it is value_type().
265 // (4) [finish + 1, end_of_storage) is a valid range.
266 // (5) Each iterator in [finish + 1, end_of_storage) points to
267 // unininitialized memory.
269 // Note one important consequence: a string of length n must manage
270 // a block of memory whose size is at least n + 1.
273 template <class _CharT, class _Traits, class _Alloc>
274 class basic_string : private _String_base<_CharT,_Alloc> {
276 typedef _CharT value_type;
277 typedef _Traits traits_type;
279 typedef value_type* pointer;
280 typedef const value_type* const_pointer;
281 typedef value_type& reference;
282 typedef const value_type& const_reference;
283 typedef size_t size_type;
284 typedef ptrdiff_t difference_type;
286 typedef const value_type* const_iterator;
287 typedef value_type* iterator;
288 typedef reverse_iterator<const_iterator> const_reverse_iterator;
289 typedef reverse_iterator<iterator> reverse_iterator;
291 static const size_type npos = -1;
293 typedef _String_base<_CharT,_Alloc> _Base;
295 public: // Constructor, destructor, assignment.
296 typedef typename _Base::allocator_type allocator_type;
297 #ifdef __STL_USE_NAMESPACES
298 using _Base::get_allocator;
299 #endif /* __STL_USE_NAMESPACES */
301 explicit basic_string(const allocator_type& __a = allocator_type())
302 : _Base(__a, 8) { construct(_M_finish); }
304 struct _Reserve_t {};
305 basic_string(_Reserve_t, size_t __n,
306 const allocator_type& __a = allocator_type())
307 : _Base(__a, __n + 1) { construct(_M_finish); }
309 basic_string(const basic_string& __s) : _Base(__s.get_allocator())
310 { _M_range_initialize(__s.begin(), __s.end()); }
312 basic_string(const basic_string& __s, size_type __pos, size_type __n = npos,
313 const allocator_type& __a = allocator_type())
315 if (__pos > __s.size())
316 _M_throw_out_of_range();
318 _M_range_initialize(__s.begin() + __pos,
319 __s.begin() + __pos + min(__n, __s.size() - __pos));
322 basic_string(const _CharT* __s, size_type __n,
323 const allocator_type& __a = allocator_type())
325 { _M_range_initialize(__s, __s + __n); }
327 basic_string(const _CharT* __s,
328 const allocator_type& __a = allocator_type())
330 { _M_range_initialize(__s, __s + _Traits::length(__s)); }
332 basic_string(size_type __n, _CharT __c,
333 const allocator_type& __a = allocator_type())
334 : _Base(__a, __n + 1)
336 _M_finish = uninitialized_fill_n(_M_start, __n, __c);
337 _M_terminate_string();
340 // Check to see if _InputIterator is an integer type. If so, then
341 // it can't be an iterator.
342 template <class _InputIterator>
343 basic_string(_InputIterator __f, _InputIterator __l,
344 const allocator_type& __a = allocator_type())
347 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
348 _M_initialize_dispatch(__f, __l, _Integral());
351 ~basic_string() { destroy(_M_start, _M_finish + 1); }
353 basic_string& operator=(const basic_string& __s) {
355 assign(__s.begin(), __s.end());
359 basic_string& operator=(const _CharT* __s)
360 { return assign(__s, __s + _Traits::length(__s)); }
362 basic_string& operator=(_CharT __c)
363 { return assign(static_cast<size_type>(1), __c); }
365 private: // Protected members inherited from base.
366 #ifdef __STL_HAS_NAMESPACES
367 using _Base::_M_allocate;
368 using _Base::_M_deallocate;
369 using _Base::_M_allocate_block;
370 using _Base::_M_deallocate_block;
371 using _Base::_M_throw_length_error;
372 using _Base::_M_throw_out_of_range;
374 using _Base::_M_start;
375 using _Base::_M_finish;
376 using _Base::_M_end_of_storage;
377 #endif /* __STL_HAS_NAMESPACES */
380 // Helper functions used by constructors. It is a severe error for
381 // any of them to be called anywhere except from within constructors.
383 void _M_terminate_string() {
385 construct(_M_finish);
387 __STL_UNWIND(destroy(_M_start, _M_finish));
390 template <class _InputIter>
391 void _M_range_initialize(_InputIter __f, _InputIter __l,
392 input_iterator_tag) {
393 _M_allocate_block(8);
394 construct(_M_finish);
398 __STL_UNWIND(destroy(_M_start, _M_finish + 1));
401 template <class _ForwardIter>
402 void _M_range_initialize(_ForwardIter __f, _ForwardIter __l,
403 forward_iterator_tag) {
404 typename iterator_traits<_ForwardIter>::difference_type __n
405 = distance(__f, __l);
406 _M_allocate_block(__n + 1);
407 _M_finish = uninitialized_copy(__f, __l, _M_start);
408 _M_terminate_string();
411 template <class _InputIter>
412 void _M_range_initialize(_InputIter __f, _InputIter __l) {
413 typedef typename iterator_traits<_InputIter>::iterator_category _Category;
414 _M_range_initialize(__f, __l, _Category());
417 template <class _Integer>
418 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
419 _M_allocate_block(__n + 1);
420 _M_finish = uninitialized_fill_n(_M_start, __n, __x);
421 _M_terminate_string();
424 template <class _InputIter>
425 void _M_initialize_dispatch(_InputIter __f, _InputIter __l, __false_type) {
426 _M_range_initialize(__f, __l);
430 public: // Iterators.
431 iterator begin() { return _M_start; }
432 iterator end() { return _M_finish; }
433 const_iterator begin() const { return _M_start; }
434 const_iterator end() const { return _M_finish; }
436 reverse_iterator rbegin()
437 { return reverse_iterator(_M_finish); }
438 reverse_iterator rend()
439 { return reverse_iterator(_M_start); }
440 const_reverse_iterator rbegin() const
441 { return const_reverse_iterator(_M_finish); }
442 const_reverse_iterator rend() const
443 { return const_reverse_iterator(_M_start); }
445 public: // Size, capacity, etc.
446 size_type size() const { return _M_finish - _M_start; }
447 size_type length() const { return size(); }
448 #ifdef __STL_USE_NAMESPACES
449 using _Base::max_size;
450 #endif /* __STL_USE_NAMESPACES */
452 void resize(size_type __n, _CharT __c = _CharT()) {
454 erase(begin() + __n, end());
456 append(__n - size(), __c);
459 void reserve(size_type = 0);
461 size_type capacity() const { return (_M_end_of_storage - _M_start) - 1; }
465 _Traits::assign(*_M_start, _CharT());
466 destroy(_M_start+1, _M_finish+1);
467 _M_finish = _M_start;
471 bool empty() const { return _M_start == _M_finish; }
473 public: // Element access.
475 const_reference operator[](size_type __n) const
476 { return *(_M_start + __n); }
477 reference operator[](size_type __n)
478 { return *(_M_start + __n); }
480 const_reference at(size_type __n) const {
482 _M_throw_out_of_range();
483 return *(_M_start + __n);
486 reference at(size_type __n) {
488 _M_throw_out_of_range();
489 return *(_M_start + __n);
492 public: // Append, operator+=, push_back.
494 basic_string& operator+=(const basic_string& __s) { return append(__s); }
495 basic_string& operator+=(const _CharT* __s) { return append(__s); }
496 basic_string& operator+=(_CharT __c) { push_back(__c); return *this; }
498 basic_string& append(const basic_string& __s)
499 { return append(__s.begin(), __s.end()); }
501 basic_string& append(const basic_string& __s,
502 size_type __pos, size_type __n)
504 if (__pos > __s.size())
505 _M_throw_out_of_range();
506 return append(__s.begin() + __pos,
507 __s.begin() + __pos + min(__n, __s.size() - __pos));
510 basic_string& append(const _CharT* __s, size_type __n)
511 { return append(__s, __s+__n); }
513 basic_string& append(const _CharT* __s)
514 { return append(__s, __s + _Traits::length(__s)); }
516 basic_string& append(size_type __n, _CharT __c);
518 // Check to see if _InputIterator is an integer type. If so, then
519 // it can't be an iterator.
520 template <class _InputIter>
521 basic_string& append(_InputIter __first, _InputIter __last) {
522 typedef typename _Is_integer<_InputIter>::_Integral _Integral;
523 return _M_append_dispatch(__first, __last, _Integral());
526 void push_back(_CharT __c) {
527 if (_M_finish + 1 == _M_end_of_storage)
528 reserve(size() + max(size(), static_cast<size_type>(1)));
529 construct(_M_finish + 1);
530 _Traits::assign(*_M_finish, __c);
535 _Traits::assign(*(_M_finish - 1), _CharT());
540 private: // Helper functions for append.
542 template <class _InputIter>
543 basic_string& append(_InputIter __f, _InputIter __l, input_iterator_tag);
545 template <class _ForwardIter>
546 basic_string& append(_ForwardIter __f, _ForwardIter __l,
547 forward_iterator_tag);
549 template <class _Integer>
550 basic_string& _M_append_dispatch(_Integer __n, _Integer __x, __true_type) {
551 return append((size_type) __n, (_CharT) __x);
554 template <class _InputIter>
555 basic_string& _M_append_dispatch(_InputIter __f, _InputIter __l,
557 typedef typename iterator_traits<_InputIter>::iterator_category _Category;
558 return append(__f, __l, _Category());
563 basic_string& assign(const basic_string& __s)
564 { return assign(__s.begin(), __s.end()); }
566 basic_string& assign(const basic_string& __s,
567 size_type __pos, size_type __n) {
568 if (__pos > __s.size())
569 _M_throw_out_of_range();
570 return assign(__s.begin() + __pos,
571 __s.begin() + __pos + min(__n, __s.size() - __pos));
574 basic_string& assign(const _CharT* __s, size_type __n)
575 { return assign(__s, __s + __n); }
577 basic_string& assign(const _CharT* __s)
578 { return assign(__s, __s + _Traits::length(__s)); }
580 basic_string& assign(size_type __n, _CharT __c);
582 // Check to see if _InputIterator is an integer type. If so, then
583 // it can't be an iterator.
584 template <class _InputIter>
585 basic_string& assign(_InputIter __first, _InputIter __last) {
586 typedef typename _Is_integer<_InputIter>::_Integral _Integral;
587 return _M_assign_dispatch(__first, __last, _Integral());
590 basic_string& assign(const _CharT* __f, const _CharT* __l);
592 private: // Helper functions for assign.
594 template <class _Integer>
595 basic_string& _M_assign_dispatch(_Integer __n, _Integer __x, __true_type) {
596 return assign((size_type) __n, (_CharT) __x);
599 template <class _InputIter>
600 basic_string& _M_assign_dispatch(_InputIter __f, _InputIter __l,
605 basic_string& insert(size_type __pos, const basic_string& __s) {
607 _M_throw_out_of_range();
608 if (size() > max_size() - __s.size())
609 _M_throw_length_error();
610 insert(_M_start + __pos, __s.begin(), __s.end());
614 basic_string& insert(size_type __pos, const basic_string& __s,
615 size_type __beg, size_type __n) {
616 if (__pos > size() || __beg > __s.size())
617 _M_throw_out_of_range();
618 size_type __len = min(__n, __s.size() - __beg);
619 if (size() > max_size() - __len)
620 _M_throw_length_error();
621 insert(_M_start + __pos,
622 __s.begin() + __beg, __s.begin() + __beg + __len);
626 basic_string& insert(size_type __pos, const _CharT* __s, size_type __n) {
628 _M_throw_out_of_range();
629 if (size() > max_size() - __n)
630 _M_throw_length_error();
631 insert(_M_start + __pos, __s, __s + __n);
635 basic_string& insert(size_type __pos, const _CharT* __s) {
637 _M_throw_out_of_range();
638 size_type __len = _Traits::length(__s);
639 if (size() > max_size() - __len)
640 _M_throw_length_error();
641 insert(_M_start + __pos, __s, __s + __len);
645 basic_string& insert(size_type __pos, size_type __n, _CharT __c) {
647 _M_throw_out_of_range();
648 if (size() > max_size() - __n)
649 _M_throw_length_error();
650 insert(_M_start + __pos, __n, __c);
654 iterator insert(iterator __p, _CharT __c) {
655 if (__p == _M_finish) {
657 return _M_finish - 1;
660 return _M_insert_aux(__p, __c);
663 void insert(iterator __p, size_t __n, _CharT __c);
665 // Check to see if _InputIterator is an integer type. If so, then
666 // it can't be an iterator.
667 template <class _InputIter>
668 void insert(iterator __p, _InputIter __first, _InputIter __last) {
669 typedef typename _Is_integer<_InputIter>::_Integral _Integral;
670 _M_insert_dispatch(__p, __first, __last, _Integral());
673 private: // Helper functions for insert.
674 template <class _InputIter>
675 void insert(iterator __p, _InputIter, _InputIter, input_iterator_tag);
677 template <class _ForwardIter>
678 void insert(iterator __p, _ForwardIter, _ForwardIter, forward_iterator_tag);
681 template <class _Integer>
682 void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x,
684 insert(__p, (size_type) __n, (_CharT) __x);
687 template <class _InputIter>
688 void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last,
690 typedef typename iterator_traits<_InputIter>::iterator_category _Category;
691 insert(__p, __first, __last, _Category());
694 iterator _M_insert_aux(iterator, _CharT);
696 template <class _InputIterator>
698 _M_copy(_InputIterator __first, _InputIterator __last, iterator __result) {
699 for ( ; __first != __last; ++__first, ++__result)
700 _Traits::assign(*__result, *__first);
704 _M_copy(const _CharT* __first, const _CharT* __last, _CharT* __result) {
705 _Traits::copy(__result, __first, __last - __first);
710 basic_string& erase(size_type __pos = 0, size_type __n = npos) {
712 _M_throw_out_of_range();
713 erase(_M_start + __pos, _M_start + __pos + min(__n, size() - __pos));
717 iterator erase(iterator __position) {
718 // The move includes the terminating _CharT().
719 _Traits::move(__position, __position + 1, _M_finish - __position);
725 iterator erase(iterator __first, iterator __last) {
726 if (__first != __last) {
727 // The move includes the terminating _CharT().
728 _Traits::move(__first, __last, (_M_finish - __last) + 1);
729 const iterator __new_finish = _M_finish - (__last - __first);
730 destroy(__new_finish + 1, _M_finish + 1);
731 _M_finish = __new_finish;
736 public: // Replace. (Conceptually equivalent
737 // to erase followed by insert.)
738 basic_string& replace(size_type __pos, size_type __n,
739 const basic_string& __s) {
741 _M_throw_out_of_range();
742 const size_type __len = min(__n, size() - __pos);
743 if (size() - __len >= max_size() - __s.size())
744 _M_throw_length_error();
745 return replace(_M_start + __pos, _M_start + __pos + __len,
746 __s.begin(), __s.end());
749 basic_string& replace(size_type __pos1, size_type __n1,
750 const basic_string& __s,
751 size_type __pos2, size_type __n2) {
752 if (__pos1 > size() || __pos2 > __s.size())
753 _M_throw_out_of_range();
754 const size_type __len1 = min(__n1, size() - __pos1);
755 const size_type __len2 = min(__n2, __s.size() - __pos2);
756 if (size() - __len1 >= max_size() - __len2)
757 _M_throw_length_error();
758 return replace(_M_start + __pos1, _M_start + __pos1 + __len1,
759 __s._M_start + __pos2, __s._M_start + __pos2 + __len2);
762 basic_string& replace(size_type __pos, size_type __n1,
763 const _CharT* __s, size_type __n2) {
765 _M_throw_out_of_range();
766 const size_type __len = min(__n1, size() - __pos);
767 if (__n2 > max_size() || size() - __len >= max_size() - __n2)
768 _M_throw_length_error();
769 return replace(_M_start + __pos, _M_start + __pos + __len,
773 basic_string& replace(size_type __pos, size_type __n1,
776 _M_throw_out_of_range();
777 const size_type __len = min(__n1, size() - __pos);
778 const size_type __n2 = _Traits::length(__s);
779 if (__n2 > max_size() || size() - __len >= max_size() - __n2)
780 _M_throw_length_error();
781 return replace(_M_start + __pos, _M_start + __pos + __len,
782 __s, __s + _Traits::length(__s));
785 basic_string& replace(size_type __pos, size_type __n1,
786 size_type __n2, _CharT __c) {
788 _M_throw_out_of_range();
789 const size_type __len = min(__n1, size() - __pos);
790 if (__n2 > max_size() || size() - __len >= max_size() - __n2)
791 _M_throw_length_error();
792 return replace(_M_start + __pos, _M_start + __pos + __len, __n2, __c);
795 basic_string& replace(iterator __first, iterator __last,
796 const basic_string& __s)
797 { return replace(__first, __last, __s.begin(), __s.end()); }
799 basic_string& replace(iterator __first, iterator __last,
800 const _CharT* __s, size_type __n)
801 { return replace(__first, __last, __s, __s + __n); }
803 basic_string& replace(iterator __first, iterator __last,
805 return replace(__first, __last, __s, __s + _Traits::length(__s));
808 basic_string& replace(iterator __first, iterator __last,
809 size_type __n, _CharT __c);
811 // Check to see if _InputIterator is an integer type. If so, then
812 // it can't be an iterator.
813 template <class _InputIter>
814 basic_string& replace(iterator __first, iterator __last,
815 _InputIter __f, _InputIter __l) {
816 typedef typename _Is_integer<_InputIter>::_Integral _Integral;
817 return _M_replace_dispatch(__first, __last, __f, __l, _Integral());
820 private: // Helper functions for replace.
822 template <class _Integer>
823 basic_string& _M_replace_dispatch(iterator __first, iterator __last,
824 _Integer __n, _Integer __x,
826 return replace(__first, __last, (size_type) __n, (_CharT) __x);
829 template <class _InputIter>
830 basic_string& _M_replace_dispatch(iterator __first, iterator __last,
831 _InputIter __f, _InputIter __l,
833 typedef typename iterator_traits<_InputIter>::iterator_category _Category;
834 return replace(__first, __last, __f, __l, _Category());
837 template <class _InputIter>
838 basic_string& replace(iterator __first, iterator __last,
839 _InputIter __f, _InputIter __l, input_iterator_tag);
841 template <class _ForwardIter>
842 basic_string& replace(iterator __first, iterator __last,
843 _ForwardIter __f, _ForwardIter __l,
844 forward_iterator_tag);
846 public: // Other modifier member functions.
848 size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const {
850 _M_throw_out_of_range();
851 const size_type __len = min(__n, size() - __pos);
852 _Traits::copy(__s, _M_start + __pos, __len);
856 void swap(basic_string& __s) {
857 __STD::swap(_M_start, __s._M_start);
858 __STD::swap(_M_finish, __s._M_finish);
859 __STD::swap(_M_end_of_storage, __s._M_end_of_storage);
862 public: // Conversion to C string.
864 const _CharT* c_str() const { return _M_start; }
865 const _CharT* data() const { return _M_start; }
869 size_type find(const basic_string& __s, size_type __pos = 0) const
870 { return find(__s.begin(), __pos, __s.size()); }
872 size_type find(const _CharT* __s, size_type __pos = 0) const
873 { return find(__s, __pos, _Traits::length(__s)); }
875 size_type find(const _CharT* __s, size_type __pos, size_type __n) const;
876 size_type find(_CharT __c, size_type __pos = 0) const;
880 size_type rfind(const basic_string& __s, size_type __pos = npos) const
881 { return rfind(__s.begin(), __pos, __s.size()); }
883 size_type rfind(const _CharT* __s, size_type __pos = npos) const
884 { return rfind(__s, __pos, _Traits::length(__s)); }
886 size_type rfind(const _CharT* __s, size_type __pos, size_type __n) const;
887 size_type rfind(_CharT __c, size_type __pos = npos) const;
889 public: // find_first_of
891 size_type find_first_of(const basic_string& __s, size_type __pos = 0) const
892 { return find_first_of(__s.begin(), __pos, __s.size()); }
894 size_type find_first_of(const _CharT* __s, size_type __pos = 0) const
895 { return find_first_of(__s, __pos, _Traits::length(__s)); }
897 size_type find_first_of(const _CharT* __s, size_type __pos,
898 size_type __n) const;
900 size_type find_first_of(_CharT __c, size_type __pos = 0) const
901 { return find(__c, __pos); }
903 public: // find_last_of
905 size_type find_last_of(const basic_string& __s,
906 size_type __pos = npos) const
907 { return find_last_of(__s.begin(), __pos, __s.size()); }
909 size_type find_last_of(const _CharT* __s, size_type __pos = npos) const
910 { return find_last_of(__s, __pos, _Traits::length(__s)); }
912 size_type find_last_of(const _CharT* __s, size_type __pos,
913 size_type __n) const;
915 size_type find_last_of(_CharT __c, size_type __pos = npos) const {
916 return rfind(__c, __pos);
919 public: // find_first_not_of
921 size_type find_first_not_of(const basic_string& __s,
922 size_type __pos = 0) const
923 { return find_first_not_of(__s.begin(), __pos, __s.size()); }
925 size_type find_first_not_of(const _CharT* __s, size_type __pos = 0) const
926 { return find_first_not_of(__s, __pos, _Traits::length(__s)); }
928 size_type find_first_not_of(const _CharT* __s, size_type __pos,
929 size_type __n) const;
931 size_type find_first_not_of(_CharT __c, size_type __pos = 0) const;
933 public: // find_last_not_of
935 size_type find_last_not_of(const basic_string& __s,
936 size_type __pos = npos) const
937 { return find_last_not_of(__s.begin(), __pos, __s.size()); }
939 size_type find_last_not_of(const _CharT* __s, size_type __pos = npos) const
940 { return find_last_not_of(__s, __pos, _Traits::length(__s)); }
942 size_type find_last_not_of(const _CharT* __s, size_type __pos,
943 size_type __n) const;
945 size_type find_last_not_of(_CharT __c, size_type __pos = npos) const;
947 public: // Substring.
949 basic_string substr(size_type __pos = 0, size_type __n = npos) const {
951 _M_throw_out_of_range();
952 return basic_string(_M_start + __pos,
953 _M_start + __pos + min(__n, size() - __pos));
958 int compare(const basic_string& __s) const
959 { return _M_compare(_M_start, _M_finish, __s._M_start, __s._M_finish); }
961 int compare(size_type __pos1, size_type __n1,
962 const basic_string& __s) const {
964 _M_throw_out_of_range();
965 return _M_compare(_M_start + __pos1,
966 _M_start + __pos1 + min(__n1, size() - __pos1),
967 __s._M_start, __s._M_finish);
970 int compare(size_type __pos1, size_type __n1,
971 const basic_string& __s,
972 size_type __pos2, size_type __n2) const {
973 if (__pos1 > size() || __pos2 > __s.size())
974 _M_throw_out_of_range();
975 return _M_compare(_M_start + __pos1,
976 _M_start + __pos1 + min(__n1, size() - __pos1),
977 __s._M_start + __pos2,
978 __s._M_start + __pos2 + min(__n2, size() - __pos2));
981 int compare(const _CharT* __s) const {
982 return _M_compare(_M_start, _M_finish, __s, __s + _Traits::length(__s));
985 int compare(size_type __pos1, size_type __n1, const _CharT* __s) const {
987 _M_throw_out_of_range();
988 return _M_compare(_M_start + __pos1,
989 _M_start + __pos1 + min(__n1, size() - __pos1),
990 __s, __s + _Traits::length(__s));
993 int compare(size_type __pos1, size_type __n1, const _CharT* __s,
994 size_type __n2) const {
996 _M_throw_out_of_range();
997 return _M_compare(_M_start + __pos1,
998 _M_start + __pos1 + min(__n1, size() - __pos1),
1002 private: // Helper functions for compare.
1004 static int _M_compare(const _CharT* __f1, const _CharT* __l1,
1005 const _CharT* __f2, const _CharT* __l2) {
1006 const ptrdiff_t __n1 = __l1 - __f1;
1007 const ptrdiff_t __n2 = __l2 - __f2;
1008 const int cmp = _Traits::compare(__f1, __f2, min(__n1, __n2));
1009 return cmp != 0 ? cmp : (__n1 < __n2 ? -1 : (__n1 > __n2 ? 1 : 0));
1012 friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&,
1013 const basic_string&);
1014 friend bool operator< __STL_NULL_TMPL_ARGS (const _CharT*,
1015 const basic_string&);
1016 friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&,
1022 // ------------------------------------------------------------
1023 // Non-inline declarations.
1025 template <class _CharT, class _Traits, class _Alloc>
1026 const basic_string<_CharT,_Traits,_Alloc>::size_type
1027 basic_string<_CharT,_Traits,_Alloc>::npos;
1029 // Change the string's capacity so that it is large enough to hold
1030 // at least __res_arg elements, plus the terminating _CharT(). Note that,
1031 // if __res_arg < capacity(), this member function may actually decrease
1032 // the string's capacity.
1033 template <class _CharT, class _Traits, class _Alloc>
1034 void basic_string<_CharT,_Traits,_Alloc>::reserve(size_type __res_arg) {
1035 if (__res_arg > max_size())
1036 _M_throw_length_error();
1038 size_type __n = max(__res_arg, size()) + 1;
1039 pointer __new_start = _M_allocate(__n);
1040 pointer __new_finish = __new_start;
1043 __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
1044 construct(__new_finish);
1046 __STL_UNWIND((destroy(__new_start, __new_finish),
1047 _M_deallocate(__new_start, __n)));
1049 destroy(_M_start, _M_finish + 1);
1050 _M_deallocate_block();
1051 _M_start = __new_start;
1052 _M_finish = __new_finish;
1053 _M_end_of_storage = __new_start + __n;
1056 template <class _CharT, class _Traits, class _Alloc>
1057 basic_string<_CharT,_Traits,_Alloc>&
1058 basic_string<_CharT,_Traits,_Alloc>::append(size_type __n, _CharT __c) {
1059 if (__n > max_size() || size() > max_size() - __n)
1060 _M_throw_length_error();
1061 if (size() + __n > capacity())
1062 reserve(size() + max(size(), __n));
1064 uninitialized_fill_n(_M_finish + 1, __n - 1, __c);
1066 construct(_M_finish + __n);
1068 __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
1069 _Traits::assign(*_M_finish, __c);
1075 template <class _Tp, class _Traits, class _Alloc>
1076 template <class _InputIterator>
1077 basic_string<_Tp, _Traits, _Alloc>&
1078 basic_string<_Tp, _Traits, _Alloc>::append(_InputIterator __first,
1079 _InputIterator __last,
1080 input_iterator_tag) {
1081 for ( ; __first != __last ; ++__first)
1082 push_back(*__first);
1086 template <class _Tp, class _Traits, class _Alloc>
1087 template <class _ForwardIter>
1088 basic_string<_Tp, _Traits, _Alloc>&
1089 basic_string<_Tp, _Traits, _Alloc>::append(_ForwardIter __first,
1090 _ForwardIter __last,
1091 forward_iterator_tag) {
1092 if (__first != __last) {
1093 const size_type __old_size = size();
1094 typename iterator_traits<_ForwardIter>::difference_type __n
1095 = distance(__first, __last);
1096 if (__n > max_size() || __old_size > max_size() - __n)
1097 _M_throw_length_error();
1098 if (__old_size + __n > capacity()) {
1099 const size_type __len = __old_size +
1100 max(__old_size, static_cast<size_type>(__n)) + 1;
1101 pointer __new_start = _M_allocate(__len);
1102 pointer __new_finish = __new_start;
1104 __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
1105 __new_finish = uninitialized_copy(__first, __last, __new_finish);
1106 construct(__new_finish);
1108 __STL_UNWIND((destroy(__new_start,__new_finish),
1109 _M_deallocate(__new_start,__len)));
1110 destroy(_M_start, _M_finish + 1);
1111 _M_deallocate_block();
1112 _M_start = __new_start;
1113 _M_finish = __new_finish;
1114 _M_end_of_storage = __new_start + __len;
1117 _ForwardIter __f1 = __first;
1119 uninitialized_copy(__f1, __last, _M_finish + 1);
1121 construct(_M_finish + __n);
1123 __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
1124 _Traits::assign(*_M_finish, *__first);
1131 template <class _CharT, class _Traits, class _Alloc>
1132 basic_string<_CharT,_Traits,_Alloc>&
1133 basic_string<_CharT,_Traits,_Alloc>::assign(size_type __n, _CharT __c) {
1134 if (__n <= size()) {
1135 _Traits::assign(_M_start, __n, __c);
1136 erase(_M_start + __n, _M_finish);
1139 _Traits::assign(_M_start, size(), __c);
1140 append(__n - size(), __c);
1145 template <class _CharT, class _Traits, class _Alloc>
1146 template <class _InputIter>
1147 basic_string<_CharT,_Traits,_Alloc>& basic_string<_CharT,_Traits,_Alloc>
1148 ::_M_assign_dispatch(_InputIter __f, _InputIter __l, __false_type)
1150 pointer __cur = _M_start;
1151 while (__f != __l && __cur != _M_finish) {
1152 _Traits::assign(*__cur, *__f);
1157 erase(__cur, _M_finish);
1163 template <class _CharT, class _Traits, class _Alloc>
1164 basic_string<_CharT,_Traits,_Alloc>&
1165 basic_string<_CharT,_Traits,_Alloc>::assign(const _CharT* __f,
1168 const ptrdiff_t __n = __l - __f;
1169 if (__n <= size()) {
1170 _Traits::copy(_M_start, __f, __n);
1171 erase(_M_start + __n, _M_finish);
1174 _Traits::copy(_M_start, __f, size());
1175 append(__f + size(), __l);
1180 template <class _CharT, class _Traits, class _Alloc>
1181 basic_string<_CharT,_Traits,_Alloc>::iterator
1182 basic_string<_CharT,_Traits,_Alloc>
1183 ::_M_insert_aux(basic_string<_CharT,_Traits,_Alloc>::iterator __p,
1186 iterator __new_pos = __p;
1187 if (_M_finish + 1 < _M_end_of_storage) {
1188 construct(_M_finish + 1);
1189 _Traits::move(__p + 1, __p, _M_finish - __p);
1190 _Traits::assign(*__p, __c);
1194 const size_type __old_len = size();
1195 const size_type __len = __old_len +
1196 max(__old_len, static_cast<size_type>(1)) + 1;
1197 iterator __new_start = _M_allocate(__len);
1198 iterator __new_finish = __new_start;
1200 __new_pos = uninitialized_copy(_M_start, __p, __new_start);
1201 construct(__new_pos, __c);
1202 __new_finish = __new_pos + 1;
1203 __new_finish = uninitialized_copy(__p, _M_finish, __new_finish);
1204 construct(__new_finish);
1206 __STL_UNWIND((destroy(__new_start,__new_finish),
1207 _M_deallocate(__new_start,__len)));
1208 destroy(_M_start, _M_finish + 1);
1209 _M_deallocate_block();
1210 _M_start = __new_start;
1211 _M_finish = __new_finish;
1212 _M_end_of_storage = __new_start + __len;
1217 template <class _CharT, class _Traits, class _Alloc>
1218 void basic_string<_CharT,_Traits,_Alloc>
1219 ::insert(basic_string<_CharT,_Traits,_Alloc>::iterator __position,
1220 size_t __n, _CharT __c)
1223 if (size_type(_M_end_of_storage - _M_finish) >= __n + 1) {
1224 const size_type __elems_after = _M_finish - __position;
1225 iterator __old_finish = _M_finish;
1226 if (__elems_after >= __n) {
1227 uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
1230 _Traits::move(__position + __n,
1231 __position, (__elems_after - __n) + 1);
1232 _Traits::assign(__position, __n, __c);
1235 uninitialized_fill_n(_M_finish + 1, __n - __elems_after - 1, __c);
1236 _M_finish += __n - __elems_after;
1238 uninitialized_copy(__position, __old_finish + 1, _M_finish);
1239 _M_finish += __elems_after;
1241 __STL_UNWIND((destroy(__old_finish + 1, _M_finish),
1242 _M_finish = __old_finish));
1243 _Traits::assign(__position, __elems_after + 1, __c);
1247 const size_type __old_size = size();
1248 const size_type __len = __old_size + max(__old_size, __n) + 1;
1249 iterator __new_start = _M_allocate(__len);
1250 iterator __new_finish = __new_start;
1252 __new_finish = uninitialized_copy(_M_start, __position, __new_start);
1253 __new_finish = uninitialized_fill_n(__new_finish, __n, __c);
1254 __new_finish = uninitialized_copy(__position, _M_finish,
1256 construct(__new_finish);
1258 __STL_UNWIND((destroy(__new_start,__new_finish),
1259 _M_deallocate(__new_start,__len)));
1260 destroy(_M_start, _M_finish + 1);
1261 _M_deallocate_block();
1262 _M_start = __new_start;
1263 _M_finish = __new_finish;
1264 _M_end_of_storage = __new_start + __len;
1269 template <class _Tp, class _Traits, class _Alloc>
1270 template <class _InputIter>
1271 void basic_string<_Tp, _Traits, _Alloc>::insert(iterator __p,
1276 for ( ; __first != __last; ++__first) {
1277 __p = insert(__p, *__first);
1282 template <class _CharT, class _Traits, class _Alloc>
1283 template <class _ForwardIter>
1285 basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position,
1286 _ForwardIter __first,
1287 _ForwardIter __last,
1288 forward_iterator_tag)
1290 if (__first != __last) {
1291 const difference_type __n = distance(__first, __last);
1292 if (_M_end_of_storage - _M_finish >= __n + 1) {
1293 const difference_type __elems_after = _M_finish - __position;
1294 iterator __old_finish = _M_finish;
1295 if (__elems_after >= __n) {
1296 uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
1299 _Traits::move(__position + __n,
1300 __position, (__elems_after - __n) + 1);
1301 _M_copy(__first, __last, __position);
1304 _ForwardIter __mid = __first;
1305 advance(__mid, __elems_after + 1);
1306 uninitialized_copy(__mid, __last, _M_finish + 1);
1307 _M_finish += __n - __elems_after;
1309 uninitialized_copy(__position, __old_finish + 1, _M_finish);
1310 _M_finish += __elems_after;
1312 __STL_UNWIND((destroy(__old_finish + 1, _M_finish),
1313 _M_finish = __old_finish));
1314 _M_copy(__first, __mid, __position);
1318 const size_type __old_size = size();
1319 const size_type __len
1320 = __old_size + max(__old_size, static_cast<size_type>(__n)) + 1;
1321 pointer __new_start = _M_allocate(__len);
1322 pointer __new_finish = __new_start;
1324 __new_finish = uninitialized_copy(_M_start, __position, __new_start);
1325 __new_finish = uninitialized_copy(__first, __last, __new_finish);
1327 = uninitialized_copy(__position, _M_finish, __new_finish);
1328 construct(__new_finish);
1330 __STL_UNWIND((destroy(__new_start,__new_finish),
1331 _M_deallocate(__new_start,__len)));
1332 destroy(_M_start, _M_finish + 1);
1333 _M_deallocate_block();
1334 _M_start = __new_start;
1335 _M_finish = __new_finish;
1336 _M_end_of_storage = __new_start + __len;
1341 template <class _CharT, class _Traits, class _Alloc>
1342 basic_string<_CharT,_Traits,_Alloc>&
1343 basic_string<_CharT,_Traits,_Alloc>
1344 ::replace(iterator __first, iterator __last, size_type __n, _CharT __c)
1346 const size_type __len = static_cast<size_type>(__last - __first);
1348 _Traits::assign(__first, __n, __c);
1349 erase(__first + __n, __last);
1352 _Traits::assign(__first, __len, __c);
1353 insert(__last, __n - __len, __c);
1358 template <class _CharT, class _Traits, class _Alloc>
1359 template <class _InputIter>
1360 basic_string<_CharT,_Traits,_Alloc>&
1361 basic_string<_CharT,_Traits,_Alloc>
1362 ::replace(iterator __first, iterator __last, _InputIter __f, _InputIter __l,
1365 for ( ; __first != __last && __f != __l; ++__first, ++__f)
1366 _Traits::assign(*__first, *__f);
1369 erase(__first, __last);
1371 insert(__last, __f, __l);
1375 template <class _CharT, class _Traits, class _Alloc>
1376 template <class _ForwardIter>
1377 basic_string<_CharT,_Traits,_Alloc>&
1378 basic_string<_CharT,_Traits,_Alloc>
1379 ::replace(iterator __first, iterator __last,
1380 _ForwardIter __f, _ForwardIter __l,
1381 forward_iterator_tag)
1383 const typename iterator_traits<_ForwardIter>::difference_type __n =
1385 const difference_type __len = __last - __first;
1387 _M_copy(__f, __l, __first);
1388 erase(__first + __n, __last);
1391 _ForwardIter m = __f;
1393 _M_copy(__f, m, __first);
1394 insert(__last, m, __l);
1399 template <class _CharT, class _Traits, class _Alloc>
1400 basic_string<_CharT,_Traits,_Alloc>::size_type
1401 basic_string<_CharT,_Traits,_Alloc>
1402 ::find(const _CharT* __s, size_type __pos, size_type __n) const
1404 if (__pos >= size())
1407 const const_iterator __result =
1408 search(_M_start + __pos, _M_finish,
1409 __s, __s + __n, _Eq_traits<_Traits>());
1410 return __result != _M_finish ? __result - begin() : npos;
1414 template <class _CharT, class _Traits, class _Alloc>
1415 basic_string<_CharT,_Traits,_Alloc>::size_type
1416 basic_string<_CharT,_Traits,_Alloc>
1417 ::find(_CharT __c, size_type __pos) const
1419 if (__pos >= size())
1422 const const_iterator __result =
1423 find_if(_M_start + __pos, _M_finish,
1424 bind2nd(_Eq_traits<_Traits>(), __c));
1425 return __result != _M_finish ? __result - begin() : npos;
1429 template <class _CharT, class _Traits, class _Alloc>
1430 basic_string<_CharT,_Traits,_Alloc>::size_type
1431 basic_string<_CharT,_Traits,_Alloc>
1432 ::rfind(const _CharT* __s, size_type __pos, size_type __n) const
1434 const size_t __len = size();
1439 return min(__len, __pos);
1441 const const_iterator __last = begin() + min(__len - __n, __pos) + __n;
1442 const const_iterator __result = find_end(begin(), __last,
1444 _Eq_traits<_Traits>());
1445 return __result != __last ? __result - begin() : npos;
1449 template <class _CharT, class _Traits, class _Alloc>
1450 basic_string<_CharT,_Traits,_Alloc>::size_type
1451 basic_string<_CharT,_Traits,_Alloc>
1452 ::rfind(_CharT __c, size_type __pos) const
1454 const size_type __len = size();
1459 const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
1460 const_reverse_iterator __rresult =
1461 find_if(const_reverse_iterator(__last), rend(),
1462 bind2nd(_Eq_traits<_Traits>(), __c));
1463 return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
1467 template <class _CharT, class _Traits, class _Alloc>
1468 basic_string<_CharT,_Traits,_Alloc>::size_type
1469 basic_string<_CharT,_Traits,_Alloc>
1470 ::find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
1472 if (__pos >= size())
1475 const const_iterator __result = std::find_first_of(begin() + __pos, end(),
1477 _Eq_traits<_Traits>());
1478 return __result != _M_finish ? __result - begin() : npos;
1483 template <class _CharT, class _Traits, class _Alloc>
1484 basic_string<_CharT,_Traits,_Alloc>::size_type
1485 basic_string<_CharT,_Traits,_Alloc>
1486 ::find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
1488 const size_type __len = size();
1493 const const_iterator __last = _M_start + min(__len - 1, __pos) + 1;
1494 const const_reverse_iterator __rresult =
1495 std::find_first_of(const_reverse_iterator(__last), rend(),
1497 _Eq_traits<_Traits>());
1498 return __rresult != rend() ? (__rresult.base() - 1) - _M_start : npos;
1503 template <class _CharT, class _Traits, class _Alloc>
1504 basic_string<_CharT,_Traits,_Alloc>::size_type
1505 basic_string<_CharT,_Traits,_Alloc>
1506 ::find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1511 const_iterator __result = find_if(_M_start + __pos, _M_finish,
1512 _Not_within_traits<_Traits>(__s, __s + __n));
1513 return __result != _M_finish ? __result - _M_start : npos;
1517 template <class _CharT, class _Traits, class _Alloc>
1518 basic_string<_CharT,_Traits,_Alloc>::size_type
1519 basic_string<_CharT,_Traits,_Alloc>
1520 ::find_first_not_of(_CharT __c, size_type __pos) const
1525 const_iterator __result
1526 = find_if(begin() + __pos, end(),
1527 not1(bind2nd(_Eq_traits<_Traits>(), __c)));
1528 return __result != _M_finish ? __result - begin() : npos;
1532 template <class _CharT, class _Traits, class _Alloc>
1533 basic_string<_CharT,_Traits,_Alloc>::size_type
1534 basic_string<_CharT,_Traits,_Alloc>
1535 ::find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1538 const size_type __len = size();
1543 const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
1544 const const_reverse_iterator __rresult =
1545 find_if(const_reverse_iterator(__last), rend(),
1546 _Not_within_traits<_Traits>(__s, __s + __n));
1547 return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
1551 template <class _Tp, class _Traits, class _Alloc>
1552 basic_string<_Tp, _Traits, _Alloc>::size_type
1553 basic_string<_Tp, _Traits, _Alloc>
1554 ::find_last_not_of(_Tp __c, size_type __pos) const
1556 const size_type __len = size();
1561 const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
1562 const_reverse_iterator __rresult =
1563 find_if(const_reverse_iterator(__last), rend(),
1564 not1(bind2nd(_Eq_traits<_Traits>(), __c)));
1565 return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
1569 // ------------------------------------------------------------
1570 // Non-member functions.
1574 template <class _CharT, class _Traits, class _Alloc>
1575 inline basic_string<_CharT,_Traits,_Alloc>
1576 operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
1577 const basic_string<_CharT,_Traits,_Alloc>& __y)
1579 typedef basic_string<_CharT,_Traits,_Alloc> _Str;
1580 typedef typename _Str::_Reserve_t _Reserve_t;
1581 _Str __result(_Reserve_t(), __x.size() + __y.size(), __x.get_allocator());
1582 __result.append(__x);
1583 __result.append(__y);
1587 template <class _CharT, class _Traits, class _Alloc>
1588 inline basic_string<_CharT,_Traits,_Alloc>
1589 operator+(const _CharT* __s,
1590 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1591 typedef basic_string<_CharT,_Traits,_Alloc> _Str;
1592 typedef typename _Str::_Reserve_t _Reserve_t;
1593 const size_t __n = _Traits::length(__s);
1594 _Str __result(_Reserve_t(), __n + __y.size());
1595 __result.append(__s, __s + __n);
1596 __result.append(__y);
1600 template <class _CharT, class _Traits, class _Alloc>
1601 inline basic_string<_CharT,_Traits,_Alloc>
1602 operator+(_CharT __c,
1603 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1604 typedef basic_string<_CharT,_Traits,_Alloc> _Str;
1605 typedef typename _Str::_Reserve_t _Reserve_t;
1606 _Str __result(_Reserve_t(), 1 + __y.size());
1607 __result.push_back(__c);
1608 __result.append(__y);
1612 template <class _CharT, class _Traits, class _Alloc>
1613 inline basic_string<_CharT,_Traits,_Alloc>
1614 operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
1615 const _CharT* __s) {
1616 typedef basic_string<_CharT,_Traits,_Alloc> _Str;
1617 typedef typename _Str::_Reserve_t _Reserve_t;
1618 const size_t __n = _Traits::length(__s);
1619 _Str __result(_Reserve_t(), __x.size() + __n, __x.get_allocator());
1620 __result.append(__x);
1621 __result.append(__s, __s + __n);
1625 template <class _CharT, class _Traits, class _Alloc>
1626 inline basic_string<_CharT,_Traits,_Alloc>
1627 operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
1629 typedef basic_string<_CharT,_Traits,_Alloc> _Str;
1630 typedef typename _Str::_Reserve_t _Reserve_t;
1631 _Str __result(_Reserve_t(), __x.size() + 1, __x.get_allocator());
1632 __result.append(__x);
1633 __result.push_back(__c);
1637 // Operator== and operator!=
1639 template <class _CharT, class _Traits, class _Alloc>
1641 operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
1642 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1643 return __x.size() == __y.size() &&
1644 _Traits::compare(__x.data(), __y.data(), __x.size()) == 0;
1647 template <class _CharT, class _Traits, class _Alloc>
1649 operator==(const _CharT* __s,
1650 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1651 size_t __n = _Traits::length(__s);
1652 return __n == __y.size() && _Traits::compare(__s, __y.data(), __n) == 0;
1655 template <class _CharT, class _Traits, class _Alloc>
1657 operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
1658 const _CharT* __s) {
1659 size_t __n = _Traits::length(__s);
1660 return __x.size() == __n && _Traits::compare(__x.data(), __s, __n) == 0;
1663 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
1665 template <class _CharT, class _Traits, class _Alloc>
1667 operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1668 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1669 return !(__x == __y);
1672 template <class _CharT, class _Traits, class _Alloc>
1674 operator!=(const _CharT* __s,
1675 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1676 return !(__s == __y);
1679 template <class _CharT, class _Traits, class _Alloc>
1681 operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1682 const _CharT* __s) {
1683 return !(__x == __s);
1686 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
1688 // Operator< (and also >, <=, and >=).
1690 template <class _CharT, class _Traits, class _Alloc>
1692 operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
1693 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1694 return basic_string<_CharT,_Traits,_Alloc>
1695 ::_M_compare(__x.begin(), __x.end(), __y.begin(), __y.end()) < 0;
1698 template <class _CharT, class _Traits, class _Alloc>
1700 operator<(const _CharT* __s,
1701 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1702 size_t __n = _Traits::length(__s);
1703 return basic_string<_CharT,_Traits,_Alloc>
1704 ::_M_compare(__s, __s + __n, __y.begin(), __y.end()) < 0;
1707 template <class _CharT, class _Traits, class _Alloc>
1709 operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
1710 const _CharT* __s) {
1711 size_t __n = _Traits::length(__s);
1712 return basic_string<_CharT,_Traits,_Alloc>
1713 ::_M_compare(__x.begin(), __x.end(), __s, __s + __n) < 0;
1716 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
1718 template <class _CharT, class _Traits, class _Alloc>
1720 operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
1721 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1725 template <class _CharT, class _Traits, class _Alloc>
1727 operator>(const _CharT* __s,
1728 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1732 template <class _CharT, class _Traits, class _Alloc>
1734 operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
1735 const _CharT* __s) {
1739 template <class _CharT, class _Traits, class _Alloc>
1741 operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1742 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1743 return !(__y < __x);
1746 template <class _CharT, class _Traits, class _Alloc>
1748 operator<=(const _CharT* __s,
1749 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1750 return !(__y < __s);
1753 template <class _CharT, class _Traits, class _Alloc>
1755 operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1756 const _CharT* __s) {
1757 return !(__s < __x);
1760 template <class _CharT, class _Traits, class _Alloc>
1762 operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1763 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1764 return !(__x < __y);
1767 template <class _CharT, class _Traits, class _Alloc>
1769 operator>=(const _CharT* __s,
1770 const basic_string<_CharT,_Traits,_Alloc>& __y) {
1771 return !(__s < __y);
1774 template <class _CharT, class _Traits, class _Alloc>
1776 operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
1777 const _CharT* __s) {
1778 return !(__x < __s);
1781 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
1785 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
1787 template <class _CharT, class _Traits, class _Alloc>
1788 inline void swap(basic_string<_CharT,_Traits,_Alloc>& __x,
1789 basic_string<_CharT,_Traits,_Alloc>& __y) {
1793 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
1795 // I/O. (Using istream and ostream only, as opposed to the
1796 // basic_istream and basic_ostream templates. The result is that
1797 // these functions really don't make all that much sense except
1798 // for basic_string<char>.)
1800 inline void __sgi_string_fill(ostream& __o, size_t __n)
1802 char __f = __o.fill();
1805 for (__i = 0; __i < __n; __i++) __o.put(__f);
1808 template <class _CharT, class _Traits, class _Alloc>
1809 ostream& operator<<(ostream& __os,
1810 const basic_string<_CharT,_Traits,_Alloc>& __s)
1812 size_t __n = __s.size();
1813 size_t __pad_len = 0;
1814 const bool __left = bool(__os.flags() & ios::left);
1815 const size_t __w = __os.width();
1818 __n = min(__w, __n);
1819 __pad_len = __w - __n;
1823 __sgi_string_fill(__os, __pad_len);
1825 const size_t __nwritten = __os.rdbuf()->sputn(__s.data(), __n);
1828 __sgi_string_fill(__os, __pad_len);
1830 if (__nwritten != __n)
1831 __os.clear(__os.rdstate() | ios::failbit);
1837 template <class _CharT, class _Traits, class _Alloc>
1838 istream& operator>>(istream& __is, basic_string<_CharT,_Traits,_Alloc>& __s)
1841 if (__is.flags() & ios::skipws) {
1845 while (__is && isspace(__c));
1850 // If we arrive at end of file (or fail for some other reason) while
1851 // still discarding whitespace, then we don't try to read the string.
1855 size_t __n = __is.width();
1857 __n = static_cast<size_t>(-1);
1866 else if (isspace(__c)) {
1874 // If we have successfully read some characters, and then arrive
1875 // at end of file, the stream should still be marked good. Note
1876 // that we only clear errors that are due to EOF, not other kinds
1878 if (__s.size() != 0 && __is.eof())
1879 __is.clear((~ios::eofbit & ~ios::failbit) & __is.rdstate());
1886 template <class _CharT, class _Traits, class _Alloc>
1887 istream& getline(istream& __is,
1888 basic_string<_CharT,_Traits,_Alloc>& __s,
1889 _CharT __delim = '\n') {
1895 while (__nread < __s.max_size() && __is.get(__c)) {
1897 if (!_Traits::eq(__c, __delim))
1900 break; // Character is extracted but not appended.
1904 if (__nread == 0 || __nread >= __s.max_size())
1905 __is.clear(__is.rdstate() | ios::failbit);
1909 template <class _CharT, class _Traits, class _Alloc>
1910 void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s,
1915 const size_t __n = min(__n - 1, __s.size());
1916 copy(__s.begin(), __s.begin() + __n, __buf);
1917 __buf[__n] = _CharT();
1921 // ------------------------------------------------------------
1924 typedef basic_string<char> string;
1925 typedef basic_string<wchar_t> wstring;
1928 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1929 #pragma reset woff 1174
1930 #pragma reset woff 1375
1935 #include <stl_hash_fun.h>
1937 __STL_BEGIN_NAMESPACE
1939 template <class _CharT, class _Traits, class _Alloc>
1940 struct hash<basic_string<_CharT,_Traits,_Alloc> > {
1941 size_t operator()(const basic_string<_CharT,_Traits,_Alloc>& __s) const {
1942 unsigned long __h = 0;
1943 for (basic_string<_CharT,_Traits,_Alloc>::const_iterator __i
1954 #endif /* __SGI_STL_STRING */