1 // Components for manipulating sequences of characters -*- C++ -*-
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
32 // ISO C++ 14882: 21 Strings library
35 // This file is included by <string>. It is not meant to be included
38 // Written by Jason Merrill based upon the specification by Takanori Adachi
39 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882.
41 #ifndef _CPP_BITS_STRING_TCC
42 #define _CPP_BITS_STRING_TCC 1
46 template<typename _CharT, typename _Traits, typename _Alloc>
48 basic_string<_CharT, _Traits, _Alloc>::
49 _Rep::_S_terminal = _CharT();
51 template<typename _CharT, typename _Traits, typename _Alloc>
52 const typename basic_string<_CharT, _Traits, _Alloc>::size_type
53 basic_string<_CharT, _Traits, _Alloc>::
54 _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
56 template<typename _CharT, typename _Traits, typename _Alloc>
57 const typename basic_string<_CharT, _Traits, _Alloc>::size_type
58 basic_string<_CharT, _Traits, _Alloc>::npos;
60 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
61 // at static init time (before static ctors are run).
62 template<typename _CharT, typename _Traits, typename _Alloc>
63 typename basic_string<_CharT, _Traits, _Alloc>::size_type
64 basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
65 (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
67 // NB: This is the special case for Input Iterators, used in
68 // istreambuf_iterators, etc.
69 // Input Iterators have a cost structure very different from
70 // pointers, calling for a different coding style.
71 template<typename _CharT, typename _Traits, typename _Alloc>
72 template<typename _InIter>
74 basic_string<_CharT, _Traits, _Alloc>::
75 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
78 if (__beg == __end && __a == _Alloc())
79 return _S_empty_rep()._M_refcopy();
80 // Avoid reallocation for common case.
83 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
85 __buf[__i++] = *__beg;
88 _Rep* __r = _Rep::_S_create(__i, __a);
89 traits_type::copy(__r->_M_refdata(), __buf, __i);
93 // NB: this loop looks precisely this way because
94 // it avoids comparing __beg != __end any more
95 // than strictly necessary; != might be expensive!
98 _CharT* __p = __r->_M_refdata() + __r->_M_length;
99 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
104 __r->_M_length = __p - __r->_M_refdata();
105 *__p = _Rep::_S_terminal; // grrr.
106 return __r->_M_refdata();
113 // Allocate more space.
114 size_type __len = __p - __r->_M_refdata();
115 _Rep* __another = _Rep::_S_create(__len + 1, __a);
116 traits_type::copy(__another->_M_refdata(),
117 __r->_M_refdata(), __len);
118 __r->_M_destroy(__a);
120 __r->_M_length = __len;
125 __r->_M_destroy(__a);
126 __throw_exception_again;
131 template<typename _CharT, typename _Traits, typename _Alloc>
132 template <class _InIter>
134 basic_string<_CharT, _Traits, _Alloc>::
135 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
136 forward_iterator_tag)
138 size_type __dnew = static_cast<size_type>(distance(__beg, __end));
140 if (__beg == __end && __a == _Alloc())
141 return _S_empty_rep()._M_refcopy();
143 // Check for out_of_range and length_error exceptions.
144 _Rep* __r = _Rep::_S_create(__dnew, __a);
146 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
149 __r->_M_destroy(__a);
150 __throw_exception_again;
152 __r->_M_length = __dnew;
154 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr.
155 return __r->_M_refdata();
158 template<typename _CharT, typename _Traits, typename _Alloc>
160 basic_string<_CharT, _Traits, _Alloc>::
161 _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
163 if (__n == 0 && __a == _Alloc())
164 return _S_empty_rep()._M_refcopy();
166 // Check for out_of_range and length_error exceptions.
167 _Rep* __r = _Rep::_S_create(__n, __a);
171 traits_type::assign(__r->_M_refdata(), __n, __c);
175 __r->_M_destroy(__a);
176 __throw_exception_again;
178 __r->_M_length = __n;
179 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr
180 return __r->_M_refdata();
183 template<typename _CharT, typename _Traits, typename _Alloc>
184 basic_string<_CharT, _Traits, _Alloc>::
185 basic_string(const basic_string& __str)
186 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
187 __str.get_allocator())
190 template<typename _CharT, typename _Traits, typename _Alloc>
191 basic_string<_CharT, _Traits, _Alloc>::
192 basic_string(const _Alloc& __a)
193 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
196 template<typename _CharT, typename _Traits, typename _Alloc>
197 basic_string<_CharT, _Traits, _Alloc>::
198 basic_string(const basic_string& __str, size_type __pos, size_type __n)
199 : _M_dataplus(_S_construct(__str._M_check(__pos),
200 __str._M_fold(__pos, __n), _Alloc()), _Alloc())
203 template<typename _CharT, typename _Traits, typename _Alloc>
204 basic_string<_CharT, _Traits, _Alloc>::
205 basic_string(const basic_string& __str, size_type __pos,
206 size_type __n, const _Alloc& __a)
207 : _M_dataplus(_S_construct(__str._M_check(__pos),
208 __str._M_fold(__pos, __n), __a), __a)
211 template<typename _CharT, typename _Traits, typename _Alloc>
212 basic_string<_CharT, _Traits, _Alloc>::
213 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
214 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
217 template<typename _CharT, typename _Traits, typename _Alloc>
218 basic_string<_CharT, _Traits, _Alloc>::
219 basic_string(const _CharT* __s, const _Alloc& __a)
220 : _M_dataplus(_S_construct(__s, __s + traits_type::length(__s), __a), __a)
223 template<typename _CharT, typename _Traits, typename _Alloc>
224 basic_string<_CharT, _Traits, _Alloc>::
225 basic_string(size_type __n, _CharT __c, const _Alloc& __a)
226 : _M_dataplus(_S_construct(__n, __c, __a), __a)
229 template<typename _CharT, typename _Traits, typename _Alloc>
230 template<typename _InputIter>
231 basic_string<_CharT, _Traits, _Alloc>::
232 basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
233 : _M_dataplus(_S_construct(__beg, __end, __a), __a)
236 template<typename _CharT, typename _Traits, typename _Alloc>
237 basic_string<_CharT, _Traits, _Alloc>&
238 basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
240 if (_M_rep() != __str._M_rep())
243 allocator_type __a = this->get_allocator();
244 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
245 _M_rep()->_M_dispose(__a);
251 template<typename _CharT, typename _Traits, typename _Alloc>
253 basic_string<_CharT, _Traits, _Alloc>::_Rep::
254 _M_destroy(const _Alloc& __a) throw ()
256 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
257 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
260 template<typename _CharT, typename _Traits, typename _Alloc>
262 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
264 if (_M_rep()->_M_is_shared())
266 _M_rep()->_M_set_leaked();
269 // _M_mutate and, below, _M_clone, include, in the same form, an exponential
270 // growth policy, necessary to meet amortized linear time requirements of
271 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
272 // The policy is active for allocations requiring an amount of memory above
273 // system pagesize. This is consistent with the requirements of the standard:
274 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
275 template<typename _CharT, typename _Traits, typename _Alloc>
277 basic_string<_CharT, _Traits, _Alloc>::
278 _M_mutate(size_type __pos, size_type __len1, size_type __len2)
280 size_type __old_size = this->size();
281 const size_type __new_size = __old_size + __len2 - __len1;
282 const _CharT* __src = _M_data() + __pos + __len1;
283 const size_type __how_much = __old_size - __pos - __len1;
285 if (_M_rep()->_M_is_shared() || __new_size > capacity())
288 allocator_type __a = get_allocator();
289 // See below (_S_create) for the meaning and value of these
291 const size_type __pagesize = 4096;
292 const size_type __malloc_header_size = 4 * sizeof (void*);
293 // The biggest string which fits in a memory page
294 const size_type __page_capacity = (__pagesize - __malloc_header_size
295 - sizeof(_Rep) - sizeof(_CharT))
298 if (__new_size > capacity() && __new_size > __page_capacity)
299 // Growing exponentially.
300 __r = _Rep::_S_create(__new_size > 2*capacity() ?
301 __new_size : 2*capacity(), __a);
303 __r = _Rep::_S_create(__new_size, __a);
307 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
309 traits_type::copy(__r->_M_refdata() + __pos + __len2,
314 __r->_M_dispose(get_allocator());
315 __throw_exception_again;
317 _M_rep()->_M_dispose(__a);
318 _M_data(__r->_M_refdata());
320 else if (__how_much && __len1 != __len2)
323 traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
325 _M_rep()->_M_set_sharable();
326 _M_rep()->_M_length = __new_size;
327 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
328 // You cannot leave those LWG people alone for a second.
331 template<typename _CharT, typename _Traits, typename _Alloc>
333 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
335 if (__res > this->capacity() || _M_rep()->_M_is_shared())
337 if (__res > this->max_size())
338 __throw_length_error("basic_string::reserve");
339 // Make sure we don't shrink below the current size
340 if (__res < this->size())
341 __res = this->size();
342 allocator_type __a = get_allocator();
343 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
344 _M_rep()->_M_dispose(__a);
349 template<typename _CharT, typename _Traits, typename _Alloc>
350 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
352 if (_M_rep()->_M_is_leaked())
353 _M_rep()->_M_set_sharable();
354 if (__s._M_rep()->_M_is_leaked())
355 __s._M_rep()->_M_set_sharable();
356 if (this->get_allocator() == __s.get_allocator())
358 _CharT* __tmp = _M_data();
359 _M_data(__s._M_data());
362 // The code below can usually be optimized away.
365 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
366 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
367 this->get_allocator());
373 template<typename _CharT, typename _Traits, typename _Alloc>
374 typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
375 basic_string<_CharT, _Traits, _Alloc>::_Rep::
376 _S_create(size_t __capacity, const _Alloc& __alloc)
378 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
379 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
380 // 83. String::npos vs. string::max_size()
381 if (__capacity > _S_max_size)
383 if (__capacity == npos)
385 __throw_length_error("basic_string::_S_create");
387 // NB: Need an array of char_type[__capacity], plus a
388 // terminating null char_type() element, plus enough for the
389 // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
390 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
392 // The standard places no restriction on allocating more memory
393 // than is strictly needed within this layer at the moment or as
394 // requested by an explicit application call to reserve(). Many
395 // malloc implementations perform quite poorly when an
396 // application attempts to allocate memory in a stepwise fashion
397 // growing each allocation size by only 1 char. Additionally,
398 // it makes little sense to allocate less linear memory than the
399 // natural blocking size of the malloc implementation.
400 // Unfortunately, we would need a somewhat low-level calculation
401 // with tuned parameters to get this perfect for any particular
402 // malloc implementation. Fortunately, generalizations about
403 // common features seen among implementations seems to suffice.
405 // __pagesize need not match the actual VM page size for good
406 // results in practice, thus we pick a common value on the low
407 // side. __malloc_header_size is an estimate of the amount of
408 // overhead per memory allocation (in practice seen N * sizeof
409 // (void*) where N is 0, 2 or 4). According to folklore,
410 // picking this value on the high side is better than
411 // low-balling it (especially when this algorithm is used with
412 // malloc implementations that allocate memory blocks rounded up
413 // to a size which is a power of 2).
414 const size_t __pagesize = 4096; // must be 2^i * __subpagesize
415 const size_t __subpagesize = 128; // should be >> __malloc_header_size
416 const size_t __malloc_header_size = 4 * sizeof (void*);
417 if ((__size + __malloc_header_size) > __pagesize)
420 (__pagesize - ((__size + __malloc_header_size) % __pagesize))
422 __capacity += __extra / sizeof(_CharT);
423 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
425 else if (__size > __subpagesize)
428 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
430 __capacity += __extra / sizeof(_CharT);
431 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
434 // NB: Might throw, but no worries about a leak, mate: _Rep()
436 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
437 _Rep *__p = new (__place) _Rep;
438 __p->_M_capacity = __capacity;
439 __p->_M_set_sharable(); // one reference
444 template<typename _CharT, typename _Traits, typename _Alloc>
446 basic_string<_CharT, _Traits, _Alloc>::_Rep::
447 _M_clone(const _Alloc& __alloc, size_type __res)
449 // Requested capacity of the clone.
450 const size_type __requested_cap = _M_length + __res;
451 // See above (_S_create) for the meaning and value of these constants.
452 const size_type __pagesize = 4096;
453 const size_type __malloc_header_size = 4 * sizeof (void*);
454 // The biggest string which fits in a memory page.
455 const size_type __page_capacity =
456 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
459 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
460 // Growing exponentially.
461 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
462 __requested_cap : 2*_M_capacity, __alloc);
464 __r = _Rep::_S_create(__requested_cap, __alloc);
469 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
472 __r->_M_destroy(__alloc);
473 __throw_exception_again;
476 __r->_M_length = _M_length;
477 return __r->_M_refdata();
480 template<typename _CharT, typename _Traits, typename _Alloc>
482 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
484 if (__n > max_size())
485 __throw_length_error("basic_string::resize");
486 size_type __size = this->size();
488 this->append(__n - __size, __c);
489 else if (__n < __size)
491 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
494 // This is the general replace helper, which gets instantiated both
495 // for input-iterators and forward-iterators. It buffers internally and
496 // then calls _M_replace_safe. For input-iterators this is almost the
497 // best we can do, but for forward-iterators many optimizations could be
498 // conceived: f.i., when source and destination ranges do not overlap
499 // buffering is not really needed. In order to easily implement them, it
500 // could become useful to add an _M_replace(forward_iterator_tag)
501 template<typename _CharT, typename _Traits, typename _Alloc>
502 template<typename _InputIter>
503 basic_string<_CharT, _Traits, _Alloc>&
504 basic_string<_CharT, _Traits, _Alloc>::
505 _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
506 _InputIter __k2, input_iterator_tag)
508 // Save concerned source string data in a temporary.
509 basic_string __s(__k1, __k2);
510 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
513 // This is a special replace helper, which does not buffer internally
514 // and can be used in the "safe" situations involving forward-iterators,
515 // i.e., when source and destination ranges are known to not overlap.
516 // Presently, is called by _M_replace, by the various append and by
518 template<typename _CharT, typename _Traits, typename _Alloc>
519 template<typename _ForwardIter>
520 basic_string<_CharT, _Traits, _Alloc>&
521 basic_string<_CharT, _Traits, _Alloc>::
522 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
525 size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
526 size_type __dold = __i2 - __i1;
527 size_type __dmax = this->max_size();
529 if (__dmax <= __dnew)
530 __throw_length_error("basic_string::_M_replace");
531 size_type __off = __i1 - _M_ibegin();
532 _M_mutate(__off, __dold, __dnew);
534 // Invalidated __i1, __i2
536 _S_copy_chars(_M_data() + __off, __k1, __k2);
541 template<typename _CharT, typename _Traits, typename _Alloc>
542 basic_string<_CharT, _Traits, _Alloc>&
543 basic_string<_CharT, _Traits, _Alloc>::
544 replace(size_type __pos1, size_type __n1, const basic_string& __str,
545 size_type __pos2, size_type __n2)
547 const size_type __strsize = __str.size();
548 if (__pos2 > __strsize)
549 __throw_out_of_range("basic_string::replace");
550 const bool __testn2 = __n2 < __strsize - __pos2;
551 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
552 return this->replace(__pos1, __n1,
553 __str._M_data() + __pos2, __foldn2);
556 template<typename _CharT, typename _Traits, typename _Alloc>
557 basic_string<_CharT, _Traits, _Alloc>&
558 basic_string<_CharT, _Traits, _Alloc>::
559 append(const basic_string& __str)
561 // Iff appending itself, string needs to pre-reserve the
562 // correct size so that _M_mutate does not clobber the
563 // iterators formed here.
564 size_type __size = __str.size();
565 size_type __len = __size + this->size();
566 if (__len > this->capacity())
567 this->reserve(__len);
568 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
572 template<typename _CharT, typename _Traits, typename _Alloc>
573 basic_string<_CharT, _Traits, _Alloc>&
574 basic_string<_CharT, _Traits, _Alloc>::
575 append(const basic_string& __str, size_type __pos, size_type __n)
577 // Iff appending itself, string needs to pre-reserve the
578 // correct size so that _M_mutate does not clobber the
579 // iterators formed here.
580 size_type __len = min(__str.size() - __pos, __n) + this->size();
581 if (__len > this->capacity())
582 this->reserve(__len);
583 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
584 __str._M_fold(__pos, __n));
587 template<typename _CharT, typename _Traits, typename _Alloc>
588 basic_string<_CharT, _Traits, _Alloc>&
589 basic_string<_CharT, _Traits, _Alloc>::
590 append(const _CharT* __s, size_type __n)
592 size_type __len = __n + this->size();
593 if (__len > this->capacity())
594 this->reserve(__len);
595 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
598 template<typename _CharT, typename _Traits, typename _Alloc>
599 basic_string<_CharT, _Traits, _Alloc>&
600 basic_string<_CharT, _Traits, _Alloc>::
601 append(size_type __n, _CharT __c)
603 size_type __len = __n + this->size();
604 if (__len > this->capacity())
605 this->reserve(__len);
606 return this->replace(_M_iend(), _M_iend(), __n, __c);
609 template<typename _CharT, typename _Traits, typename _Alloc>
610 basic_string<_CharT, _Traits, _Alloc>
611 operator+(const _CharT* __lhs,
612 const basic_string<_CharT, _Traits, _Alloc>& __rhs)
614 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
615 typedef typename __string_type::size_type __size_type;
616 __size_type __len = _Traits::length(__lhs);
618 __str.reserve(__len + __rhs.size());
619 __str.append(__lhs, __lhs + __len);
624 template<typename _CharT, typename _Traits, typename _Alloc>
625 basic_string<_CharT, _Traits, _Alloc>
626 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
628 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
629 typedef typename __string_type::size_type __size_type;
631 __size_type __len = __rhs.size();
632 __str.reserve(__len + 1);
633 __str.append(__size_type(1), __lhs);
638 template<typename _CharT, typename _Traits, typename _Alloc>
639 basic_string<_CharT, _Traits, _Alloc>&
640 basic_string<_CharT, _Traits, _Alloc>::
641 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
643 size_type __n1 = __i2 - __i1;
644 size_type __off1 = __i1 - _M_ibegin();
645 if (max_size() - (this->size() - __n1) <= __n2)
646 __throw_length_error("basic_string::replace");
647 _M_mutate (__off1, __n1, __n2);
648 // Invalidated __i1, __i2
650 traits_type::assign(_M_data() + __off1, __n2, __c);
654 template<typename _CharT, typename _Traits, typename _Alloc>
655 typename basic_string<_CharT, _Traits, _Alloc>::size_type
656 basic_string<_CharT, _Traits, _Alloc>::
657 copy(_CharT* __s, size_type __n, size_type __pos) const
659 if (__pos > this->size())
660 __throw_out_of_range("basic_string::copy");
662 if (__n > this->size() - __pos)
663 __n = this->size() - __pos;
665 traits_type::copy(__s, _M_data() + __pos, __n);
666 // 21.3.5.7 par 3: do not append null. (good.)
670 template<typename _CharT, typename _Traits, typename _Alloc>
671 typename basic_string<_CharT, _Traits, _Alloc>::size_type
672 basic_string<_CharT, _Traits, _Alloc>::
673 find(const _CharT* __s, size_type __pos, size_type __n) const
675 size_type __size = this->size();
676 size_t __xpos = __pos;
677 const _CharT* __data = _M_data();
678 for (; __xpos + __n <= __size; ++__xpos)
679 if (traits_type::compare(__data + __xpos, __s, __n) == 0)
684 template<typename _CharT, typename _Traits, typename _Alloc>
685 typename basic_string<_CharT, _Traits, _Alloc>::size_type
686 basic_string<_CharT, _Traits, _Alloc>::
687 find(_CharT __c, size_type __pos) const
689 size_type __size = this->size();
690 size_type __ret = npos;
693 const _CharT* __data = _M_data();
694 size_type __n = __size - __pos;
695 const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
697 __ret = __p - __data;
703 template<typename _CharT, typename _Traits, typename _Alloc>
704 typename basic_string<_CharT, _Traits, _Alloc>::size_type
705 basic_string<_CharT, _Traits, _Alloc>::
706 rfind(const _CharT* __s, size_type __pos, size_type __n) const
708 size_type __size = this->size();
711 __pos = std::min(__size - __n, __pos);
712 const _CharT* __data = _M_data();
715 if (traits_type::compare(__data + __pos, __s, __n) == 0)
723 template<typename _CharT, typename _Traits, typename _Alloc>
724 typename basic_string<_CharT, _Traits, _Alloc>::size_type
725 basic_string<_CharT, _Traits, _Alloc>::
726 rfind(_CharT __c, size_type __pos) const
728 size_type __size = this->size();
731 size_t __xpos = __size - 1;
735 for (++__xpos; __xpos-- > 0; )
736 if (traits_type::eq(_M_data()[__xpos], __c))
742 template<typename _CharT, typename _Traits, typename _Alloc>
743 typename basic_string<_CharT, _Traits, _Alloc>::size_type
744 basic_string<_CharT, _Traits, _Alloc>::
745 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
747 for (; __n && __pos < this->size(); ++__pos)
749 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
756 template<typename _CharT, typename _Traits, typename _Alloc>
757 typename basic_string<_CharT, _Traits, _Alloc>::size_type
758 basic_string<_CharT, _Traits, _Alloc>::
759 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
761 size_type __size = this->size();
764 if (--__size > __pos)
768 if (traits_type::find(__s, __n, _M_data()[__size]))
771 while (__size-- != 0);
776 template<typename _CharT, typename _Traits, typename _Alloc>
777 typename basic_string<_CharT, _Traits, _Alloc>::size_type
778 basic_string<_CharT, _Traits, _Alloc>::
779 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
781 size_t __xpos = __pos;
782 for (; __xpos < this->size(); ++__xpos)
783 if (!traits_type::find(__s, __n, _M_data()[__xpos]))
788 template<typename _CharT, typename _Traits, typename _Alloc>
789 typename basic_string<_CharT, _Traits, _Alloc>::size_type
790 basic_string<_CharT, _Traits, _Alloc>::
791 find_first_not_of(_CharT __c, size_type __pos) const
793 size_t __xpos = __pos;
794 for (; __xpos < this->size(); ++__xpos)
795 if (!traits_type::eq(_M_data()[__xpos], __c))
800 template<typename _CharT, typename _Traits, typename _Alloc>
801 typename basic_string<_CharT, _Traits, _Alloc>::size_type
802 basic_string<_CharT, _Traits, _Alloc>::
803 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
805 size_type __size = this->size();
808 if (--__size > __pos)
812 if (!traits_type::find(__s, __n, _M_data()[__size]))
820 template<typename _CharT, typename _Traits, typename _Alloc>
821 typename basic_string<_CharT, _Traits, _Alloc>::size_type
822 basic_string<_CharT, _Traits, _Alloc>::
823 find_last_not_of(_CharT __c, size_type __pos) const
825 size_type __size = this->size();
828 if (--__size > __pos)
832 if (!traits_type::eq(_M_data()[__size], __c))
840 template<typename _CharT, typename _Traits, typename _Alloc>
842 basic_string<_CharT, _Traits, _Alloc>::
843 compare(size_type __pos, size_type __n, const basic_string& __str) const
845 size_type __size = this->size();
846 size_type __osize = __str.size();
848 __throw_out_of_range("basic_string::compare");
850 size_type __rsize= min(__size - __pos, __n);
851 size_type __len = min(__rsize, __osize);
852 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
854 __r = __rsize - __osize;
858 template<typename _CharT, typename _Traits, typename _Alloc>
860 basic_string<_CharT, _Traits, _Alloc>::
861 compare(size_type __pos1, size_type __n1, const basic_string& __str,
862 size_type __pos2, size_type __n2) const
864 size_type __size = this->size();
865 size_type __osize = __str.size();
866 if (__pos1 > __size || __pos2 > __osize)
867 __throw_out_of_range("basic_string::compare");
869 size_type __rsize = min(__size - __pos1, __n1);
870 size_type __rosize = min(__osize - __pos2, __n2);
871 size_type __len = min(__rsize, __rosize);
872 int __r = traits_type::compare(_M_data() + __pos1,
873 __str.data() + __pos2, __len);
875 __r = __rsize - __rosize;
880 template<typename _CharT, typename _Traits, typename _Alloc>
882 basic_string<_CharT, _Traits, _Alloc>::
883 compare(const _CharT* __s) const
885 size_type __size = this->size();
886 int __r = traits_type::compare(_M_data(), __s, __size);
888 __r = __size - traits_type::length(__s);
893 template<typename _CharT, typename _Traits, typename _Alloc>
895 basic_string <_CharT, _Traits, _Alloc>::
896 compare(size_type __pos, size_type __n1, const _CharT* __s) const
898 size_type __size = this->size();
900 __throw_out_of_range("basic_string::compare");
902 size_type __osize = traits_type::length(__s);
903 size_type __rsize = min(__size - __pos, __n1);
904 size_type __len = min(__rsize, __osize);
905 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
907 __r = __rsize - __osize;
911 template<typename _CharT, typename _Traits, typename _Alloc>
913 basic_string <_CharT, _Traits, _Alloc>::
914 compare(size_type __pos, size_type __n1, const _CharT* __s,
915 size_type __n2) const
917 size_type __size = this->size();
919 __throw_out_of_range("basic_string::compare");
921 size_type __osize = min(traits_type::length(__s), __n2);
922 size_type __rsize = min(__size - __pos, __n1);
923 size_type __len = min(__rsize, __osize);
924 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
926 __r = __rsize - __osize;
930 template <class _CharT, class _Traits, class _Alloc>
932 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
933 _CharT* __buf, typename _Alloc::size_type __bufsiz)
935 typedef typename _Alloc::size_type size_type;
936 size_type __strsize = __str.size();
937 size_type __bytes = min(__strsize, __bufsiz - 1);
938 _Traits::copy(__buf, __str.data(), __bytes);
939 __buf[__bytes] = _CharT();