1 // Components for manipulating sequences of characters -*- C++ -*-
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
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
44 #pragma GCC system_header
48 template<typename _CharT, typename _Traits, typename _Alloc>
49 const typename basic_string<_CharT, _Traits, _Alloc>::size_type
50 basic_string<_CharT, _Traits, _Alloc>::
51 _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
53 template<typename _CharT, typename _Traits, typename _Alloc>
55 basic_string<_CharT, _Traits, _Alloc>::
56 _Rep::_S_terminal = _CharT();
58 template<typename _CharT, typename _Traits, typename _Alloc>
59 const typename basic_string<_CharT, _Traits, _Alloc>::size_type
60 basic_string<_CharT, _Traits, _Alloc>::npos;
62 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
63 // at static init time (before static ctors are run).
64 template<typename _CharT, typename _Traits, typename _Alloc>
65 typename basic_string<_CharT, _Traits, _Alloc>::size_type
66 basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
67 (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
69 // NB: This is the special case for Input Iterators, used in
70 // istreambuf_iterators, etc.
71 // Input Iterators have a cost structure very different from
72 // pointers, calling for a different coding style.
73 template<typename _CharT, typename _Traits, typename _Alloc>
74 template<typename _InIter>
76 basic_string<_CharT, _Traits, _Alloc>::
77 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
80 if (__beg == __end && __a == _Alloc())
81 return _S_empty_rep()._M_refcopy();
82 // Avoid reallocation for common case.
85 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
87 __buf[__i++] = *__beg;
90 _Rep* __r = _Rep::_S_create(__i, __a);
91 traits_type::copy(__r->_M_refdata(), __buf, __i);
95 // NB: this loop looks precisely this way because
96 // it avoids comparing __beg != __end any more
97 // than strictly necessary; != might be expensive!
100 _CharT* __p = __r->_M_refdata() + __r->_M_length;
101 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
106 __r->_M_length = __p - __r->_M_refdata();
107 *__p = _Rep::_S_terminal; // grrr.
108 return __r->_M_refdata();
115 // Allocate more space.
116 size_type __len = __p - __r->_M_refdata();
117 _Rep* __another = _Rep::_S_create(__len + 1, __a);
118 traits_type::copy(__another->_M_refdata(),
119 __r->_M_refdata(), __len);
120 __r->_M_destroy(__a);
122 __r->_M_length = __len;
127 __r->_M_destroy(__a);
128 __throw_exception_again;
133 template<typename _CharT, typename _Traits, typename _Alloc>
134 template <class _InIter>
136 basic_string<_CharT, _Traits, _Alloc>::
137 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
138 forward_iterator_tag)
140 if (__beg == __end && __a == _Alloc())
141 return _S_empty_rep()._M_refcopy();
143 // NB: Not required, but considered best practice.
144 if (__builtin_expect(__beg == _InIter(), 0))
145 __throw_logic_error("attempt to create string with null pointer");
147 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
149 // Check for out_of_range and length_error exceptions.
150 _Rep* __r = _Rep::_S_create(__dnew, __a);
152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
155 __r->_M_destroy(__a);
156 __throw_exception_again;
158 __r->_M_length = __dnew;
160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr.
161 return __r->_M_refdata();
164 template<typename _CharT, typename _Traits, typename _Alloc>
166 basic_string<_CharT, _Traits, _Alloc>::
167 _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
169 if (__n == 0 && __a == _Alloc())
170 return _S_empty_rep()._M_refcopy();
172 // Check for out_of_range and length_error exceptions.
173 _Rep* __r = _Rep::_S_create(__n, __a);
177 traits_type::assign(__r->_M_refdata(), __n, __c);
181 __r->_M_destroy(__a);
182 __throw_exception_again;
184 __r->_M_length = __n;
185 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr
186 return __r->_M_refdata();
189 template<typename _CharT, typename _Traits, typename _Alloc>
190 basic_string<_CharT, _Traits, _Alloc>::
191 basic_string(const basic_string& __str)
192 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
193 __str.get_allocator())
196 template<typename _CharT, typename _Traits, typename _Alloc>
197 basic_string<_CharT, _Traits, _Alloc>::
198 basic_string(const _Alloc& __a)
199 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
202 template<typename _CharT, typename _Traits, typename _Alloc>
203 basic_string<_CharT, _Traits, _Alloc>::
204 basic_string(const basic_string& __str, size_type __pos, size_type __n)
205 : _M_dataplus(_S_construct(__str._M_check(__pos),
206 __str._M_fold(__pos, __n), _Alloc()), _Alloc())
209 template<typename _CharT, typename _Traits, typename _Alloc>
210 basic_string<_CharT, _Traits, _Alloc>::
211 basic_string(const basic_string& __str, size_type __pos,
212 size_type __n, const _Alloc& __a)
213 : _M_dataplus(_S_construct(__str._M_check(__pos),
214 __str._M_fold(__pos, __n), __a), __a)
217 template<typename _CharT, typename _Traits, typename _Alloc>
218 basic_string<_CharT, _Traits, _Alloc>::
219 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
220 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
223 template<typename _CharT, typename _Traits, typename _Alloc>
224 basic_string<_CharT, _Traits, _Alloc>::
225 basic_string(const _CharT* __s, const _Alloc& __a)
226 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
227 __s + npos, __a), __a)
230 template<typename _CharT, typename _Traits, typename _Alloc>
231 basic_string<_CharT, _Traits, _Alloc>::
232 basic_string(size_type __n, _CharT __c, const _Alloc& __a)
233 : _M_dataplus(_S_construct(__n, __c, __a), __a)
236 template<typename _CharT, typename _Traits, typename _Alloc>
237 template<typename _InputIter>
238 basic_string<_CharT, _Traits, _Alloc>::
239 basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
240 : _M_dataplus(_S_construct(__beg, __end, __a), __a)
243 template<typename _CharT, typename _Traits, typename _Alloc>
244 basic_string<_CharT, _Traits, _Alloc>&
245 basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
247 if (_M_rep() != __str._M_rep())
250 allocator_type __a = this->get_allocator();
251 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
252 _M_rep()->_M_dispose(__a);
258 template<typename _CharT, typename _Traits, typename _Alloc>
259 basic_string<_CharT, _Traits, _Alloc>&
260 basic_string<_CharT, _Traits, _Alloc>::
261 assign(const basic_string& __str, size_type __pos, size_type __n)
263 const size_type __strsize = __str.size();
264 if (__pos > __strsize)
265 __throw_out_of_range("basic_string::assign");
266 const bool __testn = __n < __strsize - __pos;
267 const size_type __newsize = __testn ? __n : __strsize - __pos;
268 return this->assign(__str._M_data() + __pos, __newsize);
271 template<typename _CharT, typename _Traits, typename _Alloc>
272 basic_string<_CharT, _Traits, _Alloc>&
273 basic_string<_CharT, _Traits, _Alloc>::
274 assign(const _CharT* __s, size_type __n)
276 if (__n > this->max_size())
277 __throw_length_error("basic_string::assign");
278 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
279 || less<const _CharT*>()(_M_data() + this->size(), __s))
280 return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
284 const size_type __pos = __s - _M_data();
286 traits_type::copy(_M_data(), __s, __n);
288 traits_type::move(_M_data(), __s, __n);
289 _M_rep()->_M_length = __n;
290 _M_data()[__n] = _Rep::_S_terminal; // grr.
295 template<typename _CharT, typename _Traits, typename _Alloc>
296 basic_string<_CharT, _Traits, _Alloc>&
297 basic_string<_CharT, _Traits, _Alloc>::
298 insert(size_type __pos1, const basic_string& __str,
299 size_type __pos2, size_type __n)
301 const size_type __strsize = __str.size();
302 if (__pos2 > __strsize)
303 __throw_out_of_range("basic_string::insert");
304 const bool __testn = __n < __strsize - __pos2;
305 const size_type __newsize = __testn ? __n : __strsize - __pos2;
306 return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
309 template<typename _CharT, typename _Traits, typename _Alloc>
310 basic_string<_CharT, _Traits, _Alloc>&
311 basic_string<_CharT, _Traits, _Alloc>::
312 insert(size_type __pos, const _CharT* __s, size_type __n)
314 const size_type __size = this->size();
316 __throw_out_of_range("basic_string::insert");
317 if (__size > this->max_size() - __n)
318 __throw_length_error("basic_string::insert");
319 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
320 || less<const _CharT*>()(_M_data() + __size, __s))
321 return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
325 // Work in-place. If _M_mutate reallocates the string, __s
326 // does not point anymore to valid data, therefore we save its
327 // offset, then we restore it.
328 const size_type __off = __s - _M_data();
329 _M_mutate(__pos, 0, __n);
330 __s = _M_data() + __off;
331 _CharT* __p = _M_data() + __pos;
332 if (__s + __n <= __p)
333 traits_type::copy(__p, __s, __n);
335 traits_type::copy(__p, __s + __n, __n);
338 traits_type::copy(__p, __s, __p - __s);
339 traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
345 template<typename _CharT, typename _Traits, typename _Alloc>
346 basic_string<_CharT, _Traits, _Alloc>&
347 basic_string<_CharT, _Traits, _Alloc>::
348 replace(size_type __pos, size_type __n1, const _CharT* __s,
351 const size_type __size = this->size();
353 __throw_out_of_range("basic_string::replace");
354 const bool __testn1 = __n1 < __size - __pos;
355 const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
356 if (__size - __foldn1 > this->max_size() - __n2)
357 __throw_length_error("basic_string::replace");
358 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
359 || less<const _CharT*>()(_M_data() + __size, __s))
360 return _M_replace_safe(_M_ibegin() + __pos,
361 _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
362 // Todo: optimized in-place replace.
364 return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
366 typename iterator_traits<const _CharT*>::iterator_category());
369 template<typename _CharT, typename _Traits, typename _Alloc>
371 basic_string<_CharT, _Traits, _Alloc>::_Rep::
372 _M_destroy(const _Alloc& __a) throw ()
374 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
375 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
378 template<typename _CharT, typename _Traits, typename _Alloc>
380 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
382 if (_M_rep()->_M_is_shared())
384 _M_rep()->_M_set_leaked();
387 // _M_mutate and, below, _M_clone, include, in the same form, an exponential
388 // growth policy, necessary to meet amortized linear time requirements of
389 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
390 // The policy is active for allocations requiring an amount of memory above
391 // system pagesize. This is consistent with the requirements of the standard:
392 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
393 template<typename _CharT, typename _Traits, typename _Alloc>
395 basic_string<_CharT, _Traits, _Alloc>::
396 _M_mutate(size_type __pos, size_type __len1, size_type __len2)
398 size_type __old_size = this->size();
399 const size_type __new_size = __old_size + __len2 - __len1;
400 const _CharT* __src = _M_data() + __pos + __len1;
401 const size_type __how_much = __old_size - __pos - __len1;
403 if (_M_rep()->_M_is_shared() || __new_size > capacity())
406 allocator_type __a = get_allocator();
407 // See below (_S_create) for the meaning and value of these
409 const size_type __pagesize = 4096;
410 const size_type __malloc_header_size = 4 * sizeof (void*);
411 // The biggest string which fits in a memory page
412 const size_type __page_capacity = (__pagesize - __malloc_header_size
413 - sizeof(_Rep) - sizeof(_CharT))
416 if (__new_size > capacity() && __new_size > __page_capacity)
417 // Growing exponentially.
418 __r = _Rep::_S_create(__new_size > 2*capacity() ?
419 __new_size : 2*capacity(), __a);
421 __r = _Rep::_S_create(__new_size, __a);
425 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
427 traits_type::copy(__r->_M_refdata() + __pos + __len2,
432 __r->_M_dispose(get_allocator());
433 __throw_exception_again;
435 _M_rep()->_M_dispose(__a);
436 _M_data(__r->_M_refdata());
438 else if (__how_much && __len1 != __len2)
441 traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
443 _M_rep()->_M_set_sharable();
444 _M_rep()->_M_length = __new_size;
445 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
446 // You cannot leave those LWG people alone for a second.
449 template<typename _CharT, typename _Traits, typename _Alloc>
451 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
453 if (__res > this->capacity() || _M_rep()->_M_is_shared())
455 if (__res > this->max_size())
456 __throw_length_error("basic_string::reserve");
457 // Make sure we don't shrink below the current size
458 if (__res < this->size())
459 __res = this->size();
460 allocator_type __a = get_allocator();
461 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
462 _M_rep()->_M_dispose(__a);
467 template<typename _CharT, typename _Traits, typename _Alloc>
468 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
470 if (_M_rep()->_M_is_leaked())
471 _M_rep()->_M_set_sharable();
472 if (__s._M_rep()->_M_is_leaked())
473 __s._M_rep()->_M_set_sharable();
474 if (this->get_allocator() == __s.get_allocator())
476 _CharT* __tmp = _M_data();
477 _M_data(__s._M_data());
480 // The code below can usually be optimized away.
483 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
484 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
485 this->get_allocator());
491 template<typename _CharT, typename _Traits, typename _Alloc>
492 typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
493 basic_string<_CharT, _Traits, _Alloc>::_Rep::
494 _S_create(size_t __capacity, const _Alloc& __alloc)
496 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
497 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
498 // 83. String::npos vs. string::max_size()
499 if (__capacity > _S_max_size)
501 if (__capacity == npos)
503 __throw_length_error("basic_string::_S_create");
505 // NB: Need an array of char_type[__capacity], plus a
506 // terminating null char_type() element, plus enough for the
507 // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
508 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
510 // The standard places no restriction on allocating more memory
511 // than is strictly needed within this layer at the moment or as
512 // requested by an explicit application call to reserve(). Many
513 // malloc implementations perform quite poorly when an
514 // application attempts to allocate memory in a stepwise fashion
515 // growing each allocation size by only 1 char. Additionally,
516 // it makes little sense to allocate less linear memory than the
517 // natural blocking size of the malloc implementation.
518 // Unfortunately, we would need a somewhat low-level calculation
519 // with tuned parameters to get this perfect for any particular
520 // malloc implementation. Fortunately, generalizations about
521 // common features seen among implementations seems to suffice.
523 // __pagesize need not match the actual VM page size for good
524 // results in practice, thus we pick a common value on the low
525 // side. __malloc_header_size is an estimate of the amount of
526 // overhead per memory allocation (in practice seen N * sizeof
527 // (void*) where N is 0, 2 or 4). According to folklore,
528 // picking this value on the high side is better than
529 // low-balling it (especially when this algorithm is used with
530 // malloc implementations that allocate memory blocks rounded up
531 // to a size which is a power of 2).
532 const size_t __pagesize = 4096; // must be 2^i * __subpagesize
533 const size_t __subpagesize = 128; // should be >> __malloc_header_size
534 const size_t __malloc_header_size = 4 * sizeof (void*);
535 if ((__size + __malloc_header_size) > __pagesize)
538 (__pagesize - ((__size + __malloc_header_size) % __pagesize))
540 __capacity += __extra / sizeof(_CharT);
541 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
543 else if (__size > __subpagesize)
546 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
548 __capacity += __extra / sizeof(_CharT);
549 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
552 // NB: Might throw, but no worries about a leak, mate: _Rep()
554 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
555 _Rep *__p = new (__place) _Rep;
556 __p->_M_capacity = __capacity;
557 __p->_M_set_sharable(); // One reference.
562 template<typename _CharT, typename _Traits, typename _Alloc>
564 basic_string<_CharT, _Traits, _Alloc>::_Rep::
565 _M_clone(const _Alloc& __alloc, size_type __res)
567 // Requested capacity of the clone.
568 const size_type __requested_cap = _M_length + __res;
569 // See above (_S_create) for the meaning and value of these constants.
570 const size_type __pagesize = 4096;
571 const size_type __malloc_header_size = 4 * sizeof (void*);
572 // The biggest string which fits in a memory page.
573 const size_type __page_capacity =
574 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
577 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
578 // Growing exponentially.
579 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
580 __requested_cap : 2*_M_capacity, __alloc);
582 __r = _Rep::_S_create(__requested_cap, __alloc);
587 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
590 __r->_M_destroy(__alloc);
591 __throw_exception_again;
594 __r->_M_length = _M_length;
595 return __r->_M_refdata();
598 template<typename _CharT, typename _Traits, typename _Alloc>
600 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
602 if (__n > max_size())
603 __throw_length_error("basic_string::resize");
604 size_type __size = this->size();
606 this->append(__n - __size, __c);
607 else if (__n < __size)
609 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
612 // This is the general replace helper, which currently gets instantiated both
613 // for input iterators and reverse iterators. It buffers internally and then
614 // calls _M_replace_safe.
615 template<typename _CharT, typename _Traits, typename _Alloc>
616 template<typename _InputIter>
617 basic_string<_CharT, _Traits, _Alloc>&
618 basic_string<_CharT, _Traits, _Alloc>::
619 _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
620 _InputIter __k2, input_iterator_tag)
622 // Save concerned source string data in a temporary.
623 basic_string __s(__k1, __k2);
624 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
627 // This is a special replace helper, which does not buffer internally
628 // and can be used in "safe" situations involving forward iterators,
629 // i.e., when source and destination ranges are known to not overlap.
630 template<typename _CharT, typename _Traits, typename _Alloc>
631 template<typename _ForwardIter>
632 basic_string<_CharT, _Traits, _Alloc>&
633 basic_string<_CharT, _Traits, _Alloc>::
634 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
637 size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2));
638 size_type __dold = __i2 - __i1;
639 size_type __dmax = this->max_size();
641 if (__dmax <= __dnew)
642 __throw_length_error("basic_string::_M_replace");
643 size_type __off = __i1 - _M_ibegin();
644 _M_mutate(__off, __dold, __dnew);
646 // Invalidated __i1, __i2
648 _S_copy_chars(_M_data() + __off, __k1, __k2);
653 template<typename _CharT, typename _Traits, typename _Alloc>
654 basic_string<_CharT, _Traits, _Alloc>&
655 basic_string<_CharT, _Traits, _Alloc>::
656 replace(size_type __pos1, size_type __n1, const basic_string& __str,
657 size_type __pos2, size_type __n2)
659 const size_type __strsize = __str.size();
660 if (__pos2 > __strsize)
661 __throw_out_of_range("basic_string::replace");
662 const bool __testn2 = __n2 < __strsize - __pos2;
663 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
664 return this->replace(__pos1, __n1,
665 __str._M_data() + __pos2, __foldn2);
668 template<typename _CharT, typename _Traits, typename _Alloc>
669 basic_string<_CharT, _Traits, _Alloc>&
670 basic_string<_CharT, _Traits, _Alloc>::
671 append(const basic_string& __str)
673 // Iff appending itself, string needs to pre-reserve the
674 // correct size so that _M_mutate does not clobber the
675 // iterators formed here.
676 size_type __size = __str.size();
677 size_type __len = __size + this->size();
678 if (__len > this->capacity())
679 this->reserve(__len);
680 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
684 template<typename _CharT, typename _Traits, typename _Alloc>
685 basic_string<_CharT, _Traits, _Alloc>&
686 basic_string<_CharT, _Traits, _Alloc>::
687 append(const basic_string& __str, size_type __pos, size_type __n)
689 // Iff appending itself, string needs to pre-reserve the
690 // correct size so that _M_mutate does not clobber the
691 // iterators formed here.
692 size_type __len = std::min(size_type(__str.size() - __pos),
694 if (__len > this->capacity())
695 this->reserve(__len);
696 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
697 __str._M_fold(__pos, __n));
700 template<typename _CharT, typename _Traits, typename _Alloc>
701 basic_string<_CharT, _Traits, _Alloc>&
702 basic_string<_CharT, _Traits, _Alloc>::
703 append(const _CharT* __s, size_type __n)
705 size_type __len = __n + this->size();
706 if (__len > this->capacity())
707 this->reserve(__len);
708 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
711 template<typename _CharT, typename _Traits, typename _Alloc>
712 basic_string<_CharT, _Traits, _Alloc>&
713 basic_string<_CharT, _Traits, _Alloc>::
714 append(size_type __n, _CharT __c)
716 size_type __len = __n + this->size();
717 if (__len > this->capacity())
718 this->reserve(__len);
719 return this->replace(_M_iend(), _M_iend(), __n, __c);
722 template<typename _CharT, typename _Traits, typename _Alloc>
723 basic_string<_CharT, _Traits, _Alloc>
724 operator+(const _CharT* __lhs,
725 const basic_string<_CharT, _Traits, _Alloc>& __rhs)
727 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
728 typedef typename __string_type::size_type __size_type;
729 __size_type __len = _Traits::length(__lhs);
731 __str.reserve(__len + __rhs.size());
732 __str.append(__lhs, __lhs + __len);
737 template<typename _CharT, typename _Traits, typename _Alloc>
738 basic_string<_CharT, _Traits, _Alloc>
739 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
741 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
742 typedef typename __string_type::size_type __size_type;
744 __size_type __len = __rhs.size();
745 __str.reserve(__len + 1);
746 __str.append(__size_type(1), __lhs);
751 template<typename _CharT, typename _Traits, typename _Alloc>
752 basic_string<_CharT, _Traits, _Alloc>&
753 basic_string<_CharT, _Traits, _Alloc>::
754 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
756 size_type __n1 = __i2 - __i1;
757 size_type __off1 = __i1 - _M_ibegin();
758 if (max_size() - (this->size() - __n1) <= __n2)
759 __throw_length_error("basic_string::replace");
760 _M_mutate (__off1, __n1, __n2);
761 // Invalidated __i1, __i2
763 traits_type::assign(_M_data() + __off1, __n2, __c);
767 template<typename _CharT, typename _Traits, typename _Alloc>
768 typename basic_string<_CharT, _Traits, _Alloc>::size_type
769 basic_string<_CharT, _Traits, _Alloc>::
770 copy(_CharT* __s, size_type __n, size_type __pos) const
772 if (__pos > this->size())
773 __throw_out_of_range("basic_string::copy");
775 if (__n > this->size() - __pos)
776 __n = this->size() - __pos;
778 traits_type::copy(__s, _M_data() + __pos, __n);
779 // 21.3.5.7 par 3: do not append null. (good.)
783 template<typename _CharT, typename _Traits, typename _Alloc>
784 typename basic_string<_CharT, _Traits, _Alloc>::size_type
785 basic_string<_CharT, _Traits, _Alloc>::
786 find(const _CharT* __s, size_type __pos, size_type __n) const
788 size_type __size = this->size();
789 size_t __xpos = __pos;
790 const _CharT* __data = _M_data();
791 for (; __xpos + __n <= __size; ++__xpos)
792 if (traits_type::compare(__data + __xpos, __s, __n) == 0)
797 template<typename _CharT, typename _Traits, typename _Alloc>
798 typename basic_string<_CharT, _Traits, _Alloc>::size_type
799 basic_string<_CharT, _Traits, _Alloc>::
800 find(_CharT __c, size_type __pos) const
802 size_type __size = this->size();
803 size_type __ret = npos;
806 const _CharT* __data = _M_data();
807 size_type __n = __size - __pos;
808 const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
810 __ret = __p - __data;
816 template<typename _CharT, typename _Traits, typename _Alloc>
817 typename basic_string<_CharT, _Traits, _Alloc>::size_type
818 basic_string<_CharT, _Traits, _Alloc>::
819 rfind(const _CharT* __s, size_type __pos, size_type __n) const
821 size_type __size = this->size();
824 __pos = std::min(size_type(__size - __n), __pos);
825 const _CharT* __data = _M_data();
828 if (traits_type::compare(__data + __pos, __s, __n) == 0)
836 template<typename _CharT, typename _Traits, typename _Alloc>
837 typename basic_string<_CharT, _Traits, _Alloc>::size_type
838 basic_string<_CharT, _Traits, _Alloc>::
839 rfind(_CharT __c, size_type __pos) const
841 size_type __size = this->size();
844 size_t __xpos = __size - 1;
848 for (++__xpos; __xpos-- > 0; )
849 if (traits_type::eq(_M_data()[__xpos], __c))
855 template<typename _CharT, typename _Traits, typename _Alloc>
856 typename basic_string<_CharT, _Traits, _Alloc>::size_type
857 basic_string<_CharT, _Traits, _Alloc>::
858 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
860 for (; __n && __pos < this->size(); ++__pos)
862 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
869 template<typename _CharT, typename _Traits, typename _Alloc>
870 typename basic_string<_CharT, _Traits, _Alloc>::size_type
871 basic_string<_CharT, _Traits, _Alloc>::
872 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
874 size_type __size = this->size();
877 if (--__size > __pos)
881 if (traits_type::find(__s, __n, _M_data()[__size]))
884 while (__size-- != 0);
889 template<typename _CharT, typename _Traits, typename _Alloc>
890 typename basic_string<_CharT, _Traits, _Alloc>::size_type
891 basic_string<_CharT, _Traits, _Alloc>::
892 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
894 size_t __xpos = __pos;
895 for (; __xpos < this->size(); ++__xpos)
896 if (!traits_type::find(__s, __n, _M_data()[__xpos]))
901 template<typename _CharT, typename _Traits, typename _Alloc>
902 typename basic_string<_CharT, _Traits, _Alloc>::size_type
903 basic_string<_CharT, _Traits, _Alloc>::
904 find_first_not_of(_CharT __c, size_type __pos) const
906 size_t __xpos = __pos;
907 for (; __xpos < this->size(); ++__xpos)
908 if (!traits_type::eq(_M_data()[__xpos], __c))
913 template<typename _CharT, typename _Traits, typename _Alloc>
914 typename basic_string<_CharT, _Traits, _Alloc>::size_type
915 basic_string<_CharT, _Traits, _Alloc>::
916 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
918 size_type __size = this->size();
921 if (--__size > __pos)
925 if (!traits_type::find(__s, __n, _M_data()[__size]))
933 template<typename _CharT, typename _Traits, typename _Alloc>
934 typename basic_string<_CharT, _Traits, _Alloc>::size_type
935 basic_string<_CharT, _Traits, _Alloc>::
936 find_last_not_of(_CharT __c, size_type __pos) const
938 size_type __size = this->size();
941 if (--__size > __pos)
945 if (!traits_type::eq(_M_data()[__size], __c))
953 template<typename _CharT, typename _Traits, typename _Alloc>
955 basic_string<_CharT, _Traits, _Alloc>::
956 compare(size_type __pos, size_type __n, const basic_string& __str) const
958 size_type __size = this->size();
959 size_type __osize = __str.size();
961 __throw_out_of_range("basic_string::compare");
963 size_type __rsize= std::min(size_type(__size - __pos), __n);
964 size_type __len = std::min(__rsize, __osize);
965 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
967 __r = __rsize - __osize;
971 template<typename _CharT, typename _Traits, typename _Alloc>
973 basic_string<_CharT, _Traits, _Alloc>::
974 compare(size_type __pos1, size_type __n1, const basic_string& __str,
975 size_type __pos2, size_type __n2) const
977 size_type __size = this->size();
978 size_type __osize = __str.size();
979 if (__pos1 > __size || __pos2 > __osize)
980 __throw_out_of_range("basic_string::compare");
982 size_type __rsize = std::min(size_type(__size - __pos1), __n1);
983 size_type __rosize = std::min(size_type(__osize - __pos2), __n2);
984 size_type __len = std::min(__rsize, __rosize);
985 int __r = traits_type::compare(_M_data() + __pos1,
986 __str.data() + __pos2, __len);
988 __r = __rsize - __rosize;
993 template<typename _CharT, typename _Traits, typename _Alloc>
995 basic_string<_CharT, _Traits, _Alloc>::
996 compare(const _CharT* __s) const
998 size_type __size = this->size();
999 size_type __osize = traits_type::length(__s);
1000 size_type __len = std::min(__size, __osize);
1001 int __r = traits_type::compare(_M_data(), __s, __len);
1003 __r = __size - __osize;
1008 template<typename _CharT, typename _Traits, typename _Alloc>
1010 basic_string <_CharT, _Traits, _Alloc>::
1011 compare(size_type __pos, size_type __n1, const _CharT* __s) const
1013 size_type __size = this->size();
1015 __throw_out_of_range("basic_string::compare");
1017 size_type __osize = traits_type::length(__s);
1018 size_type __rsize = std::min(size_type(__size - __pos), __n1);
1019 size_type __len = std::min(__rsize, __osize);
1020 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1022 __r = __rsize - __osize;
1026 template<typename _CharT, typename _Traits, typename _Alloc>
1028 basic_string <_CharT, _Traits, _Alloc>::
1029 compare(size_type __pos, size_type __n1, const _CharT* __s,
1030 size_type __n2) const
1032 size_type __size = this->size();
1034 __throw_out_of_range("basic_string::compare");
1036 size_type __osize = std::min(traits_type::length(__s), __n2);
1037 size_type __rsize = std::min(size_type(__size - __pos), __n1);
1038 size_type __len = std::min(__rsize, __osize);
1039 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1041 __r = __rsize - __osize;
1045 // Inhibit implicit instantiations for required instantiations,
1046 // which are defined via explicit instantiations elsewhere.
1047 // NB: This syntax is a GNU extension.
1048 #if _GLIBCPP_EXTERN_TEMPLATE
1049 extern template class basic_string<char>;
1051 basic_istream<char>&
1052 operator>>(basic_istream<char>&, string&);
1054 basic_ostream<char>&
1055 operator<<(basic_ostream<char>&, const string&);
1057 basic_istream<char>&
1058 getline(basic_istream<char>&, string&, char);
1060 basic_istream<char>&
1061 getline(basic_istream<char>&, string&);
1063 #ifdef _GLIBCPP_USE_WCHAR_T
1064 extern template class basic_string<wchar_t>;
1066 basic_istream<wchar_t>&
1067 operator>>(basic_istream<wchar_t>&, wstring&);
1069 basic_ostream<wchar_t>&
1070 operator<<(basic_ostream<wchar_t>&, const wstring&);
1072 basic_istream<wchar_t>&
1073 getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1075 basic_istream<wchar_t>&
1076 getline(basic_istream<wchar_t>&, wstring&);