1 // Components for manipulating sequences of characters -*- C++ -*- 2 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. 11 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. 16 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. 21 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. 30 31 // 32 // ISO C++ 14882: 21 Strings library 33 // 34 35 // This file is included by <string>. It is not meant to be included 36 // separately. 37 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. 40 41 #ifndef _CPP_BITS_STRING_TCC 42 #define _CPP_BITS_STRING_TCC 1 43 44 #pragma GCC system_header 45 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; 52 53 template<typename _CharT, typename _Traits, typename _Alloc> 54 const _CharT 55 basic_string<_CharT, _Traits, _Alloc>:: 56 _Rep::_S_terminal = _CharT(); 57 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; 61 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)]; 68 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 } 132 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)); 141 142 // NB: Not required, but considered best practice. 143 if (__builtin_expect(__beg == _InIter(0), 0)) 144 __throw_logic_error("attempt to create string with null pointer"); 145 146 if (__beg == __end && __a == _Alloc()) 147 return _S_empty_rep()._M_refcopy(); 148 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; 159 160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr. 161 return __r->_M_refdata(); 162 } 163 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(); 171 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 } 188 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 { } 195 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 { } 201 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 { } 208 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 { } 216 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 { } 222 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) : 0, 227 __a), __a) 228 { } 229 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 { } 235 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 { } 242 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 } 257 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 } 266 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 } 275 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; 291 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 } 337 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 } 355 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 } 379 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"); 393 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); 398 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. 411 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 } 440 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 } 450 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); 472 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 } 486 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 } 500 501 // This is the general replace helper, which gets instantiated both 502 // for input-iterators and forward-iterators. It buffers internally and 503 // then calls _M_replace_safe. For input-iterators this is almost the 504 // best we can do, but for forward-iterators many optimizations could be 505 // conceived: f.i., when source and destination ranges do not overlap 506 // buffering is not really needed. In order to easily implement them, it 507 // could become useful to add an _M_replace(forward_iterator_tag) 508 template<typename _CharT, typename _Traits, typename _Alloc> 509 template<typename _InputIter> 510 basic_string<_CharT, _Traits, _Alloc>& 511 basic_string<_CharT, _Traits, _Alloc>:: 512 _M_replace(iterator __i1, iterator __i2, _InputIter __k1, 513 _InputIter __k2, input_iterator_tag) 514 { 515 // Save concerned source string data in a temporary. 516 basic_string __s(__k1, __k2); 517 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend()); 518 } 519 520 // This is a special replace helper, which does not buffer internally 521 // and can be used in the "safe" situations involving forward-iterators, 522 // i.e., when source and destination ranges are known to not overlap. 523 // Presently, is called by _M_replace, by the various append and by 524 // the assigns. 525 template<typename _CharT, typename _Traits, typename _Alloc> 526 template<typename _ForwardIter> 527 basic_string<_CharT, _Traits, _Alloc>& 528 basic_string<_CharT, _Traits, _Alloc>:: 529 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1, 530 _ForwardIter __k2) 531 { 532 size_type __dnew = static_cast<size_type>(distance(__k1, __k2)); 533 size_type __dold = __i2 - __i1; 534 size_type __dmax = this->max_size(); 535 536 if (__dmax <= __dnew) 537 __throw_length_error("basic_string::_M_replace"); 538 size_type __off = __i1 - _M_ibegin(); 539 _M_mutate(__off, __dold, __dnew); 540 541 // Invalidated __i1, __i2 542 if (__dnew) 543 _S_copy_chars(_M_data() + __off, __k1, __k2); 544 545 return *this; 546 } 547 548 template<typename _CharT, typename _Traits, typename _Alloc> 549 basic_string<_CharT, _Traits, _Alloc>& 550 basic_string<_CharT, _Traits, _Alloc>:: 551 replace(size_type __pos1, size_type __n1, const basic_string& __str, 552 size_type __pos2, size_type __n2) 553 { 554 const size_type __strsize = __str.size(); 555 if (__pos2 > __strsize) 556 __throw_out_of_range("basic_string::replace"); 557 const bool __testn2 = __n2 < __strsize - __pos2; 558 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2; 559 return this->replace(__pos1, __n1, 560 __str._M_data() + __pos2, __foldn2); 561 } 562 563 template<typename _CharT, typename _Traits, typename _Alloc> 564 basic_string<_CharT, _Traits, _Alloc>& 565 basic_string<_CharT, _Traits, _Alloc>:: 566 append(const basic_string& __str) 567 { 568 // Iff appending itself, string needs to pre-reserve the 569 // correct size so that _M_mutate does not clobber the 570 // iterators formed here. 571 size_type __size = __str.size(); 572 size_type __len = __size + this->size(); 573 if (__len > this->capacity()) 574 this->reserve(__len); 575 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(), 576 __str._M_iend()); 577 } 578 579 template<typename _CharT, typename _Traits, typename _Alloc> 580 basic_string<_CharT, _Traits, _Alloc>& 581 basic_string<_CharT, _Traits, _Alloc>:: 582 append(const basic_string& __str, size_type __pos, size_type __n) 583 { 584 // Iff appending itself, string needs to pre-reserve the 585 // correct size so that _M_mutate does not clobber the 586 // iterators formed here. 587 size_type __len = min(__str.size() - __pos, __n) + this->size(); 588 if (__len > this->capacity()) 589 this->reserve(__len); 590 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos), 591 __str._M_fold(__pos, __n)); 592 } 593 594 template<typename _CharT, typename _Traits, typename _Alloc> 595 basic_string<_CharT, _Traits, _Alloc>& 596 basic_string<_CharT, _Traits, _Alloc>:: 597 append(const _CharT* __s, size_type __n) 598 { 599 size_type __len = __n + this->size(); 600 if (__len > this->capacity()) 601 this->reserve(__len); 602 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n); 603 } 604 605 template<typename _CharT, typename _Traits, typename _Alloc> 606 basic_string<_CharT, _Traits, _Alloc>& 607 basic_string<_CharT, _Traits, _Alloc>:: 608 append(size_type __n, _CharT __c) 609 { 610 size_type __len = __n + this->size(); 611 if (__len > this->capacity()) 612 this->reserve(__len); 613 return this->replace(_M_iend(), _M_iend(), __n, __c); 614 } 615 616 template<typename _CharT, typename _Traits, typename _Alloc> 617 basic_string<_CharT, _Traits, _Alloc> 618 operator+(const _CharT* __lhs, 619 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 620 { 621 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 622 typedef typename __string_type::size_type __size_type; 623 __size_type __len = _Traits::length(__lhs); 624 __string_type __str; 625 __str.reserve(__len + __rhs.size()); 626 __str.append(__lhs, __lhs + __len); 627 __str.append(__rhs); 628 return __str; 629 } 630 631 template<typename _CharT, typename _Traits, typename _Alloc> 632 basic_string<_CharT, _Traits, _Alloc> 633 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 634 { 635 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 636 typedef typename __string_type::size_type __size_type; 637 __string_type __str; 638 __size_type __len = __rhs.size(); 639 __str.reserve(__len + 1); 640 __str.append(__size_type(1), __lhs); 641 __str.append(__rhs); 642 return __str; 643 } 644 645 template<typename _CharT, typename _Traits, typename _Alloc> 646 basic_string<_CharT, _Traits, _Alloc>& 647 basic_string<_CharT, _Traits, _Alloc>:: 648 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c) 649 { 650 size_type __n1 = __i2 - __i1; 651 size_type __off1 = __i1 - _M_ibegin(); 652 if (max_size() - (this->size() - __n1) <= __n2) 653 __throw_length_error("basic_string::replace"); 654 _M_mutate (__off1, __n1, __n2); 655 // Invalidated __i1, __i2 656 if (__n2) 657 traits_type::assign(_M_data() + __off1, __n2, __c); 658 return *this; 659 } 660 661 template<typename _CharT, typename _Traits, typename _Alloc> 662 typename basic_string<_CharT, _Traits, _Alloc>::size_type 663 basic_string<_CharT, _Traits, _Alloc>:: 664 copy(_CharT* __s, size_type __n, size_type __pos) const 665 { 666 if (__pos > this->size()) 667 __throw_out_of_range("basic_string::copy"); 668 669 if (__n > this->size() - __pos) 670 __n = this->size() - __pos; 671 672 traits_type::copy(__s, _M_data() + __pos, __n); 673 // 21.3.5.7 par 3: do not append null. (good.) 674 return __n; 675 } 676 677 template<typename _CharT, typename _Traits, typename _Alloc> 678 typename basic_string<_CharT, _Traits, _Alloc>::size_type 679 basic_string<_CharT, _Traits, _Alloc>:: 680 find(const _CharT* __s, size_type __pos, size_type __n) const 681 { 682 size_type __size = this->size(); 683 size_t __xpos = __pos; 684 const _CharT* __data = _M_data(); 685 for (; __xpos + __n <= __size; ++__xpos) 686 if (traits_type::compare(__data + __xpos, __s, __n) == 0) 687 return __xpos; 688 return npos; 689 } 690 691 template<typename _CharT, typename _Traits, typename _Alloc> 692 typename basic_string<_CharT, _Traits, _Alloc>::size_type 693 basic_string<_CharT, _Traits, _Alloc>:: 694 find(_CharT __c, size_type __pos) const 695 { 696 size_type __size = this->size(); 697 size_type __ret = npos; 698 if (__pos < __size) 699 { 700 const _CharT* __data = _M_data(); 701 size_type __n = __size - __pos; 702 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 703 if (__p) 704 __ret = __p - __data; 705 } 706 return __ret; 707 } 708 709 710 template<typename _CharT, typename _Traits, typename _Alloc> 711 typename basic_string<_CharT, _Traits, _Alloc>::size_type 712 basic_string<_CharT, _Traits, _Alloc>:: 713 rfind(const _CharT* __s, size_type __pos, size_type __n) const 714 { 715 size_type __size = this->size(); 716 if (__n <= __size) 717 { 718 __pos = std::min(__size - __n, __pos); 719 const _CharT* __data = _M_data(); 720 do 721 { 722 if (traits_type::compare(__data + __pos, __s, __n) == 0) 723 return __pos; 724 } 725 while (__pos-- > 0); 726 } 727 return npos; 728 } 729 730 template<typename _CharT, typename _Traits, typename _Alloc> 731 typename basic_string<_CharT, _Traits, _Alloc>::size_type 732 basic_string<_CharT, _Traits, _Alloc>:: 733 rfind(_CharT __c, size_type __pos) const 734 { 735 size_type __size = this->size(); 736 if (__size) 737 { 738 size_t __xpos = __size - 1; 739 if (__xpos > __pos) 740 __xpos = __pos; 741 742 for (++__xpos; __xpos-- > 0; ) 743 if (traits_type::eq(_M_data()[__xpos], __c)) 744 return __xpos; 745 } 746 return npos; 747 } 748 749 template<typename _CharT, typename _Traits, typename _Alloc> 750 typename basic_string<_CharT, _Traits, _Alloc>::size_type 751 basic_string<_CharT, _Traits, _Alloc>:: 752 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 753 { 754 for (; __n && __pos < this->size(); ++__pos) 755 { 756 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 757 if (__p) 758 return __pos; 759 } 760 return npos; 761 } 762 763 template<typename _CharT, typename _Traits, typename _Alloc> 764 typename basic_string<_CharT, _Traits, _Alloc>::size_type 765 basic_string<_CharT, _Traits, _Alloc>:: 766 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 767 { 768 size_type __size = this->size(); 769 if (__size && __n) 770 { 771 if (--__size > __pos) 772 __size = __pos; 773 do 774 { 775 if (traits_type::find(__s, __n, _M_data()[__size])) 776 return __size; 777 } 778 while (__size-- != 0); 779 } 780 return npos; 781 } 782 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_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 787 { 788 size_t __xpos = __pos; 789 for (; __xpos < this->size(); ++__xpos) 790 if (!traits_type::find(__s, __n, _M_data()[__xpos])) 791 return __xpos; 792 return npos; 793 } 794 795 template<typename _CharT, typename _Traits, typename _Alloc> 796 typename basic_string<_CharT, _Traits, _Alloc>::size_type 797 basic_string<_CharT, _Traits, _Alloc>:: 798 find_first_not_of(_CharT __c, size_type __pos) const 799 { 800 size_t __xpos = __pos; 801 for (; __xpos < this->size(); ++__xpos) 802 if (!traits_type::eq(_M_data()[__xpos], __c)) 803 return __xpos; 804 return npos; 805 } 806 807 template<typename _CharT, typename _Traits, typename _Alloc> 808 typename basic_string<_CharT, _Traits, _Alloc>::size_type 809 basic_string<_CharT, _Traits, _Alloc>:: 810 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 811 { 812 size_type __size = this->size(); 813 if (__size) 814 { 815 if (--__size > __pos) 816 __size = __pos; 817 do 818 { 819 if (!traits_type::find(__s, __n, _M_data()[__size])) 820 return __size; 821 } 822 while (__size--); 823 } 824 return npos; 825 } 826 827 template<typename _CharT, typename _Traits, typename _Alloc> 828 typename basic_string<_CharT, _Traits, _Alloc>::size_type 829 basic_string<_CharT, _Traits, _Alloc>:: 830 find_last_not_of(_CharT __c, size_type __pos) const 831 { 832 size_type __size = this->size(); 833 if (__size) 834 { 835 if (--__size > __pos) 836 __size = __pos; 837 do 838 { 839 if (!traits_type::eq(_M_data()[__size], __c)) 840 return __size; 841 } 842 while (__size--); 843 } 844 return npos; 845 } 846 847 template<typename _CharT, typename _Traits, typename _Alloc> 848 int 849 basic_string<_CharT, _Traits, _Alloc>:: 850 compare(size_type __pos, size_type __n, const basic_string& __str) const 851 { 852 size_type __size = this->size(); 853 size_type __osize = __str.size(); 854 if (__pos > __size) 855 __throw_out_of_range("basic_string::compare"); 856 857 size_type __rsize= min(__size - __pos, __n); 858 size_type __len = min(__rsize, __osize); 859 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 860 if (!__r) 861 __r = __rsize - __osize; 862 return __r; 863 } 864 865 template<typename _CharT, typename _Traits, typename _Alloc> 866 int 867 basic_string<_CharT, _Traits, _Alloc>:: 868 compare(size_type __pos1, size_type __n1, const basic_string& __str, 869 size_type __pos2, size_type __n2) const 870 { 871 size_type __size = this->size(); 872 size_type __osize = __str.size(); 873 if (__pos1 > __size || __pos2 > __osize) 874 __throw_out_of_range("basic_string::compare"); 875 876 size_type __rsize = min(__size - __pos1, __n1); 877 size_type __rosize = min(__osize - __pos2, __n2); 878 size_type __len = min(__rsize, __rosize); 879 int __r = traits_type::compare(_M_data() + __pos1, 880 __str.data() + __pos2, __len); 881 if (!__r) 882 __r = __rsize - __rosize; 883 return __r; 884 } 885 886 887 template<typename _CharT, typename _Traits, typename _Alloc> 888 int 889 basic_string<_CharT, _Traits, _Alloc>:: 890 compare(const _CharT* __s) const 891 { 892 size_type __size = this->size(); 893 int __r = traits_type::compare(_M_data(), __s, __size); 894 if (!__r) 895 __r = __size - traits_type::length(__s); 896 return __r; 897 } 898 899 900 template<typename _CharT, typename _Traits, typename _Alloc> 901 int 902 basic_string <_CharT, _Traits, _Alloc>:: 903 compare(size_type __pos, size_type __n1, const _CharT* __s) const 904 { 905 size_type __size = this->size(); 906 if (__pos > __size) 907 __throw_out_of_range("basic_string::compare"); 908 909 size_type __osize = traits_type::length(__s); 910 size_type __rsize = min(__size - __pos, __n1); 911 size_type __len = min(__rsize, __osize); 912 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 913 if (!__r) 914 __r = __rsize - __osize; 915 return __r; 916 } 917 918 template<typename _CharT, typename _Traits, typename _Alloc> 919 int 920 basic_string <_CharT, _Traits, _Alloc>:: 921 compare(size_type __pos, size_type __n1, const _CharT* __s, 922 size_type __n2) const 923 { 924 size_type __size = this->size(); 925 if (__pos > __size) 926 __throw_out_of_range("basic_string::compare"); 927 928 size_type __osize = min(traits_type::length(__s), __n2); 929 size_type __rsize = min(__size - __pos, __n1); 930 size_type __len = min(__rsize, __osize); 931 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 932 if (!__r) 933 __r = __rsize - __osize; 934 return __r; 935 } 936 937 template <class _CharT, class _Traits, class _Alloc> 938 void 939 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str, 940 _CharT* __buf, typename _Alloc::size_type __bufsiz) 941 { 942 typedef typename _Alloc::size_type size_type; 943 size_type __strsize = __str.size(); 944 size_type __bytes = min(__strsize, __bufsiz - 1); 945 _Traits::copy(__buf, __str.data(), __bytes); 946 __buf[__bytes] = _CharT(); 947 } 948 949 // Inhibit implicit instantiations for required instantiations, 950 // which are defined via explicit instantiations elsewhere. 951 // NB: This syntax is a GNU extension. 952 extern template class basic_string<char>; 953 extern template 954 basic_istream<char>& 955 operator>>(basic_istream<char>&, string&); 956 extern template 957 basic_ostream<char>& 958 operator<<(basic_ostream<char>&, const string&); 959 extern template 960 basic_istream<char>& 961 getline(basic_istream<char>&, string&, char); 962 extern template 963 basic_istream<char>& 964 getline(basic_istream<char>&, string&); 965 966 extern template class basic_string<wchar_t>; 967 extern template 968 basic_istream<wchar_t>& 969 operator>>(basic_istream<wchar_t>&, wstring&); 970 extern template 971 basic_ostream<wchar_t>& 972 operator<<(basic_ostream<wchar_t>&, const wstring&); 973 extern template 974 basic_istream<wchar_t>& 975 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 976 extern template 977 basic_istream<wchar_t>& 978 getline(basic_istream<wchar_t>&, wstring&); 979 } // namespace std 980 981 #endif 982