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 /** @file basic_string.h 36 * This is an internal header file, included by other library headers. 37 * You should not attempt to use it directly. 38 */ 39 40 #ifndef _CPP_BITS_STRING_H 41 #define _CPP_BITS_STRING_H 1 42 43 #pragma GCC system_header 44 45 #include <bits/atomicity.h> 46 47 namespace std 48 { 49 // Documentation? What's that? 50 // Nathan Myers <[email protected]>. 51 // 52 // A string looks like this: 53 // 54 // [_Rep] 55 // _M_length 56 // [basic_string<char_type>] _M_capacity 57 // _M_dataplus _M_state 58 // _M_p ----------------> unnamed array of char_type 59 60 // Where the _M_p points to the first character in the string, and 61 // you cast it to a pointer-to-_Rep and subtract 1 to get a 62 // pointer to the header. 63 64 // This approach has the enormous advantage that a string object 65 // requires only one allocation. All the ugliness is confined 66 // within a single pair of inline functions, which each compile to 67 // a single "add" instruction: _Rep::_M_data(), and 68 // string::_M_rep(); and the allocation function which gets a 69 // block of raw bytes and with room enough and constructs a _Rep 70 // object at the front. 71 72 // The reason you want _M_data pointing to the character array and 73 // not the _Rep is so that the debugger can see the string 74 // contents. (Probably we should add a non-inline member to get 75 // the _Rep for the debugger to use, so users can check the actual 76 // string length.) 77 78 // Note that the _Rep object is a POD so that you can have a 79 // static "empty string" _Rep object already "constructed" before 80 // static constructors have run. The reference-count encoding is 81 // chosen so that a 0 indicates one reference, so you never try to 82 // destroy the empty-string _Rep object. 83 84 // All but the last paragraph is considered pretty conventional 85 // for a C++ string implementation. 86 87 // 21.3 Template class basic_string 88 template<typename _CharT, typename _Traits, typename _Alloc> 89 class basic_string 90 { 91 // Types: 92 public: 93 typedef _Traits traits_type; 94 typedef typename _Traits::char_type value_type; 95 typedef _Alloc allocator_type; 96 typedef typename _Alloc::size_type size_type; 97 typedef typename _Alloc::difference_type difference_type; 98 typedef typename _Alloc::reference reference; 99 typedef typename _Alloc::const_reference const_reference; 100 typedef typename _Alloc::pointer pointer; 101 typedef typename _Alloc::const_pointer const_pointer; 102 typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator; 103 typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string> 104 const_iterator; 105 typedef reverse_iterator<const_iterator> const_reverse_iterator; 106 typedef reverse_iterator<iterator> reverse_iterator; 107 108 private: 109 // _Rep: string representation 110 // Invariants: 111 // 1. String really contains _M_length + 1 characters; last is set 112 // to 0 only on call to c_str(). We avoid instantiating 113 // _CharT() where the interface does not require it. 114 // 2. _M_capacity >= _M_length 115 // Allocated memory is always _M_capacity + (1 * sizeof(_CharT)). 116 // 3. _M_references has three states: 117 // -1: leaked, one reference, no ref-copies allowed, non-const. 118 // 0: one reference, non-const. 119 // n>0: n + 1 references, operations require a lock, const. 120 // 4. All fields==0 is an empty string, given the extra storage 121 // beyond-the-end for a null terminator; thus, the shared 122 // empty string representation needs no constructor. 123 struct _Rep 124 { 125 // Types: 126 typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc; 127 128 // (Public) Data members: 129 130 // The maximum number of individual char_type elements of an 131 // individual string is determined by _S_max_size. This is the 132 // value that will be returned by max_size(). (Whereas npos 133 // is the maximum number of bytes the allocator can allocate.) 134 // If one was to divvy up the theoretical largest size string, 135 // with a terminating character and m _CharT elements, it'd 136 // look like this: 137 // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT) 138 // Solving for m: 139 // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1 140 // In addition, this implementation quarters this ammount. 141 static const size_type _S_max_size; 142 static const _CharT _S_terminal; 143 144 size_type _M_length; 145 size_type _M_capacity; 146 _Atomic_word _M_references; 147 148 bool 149 _M_is_leaked() const 150 { return _M_references < 0; } 151 152 bool 153 _M_is_shared() const 154 { return _M_references > 0; } 155 156 void 157 _M_set_leaked() 158 { _M_references = -1; } 159 160 void 161 _M_set_sharable() 162 { _M_references = 0; } 163 164 _CharT* 165 _M_refdata() throw() 166 { return reinterpret_cast<_CharT*>(this + 1); } 167 168 _CharT& 169 operator[](size_t __s) throw() 170 { return _M_refdata() [__s]; } 171 172 _CharT* 173 _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2) 174 { 175 return (!_M_is_leaked() && __alloc1 == __alloc2) 176 ? _M_refcopy() : _M_clone(__alloc1); 177 } 178 179 // Create & Destroy 180 static _Rep* 181 _S_create(size_t, const _Alloc&); 182 183 void 184 _M_dispose(const _Alloc& __a) 185 { 186 if (__exchange_and_add(&_M_references, -1) <= 0) 187 _M_destroy(__a); 188 } // XXX MT 189 190 void 191 _M_destroy(const _Alloc&) throw(); 192 193 _CharT* 194 _M_refcopy() throw() 195 { 196 __atomic_add(&_M_references, 1); 197 return _M_refdata(); 198 } // XXX MT 199 200 _CharT* 201 _M_clone(const _Alloc&, size_type __res = 0); 202 }; 203 204 // Use empty-base optimization: http://www.cantrip.org/emptyopt.html 205 struct _Alloc_hider : _Alloc 206 { 207 _Alloc_hider(_CharT* __dat, const _Alloc& __a) 208 : _Alloc(__a), _M_p(__dat) { } 209 210 _CharT* _M_p; // The actual data. 211 }; 212 213 public: 214 // Data Members (public): 215 // NB: This is an unsigned type, and thus represents the maximum 216 // size that the allocator can hold. 217 static const size_type npos = static_cast<size_type>(-1); 218 219 private: 220 // Data Members (private): 221 mutable _Alloc_hider _M_dataplus; 222 223 // The following storage is init'd to 0 by the linker, resulting 224 // (carefully) in an empty string with one reference. 225 static size_type _S_empty_rep_storage[(sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)]; 226 227 _CharT* 228 _M_data() const 229 { return _M_dataplus._M_p; } 230 231 _CharT* 232 _M_data(_CharT* __p) 233 { return (_M_dataplus._M_p = __p); } 234 235 _Rep* 236 _M_rep() const 237 { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); } 238 239 // For the internal use we have functions similar to `begin'/`end' 240 // but they do not call _M_leak. 241 iterator 242 _M_ibegin() const { return iterator(_M_data()); } 243 244 iterator 245 _M_iend() const { return iterator(_M_data() + this->size()); } 246 247 void 248 _M_leak() // for use in begin() & non-const op[] 249 { 250 if (!_M_rep()->_M_is_leaked()) 251 _M_leak_hard(); 252 } 253 254 iterator 255 _M_check(size_type __pos) const 256 { 257 if (__pos > this->size()) 258 __throw_out_of_range("basic_string::_M_check"); 259 return _M_ibegin() + __pos; 260 } 261 262 // NB: _M_fold doesn't check for a bad __pos1 value. 263 iterator 264 _M_fold(size_type __pos, size_type __off) const 265 { 266 bool __testoff = __off < this->size() - __pos; 267 size_type __newoff = __testoff ? __off : this->size() - __pos; 268 return (_M_ibegin() + __pos + __newoff); 269 } 270 271 // _S_copy_chars is a separate template to permit specialization 272 // to optimize for the common case of pointers as iterators. 273 template<class _Iterator> 274 static void 275 _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2) 276 { 277 for (; __k1 != __k2; ++__k1, ++__p) 278 traits_type::assign(*__p, *__k1); // These types are off. 279 } 280 281 static void 282 _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) 283 { _S_copy_chars(__p, __k1.base(), __k2.base()); } 284 285 static void 286 _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2) 287 { _S_copy_chars(__p, __k1.base(), __k2.base()); } 288 289 static void 290 _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) 291 { traits_type::copy(__p, __k1, __k2 - __k1); } 292 293 static void 294 _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2) 295 { traits_type::copy(__p, __k1, __k2 - __k1); } 296 297 void 298 _M_mutate(size_type __pos, size_type __len1, size_type __len2); 299 300 void 301 _M_leak_hard(); 302 303 static _Rep& 304 _S_empty_rep() 305 { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); } 306 307 public: 308 // Construct/copy/destroy: 309 // NB: We overload ctors in some cases instead of using default 310 // arguments, per 17.4.4.4 para. 2 item 2. 311 312 inline 313 basic_string(); 314 315 explicit 316 basic_string(const _Alloc& __a); 317 318 // NB: per LWG issue 42, semantics different from IS: 319 basic_string(const basic_string& __str); 320 basic_string(const basic_string& __str, size_type __pos, 321 size_type __n = npos); 322 basic_string(const basic_string& __str, size_type __pos, 323 size_type __n, const _Alloc& __a); 324 325 basic_string(const _CharT* __s, size_type __n, 326 const _Alloc& __a = _Alloc()); 327 basic_string(const _CharT* __s, const _Alloc& __a = _Alloc()); 328 basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc()); 329 330 template<class _InputIterator> 331 basic_string(_InputIterator __beg, _InputIterator __end, 332 const _Alloc& __a = _Alloc()); 333 334 ~basic_string() 335 { _M_rep()->_M_dispose(this->get_allocator()); } 336 337 basic_string& 338 operator=(const basic_string& __str) { return this->assign(__str); } 339 340 basic_string& 341 operator=(const _CharT* __s) { return this->assign(__s); } 342 343 basic_string& 344 operator=(_CharT __c) { return this->assign(1, __c); } 345 346 // Iterators: 347 iterator 348 begin() 349 { 350 _M_leak(); 351 return iterator(_M_data()); 352 } 353 354 const_iterator 355 begin() const 356 { return const_iterator(_M_data()); } 357 358 iterator 359 end() 360 { 361 _M_leak(); 362 return iterator(_M_data() + this->size()); 363 } 364 365 const_iterator 366 end() const 367 { return const_iterator(_M_data() + this->size()); } 368 369 reverse_iterator 370 rbegin() 371 { return reverse_iterator(this->end()); } 372 373 const_reverse_iterator 374 rbegin() const 375 { return const_reverse_iterator(this->end()); } 376 377 reverse_iterator 378 rend() 379 { return reverse_iterator(this->begin()); } 380 381 const_reverse_iterator 382 rend() const 383 { return const_reverse_iterator(this->begin()); } 384 385 public: 386 // Capacity: 387 size_type 388 size() const { return _M_rep()->_M_length; } 389 390 size_type 391 length() const { return _M_rep()->_M_length; } 392 393 size_type 394 max_size() const { return _Rep::_S_max_size; } 395 396 void 397 resize(size_type __n, _CharT __c); 398 399 void 400 resize(size_type __n) { this->resize(__n, _CharT()); } 401 402 size_type 403 capacity() const { return _M_rep()->_M_capacity; } 404 405 void 406 reserve(size_type __res_arg = 0); 407 408 void 409 clear() { _M_mutate(0, this->size(), 0); } 410 411 bool 412 empty() const { return this->size() == 0; } 413 414 // Element access: 415 const_reference 416 operator[] (size_type __pos) const 417 { return _M_data()[__pos]; } 418 419 reference 420 operator[](size_type __pos) 421 { 422 _M_leak(); 423 return _M_data()[__pos]; 424 } 425 426 const_reference 427 at(size_type __n) const 428 { 429 if (__n >= this->size()) 430 __throw_out_of_range("basic_string::at"); 431 return _M_data()[__n]; 432 } 433 434 reference 435 at(size_type __n) 436 { 437 if (__n >= size()) 438 __throw_out_of_range("basic_string::at"); 439 _M_leak(); 440 return _M_data()[__n]; 441 } 442 443 // Modifiers: 444 basic_string& 445 operator+=(const basic_string& __str) { return this->append(__str); } 446 447 basic_string& 448 operator+=(const _CharT* __s) { return this->append(__s); } 449 450 basic_string& 451 operator+=(_CharT __c) { return this->append(size_type(1), __c); } 452 453 basic_string& 454 append(const basic_string& __str); 455 456 basic_string& 457 append(const basic_string& __str, size_type __pos, size_type __n); 458 459 basic_string& 460 append(const _CharT* __s, size_type __n); 461 462 basic_string& 463 append(const _CharT* __s) 464 { return this->append(__s, traits_type::length(__s)); } 465 466 basic_string& 467 append(size_type __n, _CharT __c); 468 469 template<class _InputIterator> 470 basic_string& 471 append(_InputIterator __first, _InputIterator __last) 472 { return this->replace(_M_iend(), _M_iend(), __first, __last); } 473 474 void 475 push_back(_CharT __c) 476 { this->replace(_M_iend(), _M_iend(), 1, __c); } 477 478 basic_string& 479 assign(const basic_string& __str); 480 481 basic_string& 482 assign(const basic_string& __str, size_type __pos, size_type __n) 483 { 484 const size_type __strsize = __str.size(); 485 if (__pos > __strsize) 486 __throw_out_of_range("basic_string::assign"); 487 const bool __testn = __n < __strsize - __pos; 488 const size_type __newsize = __testn ? __n : __strsize - __pos; 489 return this->assign(__str._M_data() + __pos, __newsize); 490 } 491 492 basic_string& 493 assign(const _CharT* __s, size_type __n) 494 { 495 if (__n > this->max_size()) 496 __throw_length_error("basic_string::assign"); 497 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 498 || less<const _CharT*>()(_M_data() + this->size(), __s)) 499 return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n); 500 else 501 { 502 // Work in-place 503 const size_type __pos = __s - _M_data(); 504 if (__pos >= __n) 505 traits_type::copy(_M_data(), __s, __n); 506 else if (__pos) 507 traits_type::move(_M_data(), __s, __n); 508 _M_rep()->_M_length = __n; 509 _M_data()[__n] = _Rep::_S_terminal; 510 return *this; 511 } 512 } 513 514 basic_string& 515 assign(const _CharT* __s) 516 { return this->assign(__s, traits_type::length(__s)); } 517 518 basic_string& 519 assign(size_type __n, _CharT __c) 520 { return this->replace(_M_ibegin(), _M_iend(), __n, __c); } 521 522 template<class _InputIterator> 523 basic_string& 524 assign(_InputIterator __first, _InputIterator __last) 525 { return this->replace(_M_ibegin(), _M_iend(), __first, __last); } 526 527 void 528 insert(iterator __p, size_type __n, _CharT __c) 529 { this->replace(__p, __p, __n, __c); } 530 531 template<class _InputIterator> 532 void insert(iterator __p, _InputIterator __beg, _InputIterator __end) 533 { this->replace(__p, __p, __beg, __end); } 534 535 basic_string& 536 insert(size_type __pos1, const basic_string& __str) 537 { return this->insert(__pos1, __str, 0, __str.size()); } 538 539 basic_string& 540 insert(size_type __pos1, const basic_string& __str, 541 size_type __pos2, size_type __n) 542 { 543 const size_type __strsize = __str.size(); 544 if (__pos2 > __strsize) 545 __throw_out_of_range("basic_string::insert"); 546 const bool __testn = __n < __strsize - __pos2; 547 const size_type __newsize = __testn ? __n : __strsize - __pos2; 548 return this->insert(__pos1, __str._M_data() + __pos2, __newsize); 549 } 550 551 basic_string& 552 insert(size_type __pos, const _CharT* __s, size_type __n) 553 { 554 const size_type __size = this->size(); 555 if (__pos > __size) 556 __throw_out_of_range("basic_string::insert"); 557 if (__size > this->max_size() - __n) 558 __throw_length_error("basic_string::insert"); 559 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 560 || less<const _CharT*>()(_M_data() + __size, __s)) 561 return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos, 562 __s, __s + __n); 563 else 564 { 565 // Work in-place. If _M_mutate reallocates the string, __s 566 // does not point anymore to valid data, therefore we save its 567 // offset, then we restore it. 568 const size_type __off = __s - _M_data(); 569 _M_mutate(__pos, 0, __n); 570 __s = _M_data() + __off; 571 _CharT* __p = _M_data() + __pos; 572 if (__s + __n <= __p) 573 traits_type::copy(__p, __s, __n); 574 else if (__s >= __p) 575 traits_type::copy(__p, __s + __n, __n); 576 else 577 { 578 traits_type::copy(__p, __s, __p - __s); 579 traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s)); 580 } 581 return *this; 582 } 583 } 584 585 basic_string& 586 insert(size_type __pos, const _CharT* __s) 587 { return this->insert(__pos, __s, traits_type::length(__s)); } 588 589 basic_string& 590 insert(size_type __pos, size_type __n, _CharT __c) 591 { 592 this->insert(_M_check(__pos), __n, __c); 593 return *this; 594 } 595 596 iterator 597 insert(iterator __p, _CharT __c = _CharT()) 598 { 599 size_type __pos = __p - _M_ibegin(); 600 this->insert(_M_check(__pos), size_type(1), __c); 601 _M_rep()->_M_set_leaked(); 602 return this->_M_ibegin() + __pos; 603 } 604 605 basic_string& 606 erase(size_type __pos = 0, size_type __n = npos) 607 { 608 return this->replace(_M_check(__pos), _M_fold(__pos, __n), 609 _M_data(), _M_data()); 610 } 611 612 iterator 613 erase(iterator __position) 614 { 615 size_type __i = __position - _M_ibegin(); 616 this->replace(__position, __position + 1, _M_data(), _M_data()); 617 _M_rep()->_M_set_leaked(); 618 return _M_ibegin() + __i; 619 } 620 621 iterator 622 erase(iterator __first, iterator __last) 623 { 624 size_type __i = __first - _M_ibegin(); 625 this->replace(__first, __last, _M_data(), _M_data()); 626 _M_rep()->_M_set_leaked(); 627 return _M_ibegin() + __i; 628 } 629 630 basic_string& 631 replace(size_type __pos, size_type __n, const basic_string& __str) 632 { return this->replace(__pos, __n, __str._M_data(), __str.size()); } 633 634 basic_string& 635 replace(size_type __pos1, size_type __n1, const basic_string& __str, 636 size_type __pos2, size_type __n2); 637 638 basic_string& 639 replace(size_type __pos, size_type __n1, const _CharT* __s, 640 size_type __n2) 641 { 642 const size_type __size = this->size(); 643 if (__pos > __size) 644 __throw_out_of_range("basic_string::replace"); 645 const bool __testn1 = __n1 < __size - __pos; 646 const size_type __foldn1 = __testn1 ? __n1 : __size - __pos; 647 if (__size - __foldn1 > this->max_size() - __n2) 648 __throw_length_error("basic_string::replace"); 649 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 650 || less<const _CharT*>()(_M_data() + __size, __s)) 651 return _M_replace_safe(_M_ibegin() + __pos, 652 _M_ibegin() + __pos + __foldn1, __s, __s + __n2); 653 // Todo: optimized in-place replace. 654 else return 655 _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1, 656 __s, __s + __n2, 657 typename iterator_traits<const _CharT*>::iterator_category()); 658 } 659 660 basic_string& 661 replace(size_type __pos, size_type __n1, const _CharT* __s) 662 { return this->replace(__pos, __n1, __s, traits_type::length(__s)); } 663 664 basic_string& 665 replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c) 666 { return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c); } 667 668 basic_string& 669 replace(iterator __i1, iterator __i2, const basic_string& __str) 670 { return this->replace(__i1, __i2, __str._M_data(), __str.size()); } 671 672 basic_string& 673 replace(iterator __i1, iterator __i2, 674 const _CharT* __s, size_type __n) 675 { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n); } 676 677 basic_string& 678 replace(iterator __i1, iterator __i2, const _CharT* __s) 679 { return this->replace(__i1, __i2, __s, traits_type::length(__s)); } 680 681 basic_string& 682 replace(iterator __i1, iterator __i2, size_type __n, _CharT __c); 683 684 template<class _InputIterator> 685 basic_string& 686 replace(iterator __i1, iterator __i2, 687 _InputIterator __k1, _InputIterator __k2) 688 { return _M_replace(__i1, __i2, __k1, __k2, 689 typename iterator_traits<_InputIterator>::iterator_category()); } 690 691 // Specializations for the common case of pointer and iterator: 692 // useful to avoid the overhead of temporary buffering in _M_replace. 693 basic_string& 694 replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2) 695 { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, 696 __k1, __k2 - __k1); } 697 698 basic_string& 699 replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2) 700 { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, 701 __k1, __k2 - __k1); } 702 703 basic_string& 704 replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2) 705 { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, 706 __k1.base(), __k2 - __k1); 707 } 708 709 basic_string& 710 replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2) 711 { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, 712 __k1.base(), __k2 - __k1); 713 } 714 715 private: 716 template<class _InputIterator> 717 basic_string& 718 _M_replace(iterator __i1, iterator __i2, _InputIterator __k1, 719 _InputIterator __k2, input_iterator_tag); 720 721 template<class _ForwardIterator> 722 basic_string& 723 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1, 724 _ForwardIterator __k2); 725 726 // _S_construct_aux is used to implement the 21.3.1 para 15 which 727 // requires special behaviour if _InIter is an integral type 728 template<class _InIter> 729 static _CharT* 730 _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a, 731 __false_type) 732 { 733 typedef typename iterator_traits<_InIter>::iterator_category _Tag; 734 return _S_construct(__beg, __end, __a, _Tag()); 735 } 736 737 template<class _InIter> 738 static _CharT* 739 _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a, 740 __true_type) 741 { 742 return _S_construct(static_cast<size_type>(__beg), 743 static_cast<value_type>(__end), __a); 744 } 745 746 template<class _InIter> 747 static _CharT* 748 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a) 749 { 750 typedef typename _Is_integer<_InIter>::_Integral _Integral; 751 return _S_construct_aux(__beg, __end, __a, _Integral()); 752 } 753 754 // For Input Iterators, used in istreambuf_iterators, etc. 755 template<class _InIter> 756 static _CharT* 757 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 758 input_iterator_tag); 759 760 // For forward_iterators up to random_access_iterators, used for 761 // string::iterator, _CharT*, etc. 762 template<class _FwdIter> 763 static _CharT* 764 _S_construct(_FwdIter __beg, _FwdIter __end, const _Alloc& __a, 765 forward_iterator_tag); 766 767 static _CharT* 768 _S_construct(size_type __req, _CharT __c, const _Alloc& __a); 769 770 public: 771 772 size_type 773 copy(_CharT* __s, size_type __n, size_type __pos = 0) const; 774 775 void 776 swap(basic_string<_CharT, _Traits, _Alloc>& __s); 777 778 // String operations: 779 const _CharT* 780 c_str() const 781 { 782 // MT: This assumes concurrent writes are OK. 783 size_type __n = this->size(); 784 traits_type::assign(_M_data()[__n], _Rep::_S_terminal); 785 return _M_data(); 786 } 787 788 const _CharT* 789 data() const { return _M_data(); } 790 791 allocator_type 792 get_allocator() const { return _M_dataplus; } 793 794 size_type 795 find(const _CharT* __s, size_type __pos, size_type __n) const; 796 797 size_type 798 find(const basic_string& __str, size_type __pos = 0) const 799 { return this->find(__str.data(), __pos, __str.size()); } 800 801 size_type 802 find(const _CharT* __s, size_type __pos = 0) const 803 { return this->find(__s, __pos, traits_type::length(__s)); } 804 805 size_type 806 find(_CharT __c, size_type __pos = 0) const; 807 808 size_type 809 rfind(const basic_string& __str, size_type __pos = npos) const 810 { return this->rfind(__str.data(), __pos, __str.size()); } 811 812 size_type 813 rfind(const _CharT* __s, size_type __pos, size_type __n) const; 814 815 size_type 816 rfind(const _CharT* __s, size_type __pos = npos) const 817 { return this->rfind(__s, __pos, traits_type::length(__s)); } 818 819 size_type 820 rfind(_CharT __c, size_type __pos = npos) const; 821 822 size_type 823 find_first_of(const basic_string& __str, size_type __pos = 0) const 824 { return this->find_first_of(__str.data(), __pos, __str.size()); } 825 826 size_type 827 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const; 828 829 size_type 830 find_first_of(const _CharT* __s, size_type __pos = 0) const 831 { return this->find_first_of(__s, __pos, traits_type::length(__s)); } 832 833 size_type 834 find_first_of(_CharT __c, size_type __pos = 0) const 835 { return this->find(__c, __pos); } 836 837 size_type 838 find_last_of(const basic_string& __str, size_type __pos = npos) const 839 { return this->find_last_of(__str.data(), __pos, __str.size()); } 840 841 size_type 842 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const; 843 844 size_type 845 find_last_of(const _CharT* __s, size_type __pos = npos) const 846 { return this->find_last_of(__s, __pos, traits_type::length(__s)); } 847 848 size_type 849 find_last_of(_CharT __c, size_type __pos = npos) const 850 { return this->rfind(__c, __pos); } 851 852 size_type 853 find_first_not_of(const basic_string& __str, size_type __pos = 0) const 854 { return this->find_first_not_of(__str.data(), __pos, __str.size()); } 855 856 size_type 857 find_first_not_of(const _CharT* __s, size_type __pos, 858 size_type __n) const; 859 860 size_type 861 find_first_not_of(const _CharT* __s, size_type __pos = 0) const 862 { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); } 863 864 size_type 865 find_first_not_of(_CharT __c, size_type __pos = 0) const; 866 867 size_type 868 find_last_not_of(const basic_string& __str, size_type __pos = npos) const 869 { return this->find_last_not_of(__str.data(), __pos, __str.size()); } 870 871 size_type 872 find_last_not_of(const _CharT* __s, size_type __pos, 873 size_type __n) const; 874 size_type 875 find_last_not_of(const _CharT* __s, size_type __pos = npos) const 876 { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); } 877 878 size_type 879 find_last_not_of(_CharT __c, size_type __pos = npos) const; 880 881 basic_string 882 substr(size_type __pos = 0, size_type __n = npos) const 883 { 884 if (__pos > this->size()) 885 __throw_out_of_range("basic_string::substr"); 886 return basic_string(*this, __pos, __n); 887 } 888 889 int 890 compare(const basic_string& __str) const 891 { 892 size_type __size = this->size(); 893 size_type __osize = __str.size(); 894 size_type __len = min(__size, __osize); 895 896 int __r = traits_type::compare(_M_data(), __str.data(), __len); 897 if (!__r) 898 __r = __size - __osize; 899 return __r; 900 } 901 902 int 903 compare(size_type __pos, size_type __n, const basic_string& __str) const; 904 905 int 906 compare(size_type __pos1, size_type __n1, const basic_string& __str, 907 size_type __pos2, size_type __n2) const; 908 909 int 910 compare(const _CharT* __s) const; 911 912 // _GLIBCPP_RESOLVE_LIB_DEFECTS 913 // 5. String::compare specification questionable 914 int 915 compare(size_type __pos, size_type __n1, const _CharT* __s) const; 916 917 int 918 compare(size_type __pos, size_type __n1, const _CharT* __s, 919 size_type __n2) const; 920 }; 921 922 923 template<typename _CharT, typename _Traits, typename _Alloc> 924 inline basic_string<_CharT, _Traits, _Alloc>:: 925 basic_string() 926 : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { } 927 928 // operator+ 929 template<typename _CharT, typename _Traits, typename _Alloc> 930 basic_string<_CharT, _Traits, _Alloc> 931 operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 932 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 933 { 934 basic_string<_CharT, _Traits, _Alloc> __str(__lhs); 935 __str.append(__rhs); 936 return __str; 937 } 938 939 template<typename _CharT, typename _Traits, typename _Alloc> 940 basic_string<_CharT,_Traits,_Alloc> 941 operator+(const _CharT* __lhs, 942 const basic_string<_CharT,_Traits,_Alloc>& __rhs); 943 944 template<typename _CharT, typename _Traits, typename _Alloc> 945 basic_string<_CharT,_Traits,_Alloc> 946 operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs); 947 948 template<typename _CharT, typename _Traits, typename _Alloc> 949 inline basic_string<_CharT, _Traits, _Alloc> 950 operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 951 const _CharT* __rhs) 952 { 953 basic_string<_CharT, _Traits, _Alloc> __str(__lhs); 954 __str.append(__rhs); 955 return __str; 956 } 957 958 template<typename _CharT, typename _Traits, typename _Alloc> 959 inline basic_string<_CharT, _Traits, _Alloc> 960 operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs) 961 { 962 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 963 typedef typename __string_type::size_type __size_type; 964 __string_type __str(__lhs); 965 __str.append(__size_type(1), __rhs); 966 return __str; 967 } 968 969 // operator == 970 template<typename _CharT, typename _Traits, typename _Alloc> 971 inline bool 972 operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 973 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 974 { return __lhs.compare(__rhs) == 0; } 975 976 template<typename _CharT, typename _Traits, typename _Alloc> 977 inline bool 978 operator==(const _CharT* __lhs, 979 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 980 { return __rhs.compare(__lhs) == 0; } 981 982 template<typename _CharT, typename _Traits, typename _Alloc> 983 inline bool 984 operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 985 const _CharT* __rhs) 986 { return __lhs.compare(__rhs) == 0; } 987 988 // operator != 989 template<typename _CharT, typename _Traits, typename _Alloc> 990 inline bool 991 operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 992 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 993 { return __rhs.compare(__lhs) != 0; } 994 995 template<typename _CharT, typename _Traits, typename _Alloc> 996 inline bool 997 operator!=(const _CharT* __lhs, 998 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 999 { return __rhs.compare(__lhs) != 0; } 1000 1001 template<typename _CharT, typename _Traits, typename _Alloc> 1002 inline bool 1003 operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1004 const _CharT* __rhs) 1005 { return __lhs.compare(__rhs) != 0; } 1006 1007 // operator < 1008 template<typename _CharT, typename _Traits, typename _Alloc> 1009 inline bool 1010 operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1011 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1012 { return __lhs.compare(__rhs) < 0; } 1013 1014 template<typename _CharT, typename _Traits, typename _Alloc> 1015 inline bool 1016 operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1017 const _CharT* __rhs) 1018 { return __lhs.compare(__rhs) < 0; } 1019 1020 template<typename _CharT, typename _Traits, typename _Alloc> 1021 inline bool 1022 operator<(const _CharT* __lhs, 1023 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1024 { return __rhs.compare(__lhs) > 0; } 1025 1026 // operator > 1027 template<typename _CharT, typename _Traits, typename _Alloc> 1028 inline bool 1029 operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1030 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1031 { return __lhs.compare(__rhs) > 0; } 1032 1033 template<typename _CharT, typename _Traits, typename _Alloc> 1034 inline bool 1035 operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1036 const _CharT* __rhs) 1037 { return __lhs.compare(__rhs) > 0; } 1038 1039 template<typename _CharT, typename _Traits, typename _Alloc> 1040 inline bool 1041 operator>(const _CharT* __lhs, 1042 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1043 { return __rhs.compare(__lhs) < 0; } 1044 1045 // operator <= 1046 template<typename _CharT, typename _Traits, typename _Alloc> 1047 inline bool 1048 operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1049 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1050 { return __lhs.compare(__rhs) <= 0; } 1051 1052 template<typename _CharT, typename _Traits, typename _Alloc> 1053 inline bool 1054 operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1055 const _CharT* __rhs) 1056 { return __lhs.compare(__rhs) <= 0; } 1057 1058 template<typename _CharT, typename _Traits, typename _Alloc> 1059 inline bool 1060 operator<=(const _CharT* __lhs, 1061 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1062 { return __rhs.compare(__lhs) >= 0; } 1063 1064 // operator >= 1065 template<typename _CharT, typename _Traits, typename _Alloc> 1066 inline bool 1067 operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1068 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1069 { return __lhs.compare(__rhs) >= 0; } 1070 1071 template<typename _CharT, typename _Traits, typename _Alloc> 1072 inline bool 1073 operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs, 1074 const _CharT* __rhs) 1075 { return __lhs.compare(__rhs) >= 0; } 1076 1077 template<typename _CharT, typename _Traits, typename _Alloc> 1078 inline bool 1079 operator>=(const _CharT* __lhs, 1080 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1081 { return __rhs.compare(__lhs) <= 0; } 1082 1083 1084 template<typename _CharT, typename _Traits, typename _Alloc> 1085 inline void 1086 swap(basic_string<_CharT, _Traits, _Alloc>& __lhs, 1087 basic_string<_CharT, _Traits, _Alloc>& __rhs) 1088 { __lhs.swap(__rhs); } 1089 1090 template<typename _CharT, typename _Traits, typename _Alloc> 1091 basic_istream<_CharT, _Traits>& 1092 operator>>(basic_istream<_CharT, _Traits>& __is, 1093 basic_string<_CharT, _Traits, _Alloc>& __str); 1094 1095 template<typename _CharT, typename _Traits, typename _Alloc> 1096 basic_ostream<_CharT, _Traits>& 1097 operator<<(basic_ostream<_CharT, _Traits>& __os, 1098 const basic_string<_CharT, _Traits, _Alloc>& __str); 1099 1100 template<typename _CharT, typename _Traits, typename _Alloc> 1101 basic_istream<_CharT,_Traits>& 1102 getline(basic_istream<_CharT, _Traits>& __is, 1103 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim); 1104 1105 template<typename _CharT, typename _Traits, typename _Alloc> 1106 inline basic_istream<_CharT,_Traits>& 1107 getline(basic_istream<_CharT, _Traits>& __is, 1108 basic_string<_CharT, _Traits, _Alloc>& __str); 1109 } // namespace std 1110 1111 #endif /* _CPP_BITS_STRING_H */ 1112