basic_string.tcc revision 132720
1// Components for manipulating sequences of characters -*- C++ -*- 2 3// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 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 _BASIC_STRING_TCC 42#define _BASIC_STRING_TCC 1 43 44#pragma GCC system_header 45 46namespace std 47{ 48 template<typename _Type> 49 inline bool 50 __is_null_pointer(_Type* __ptr) 51 { return __ptr == 0; } 52 53 template<typename _Type> 54 inline bool 55 __is_null_pointer(_Type) 56 { return false; } 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>:: 61 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 62 63 template<typename _CharT, typename _Traits, typename _Alloc> 64 const _CharT 65 basic_string<_CharT, _Traits, _Alloc>:: 66 _Rep::_S_terminal = _CharT(); 67 68 template<typename _CharT, typename _Traits, typename _Alloc> 69 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 70 basic_string<_CharT, _Traits, _Alloc>::npos; 71 72 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 73 // at static init time (before static ctors are run). 74 template<typename _CharT, typename _Traits, typename _Alloc> 75 typename basic_string<_CharT, _Traits, _Alloc>::size_type 76 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 77 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 78 sizeof(size_type)]; 79 80 // NB: This is the special case for Input Iterators, used in 81 // istreambuf_iterators, etc. 82 // Input Iterators have a cost structure very different from 83 // pointers, calling for a different coding style. 84 template<typename _CharT, typename _Traits, typename _Alloc> 85 template<typename _InIterator> 86 _CharT* 87 basic_string<_CharT, _Traits, _Alloc>:: 88 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 89 input_iterator_tag) 90 { 91 if (__beg == __end && __a == _Alloc()) 92 return _S_empty_rep()._M_refdata(); 93 // Avoid reallocation for common case. 94 _CharT __buf[128]; 95 size_type __len = 0; 96 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 97 { 98 __buf[__len++] = *__beg; 99 ++__beg; 100 } 101 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 102 traits_type::copy(__r->_M_refdata(), __buf, __len); 103 try 104 { 105 while (__beg != __end) 106 { 107 if (__len == __r->_M_capacity) 108 { 109 // Allocate more space. 110 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 111 traits_type::copy(__another->_M_refdata(), 112 __r->_M_refdata(), __len); 113 __r->_M_destroy(__a); 114 __r = __another; 115 } 116 __r->_M_refdata()[__len++] = *__beg; 117 ++__beg; 118 } 119 } 120 catch(...) 121 { 122 __r->_M_destroy(__a); 123 __throw_exception_again; 124 } 125 __r->_M_length = __len; 126 __r->_M_refdata()[__len] = _Rep::_S_terminal; // grrr. 127 return __r->_M_refdata(); 128 } 129 130 template<typename _CharT, typename _Traits, typename _Alloc> 131 template <typename _InIterator> 132 _CharT* 133 basic_string<_CharT, _Traits, _Alloc>:: 134 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 135 forward_iterator_tag) 136 { 137 if (__beg == __end && __a == _Alloc()) 138 return _S_empty_rep()._M_refdata(); 139 140 // NB: Not required, but considered best practice. 141 if (__builtin_expect(__is_null_pointer(__beg), 0)) 142 __throw_logic_error(__N("basic_string::_S_construct NULL not valid")); 143 144 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 145 __end)); 146 // Check for out_of_range and length_error exceptions. 147 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 148 try 149 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 150 catch(...) 151 { 152 __r->_M_destroy(__a); 153 __throw_exception_again; 154 } 155 __r->_M_length = __dnew; 156 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr. 157 return __r->_M_refdata(); 158 } 159 160 template<typename _CharT, typename _Traits, typename _Alloc> 161 _CharT* 162 basic_string<_CharT, _Traits, _Alloc>:: 163 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 164 { 165 if (__n == 0 && __a == _Alloc()) 166 return _S_empty_rep()._M_refdata(); 167 168 // Check for out_of_range and length_error exceptions. 169 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 170 if (__n) 171 traits_type::assign(__r->_M_refdata(), __n, __c); 172 173 __r->_M_length = __n; 174 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr 175 return __r->_M_refdata(); 176 } 177 178 template<typename _CharT, typename _Traits, typename _Alloc> 179 basic_string<_CharT, _Traits, _Alloc>:: 180 basic_string(const basic_string& __str) 181 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 182 __str.get_allocator()), 183 __str.get_allocator()) 184 { } 185 186 template<typename _CharT, typename _Traits, typename _Alloc> 187 basic_string<_CharT, _Traits, _Alloc>:: 188 basic_string(const _Alloc& __a) 189 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 190 { } 191 192 template<typename _CharT, typename _Traits, typename _Alloc> 193 basic_string<_CharT, _Traits, _Alloc>:: 194 basic_string(const basic_string& __str, size_type __pos, size_type __n) 195 : _M_dataplus(_S_construct(__str._M_data() 196 + __str._M_check(__pos, 197 "basic_string::basic_string"), 198 __str._M_data() + __str._M_limit(__pos, __n) 199 + __pos, _Alloc()), _Alloc()) 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, 205 size_type __n, const _Alloc& __a) 206 : _M_dataplus(_S_construct(__str._M_data() 207 + __str._M_check(__pos, 208 "basic_string::basic_string"), 209 __str._M_data() + __str._M_limit(__pos, __n) 210 + __pos, __a), __a) 211 { } 212 213 // TBD: DPG annotate 214 template<typename _CharT, typename _Traits, typename _Alloc> 215 basic_string<_CharT, _Traits, _Alloc>:: 216 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 217 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 218 { } 219 220 // TBD: DPG annotate 221 template<typename _CharT, typename _Traits, typename _Alloc> 222 basic_string<_CharT, _Traits, _Alloc>:: 223 basic_string(const _CharT* __s, const _Alloc& __a) 224 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 225 __s + npos, __a), __a) 226 { } 227 228 template<typename _CharT, typename _Traits, typename _Alloc> 229 basic_string<_CharT, _Traits, _Alloc>:: 230 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 231 : _M_dataplus(_S_construct(__n, __c, __a), __a) 232 { } 233 234 // TBD: DPG annotate 235 template<typename _CharT, typename _Traits, typename _Alloc> 236 template<typename _InputIterator> 237 basic_string<_CharT, _Traits, _Alloc>:: 238 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 239 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 240 { } 241 242 template<typename _CharT, typename _Traits, typename _Alloc> 243 basic_string<_CharT, _Traits, _Alloc>& 244 basic_string<_CharT, _Traits, _Alloc>:: 245 assign(const basic_string& __str) 246 { 247 if (_M_rep() != __str._M_rep()) 248 { 249 // XXX MT 250 const 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 basic_string<_CharT, _Traits, _Alloc>& 260 basic_string<_CharT, _Traits, _Alloc>:: 261 assign(const _CharT* __s, size_type __n) 262 { 263 __glibcxx_requires_string_len(__s, __n); 264 if (__n > this->max_size()) 265 __throw_length_error(__N("basic_string::assign")); 266 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 267 || less<const _CharT*>()(_M_data() + this->size(), __s)) 268 return _M_replace_safe(size_type(0), this->size(), __s, __n); 269 else 270 { 271 // Work in-place 272 const size_type __pos = __s - _M_data(); 273 if (__pos >= __n) 274 traits_type::copy(_M_data(), __s, __n); 275 else if (__pos) 276 traits_type::move(_M_data(), __s, __n); 277 _M_rep()->_M_set_sharable(); 278 _M_rep()->_M_length = __n; 279 _M_data()[__n] = _Rep::_S_terminal; // grr. 280 return *this; 281 } 282 } 283 284 template<typename _CharT, typename _Traits, typename _Alloc> 285 basic_string<_CharT, _Traits, _Alloc>& 286 basic_string<_CharT, _Traits, _Alloc>:: 287 insert(size_type __pos, const _CharT* __s, size_type __n) 288 { 289 __glibcxx_requires_string_len(__s, __n); 290 _M_check(__pos, "basic_string::insert"); 291 if (this->max_size() - this->size() < __n) 292 __throw_length_error(__N("basic_string::insert")); 293 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 294 || less<const _CharT*>()(_M_data() + this->size(), __s)) 295 return _M_replace_safe(__pos, size_type(0), __s, __n); 296 else 297 { 298 // Work in-place. If _M_mutate reallocates the string, __s 299 // does not point anymore to valid data, therefore we save its 300 // offset, then we restore it. 301 const size_type __off = __s - _M_data(); 302 _M_mutate(__pos, 0, __n); 303 __s = _M_data() + __off; 304 _CharT* __p = _M_data() + __pos; 305 if (__s + __n <= __p) 306 traits_type::copy(__p, __s, __n); 307 else if (__s >= __p) 308 traits_type::copy(__p, __s + __n, __n); 309 else 310 { 311 const size_type __nleft = __p - __s; 312 traits_type::copy(__p, __s, __nleft); 313 traits_type::copy(__p + __nleft, __p + __n, __n - __nleft); 314 } 315 return *this; 316 } 317 } 318 319 template<typename _CharT, typename _Traits, typename _Alloc> 320 basic_string<_CharT, _Traits, _Alloc>& 321 basic_string<_CharT, _Traits, _Alloc>:: 322 replace(size_type __pos, size_type __n1, const _CharT* __s, 323 size_type __n2) 324 { 325 __glibcxx_requires_string_len(__s, __n2); 326 _M_check(__pos, "basic_string::replace"); 327 __n1 = _M_limit(__pos, __n1); 328 if (this->max_size() - (this->size() - __n1) < __n2) 329 __throw_length_error(__N("basic_string::replace")); 330 bool __left; 331 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 332 || less<const _CharT*>()(_M_data() + this->size(), __s)) 333 return _M_replace_safe(__pos, __n1, __s, __n2); 334 else if ((__left = __s + __n2 <= _M_data() + __pos) 335 || _M_data() + __pos + __n1 <= __s) 336 { 337 // Work in-place: non-overlapping case. 338 const size_type __off = __s - _M_data(); 339 _M_mutate(__pos, __n1, __n2); 340 if (__left) 341 traits_type::copy(_M_data() + __pos, 342 _M_data() + __off, __n2); 343 else 344 traits_type::copy(_M_data() + __pos, 345 _M_data() + __off + __n2 - __n1, __n2); 346 return *this; 347 } 348 else 349 { 350 // Todo: overlapping case. 351 const basic_string __tmp(__s, __n2); 352 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 353 } 354 } 355 356 template<typename _CharT, typename _Traits, typename _Alloc> 357 void 358 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 359 _M_destroy(const _Alloc& __a) throw () 360 { 361 if (this == &_S_empty_rep()) 362 return; 363 const size_type __size = sizeof(_Rep_base) + 364 (this->_M_capacity + 1) * sizeof(_CharT); 365 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 366 } 367 368 template<typename _CharT, typename _Traits, typename _Alloc> 369 void 370 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard() 371 { 372 if (_M_rep() == &_S_empty_rep()) 373 return; 374 if (_M_rep()->_M_is_shared()) 375 _M_mutate(0, 0, 0); 376 _M_rep()->_M_set_leaked(); 377 } 378 379 template<typename _CharT, typename _Traits, typename _Alloc> 380 void 381 basic_string<_CharT, _Traits, _Alloc>:: 382 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 383 { 384 const size_type __old_size = this->size(); 385 const size_type __new_size = __old_size + __len2 - __len1; 386 const size_type __how_much = __old_size - __pos - __len1; 387 388 if (_M_rep() == &_S_empty_rep() 389 || _M_rep()->_M_is_shared() || __new_size > capacity()) 390 { 391 // Must reallocate. 392 const allocator_type __a = get_allocator(); 393 _Rep* __r = _Rep::_S_create(__new_size, capacity(), __a); 394 395 if (__pos) 396 traits_type::copy(__r->_M_refdata(), _M_data(), __pos); 397 if (__how_much) 398 traits_type::copy(__r->_M_refdata() + __pos + __len2, 399 _M_data() + __pos + __len1, __how_much); 400 401 _M_rep()->_M_dispose(__a); 402 _M_data(__r->_M_refdata()); 403 } 404 else if (__how_much && __len1 != __len2) 405 { 406 // Work in-place 407 traits_type::move(_M_data() + __pos + __len2, 408 _M_data() + __pos + __len1, __how_much); 409 } 410 _M_rep()->_M_set_sharable(); 411 _M_rep()->_M_length = __new_size; 412 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4) 413 // You cannot leave those LWG people alone for a second. 414 } 415 416 template<typename _CharT, typename _Traits, typename _Alloc> 417 void 418 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res) 419 { 420 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 421 { 422 if (__res > this->max_size()) 423 __throw_length_error(__N("basic_string::reserve")); 424 // Make sure we don't shrink below the current size 425 if (__res < this->size()) 426 __res = this->size(); 427 const allocator_type __a = get_allocator(); 428 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 429 _M_rep()->_M_dispose(__a); 430 _M_data(__tmp); 431 } 432 } 433 434 template<typename _CharT, typename _Traits, typename _Alloc> 435 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s) 436 { 437 if (_M_rep()->_M_is_leaked()) 438 _M_rep()->_M_set_sharable(); 439 if (__s._M_rep()->_M_is_leaked()) 440 __s._M_rep()->_M_set_sharable(); 441 if (this->get_allocator() == __s.get_allocator()) 442 { 443 _CharT* __tmp = _M_data(); 444 _M_data(__s._M_data()); 445 __s._M_data(__tmp); 446 } 447 // The code below can usually be optimized away. 448 else 449 { 450 const basic_string __tmp1(_M_ibegin(), _M_iend(), 451 __s.get_allocator()); 452 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 453 this->get_allocator()); 454 *this = __tmp2; 455 __s = __tmp1; 456 } 457 } 458 459 template<typename _CharT, typename _Traits, typename _Alloc> 460 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 461 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 462 _S_create(size_type __capacity, size_type __old_capacity, 463 const _Alloc& __alloc) 464 { 465 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 466 // _GLIBCXX_RESOLVE_LIB_DEFECTS 467 // 83. String::npos vs. string::max_size() 468 if (__capacity > _S_max_size) 469 __throw_length_error(__N("basic_string::_S_create")); 470 471 // The standard places no restriction on allocating more memory 472 // than is strictly needed within this layer at the moment or as 473 // requested by an explicit application call to reserve(). 474 475 // Many malloc implementations perform quite poorly when an 476 // application attempts to allocate memory in a stepwise fashion 477 // growing each allocation size by only 1 char. Additionally, 478 // it makes little sense to allocate less linear memory than the 479 // natural blocking size of the malloc implementation. 480 // Unfortunately, we would need a somewhat low-level calculation 481 // with tuned parameters to get this perfect for any particular 482 // malloc implementation. Fortunately, generalizations about 483 // common features seen among implementations seems to suffice. 484 485 // __pagesize need not match the actual VM page size for good 486 // results in practice, thus we pick a common value on the low 487 // side. __malloc_header_size is an estimate of the amount of 488 // overhead per memory allocation (in practice seen N * sizeof 489 // (void*) where N is 0, 2 or 4). According to folklore, 490 // picking this value on the high side is better than 491 // low-balling it (especially when this algorithm is used with 492 // malloc implementations that allocate memory blocks rounded up 493 // to a size which is a power of 2). 494 const size_type __pagesize = 4096; // must be 2^i * __subpagesize 495 const size_type __subpagesize = 128; // should be >> __malloc_header_size 496 const size_type __malloc_header_size = 4 * sizeof (void*); 497 498 // The below implements an exponential growth policy, necessary to 499 // meet amortized linear time requirements of the library: see 500 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 501 // It's active for allocations requiring an amount of memory above 502 // system pagesize. This is consistent with the requirements of the 503 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 504 505 // The biggest string which fits in a memory page 506 const size_type __page_capacity = ((__pagesize - __malloc_header_size 507 - sizeof(_Rep) - sizeof(_CharT)) 508 / sizeof(_CharT)); 509 510 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity 511 && __capacity > __page_capacity) 512 __capacity = 2 * __old_capacity; 513 514 // NB: Need an array of char_type[__capacity], plus a terminating 515 // null char_type() element, plus enough for the _Rep data structure. 516 // Whew. Seemingly so needy, yet so elemental. 517 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 518 519 const size_type __adj_size = __size + __malloc_header_size; 520 if (__adj_size > __pagesize) 521 { 522 const size_type __extra = __pagesize - __adj_size % __pagesize; 523 __capacity += __extra / sizeof(_CharT); 524 // Never allocate a string bigger than _S_max_size. 525 if (__capacity > _S_max_size) 526 __capacity = _S_max_size; 527 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 528 } 529 else if (__size > __subpagesize) 530 { 531 const size_type __extra = __subpagesize - __adj_size % __subpagesize; 532 __capacity += __extra / sizeof(_CharT); 533 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 534 } 535 536 // NB: Might throw, but no worries about a leak, mate: _Rep() 537 // does not throw. 538 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 539 _Rep *__p = new (__place) _Rep; 540 __p->_M_capacity = __capacity; 541 __p->_M_set_sharable(); // One reference. 542 __p->_M_length = 0; 543 return __p; 544 } 545 546 template<typename _CharT, typename _Traits, typename _Alloc> 547 _CharT* 548 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 549 _M_clone(const _Alloc& __alloc, size_type __res) 550 { 551 // Requested capacity of the clone. 552 const size_type __requested_cap = this->_M_length + __res; 553 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 554 __alloc); 555 if (this->_M_length) 556 traits_type::copy(__r->_M_refdata(), _M_refdata(), 557 this->_M_length); 558 559 __r->_M_length = this->_M_length; 560 __r->_M_refdata()[this->_M_length] = _Rep::_S_terminal; 561 return __r->_M_refdata(); 562 } 563 564 template<typename _CharT, typename _Traits, typename _Alloc> 565 void 566 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c) 567 { 568 if (__n > max_size()) 569 __throw_length_error(__N("basic_string::resize")); 570 const size_type __size = this->size(); 571 if (__size < __n) 572 this->append(__n - __size, __c); 573 else if (__n < __size) 574 this->erase(__n); 575 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 576 } 577 578 template<typename _CharT, typename _Traits, typename _Alloc> 579 template<typename _InputIterator> 580 basic_string<_CharT, _Traits, _Alloc>& 581 basic_string<_CharT, _Traits, _Alloc>:: 582 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 583 _InputIterator __k2, __false_type) 584 { 585 const basic_string __s(__k1, __k2); 586 const size_type __n1 = __i2 - __i1; 587 if (this->max_size() - (this->size() - __n1) < __s.size()) 588 __throw_length_error(__N("basic_string::_M_replace_dispatch")); 589 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 590 __s.size()); 591 } 592 593 template<typename _CharT, typename _Traits, typename _Alloc> 594 basic_string<_CharT, _Traits, _Alloc>& 595 basic_string<_CharT, _Traits, _Alloc>:: 596 append(const basic_string& __str) 597 { 598 // Iff appending itself, string needs to pre-reserve the 599 // correct size so that _M_mutate does not clobber the 600 // pointer __str._M_data() formed here. 601 const size_type __size = __str.size(); 602 const size_type __len = __size + this->size(); 603 if (__len > this->capacity()) 604 this->reserve(__len); 605 return _M_replace_safe(this->size(), size_type(0), __str._M_data(), 606 __str.size()); 607 } 608 609 template<typename _CharT, typename _Traits, typename _Alloc> 610 basic_string<_CharT, _Traits, _Alloc>& 611 basic_string<_CharT, _Traits, _Alloc>:: 612 append(const basic_string& __str, size_type __pos, size_type __n) 613 { 614 // Iff appending itself, string needs to pre-reserve the 615 // correct size so that _M_mutate does not clobber the 616 // pointer __str._M_data() formed here. 617 __str._M_check(__pos, "basic_string::append"); 618 __n = __str._M_limit(__pos, __n); 619 const size_type __len = __n + this->size(); 620 if (__len > this->capacity()) 621 this->reserve(__len); 622 return _M_replace_safe(this->size(), size_type(0), __str._M_data() 623 + __pos, __n); 624 } 625 626 template<typename _CharT, typename _Traits, typename _Alloc> 627 basic_string<_CharT, _Traits, _Alloc>& 628 basic_string<_CharT, _Traits, _Alloc>:: 629 append(const _CharT* __s, size_type __n) 630 { 631 __glibcxx_requires_string_len(__s, __n); 632 const size_type __len = __n + this->size(); 633 if (__len > this->capacity()) 634 this->reserve(__len); 635 return _M_replace_safe(this->size(), size_type(0), __s, __n); 636 } 637 638 template<typename _CharT, typename _Traits, typename _Alloc> 639 basic_string<_CharT, _Traits, _Alloc> 640 operator+(const _CharT* __lhs, 641 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 642 { 643 __glibcxx_requires_string(__lhs); 644 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 645 typedef typename __string_type::size_type __size_type; 646 const __size_type __len = _Traits::length(__lhs); 647 __string_type __str; 648 __str.reserve(__len + __rhs.size()); 649 __str.append(__lhs, __len); 650 __str.append(__rhs); 651 return __str; 652 } 653 654 template<typename _CharT, typename _Traits, typename _Alloc> 655 basic_string<_CharT, _Traits, _Alloc> 656 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 657 { 658 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 659 typedef typename __string_type::size_type __size_type; 660 __string_type __str; 661 const __size_type __len = __rhs.size(); 662 __str.reserve(__len + 1); 663 __str.append(__size_type(1), __lhs); 664 __str.append(__rhs); 665 return __str; 666 } 667 668 template<typename _CharT, typename _Traits, typename _Alloc> 669 typename basic_string<_CharT, _Traits, _Alloc>::size_type 670 basic_string<_CharT, _Traits, _Alloc>:: 671 copy(_CharT* __s, size_type __n, size_type __pos) const 672 { 673 _M_check(__pos, "basic_string::copy"); 674 __n = _M_limit(__pos, __n); 675 __glibcxx_requires_string_len(__s, __n); 676 if (__n) 677 traits_type::copy(__s, _M_data() + __pos, __n); 678 // 21.3.5.7 par 3: do not append null. (good.) 679 return __n; 680 } 681 682 template<typename _CharT, typename _Traits, typename _Alloc> 683 typename basic_string<_CharT, _Traits, _Alloc>::size_type 684 basic_string<_CharT, _Traits, _Alloc>:: 685 find(const _CharT* __s, size_type __pos, size_type __n) const 686 { 687 __glibcxx_requires_string_len(__s, __n); 688 const size_type __size = this->size(); 689 const _CharT* __data = _M_data(); 690 for (; __pos + __n <= __size; ++__pos) 691 if (traits_type::compare(__data + __pos, __s, __n) == 0) 692 return __pos; 693 return npos; 694 } 695 696 template<typename _CharT, typename _Traits, typename _Alloc> 697 typename basic_string<_CharT, _Traits, _Alloc>::size_type 698 basic_string<_CharT, _Traits, _Alloc>:: 699 find(_CharT __c, size_type __pos) const 700 { 701 const size_type __size = this->size(); 702 size_type __ret = npos; 703 if (__pos < __size) 704 { 705 const _CharT* __data = _M_data(); 706 const size_type __n = __size - __pos; 707 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 708 if (__p) 709 __ret = __p - __data; 710 } 711 return __ret; 712 } 713 714 template<typename _CharT, typename _Traits, typename _Alloc> 715 typename basic_string<_CharT, _Traits, _Alloc>::size_type 716 basic_string<_CharT, _Traits, _Alloc>:: 717 rfind(const _CharT* __s, size_type __pos, size_type __n) const 718 { 719 __glibcxx_requires_string_len(__s, __n); 720 const size_type __size = this->size(); 721 if (__n <= __size) 722 { 723 __pos = std::min(size_type(__size - __n), __pos); 724 const _CharT* __data = _M_data(); 725 do 726 { 727 if (traits_type::compare(__data + __pos, __s, __n) == 0) 728 return __pos; 729 } 730 while (__pos-- > 0); 731 } 732 return npos; 733 } 734 735 template<typename _CharT, typename _Traits, typename _Alloc> 736 typename basic_string<_CharT, _Traits, _Alloc>::size_type 737 basic_string<_CharT, _Traits, _Alloc>:: 738 rfind(_CharT __c, size_type __pos) const 739 { 740 size_type __size = this->size(); 741 if (__size) 742 { 743 if (--__size > __pos) 744 __size = __pos; 745 for (++__size; __size-- > 0; ) 746 if (traits_type::eq(_M_data()[__size], __c)) 747 return __size; 748 } 749 return npos; 750 } 751 752 template<typename _CharT, typename _Traits, typename _Alloc> 753 typename basic_string<_CharT, _Traits, _Alloc>::size_type 754 basic_string<_CharT, _Traits, _Alloc>:: 755 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 756 { 757 __glibcxx_requires_string_len(__s, __n); 758 for (; __n && __pos < this->size(); ++__pos) 759 { 760 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 761 if (__p) 762 return __pos; 763 } 764 return npos; 765 } 766 767 template<typename _CharT, typename _Traits, typename _Alloc> 768 typename basic_string<_CharT, _Traits, _Alloc>::size_type 769 basic_string<_CharT, _Traits, _Alloc>:: 770 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 771 { 772 __glibcxx_requires_string_len(__s, __n); 773 size_type __size = this->size(); 774 if (__size && __n) 775 { 776 if (--__size > __pos) 777 __size = __pos; 778 do 779 { 780 if (traits_type::find(__s, __n, _M_data()[__size])) 781 return __size; 782 } 783 while (__size-- != 0); 784 } 785 return npos; 786 } 787 788 template<typename _CharT, typename _Traits, typename _Alloc> 789 typename basic_string<_CharT, _Traits, _Alloc>::size_type 790 basic_string<_CharT, _Traits, _Alloc>:: 791 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 792 { 793 __glibcxx_requires_string_len(__s, __n); 794 for (; __pos < this->size(); ++__pos) 795 if (!traits_type::find(__s, __n, _M_data()[__pos])) 796 return __pos; 797 return npos; 798 } 799 800 template<typename _CharT, typename _Traits, typename _Alloc> 801 typename basic_string<_CharT, _Traits, _Alloc>::size_type 802 basic_string<_CharT, _Traits, _Alloc>:: 803 find_first_not_of(_CharT __c, size_type __pos) const 804 { 805 for (; __pos < this->size(); ++__pos) 806 if (!traits_type::eq(_M_data()[__pos], __c)) 807 return __pos; 808 return npos; 809 } 810 811 template<typename _CharT, typename _Traits, typename _Alloc> 812 typename basic_string<_CharT, _Traits, _Alloc>::size_type 813 basic_string<_CharT, _Traits, _Alloc>:: 814 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 815 { 816 __glibcxx_requires_string_len(__s, __n); 817 size_type __size = this->size(); 818 if (__size) 819 { 820 if (--__size > __pos) 821 __size = __pos; 822 do 823 { 824 if (!traits_type::find(__s, __n, _M_data()[__size])) 825 return __size; 826 } 827 while (__size--); 828 } 829 return npos; 830 } 831 832 template<typename _CharT, typename _Traits, typename _Alloc> 833 typename basic_string<_CharT, _Traits, _Alloc>::size_type 834 basic_string<_CharT, _Traits, _Alloc>:: 835 find_last_not_of(_CharT __c, size_type __pos) const 836 { 837 size_type __size = this->size(); 838 if (__size) 839 { 840 if (--__size > __pos) 841 __size = __pos; 842 do 843 { 844 if (!traits_type::eq(_M_data()[__size], __c)) 845 return __size; 846 } 847 while (__size--); 848 } 849 return npos; 850 } 851 852 template<typename _CharT, typename _Traits, typename _Alloc> 853 int 854 basic_string<_CharT, _Traits, _Alloc>:: 855 compare(size_type __pos, size_type __n, const basic_string& __str) const 856 { 857 _M_check(__pos, "basic_string::compare"); 858 __n = _M_limit(__pos, __n); 859 const size_type __osize = __str.size(); 860 const size_type __len = std::min(__n, __osize); 861 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 862 if (!__r) 863 __r = __n - __osize; 864 return __r; 865 } 866 867 template<typename _CharT, typename _Traits, typename _Alloc> 868 int 869 basic_string<_CharT, _Traits, _Alloc>:: 870 compare(size_type __pos1, size_type __n1, const basic_string& __str, 871 size_type __pos2, size_type __n2) const 872 { 873 _M_check(__pos1, "basic_string::compare"); 874 __str._M_check(__pos2, "basic_string::compare"); 875 __n1 = _M_limit(__pos1, __n1); 876 __n2 = __str._M_limit(__pos2, __n2); 877 const size_type __len = std::min(__n1, __n2); 878 int __r = traits_type::compare(_M_data() + __pos1, 879 __str.data() + __pos2, __len); 880 if (!__r) 881 __r = __n1 - __n2; 882 return __r; 883 } 884 885 template<typename _CharT, typename _Traits, typename _Alloc> 886 int 887 basic_string<_CharT, _Traits, _Alloc>:: 888 compare(const _CharT* __s) const 889 { 890 __glibcxx_requires_string(__s); 891 const size_type __size = this->size(); 892 const size_type __osize = traits_type::length(__s); 893 const size_type __len = std::min(__size, __osize); 894 int __r = traits_type::compare(_M_data(), __s, __len); 895 if (!__r) 896 __r = __size - __osize; 897 return __r; 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 __glibcxx_requires_string(__s); 906 _M_check(__pos, "basic_string::compare"); 907 __n1 = _M_limit(__pos, __n1); 908 const size_type __osize = traits_type::length(__s); 909 const size_type __len = std::min(__n1, __osize); 910 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 911 if (!__r) 912 __r = __n1 - __osize; 913 return __r; 914 } 915 916 template<typename _CharT, typename _Traits, typename _Alloc> 917 int 918 basic_string <_CharT, _Traits, _Alloc>:: 919 compare(size_type __pos, size_type __n1, const _CharT* __s, 920 size_type __n2) const 921 { 922 __glibcxx_requires_string_len(__s, __n2); 923 _M_check(__pos, "basic_string::compare"); 924 __n1 = _M_limit(__pos, __n1); 925 const size_type __len = std::min(__n1, __n2); 926 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 927 if (!__r) 928 __r = __n1 - __n2; 929 return __r; 930 } 931 932 // Inhibit implicit instantiations for required instantiations, 933 // which are defined via explicit instantiations elsewhere. 934 // NB: This syntax is a GNU extension. 935#if _GLIBCXX_EXTERN_TEMPLATE 936 extern template class basic_string<char>; 937 extern template 938 basic_istream<char>& 939 operator>>(basic_istream<char>&, string&); 940 extern template 941 basic_ostream<char>& 942 operator<<(basic_ostream<char>&, const string&); 943 extern template 944 basic_istream<char>& 945 getline(basic_istream<char>&, string&, char); 946 extern template 947 basic_istream<char>& 948 getline(basic_istream<char>&, string&); 949 950#ifdef _GLIBCXX_USE_WCHAR_T 951 extern template class basic_string<wchar_t>; 952 extern template 953 basic_istream<wchar_t>& 954 operator>>(basic_istream<wchar_t>&, wstring&); 955 extern template 956 basic_ostream<wchar_t>& 957 operator<<(basic_ostream<wchar_t>&, const wstring&); 958 extern template 959 basic_istream<wchar_t>& 960 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 961 extern template 962 basic_istream<wchar_t>& 963 getline(basic_istream<wchar_t>&, wstring&); 964#endif 965#endif 966} // namespace std 967 968#endif 969