| blob | 4a22d8967929e51cc99e44c507885962acd279cf |
1 // Components for manipulating sequences of characters -*- C++ -*-
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
4 // Free Software Foundation, Inc.
5 //
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)
10 // any later version.
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,
20 // USA.
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.
31 //
32 // ISO C++ 14882: 21 Strings library
33 //
35 // This file is included by <string>. It is not meant to be included
36 // separately.
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
46 namespace std
47 {
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>
54 const _CharT
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>
75 _CharT*
76 basic_string<_CharT, _Traits, _Alloc>::
77 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
78 input_iterator_tag)
79 {
80 if (__beg == __end && __a == _Alloc())
81 return _S_empty_rep()._M_refcopy();
82 // Avoid reallocation for common case.
83 _CharT __buf[100];
84 size_type __i = 0;
85 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
86 {
87 __buf[__i++] = *__beg;
88 ++__beg;
89 }
90 _Rep* __r = _Rep::_S_create(__i, __a);
91 traits_type::copy(__r->_M_refdata(), __buf, __i);
92 __r->_M_length = __i;
93 try
94 {
95 // NB: this loop looks precisely this way because
96 // it avoids comparing __beg != __end any more
97 // than strictly necessary; != might be expensive!
98 for (;;)
99 {
100 _CharT* __p = __r->_M_refdata() + __r->_M_length;
101 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
102 for (;;)
103 {
104 if (__beg == __end)
105 {
106 __r->_M_length = __p - __r->_M_refdata();
107 *__p = _Rep::_S_terminal; // grrr.
108 return __r->_M_refdata();
109 }
110 if (__p == __last)
111 break;
112 *__p++ = *__beg;
113 ++__beg;
114 }
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);
121 __r = __another;
122 __r->_M_length = __len;
123 }
124 }
125 catch(...)
126 {
127 __r->_M_destroy(__a);
128 __throw_exception_again;
129 }
130 return 0;
131 }
133 template<typename _CharT, typename _Traits, typename _Alloc>
134 template <class _InIter>
135 _CharT*
136 basic_string<_CharT, _Traits, _Alloc>::
137 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
138 forward_iterator_tag)
139 {
140 size_type __dnew = static_cast<size_type>(distance(__beg, __end));
142 if (__beg == __end && __a == _Alloc())
143 return _S_empty_rep()._M_refcopy();
145 // NB: Not required, but considered best practice.
146 if (__builtin_expect(__beg == _InIter(), 0))
147 __throw_logic_error("attempt to create string with null pointer");
149 // Check for out_of_range and length_error exceptions.
150 _Rep* __r = _Rep::_S_create(__dnew, __a);
151 try
152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
153 catch(...)
154 {
155 __r->_M_destroy(__a);
156 __throw_exception_again;
157 }
158 __r->_M_length = __dnew;
160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr.
161 return __r->_M_refdata();
162 }
164 template<typename _CharT, typename _Traits, typename _Alloc>
165 _CharT*
166 basic_string<_CharT, _Traits, _Alloc>::
167 _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
168 {
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);
174 try
175 {
176 if (__n)
177 traits_type::assign(__r->_M_refdata(), __n, __c);
178 }
179 catch(...)
180 {
181 __r->_M_destroy(__a);
182 __throw_exception_again;
183 }
184 __r->_M_length = __n;
185 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr
186 return __r->_M_refdata();
187 }
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())
194 { }
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)
200 { }
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())
207 { }
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)
215 { }
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)
221 { }
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)
228 { }
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)
234 { }
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)
241 { }
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)
246 {
247 if (_M_rep() != __str._M_rep())
248 {
249 // XXX MT
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);
253 _M_data(__tmp);
254 }
255 return *this;
256 }
258 template<typename _CharT, typename _Traits, typename _Alloc>
259 void
260 basic_string<_CharT, _Traits, _Alloc>::_Rep::
261 _M_destroy(const _Alloc& __a) throw ()
262 {
263 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
264 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
265 }
267 template<typename _CharT, typename _Traits, typename _Alloc>
268 void
269 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
270 {
271 if (_M_rep()->_M_is_shared())
272 _M_mutate(0, 0, 0);
273 _M_rep()->_M_set_leaked();
274 }
276 // _M_mutate and, below, _M_clone, include, in the same form, an exponential
277 // growth policy, necessary to meet amortized linear time requirements of
278 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
279 // The policy is active for allocations requiring an amount of memory above
280 // system pagesize. This is consistent with the requirements of the standard:
281 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
282 template<typename _CharT, typename _Traits, typename _Alloc>
283 void
284 basic_string<_CharT, _Traits, _Alloc>::
285 _M_mutate(size_type __pos, size_type __len1, size_type __len2)
286 {
287 size_type __old_size = this->size();
288 const size_type __new_size = __old_size + __len2 - __len1;
289 const _CharT* __src = _M_data() + __pos + __len1;
290 const size_type __how_much = __old_size - __pos - __len1;
292 if (_M_rep()->_M_is_shared() || __new_size > capacity())
293 {
294 // Must reallocate.
295 allocator_type __a = get_allocator();
296 // See below (_S_create) for the meaning and value of these
297 // constants.
298 const size_type __pagesize = 4096;
299 const size_type __malloc_header_size = 4 * sizeof (void*);
300 // The biggest string which fits in a memory page
301 const size_type __page_capacity = (__pagesize - __malloc_header_size
302 - sizeof(_Rep) - sizeof(_CharT))
303 / sizeof(_CharT);
304 _Rep* __r;
305 if (__new_size > capacity() && __new_size > __page_capacity)
306 // Growing exponentially.
307 __r = _Rep::_S_create(__new_size > 2*capacity() ?
308 __new_size : 2*capacity(), __a);
309 else
310 __r = _Rep::_S_create(__new_size, __a);
311 try
312 {
313 if (__pos)
314 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
315 if (__how_much)
316 traits_type::copy(__r->_M_refdata() + __pos + __len2,
317 __src, __how_much);
318 }
319 catch(...)
320 {
321 __r->_M_dispose(get_allocator());
322 __throw_exception_again;
323 }
324 _M_rep()->_M_dispose(__a);
325 _M_data(__r->_M_refdata());
326 }
327 else if (__how_much && __len1 != __len2)
328 {
329 // Work in-place
330 traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
331 }
332 _M_rep()->_M_set_sharable();
333 _M_rep()->_M_length = __new_size;
334 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
335 // You cannot leave those LWG people alone for a second.
336 }
338 template<typename _CharT, typename _Traits, typename _Alloc>
339 void
340 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
341 {
342 if (__res > this->capacity() || _M_rep()->_M_is_shared())
343 {
344 if (__res > this->max_size())
345 __throw_length_error("basic_string::reserve");
346 // Make sure we don't shrink below the current size
347 if (__res < this->size())
348 __res = this->size();
349 allocator_type __a = get_allocator();
350 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
351 _M_rep()->_M_dispose(__a);
352 _M_data(__tmp);
353 }
354 }
356 template<typename _CharT, typename _Traits, typename _Alloc>
357 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
358 {
359 if (_M_rep()->_M_is_leaked())
360 _M_rep()->_M_set_sharable();
361 if (__s._M_rep()->_M_is_leaked())
362 __s._M_rep()->_M_set_sharable();
363 if (this->get_allocator() == __s.get_allocator())
364 {
365 _CharT* __tmp = _M_data();
366 _M_data(__s._M_data());
367 __s._M_data(__tmp);
368 }
369 // The code below can usually be optimized away.
370 else
371 {
372 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
373 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
374 this->get_allocator());
375 *this = __tmp2;
376 __s = __tmp1;
377 }
378 }
380 template<typename _CharT, typename _Traits, typename _Alloc>
381 typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
382 basic_string<_CharT, _Traits, _Alloc>::_Rep::
383 _S_create(size_t __capacity, const _Alloc& __alloc)
384 {
385 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
386 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
387 // 83. String::npos vs. string::max_size()
388 if (__capacity > _S_max_size)
389 #else
390 if (__capacity == npos)
391 #endif
392 __throw_length_error("basic_string::_S_create");
394 // NB: Need an array of char_type[__capacity], plus a
395 // terminating null char_type() element, plus enough for the
396 // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
397 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
399 // The standard places no restriction on allocating more memory
400 // than is strictly needed within this layer at the moment or as
401 // requested by an explicit application call to reserve(). Many
402 // malloc implementations perform quite poorly when an
403 // application attempts to allocate memory in a stepwise fashion
404 // growing each allocation size by only 1 char. Additionally,
405 // it makes little sense to allocate less linear memory than the
406 // natural blocking size of the malloc implementation.
407 // Unfortunately, we would need a somewhat low-level calculation
408 // with tuned parameters to get this perfect for any particular
409 // malloc implementation. Fortunately, generalizations about
410 // common features seen among implementations seems to suffice.
412 // __pagesize need not match the actual VM page size for good
413 // results in practice, thus we pick a common value on the low
414 // side. __malloc_header_size is an estimate of the amount of
415 // overhead per memory allocation (in practice seen N * sizeof
416 // (void*) where N is 0, 2 or 4). According to folklore,
417 // picking this value on the high side is better than
418 // low-balling it (especially when this algorithm is used with
419 // malloc implementations that allocate memory blocks rounded up
420 // to a size which is a power of 2).
421 const size_t __pagesize = 4096; // must be 2^i * __subpagesize
422 const size_t __subpagesize = 128; // should be >> __malloc_header_size
423 const size_t __malloc_header_size = 4 * sizeof (void*);
424 if ((__size + __malloc_header_size) > __pagesize)
425 {
426 size_t __extra =
427 (__pagesize - ((__size + __malloc_header_size) % __pagesize))
428 % __pagesize;
429 __capacity += __extra / sizeof(_CharT);
430 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
431 }
432 else if (__size > __subpagesize)
433 {
434 size_t __extra =
435 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
436 % __subpagesize;
437 __capacity += __extra / sizeof(_CharT);
438 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
439 }
441 // NB: Might throw, but no worries about a leak, mate: _Rep()
442 // does not throw.
443 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
444 _Rep *__p = new (__place) _Rep;
445 __p->_M_capacity = __capacity;
446 __p->_M_set_sharable(); // One reference.
447 __p->_M_length = 0;
448 return __p;
449 }
451 template<typename _CharT, typename _Traits, typename _Alloc>
452 _CharT*
453 basic_string<_CharT, _Traits, _Alloc>::_Rep::
454 _M_clone(const _Alloc& __alloc, size_type __res)
455 {
456 // Requested capacity of the clone.
457 const size_type __requested_cap = _M_length + __res;
458 // See above (_S_create) for the meaning and value of these constants.
459 const size_type __pagesize = 4096;
460 const size_type __malloc_header_size = 4 * sizeof (void*);
461 // The biggest string which fits in a memory page.
462 const size_type __page_capacity =
463 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
464 / sizeof(_CharT);
465 _Rep* __r;
466 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
467 // Growing exponentially.
468 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
469 __requested_cap : 2*_M_capacity, __alloc);
470 else
471 __r = _Rep::_S_create(__requested_cap, __alloc);
473 if (_M_length)
474 {
475 try
476 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
477 catch(...)
478 {
479 __r->_M_destroy(__alloc);
480 __throw_exception_again;
481 }
482 }
483 __r->_M_length = _M_length;
484 return __r->_M_refdata();
485 }
487 template<typename _CharT, typename _Traits, typename _Alloc>
488 void
489 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
490 {
491 if (__n > max_size())
492 __throw_length_error("basic_string::resize");
493 size_type __size = this->size();
494 if (__size < __n)
495 this->append(__n - __size, __c);
496 else if (__n < __size)
497 this->erase(__n);
498 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
499 }
501 // This is the general replace helper, which currently gets instantiated both
502 // for input iterators and reverse iterators. It buffers internally and then
503 // calls _M_replace_safe.
504 template<typename _CharT, typename _Traits, typename _Alloc>
505 template<typename _InputIter>
506 basic_string<_CharT, _Traits, _Alloc>&
507 basic_string<_CharT, _Traits, _Alloc>::
508 _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
509 _InputIter __k2, input_iterator_tag)
510 {
511 // Save concerned source string data in a temporary.
512 basic_string __s(__k1, __k2);
513 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
514 }
516 // This is a special replace helper, which does not buffer internally
517 // and can be used in "safe" situations involving forward iterators,
518 // i.e., when source and destination ranges are known to not overlap.
519 template<typename _CharT, typename _Traits, typename _Alloc>
520 template<typename _ForwardIter>
521 basic_string<_CharT, _Traits, _Alloc>&
522 basic_string<_CharT, _Traits, _Alloc>::
523 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
524 _ForwardIter __k2)
525 {
526 size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
527 size_type __dold = __i2 - __i1;
528 size_type __dmax = this->max_size();
530 if (__dmax <= __dnew)
531 __throw_length_error("basic_string::_M_replace");
532 size_type __off = __i1 - _M_ibegin();
533 _M_mutate(__off, __dold, __dnew);
535 // Invalidated __i1, __i2
536 if (__dnew)
537 _S_copy_chars(_M_data() + __off, __k1, __k2);
539 return *this;
540 }
542 template<typename _CharT, typename _Traits, typename _Alloc>
543 basic_string<_CharT, _Traits, _Alloc>&
544 basic_string<_CharT, _Traits, _Alloc>::
545 replace(size_type __pos1, size_type __n1, const basic_string& __str,
546 size_type __pos2, size_type __n2)
547 {
548 const size_type __strsize = __str.size();
549 if (__pos2 > __strsize)
550 __throw_out_of_range("basic_string::replace");
551 const bool __testn2 = __n2 < __strsize - __pos2;
552 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
553 return this->replace(__pos1, __n1,
554 __str._M_data() + __pos2, __foldn2);
555 }
557 template<typename _CharT, typename _Traits, typename _Alloc>
558 basic_string<_CharT, _Traits, _Alloc>&
559 basic_string<_CharT, _Traits, _Alloc>::
560 append(const basic_string& __str)
561 {
562 // Iff appending itself, string needs to pre-reserve the
563 // correct size so that _M_mutate does not clobber the
564 // iterators formed here.
565 size_type __size = __str.size();
566 size_type __len = __size + this->size();
567 if (__len > this->capacity())
568 this->reserve(__len);
569 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
570 __str._M_iend());
571 }
573 template<typename _CharT, typename _Traits, typename _Alloc>
574 basic_string<_CharT, _Traits, _Alloc>&
575 basic_string<_CharT, _Traits, _Alloc>::
576 append(const basic_string& __str, size_type __pos, size_type __n)
577 {
578 // Iff appending itself, string needs to pre-reserve the
579 // correct size so that _M_mutate does not clobber the
580 // iterators formed here.
581 size_type __len = min(__str.size() - __pos, __n) + this->size();
582 if (__len > this->capacity())
583 this->reserve(__len);
584 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
585 __str._M_fold(__pos, __n));
586 }
588 template<typename _CharT, typename _Traits, typename _Alloc>
589 basic_string<_CharT, _Traits, _Alloc>&
590 basic_string<_CharT, _Traits, _Alloc>::
591 append(const _CharT* __s, size_type __n)
592 {
593 size_type __len = __n + this->size();
594 if (__len > this->capacity())
595 this->reserve(__len);
596 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
597 }
599 template<typename _CharT, typename _Traits, typename _Alloc>
600 basic_string<_CharT, _Traits, _Alloc>&
601 basic_string<_CharT, _Traits, _Alloc>::
602 append(size_type __n, _CharT __c)
603 {
604 size_type __len = __n + this->size();
605 if (__len > this->capacity())
606 this->reserve(__len);
607 return this->replace(_M_iend(), _M_iend(), __n, __c);
608 }
610 template<typename _CharT, typename _Traits, typename _Alloc>
611 basic_string<_CharT, _Traits, _Alloc>
612 operator+(const _CharT* __lhs,
613 const basic_string<_CharT, _Traits, _Alloc>& __rhs)
614 {
615 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
616 typedef typename __string_type::size_type __size_type;
617 __size_type __len = _Traits::length(__lhs);
618 __string_type __str;
619 __str.reserve(__len + __rhs.size());
620 __str.append(__lhs, __lhs + __len);
621 __str.append(__rhs);
622 return __str;
623 }
625 template<typename _CharT, typename _Traits, typename _Alloc>
626 basic_string<_CharT, _Traits, _Alloc>
627 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
628 {
629 typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
630 typedef typename __string_type::size_type __size_type;
631 __string_type __str;
632 __size_type __len = __rhs.size();
633 __str.reserve(__len + 1);
634 __str.append(__size_type(1), __lhs);
635 __str.append(__rhs);
636 return __str;
637 }
639 template<typename _CharT, typename _Traits, typename _Alloc>
640 basic_string<_CharT, _Traits, _Alloc>&
641 basic_string<_CharT, _Traits, _Alloc>::
642 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
643 {
644 size_type __n1 = __i2 - __i1;
645 size_type __off1 = __i1 - _M_ibegin();
646 if (max_size() - (this->size() - __n1) <= __n2)
647 __throw_length_error("basic_string::replace");
648 _M_mutate (__off1, __n1, __n2);
649 // Invalidated __i1, __i2
650 if (__n2)
651 traits_type::assign(_M_data() + __off1, __n2, __c);
652 return *this;
653 }
655 template<typename _CharT, typename _Traits, typename _Alloc>
656 typename basic_string<_CharT, _Traits, _Alloc>::size_type
657 basic_string<_CharT, _Traits, _Alloc>::
658 copy(_CharT* __s, size_type __n, size_type __pos) const
659 {
660 if (__pos > this->size())
661 __throw_out_of_range("basic_string::copy");
663 if (__n > this->size() - __pos)
664 __n = this->size() - __pos;
666 traits_type::copy(__s, _M_data() + __pos, __n);
667 // 21.3.5.7 par 3: do not append null. (good.)
668 return __n;
669 }
671 template<typename _CharT, typename _Traits, typename _Alloc>
672 typename basic_string<_CharT, _Traits, _Alloc>::size_type
673 basic_string<_CharT, _Traits, _Alloc>::
674 find(const _CharT* __s, size_type __pos, size_type __n) const
675 {
676 size_type __size = this->size();
677 size_t __xpos = __pos;
678 const _CharT* __data = _M_data();
679 for (; __xpos + __n <= __size; ++__xpos)
680 if (traits_type::compare(__data + __xpos, __s, __n) == 0)
681 return __xpos;
682 return npos;
683 }
685 template<typename _CharT, typename _Traits, typename _Alloc>
686 typename basic_string<_CharT, _Traits, _Alloc>::size_type
687 basic_string<_CharT, _Traits, _Alloc>::
688 find(_CharT __c, size_type __pos) const
689 {
690 size_type __size = this->size();
691 size_type __ret = npos;
692 if (__pos < __size)
693 {
694 const _CharT* __data = _M_data();
695 size_type __n = __size - __pos;
696 const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
697 if (__p)
698 __ret = __p - __data;
699 }
700 return __ret;
701 }
704 template<typename _CharT, typename _Traits, typename _Alloc>
705 typename basic_string<_CharT, _Traits, _Alloc>::size_type
706 basic_string<_CharT, _Traits, _Alloc>::
707 rfind(const _CharT* __s, size_type __pos, size_type __n) const
708 {
709 size_type __size = this->size();
710 if (__n <= __size)
711 {
712 __pos = std::min(__size - __n, __pos);
713 const _CharT* __data = _M_data();
714 do
715 {
716 if (traits_type::compare(__data + __pos, __s, __n) == 0)
717 return __pos;
718 }
719 while (__pos-- > 0);
720 }
721 return npos;
722 }
724 template<typename _CharT, typename _Traits, typename _Alloc>
725 typename basic_string<_CharT, _Traits, _Alloc>::size_type
726 basic_string<_CharT, _Traits, _Alloc>::
727 rfind(_CharT __c, size_type __pos) const
728 {
729 size_type __size = this->size();
730 if (__size)
731 {
732 size_t __xpos = __size - 1;
733 if (__xpos > __pos)
734 __xpos = __pos;
736 for (++__xpos; __xpos-- > 0; )
737 if (traits_type::eq(_M_data()[__xpos], __c))
738 return __xpos;
739 }
740 return npos;
741 }
743 template<typename _CharT, typename _Traits, typename _Alloc>
744 typename basic_string<_CharT, _Traits, _Alloc>::size_type
745 basic_string<_CharT, _Traits, _Alloc>::
746 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
747 {
748 for (; __n && __pos < this->size(); ++__pos)
749 {
750 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
751 if (__p)
752 return __pos;
753 }
754 return npos;
755 }
757 template<typename _CharT, typename _Traits, typename _Alloc>
758 typename basic_string<_CharT, _Traits, _Alloc>::size_type
759 basic_string<_CharT, _Traits, _Alloc>::
760 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
761 {
762 size_type __size = this->size();
763 if (__size && __n)
764 {
765 if (--__size > __pos)
766 __size = __pos;
767 do
768 {
769 if (traits_type::find(__s, __n, _M_data()[__size]))
770 return __size;
771 }
772 while (__size-- != 0);
773 }
774 return npos;
775 }
777 template<typename _CharT, typename _Traits, typename _Alloc>
778 typename basic_string<_CharT, _Traits, _Alloc>::size_type
779 basic_string<_CharT, _Traits, _Alloc>::
780 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
781 {
782 size_t __xpos = __pos;
783 for (; __xpos < this->size(); ++__xpos)
784 if (!traits_type::find(__s, __n, _M_data()[__xpos]))
785 return __xpos;
786 return npos;
787 }
789 template<typename _CharT, typename _Traits, typename _Alloc>
790 typename basic_string<_CharT, _Traits, _Alloc>::size_type
791 basic_string<_CharT, _Traits, _Alloc>::
792 find_first_not_of(_CharT __c, size_type __pos) const
793 {
794 size_t __xpos = __pos;
795 for (; __xpos < this->size(); ++__xpos)
796 if (!traits_type::eq(_M_data()[__xpos], __c))
797 return __xpos;
798 return npos;
799 }
801 template<typename _CharT, typename _Traits, typename _Alloc>
802 typename basic_string<_CharT, _Traits, _Alloc>::size_type
803 basic_string<_CharT, _Traits, _Alloc>::
804 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
805 {
806 size_type __size = this->size();
807 if (__size)
808 {
809 if (--__size > __pos)
810 __size = __pos;
811 do
812 {
813 if (!traits_type::find(__s, __n, _M_data()[__size]))
814 return __size;
815 }
816 while (__size--);
817 }
818 return npos;
819 }
821 template<typename _CharT, typename _Traits, typename _Alloc>
822 typename basic_string<_CharT, _Traits, _Alloc>::size_type
823 basic_string<_CharT, _Traits, _Alloc>::
824 find_last_not_of(_CharT __c, size_type __pos) const
825 {
826 size_type __size = this->size();
827 if (__size)
828 {
829 if (--__size > __pos)
830 __size = __pos;
831 do
832 {
833 if (!traits_type::eq(_M_data()[__size], __c))
834 return __size;
835 }
836 while (__size--);
837 }
838 return npos;
839 }
841 template<typename _CharT, typename _Traits, typename _Alloc>
842 int
843 basic_string<_CharT, _Traits, _Alloc>::
844 compare(size_type __pos, size_type __n, const basic_string& __str) const
845 {
846 size_type __size = this->size();
847 size_type __osize = __str.size();
848 if (__pos > __size)
849 __throw_out_of_range("basic_string::compare");
851 size_type __rsize= min(__size - __pos, __n);
852 size_type __len = min(__rsize, __osize);
853 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
854 if (!__r)
855 __r = __rsize - __osize;
856 return __r;
857 }
859 template<typename _CharT, typename _Traits, typename _Alloc>
860 int
861 basic_string<_CharT, _Traits, _Alloc>::
862 compare(size_type __pos1, size_type __n1, const basic_string& __str,
863 size_type __pos2, size_type __n2) const
864 {
865 size_type __size = this->size();
866 size_type __osize = __str.size();
867 if (__pos1 > __size || __pos2 > __osize)
868 __throw_out_of_range("basic_string::compare");
870 size_type __rsize = min(__size - __pos1, __n1);
871 size_type __rosize = min(__osize - __pos2, __n2);
872 size_type __len = min(__rsize, __rosize);
873 int __r = traits_type::compare(_M_data() + __pos1,
874 __str.data() + __pos2, __len);
875 if (!__r)
876 __r = __rsize - __rosize;
877 return __r;
878 }
881 template<typename _CharT, typename _Traits, typename _Alloc>
882 int
883 basic_string<_CharT, _Traits, _Alloc>::
884 compare(const _CharT* __s) const
885 {
886 size_type __size = this->size();
887 size_type __osize = traits_type::length(__s);
888 size_type __len = min(__size, __osize);
889 int __r = traits_type::compare(_M_data(), __s, __len);
890 if (!__r)
891 __r = __size - __osize;
892 return __r;
893 }
896 template<typename _CharT, typename _Traits, typename _Alloc>
897 int
898 basic_string <_CharT, _Traits, _Alloc>::
899 compare(size_type __pos, size_type __n1, const _CharT* __s) const
900 {
901 size_type __size = this->size();
902 if (__pos > __size)
903 __throw_out_of_range("basic_string::compare");
905 size_type __osize = traits_type::length(__s);
906 size_type __rsize = min(__size - __pos, __n1);
907 size_type __len = min(__rsize, __osize);
908 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
909 if (!__r)
910 __r = __rsize - __osize;
911 return __r;
912 }
914 template<typename _CharT, typename _Traits, typename _Alloc>
915 int
916 basic_string <_CharT, _Traits, _Alloc>::
917 compare(size_type __pos, size_type __n1, const _CharT* __s,
918 size_type __n2) const
919 {
920 size_type __size = this->size();
921 if (__pos > __size)
922 __throw_out_of_range("basic_string::compare");
924 size_type __osize = min(traits_type::length(__s), __n2);
925 size_type __rsize = min(__size - __pos, __n1);
926 size_type __len = min(__rsize, __osize);
927 int __r = traits_type::compare(_M_data() + __pos, __s, __len);
928 if (!__r)
929 __r = __rsize - __osize;
930 return __r;
931 }
933 template <class _CharT, class _Traits, class _Alloc>
934 void
935 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
936 _CharT* __buf, typename _Alloc::size_type __bufsiz)
937 {
938 typedef typename _Alloc::size_type size_type;
939 size_type __strsize = __str.size();
940 size_type __bytes = min(__strsize, __bufsiz - 1);
941 _Traits::copy(__buf, __str.data(), __bytes);
942 __buf[__bytes] = _CharT();
943 }
945 // Inhibit implicit instantiations for required instantiations,
946 // which are defined via explicit instantiations elsewhere.
947 // NB: This syntax is a GNU extension.
948 extern template class basic_string<char>;
949 extern template
950 basic_istream<char>&
951 operator>>(basic_istream<char>&, string&);
952 extern template
953 basic_ostream<char>&
954 operator<<(basic_ostream<char>&, const string&);
955 extern template
956 basic_istream<char>&
957 getline(basic_istream<char>&, string&, char);
958 extern template
959 basic_istream<char>&
960 getline(basic_istream<char>&, string&);
962 #ifdef _GLIBCPP_USE_WCHAR_T
963 extern template class basic_string<wchar_t>;
964 extern template
965 basic_istream<wchar_t>&
966 operator>>(basic_istream<wchar_t>&, wstring&);
967 extern template
968 basic_ostream<wchar_t>&
969 operator<<(basic_ostream<wchar_t>&, const wstring&);
970 extern template
971 basic_istream<wchar_t>&
972 getline(basic_istream<wchar_t>&, wstring&, wchar_t);
973 extern template
974 basic_istream<wchar_t>&
975 getline(basic_istream<wchar_t>&, wstring&);
976 #endif
977 } // namespace std
979 #endif