basic_string.tcc

00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 // 00032 // ISO C++ 14882: 21 Strings library 00033 // 00034 00035 // This file is included by <string>. It is not meant to be included 00036 // separately. 00037 00038 // Written by Jason Merrill based upon the specification by Takanori Adachi 00039 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 00040 00041 #ifndef _CPP_BITS_STRING_TCC 00042 #define _CPP_BITS_STRING_TCC 1 00043 00044 #pragma GCC system_header 00045 00046 namespace std 00047 { 00048 template<typename _CharT, typename _Traits, typename _Alloc> 00049 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00050 basic_string<_CharT, _Traits, _Alloc>:: 00051 _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4; 00052 00053 template<typename _CharT, typename _Traits, typename _Alloc> 00054 const _CharT 00055 basic_string<_CharT, _Traits, _Alloc>:: 00056 _Rep::_S_terminal = _CharT(); 00057 00058 template<typename _CharT, typename _Traits, typename _Alloc> 00059 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00060 basic_string<_CharT, _Traits, _Alloc>::npos; 00061 00062 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 00063 // at static init time (before static ctors are run). 00064 template<typename _CharT, typename _Traits, typename _Alloc> 00065 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00066 basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[ 00067 (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)]; 00068 00069 // NB: This is the special case for Input Iterators, used in 00070 // istreambuf_iterators, etc. 00071 // Input Iterators have a cost structure very different from 00072 // pointers, calling for a different coding style. 00073 template<typename _CharT, typename _Traits, typename _Alloc> 00074 template<typename _InIter> 00075 _CharT* 00076 basic_string<_CharT, _Traits, _Alloc>:: 00077 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 00078 input_iterator_tag) 00079 { 00080 if (__beg == __end && __a == _Alloc()) 00081 return _S_empty_rep()._M_refcopy(); 00082 // Avoid reallocation for common case. 00083 _CharT __buf[100]; 00084 size_type __i = 0; 00085 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT)) 00086 { 00087 __buf[__i++] = *__beg; 00088 ++__beg; 00089 } 00090 _Rep* __r = _Rep::_S_create(__i, __a); 00091 traits_type::copy(__r->_M_refdata(), __buf, __i); 00092 __r->_M_length = __i; 00093 try 00094 { 00095 // NB: this loop looks precisely this way because 00096 // it avoids comparing __beg != __end any more 00097 // than strictly necessary; != might be expensive! 00098 for (;;) 00099 { 00100 _CharT* __p = __r->_M_refdata() + __r->_M_length; 00101 _CharT* __last = __r->_M_refdata() + __r->_M_capacity; 00102 for (;;) 00103 { 00104 if (__beg == __end) 00105 { 00106 __r->_M_length = __p - __r->_M_refdata(); 00107 *__p = _Rep::_S_terminal; // grrr. 00108 return __r->_M_refdata(); 00109 } 00110 if (__p == __last) 00111 break; 00112 *__p++ = *__beg; 00113 ++__beg; 00114 } 00115 // Allocate more space. 00116 size_type __len = __p - __r->_M_refdata(); 00117 _Rep* __another = _Rep::_S_create(__len + 1, __a); 00118 traits_type::copy(__another->_M_refdata(), 00119 __r->_M_refdata(), __len); 00120 __r->_M_destroy(__a); 00121 __r = __another; 00122 __r->_M_length = __len; 00123 } 00124 } 00125 catch(...) 00126 { 00127 __r->_M_destroy(__a); 00128 __throw_exception_again; 00129 } 00130 return 0; 00131 } 00132 00133 template<typename _CharT, typename _Traits, typename _Alloc> 00134 template <class _InIter> 00135 _CharT* 00136 basic_string<_CharT, _Traits, _Alloc>:: 00137 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 00138 forward_iterator_tag) 00139 { 00140 size_type __dnew = static_cast<size_type>(distance(__beg, __end)); 00141 00142 if (__beg == __end && __a == _Alloc()) 00143 return _S_empty_rep()._M_refcopy(); 00144 00145 // NB: Not required, but considered best practice. 00146 if (__builtin_expect(__beg == _InIter(), 0)) 00147 __throw_logic_error("attempt to create string with null pointer"); 00148 00149 // Check for out_of_range and length_error exceptions. 00150 _Rep* __r = _Rep::_S_create(__dnew, __a); 00151 try 00152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 00153 catch(...) 00154 { 00155 __r->_M_destroy(__a); 00156 __throw_exception_again; 00157 } 00158 __r->_M_length = __dnew; 00159 00160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr. 00161 return __r->_M_refdata(); 00162 } 00163 00164 template<typename _CharT, typename _Traits, typename _Alloc> 00165 _CharT* 00166 basic_string<_CharT, _Traits, _Alloc>:: 00167 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 00168 { 00169 if (__n == 0 && __a == _Alloc()) 00170 return _S_empty_rep()._M_refcopy(); 00171 00172 // Check for out_of_range and length_error exceptions. 00173 _Rep* __r = _Rep::_S_create(__n, __a); 00174 try 00175 { 00176 if (__n) 00177 traits_type::assign(__r->_M_refdata(), __n, __c); 00178 } 00179 catch(...) 00180 { 00181 __r->_M_destroy(__a); 00182 __throw_exception_again; 00183 } 00184 __r->_M_length = __n; 00185 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr 00186 return __r->_M_refdata(); 00187 } 00188 00189 template<typename _CharT, typename _Traits, typename _Alloc> 00190 basic_string<_CharT, _Traits, _Alloc>:: 00191 basic_string(const basic_string& __str) 00192 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()), 00193 __str.get_allocator()) 00194 { } 00195 00196 template<typename _CharT, typename _Traits, typename _Alloc> 00197 basic_string<_CharT, _Traits, _Alloc>:: 00198 basic_string(const _Alloc& __a) 00199 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 00200 { } 00201 00202 template<typename _CharT, typename _Traits, typename _Alloc> 00203 basic_string<_CharT, _Traits, _Alloc>:: 00204 basic_string(const basic_string& __str, size_type __pos, size_type __n) 00205 : _M_dataplus(_S_construct(__str._M_check(__pos), 00206 __str._M_fold(__pos, __n), _Alloc()), _Alloc()) 00207 { } 00208 00209 template<typename _CharT, typename _Traits, typename _Alloc> 00210 basic_string<_CharT, _Traits, _Alloc>:: 00211 basic_string(const basic_string& __str, size_type __pos, 00212 size_type __n, const _Alloc& __a) 00213 : _M_dataplus(_S_construct(__str._M_check(__pos), 00214 __str._M_fold(__pos, __n), __a), __a) 00215 { } 00216 00217 template<typename _CharT, typename _Traits, typename _Alloc> 00218 basic_string<_CharT, _Traits, _Alloc>:: 00219 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00220 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00221 { } 00222 00223 template<typename _CharT, typename _Traits, typename _Alloc> 00224 basic_string<_CharT, _Traits, _Alloc>:: 00225 basic_string(const _CharT* __s, const _Alloc& __a) 00226 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00227 __s + npos, __a), __a) 00228 { } 00229 00230 template<typename _CharT, typename _Traits, typename _Alloc> 00231 basic_string<_CharT, _Traits, _Alloc>:: 00232 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00233 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00234 { } 00235 00236 template<typename _CharT, typename _Traits, typename _Alloc> 00237 template<typename _InputIter> 00238 basic_string<_CharT, _Traits, _Alloc>:: 00239 basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a) 00240 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00241 { } 00242 00243 template<typename _CharT, typename _Traits, typename _Alloc> 00244 basic_string<_CharT, _Traits, _Alloc>& 00245 basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str) 00246 { 00247 if (_M_rep() != __str._M_rep()) 00248 { 00249 // XXX MT 00250 allocator_type __a = this->get_allocator(); 00251 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00252 _M_rep()->_M_dispose(__a); 00253 _M_data(__tmp); 00254 } 00255 return *this; 00256 } 00257 00258 template<typename _CharT, typename _Traits, typename _Alloc> 00259 void 00260 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00261 _M_destroy(const _Alloc& __a) throw () 00262 { 00263 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT); 00264 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00265 } 00266 00267 template<typename _CharT, typename _Traits, typename _Alloc> 00268 void 00269 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard() 00270 { 00271 if (_M_rep()->_M_is_shared()) 00272 _M_mutate(0, 0, 0); 00273 _M_rep()->_M_set_leaked(); 00274 } 00275 00276 // _M_mutate and, below, _M_clone, include, in the same form, an exponential 00277 // growth policy, necessary to meet amortized linear time requirements of 00278 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00279 // The policy is active for allocations requiring an amount of memory above 00280 // system pagesize. This is consistent with the requirements of the standard: 00281 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 00282 template<typename _CharT, typename _Traits, typename _Alloc> 00283 void 00284 basic_string<_CharT, _Traits, _Alloc>:: 00285 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00286 { 00287 size_type __old_size = this->size(); 00288 const size_type __new_size = __old_size + __len2 - __len1; 00289 const _CharT* __src = _M_data() + __pos + __len1; 00290 const size_type __how_much = __old_size - __pos - __len1; 00291 00292 if (_M_rep()->_M_is_shared() || __new_size > capacity()) 00293 { 00294 // Must reallocate. 00295 allocator_type __a = get_allocator(); 00296 // See below (_S_create) for the meaning and value of these 00297 // constants. 00298 const size_type __pagesize = 4096; 00299 const size_type __malloc_header_size = 4 * sizeof (void*); 00300 // The biggest string which fits in a memory page 00301 const size_type __page_capacity = (__pagesize - __malloc_header_size 00302 - sizeof(_Rep) - sizeof(_CharT)) 00303 / sizeof(_CharT); 00304 _Rep* __r; 00305 if (__new_size > capacity() && __new_size > __page_capacity) 00306 // Growing exponentially. 00307 __r = _Rep::_S_create(__new_size > 2*capacity() ? 00308 __new_size : 2*capacity(), __a); 00309 else 00310 __r = _Rep::_S_create(__new_size, __a); 00311 try 00312 { 00313 if (__pos) 00314 traits_type::copy(__r->_M_refdata(), _M_data(), __pos); 00315 if (__how_much) 00316 traits_type::copy(__r->_M_refdata() + __pos + __len2, 00317 __src, __how_much); 00318 } 00319 catch(...) 00320 { 00321 __r->_M_dispose(get_allocator()); 00322 __throw_exception_again; 00323 } 00324 _M_rep()->_M_dispose(__a); 00325 _M_data(__r->_M_refdata()); 00326 } 00327 else if (__how_much && __len1 != __len2) 00328 { 00329 // Work in-place 00330 traits_type::move(_M_data() + __pos + __len2, __src, __how_much); 00331 } 00332 _M_rep()->_M_set_sharable(); 00333 _M_rep()->_M_length = __new_size; 00334 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4) 00335 // You cannot leave those LWG people alone for a second. 00336 } 00337 00338 template<typename _CharT, typename _Traits, typename _Alloc> 00339 void 00340 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res) 00341 { 00342 if (__res > this->capacity() || _M_rep()->_M_is_shared()) 00343 { 00344 if (__res > this->max_size()) 00345 __throw_length_error("basic_string::reserve"); 00346 // Make sure we don't shrink below the current size 00347 if (__res < this->size()) 00348 __res = this->size(); 00349 allocator_type __a = get_allocator(); 00350 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00351 _M_rep()->_M_dispose(__a); 00352 _M_data(__tmp); 00353 } 00354 } 00355 00356 template<typename _CharT, typename _Traits, typename _Alloc> 00357 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s) 00358 { 00359 if (_M_rep()->_M_is_leaked()) 00360 _M_rep()->_M_set_sharable(); 00361 if (__s._M_rep()->_M_is_leaked()) 00362 __s._M_rep()->_M_set_sharable(); 00363 if (this->get_allocator() == __s.get_allocator()) 00364 { 00365 _CharT* __tmp = _M_data(); 00366 _M_data(__s._M_data()); 00367 __s._M_data(__tmp); 00368 } 00369 // The code below can usually be optimized away. 00370 else 00371 { 00372 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator()); 00373 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00374 this->get_allocator()); 00375 *this = __tmp2; 00376 __s = __tmp1; 00377 } 00378 } 00379 00380 template<typename _CharT, typename _Traits, typename _Alloc> 00381 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00382 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00383 _S_create(size_t __capacity, const _Alloc& __alloc) 00384 { 00385 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00386 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS 00387 // 83. String::npos vs. string::max_size() 00388 if (__capacity > _S_max_size) 00389 #else 00390 if (__capacity == npos) 00391 #endif 00392 __throw_length_error("basic_string::_S_create"); 00393 00394 // NB: Need an array of char_type[__capacity], plus a 00395 // terminating null char_type() element, plus enough for the 00396 // _Rep data structure. Whew. Seemingly so needy, yet so elemental. 00397 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00398 00399 // The standard places no restriction on allocating more memory 00400 // than is strictly needed within this layer at the moment or as 00401 // requested by an explicit application call to reserve(). Many 00402 // malloc implementations perform quite poorly when an 00403 // application attempts to allocate memory in a stepwise fashion 00404 // growing each allocation size by only 1 char. Additionally, 00405 // it makes little sense to allocate less linear memory than the 00406 // natural blocking size of the malloc implementation. 00407 // Unfortunately, we would need a somewhat low-level calculation 00408 // with tuned parameters to get this perfect for any particular 00409 // malloc implementation. Fortunately, generalizations about 00410 // common features seen among implementations seems to suffice. 00411 00412 // __pagesize need not match the actual VM page size for good 00413 // results in practice, thus we pick a common value on the low 00414 // side. __malloc_header_size is an estimate of the amount of 00415 // overhead per memory allocation (in practice seen N * sizeof 00416 // (void*) where N is 0, 2 or 4). According to folklore, 00417 // picking this value on the high side is better than 00418 // low-balling it (especially when this algorithm is used with 00419 // malloc implementations that allocate memory blocks rounded up 00420 // to a size which is a power of 2). 00421 const size_t __pagesize = 4096; // must be 2^i * __subpagesize 00422 const size_t __subpagesize = 128; // should be >> __malloc_header_size 00423 const size_t __malloc_header_size = 4 * sizeof (void*); 00424 if ((__size + __malloc_header_size) > __pagesize) 00425 { 00426 size_t __extra = 00427 (__pagesize - ((__size + __malloc_header_size) % __pagesize)) 00428 % __pagesize; 00429 __capacity += __extra / sizeof(_CharT); 00430 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00431 } 00432 else if (__size > __subpagesize) 00433 { 00434 size_t __extra = 00435 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize)) 00436 % __subpagesize; 00437 __capacity += __extra / sizeof(_CharT); 00438 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00439 } 00440 00441 // NB: Might throw, but no worries about a leak, mate: _Rep() 00442 // does not throw. 00443 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 00444 _Rep *__p = new (__place) _Rep; 00445 __p->_M_capacity = __capacity; 00446 __p->_M_set_sharable(); // One reference. 00447 __p->_M_length = 0; 00448 return __p; 00449 } 00450 00451 template<typename _CharT, typename _Traits, typename _Alloc> 00452 _CharT* 00453 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00454 _M_clone(const _Alloc& __alloc, size_type __res) 00455 { 00456 // Requested capacity of the clone. 00457 const size_type __requested_cap = _M_length + __res; 00458 // See above (_S_create) for the meaning and value of these constants. 00459 const size_type __pagesize = 4096; 00460 const size_type __malloc_header_size = 4 * sizeof (void*); 00461 // The biggest string which fits in a memory page. 00462 const size_type __page_capacity = 00463 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT)) 00464 / sizeof(_CharT); 00465 _Rep* __r; 00466 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity) 00467 // Growing exponentially. 00468 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ? 00469 __requested_cap : 2*_M_capacity, __alloc); 00470 else 00471 __r = _Rep::_S_create(__requested_cap, __alloc); 00472 00473 if (_M_length) 00474 { 00475 try 00476 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); } 00477 catch(...) 00478 { 00479 __r->_M_destroy(__alloc); 00480 __throw_exception_again; 00481 } 00482 } 00483 __r->_M_length = _M_length; 00484 return __r->_M_refdata(); 00485 } 00486 00487 template<typename _CharT, typename _Traits, typename _Alloc> 00488 void 00489 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c) 00490 { 00491 if (__n > max_size()) 00492 __throw_length_error("basic_string::resize"); 00493 size_type __size = this->size(); 00494 if (__size < __n) 00495 this->append(__n - __size, __c); 00496 else if (__n < __size) 00497 this->erase(__n); 00498 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 00499 } 00500 00501 // This is the general replace helper, which currently gets instantiated both 00502 // for input iterators and reverse iterators. It buffers internally and then 00503 // calls _M_replace_safe. 00504 template<typename _CharT, typename _Traits, typename _Alloc> 00505 template<typename _InputIter> 00506 basic_string<_CharT, _Traits, _Alloc>& 00507 basic_string<_CharT, _Traits, _Alloc>:: 00508 _M_replace(iterator __i1, iterator __i2, _InputIter __k1, 00509 _InputIter __k2, input_iterator_tag) 00510 { 00511 // Save concerned source string data in a temporary. 00512 basic_string __s(__k1, __k2); 00513 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend()); 00514 } 00515 00516 // This is a special replace helper, which does not buffer internally 00517 // and can be used in "safe" situations involving forward iterators, 00518 // i.e., when source and destination ranges are known to not overlap. 00519 template<typename _CharT, typename _Traits, typename _Alloc> 00520 template<typename _ForwardIter> 00521 basic_string<_CharT, _Traits, _Alloc>& 00522 basic_string<_CharT, _Traits, _Alloc>:: 00523 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1, 00524 _ForwardIter __k2) 00525 { 00526 size_type __dnew = static_cast<size_type>(distance(__k1, __k2)); 00527 size_type __dold = __i2 - __i1; 00528 size_type __dmax = this->max_size(); 00529 00530 if (__dmax <= __dnew) 00531 __throw_length_error("basic_string::_M_replace"); 00532 size_type __off = __i1 - _M_ibegin(); 00533 _M_mutate(__off, __dold, __dnew); 00534 00535 // Invalidated __i1, __i2 00536 if (__dnew) 00537 _S_copy_chars(_M_data() + __off, __k1, __k2); 00538 00539 return *this; 00540 } 00541 00542 template<typename _CharT, typename _Traits, typename _Alloc> 00543 basic_string<_CharT, _Traits, _Alloc>& 00544 basic_string<_CharT, _Traits, _Alloc>:: 00545 replace(size_type __pos1, size_type __n1, const basic_string& __str, 00546 size_type __pos2, size_type __n2) 00547 { 00548 const size_type __strsize = __str.size(); 00549 if (__pos2 > __strsize) 00550 __throw_out_of_range("basic_string::replace"); 00551 const bool __testn2 = __n2 < __strsize - __pos2; 00552 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2; 00553 return this->replace(__pos1, __n1, 00554 __str._M_data() + __pos2, __foldn2); 00555 } 00556 00557 template<typename _CharT, typename _Traits, typename _Alloc> 00558 basic_string<_CharT, _Traits, _Alloc>& 00559 basic_string<_CharT, _Traits, _Alloc>:: 00560 append(const basic_string& __str) 00561 { 00562 // Iff appending itself, string needs to pre-reserve the 00563 // correct size so that _M_mutate does not clobber the 00564 // iterators formed here. 00565 size_type __size = __str.size(); 00566 size_type __len = __size + this->size(); 00567 if (__len > this->capacity()) 00568 this->reserve(__len); 00569 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(), 00570 __str._M_iend()); 00571 } 00572 00573 template<typename _CharT, typename _Traits, typename _Alloc> 00574 basic_string<_CharT, _Traits, _Alloc>& 00575 basic_string<_CharT, _Traits, _Alloc>:: 00576 append(const basic_string& __str, size_type __pos, size_type __n) 00577 { 00578 // Iff appending itself, string needs to pre-reserve the 00579 // correct size so that _M_mutate does not clobber the 00580 // iterators formed here. 00581 size_type __len = min(__str.size() - __pos, __n) + this->size(); 00582 if (__len > this->capacity()) 00583 this->reserve(__len); 00584 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos), 00585 __str._M_fold(__pos, __n)); 00586 } 00587 00588 template<typename _CharT, typename _Traits, typename _Alloc> 00589 basic_string<_CharT, _Traits, _Alloc>& 00590 basic_string<_CharT, _Traits, _Alloc>:: 00591 append(const _CharT* __s, size_type __n) 00592 { 00593 size_type __len = __n + this->size(); 00594 if (__len > this->capacity()) 00595 this->reserve(__len); 00596 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n); 00597 } 00598 00599 template<typename _CharT, typename _Traits, typename _Alloc> 00600 basic_string<_CharT, _Traits, _Alloc>& 00601 basic_string<_CharT, _Traits, _Alloc>:: 00602 append(size_type __n, _CharT __c) 00603 { 00604 size_type __len = __n + this->size(); 00605 if (__len > this->capacity()) 00606 this->reserve(__len); 00607 return this->replace(_M_iend(), _M_iend(), __n, __c); 00608 } 00609 00610 template<typename _CharT, typename _Traits, typename _Alloc> 00611 basic_string<_CharT, _Traits, _Alloc> 00612 operator+(const _CharT* __lhs, 00613 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00614 { 00615 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00616 typedef typename __string_type::size_type __size_type; 00617 __size_type __len = _Traits::length(__lhs); 00618 __string_type __str; 00619 __str.reserve(__len + __rhs.size()); 00620 __str.append(__lhs, __lhs + __len); 00621 __str.append(__rhs); 00622 return __str; 00623 } 00624 00625 template<typename _CharT, typename _Traits, typename _Alloc> 00626 basic_string<_CharT, _Traits, _Alloc> 00627 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00628 { 00629 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00630 typedef typename __string_type::size_type __size_type; 00631 __string_type __str; 00632 __size_type __len = __rhs.size(); 00633 __str.reserve(__len + 1); 00634 __str.append(__size_type(1), __lhs); 00635 __str.append(__rhs); 00636 return __str; 00637 } 00638 00639 template<typename _CharT, typename _Traits, typename _Alloc> 00640 basic_string<_CharT, _Traits, _Alloc>& 00641 basic_string<_CharT, _Traits, _Alloc>:: 00642 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c) 00643 { 00644 size_type __n1 = __i2 - __i1; 00645 size_type __off1 = __i1 - _M_ibegin(); 00646 if (max_size() - (this->size() - __n1) <= __n2) 00647 __throw_length_error("basic_string::replace"); 00648 _M_mutate (__off1, __n1, __n2); 00649 // Invalidated __i1, __i2 00650 if (__n2) 00651 traits_type::assign(_M_data() + __off1, __n2, __c); 00652 return *this; 00653 } 00654 00655 template<typename _CharT, typename _Traits, typename _Alloc> 00656 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00657 basic_string<_CharT, _Traits, _Alloc>:: 00658 copy(_CharT* __s, size_type __n, size_type __pos) const 00659 { 00660 if (__pos > this->size()) 00661 __throw_out_of_range("basic_string::copy"); 00662 00663 if (__n > this->size() - __pos) 00664 __n = this->size() - __pos; 00665 00666 traits_type::copy(__s, _M_data() + __pos, __n); 00667 // 21.3.5.7 par 3: do not append null. (good.) 00668 return __n; 00669 } 00670 00671 template<typename _CharT, typename _Traits, typename _Alloc> 00672 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00673 basic_string<_CharT, _Traits, _Alloc>:: 00674 find(const _CharT* __s, size_type __pos, size_type __n) const 00675 { 00676 size_type __size = this->size(); 00677 size_t __xpos = __pos; 00678 const _CharT* __data = _M_data(); 00679 for (; __xpos + __n <= __size; ++__xpos) 00680 if (traits_type::compare(__data + __xpos, __s, __n) == 0) 00681 return __xpos; 00682 return npos; 00683 } 00684 00685 template<typename _CharT, typename _Traits, typename _Alloc> 00686 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00687 basic_string<_CharT, _Traits, _Alloc>:: 00688 find(_CharT __c, size_type __pos) const 00689 { 00690 size_type __size = this->size(); 00691 size_type __ret = npos; 00692 if (__pos < __size) 00693 { 00694 const _CharT* __data = _M_data(); 00695 size_type __n = __size - __pos; 00696 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 00697 if (__p) 00698 __ret = __p - __data; 00699 } 00700 return __ret; 00701 } 00702 00703 00704 template<typename _CharT, typename _Traits, typename _Alloc> 00705 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00706 basic_string<_CharT, _Traits, _Alloc>:: 00707 rfind(const _CharT* __s, size_type __pos, size_type __n) const 00708 { 00709 size_type __size = this->size(); 00710 if (__n <= __size) 00711 { 00712 __pos = std::min(__size - __n, __pos); 00713 const _CharT* __data = _M_data(); 00714 do 00715 { 00716 if (traits_type::compare(__data + __pos, __s, __n) == 0) 00717 return __pos; 00718 } 00719 while (__pos-- > 0); 00720 } 00721 return npos; 00722 } 00723 00724 template<typename _CharT, typename _Traits, typename _Alloc> 00725 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00726 basic_string<_CharT, _Traits, _Alloc>:: 00727 rfind(_CharT __c, size_type __pos) const 00728 { 00729 size_type __size = this->size(); 00730 if (__size) 00731 { 00732 size_t __xpos = __size - 1; 00733 if (__xpos > __pos) 00734 __xpos = __pos; 00735 00736 for (++__xpos; __xpos-- > 0; ) 00737 if (traits_type::eq(_M_data()[__xpos], __c)) 00738 return __xpos; 00739 } 00740 return npos; 00741 } 00742 00743 template<typename _CharT, typename _Traits, typename _Alloc> 00744 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00745 basic_string<_CharT, _Traits, _Alloc>:: 00746 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 00747 { 00748 for (; __n && __pos < this->size(); ++__pos) 00749 { 00750 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 00751 if (__p) 00752 return __pos; 00753 } 00754 return npos; 00755 } 00756 00757 template<typename _CharT, typename _Traits, typename _Alloc> 00758 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00759 basic_string<_CharT, _Traits, _Alloc>:: 00760 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 00761 { 00762 size_type __size = this->size(); 00763 if (__size && __n) 00764 { 00765 if (--__size > __pos) 00766 __size = __pos; 00767 do 00768 { 00769 if (traits_type::find(__s, __n, _M_data()[__size])) 00770 return __size; 00771 } 00772 while (__size-- != 0); 00773 } 00774 return npos; 00775 } 00776 00777 template<typename _CharT, typename _Traits, typename _Alloc> 00778 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00779 basic_string<_CharT, _Traits, _Alloc>:: 00780 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00781 { 00782 size_t __xpos = __pos; 00783 for (; __xpos < this->size(); ++__xpos) 00784 if (!traits_type::find(__s, __n, _M_data()[__xpos])) 00785 return __xpos; 00786 return npos; 00787 } 00788 00789 template<typename _CharT, typename _Traits, typename _Alloc> 00790 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00791 basic_string<_CharT, _Traits, _Alloc>:: 00792 find_first_not_of(_CharT __c, size_type __pos) const 00793 { 00794 size_t __xpos = __pos; 00795 for (; __xpos < this->size(); ++__xpos) 00796 if (!traits_type::eq(_M_data()[__xpos], __c)) 00797 return __xpos; 00798 return npos; 00799 } 00800 00801 template<typename _CharT, typename _Traits, typename _Alloc> 00802 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00803 basic_string<_CharT, _Traits, _Alloc>:: 00804 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00805 { 00806 size_type __size = this->size(); 00807 if (__size) 00808 { 00809 if (--__size > __pos) 00810 __size = __pos; 00811 do 00812 { 00813 if (!traits_type::find(__s, __n, _M_data()[__size])) 00814 return __size; 00815 } 00816 while (__size--); 00817 } 00818 return npos; 00819 } 00820 00821 template<typename _CharT, typename _Traits, typename _Alloc> 00822 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00823 basic_string<_CharT, _Traits, _Alloc>:: 00824 find_last_not_of(_CharT __c, size_type __pos) const 00825 { 00826 size_type __size = this->size(); 00827 if (__size) 00828 { 00829 if (--__size > __pos) 00830 __size = __pos; 00831 do 00832 { 00833 if (!traits_type::eq(_M_data()[__size], __c)) 00834 return __size; 00835 } 00836 while (__size--); 00837 } 00838 return npos; 00839 } 00840 00841 template<typename _CharT, typename _Traits, typename _Alloc> 00842 int 00843 basic_string<_CharT, _Traits, _Alloc>:: 00844 compare(size_type __pos, size_type __n, const basic_string& __str) const 00845 { 00846 size_type __size = this->size(); 00847 size_type __osize = __str.size(); 00848 if (__pos > __size) 00849 __throw_out_of_range("basic_string::compare"); 00850 00851 size_type __rsize= min(__size - __pos, __n); 00852 size_type __len = min(__rsize, __osize); 00853 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 00854 if (!__r) 00855 __r = __rsize - __osize; 00856 return __r; 00857 } 00858 00859 template<typename _CharT, typename _Traits, typename _Alloc> 00860 int 00861 basic_string<_CharT, _Traits, _Alloc>:: 00862 compare(size_type __pos1, size_type __n1, const basic_string& __str, 00863 size_type __pos2, size_type __n2) const 00864 { 00865 size_type __size = this->size(); 00866 size_type __osize = __str.size(); 00867 if (__pos1 > __size || __pos2 > __osize) 00868 __throw_out_of_range("basic_string::compare"); 00869 00870 size_type __rsize = min(__size - __pos1, __n1); 00871 size_type __rosize = min(__osize - __pos2, __n2); 00872 size_type __len = min(__rsize, __rosize); 00873 int __r = traits_type::compare(_M_data() + __pos1, 00874 __str.data() + __pos2, __len); 00875 if (!__r) 00876 __r = __rsize - __rosize; 00877 return __r; 00878 } 00879 00880 00881 template<typename _CharT, typename _Traits, typename _Alloc> 00882 int 00883 basic_string<_CharT, _Traits, _Alloc>:: 00884 compare(const _CharT* __s) const 00885 { 00886 size_type __size = this->size(); 00887 size_type __osize = traits_type::length(__s); 00888 size_type __len = min(__size, __osize); 00889 int __r = traits_type::compare(_M_data(), __s, __len); 00890 if (!__r) 00891 __r = __size - __osize; 00892 return __r; 00893 } 00894 00895 00896 template<typename _CharT, typename _Traits, typename _Alloc> 00897 int 00898 basic_string <_CharT, _Traits, _Alloc>:: 00899 compare(size_type __pos, size_type __n1, const _CharT* __s) const 00900 { 00901 size_type __size = this->size(); 00902 if (__pos > __size) 00903 __throw_out_of_range("basic_string::compare"); 00904 00905 size_type __osize = traits_type::length(__s); 00906 size_type __rsize = min(__size - __pos, __n1); 00907 size_type __len = min(__rsize, __osize); 00908 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 00909 if (!__r) 00910 __r = __rsize - __osize; 00911 return __r; 00912 } 00913 00914 template<typename _CharT, typename _Traits, typename _Alloc> 00915 int 00916 basic_string <_CharT, _Traits, _Alloc>:: 00917 compare(size_type __pos, size_type __n1, const _CharT* __s, 00918 size_type __n2) const 00919 { 00920 size_type __size = this->size(); 00921 if (__pos > __size) 00922 __throw_out_of_range("basic_string::compare"); 00923 00924 size_type __osize = min(traits_type::length(__s), __n2); 00925 size_type __rsize = min(__size - __pos, __n1); 00926 size_type __len = min(__rsize, __osize); 00927 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 00928 if (!__r) 00929 __r = __rsize - __osize; 00930 return __r; 00931 } 00932 00933 template <class _CharT, class _Traits, class _Alloc> 00934 void 00935 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str, 00936 _CharT* __buf, typename _Alloc::size_type __bufsiz) 00937 { 00938 typedef typename _Alloc::size_type size_type; 00939 size_type __strsize = __str.size(); 00940 size_type __bytes = min(__strsize, __bufsiz - 1); 00941 _Traits::copy(__buf, __str.data(), __bytes); 00942 __buf[__bytes] = _CharT(); 00943 } 00944 00945 // Inhibit implicit instantiations for required instantiations, 00946 // which are defined via explicit instantiations elsewhere. 00947 // NB: This syntax is a GNU extension. 00948 extern template class basic_string<char>; 00949 extern template 00950 basic_istream<char>& 00951 operator>>(basic_istream<char>&, string&); 00952 extern template 00953 basic_ostream<char>& 00954 operator<<(basic_ostream<char>&, const string&); 00955 extern template 00956 basic_istream<char>& 00957 getline(basic_istream<char>&, string&, char); 00958 extern template 00959 basic_istream<char>& 00960 getline(basic_istream<char>&, string&); 00961 00962 #ifdef _GLIBCPP_USE_WCHAR_T 00963 extern template class basic_string<wchar_t>; 00964 extern template 00965 basic_istream<wchar_t>& 00966 operator>>(basic_istream<wchar_t>&, wstring&); 00967 extern template 00968 basic_ostream<wchar_t>& 00969 operator<<(basic_ostream<wchar_t>&, const wstring&); 00970 extern template 00971 basic_istream<wchar_t>& 00972 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 00973 extern template 00974 basic_istream<wchar_t>& 00975 getline(basic_istream<wchar_t>&, wstring&); 00976 #endif 00977 } // namespace std 00978 00979 #endif

Generated on Wed Sep 29 13:54:47 2004 for libstdc++-v3 Source by doxygen 1.3.7