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