1 // Components for manipulating sequences of characters -*- C++ -*- 2 3 // Copyright (C) 1997-2021 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/basic_string.tcc 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{string} 28 */ 29 30 // 31 // ISO C++ 14882: 21 Strings library 32 // 33 34 // Written by Jason Merrill based upon the specification by Takanori Adachi 35 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 36 // Non-reference-counted implementation written by Paolo Carlini and 37 // updated by Jonathan Wakely for ISO-14882-2011. 38 39 #ifndef _BASIC_STRING_TCC 40 #define _BASIC_STRING_TCC 1 41 42 #pragma GCC system_header 43 44 #include <bits/cxxabi_forced.h> 45 46 namespace std _GLIBCXX_VISIBILITY(default) 47 { 48 _GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 #if _GLIBCXX_USE_CXX11_ABI 51 52 template<typename _CharT, typename _Traits, typename _Alloc> 53 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 54 basic_string<_CharT, _Traits, _Alloc>::npos; 55 56 template<typename _CharT, typename _Traits, typename _Alloc> 57 void 58 basic_string<_CharT, _Traits, _Alloc>:: swap(basic_string & __s)59 swap(basic_string& __s) _GLIBCXX_NOEXCEPT 60 { 61 if (this == &__s) 62 return; 63 64 _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator()); 65 66 if (_M_is_local()) 67 if (__s._M_is_local()) 68 { 69 if (length() && __s.length()) 70 { 71 _CharT __tmp_data[_S_local_capacity + 1]; 72 traits_type::copy(__tmp_data, __s._M_local_buf, 73 _S_local_capacity + 1); 74 traits_type::copy(__s._M_local_buf, _M_local_buf, 75 _S_local_capacity + 1); 76 traits_type::copy(_M_local_buf, __tmp_data, 77 _S_local_capacity + 1); 78 } 79 else if (__s.length()) 80 { 81 traits_type::copy(_M_local_buf, __s._M_local_buf, 82 _S_local_capacity + 1); 83 _M_length(__s.length()); 84 __s._M_set_length(0); 85 return; 86 } 87 else if (length()) 88 { 89 traits_type::copy(__s._M_local_buf, _M_local_buf, 90 _S_local_capacity + 1); 91 __s._M_length(length()); 92 _M_set_length(0); 93 return; 94 } 95 } 96 else 97 { 98 const size_type __tmp_capacity = __s._M_allocated_capacity; 99 traits_type::copy(__s._M_local_buf, _M_local_buf, 100 _S_local_capacity + 1); 101 _M_data(__s._M_data()); 102 __s._M_data(__s._M_local_buf); 103 _M_capacity(__tmp_capacity); 104 } 105 else 106 { 107 const size_type __tmp_capacity = _M_allocated_capacity; 108 if (__s._M_is_local()) 109 { 110 traits_type::copy(_M_local_buf, __s._M_local_buf, 111 _S_local_capacity + 1); 112 __s._M_data(_M_data()); 113 _M_data(_M_local_buf); 114 } 115 else 116 { 117 pointer __tmp_ptr = _M_data(); 118 _M_data(__s._M_data()); 119 __s._M_data(__tmp_ptr); 120 _M_capacity(__s._M_allocated_capacity); 121 } 122 __s._M_capacity(__tmp_capacity); 123 } 124 125 const size_type __tmp_length = length(); 126 _M_length(__s.length()); 127 __s._M_length(__tmp_length); 128 } 129 130 template<typename _CharT, typename _Traits, typename _Alloc> 131 typename basic_string<_CharT, _Traits, _Alloc>::pointer 132 basic_string<_CharT, _Traits, _Alloc>:: _M_create(size_type & __capacity,size_type __old_capacity)133 _M_create(size_type& __capacity, size_type __old_capacity) 134 { 135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 136 // 83. String::npos vs. string::max_size() 137 if (__capacity > max_size()) 138 std::__throw_length_error(__N("basic_string::_M_create")); 139 140 // The below implements an exponential growth policy, necessary to 141 // meet amortized linear time requirements of the library: see 142 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 143 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 144 { 145 __capacity = 2 * __old_capacity; 146 // Never allocate a string bigger than max_size. 147 if (__capacity > max_size()) 148 __capacity = max_size(); 149 } 150 151 // NB: Need an array of char_type[__capacity], plus a terminating 152 // null char_type() element. 153 return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1); 154 } 155 156 // NB: This is the special case for Input Iterators, used in 157 // istreambuf_iterators, etc. 158 // Input Iterators have a cost structure very different from 159 // pointers, calling for a different coding style. 160 template<typename _CharT, typename _Traits, typename _Alloc> 161 template<typename _InIterator> 162 void 163 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(_InIterator __beg,_InIterator __end,std::input_iterator_tag)164 _M_construct(_InIterator __beg, _InIterator __end, 165 std::input_iterator_tag) 166 { 167 size_type __len = 0; 168 size_type __capacity = size_type(_S_local_capacity); 169 170 while (__beg != __end && __len < __capacity) 171 { 172 _M_data()[__len++] = *__beg; 173 ++__beg; 174 } 175 176 __try 177 { 178 while (__beg != __end) 179 { 180 if (__len == __capacity) 181 { 182 // Allocate more space. 183 __capacity = __len + 1; 184 pointer __another = _M_create(__capacity, __len); 185 this->_S_copy(__another, _M_data(), __len); 186 _M_dispose(); 187 _M_data(__another); 188 _M_capacity(__capacity); 189 } 190 _M_data()[__len++] = *__beg; 191 ++__beg; 192 } 193 } 194 __catch(...) 195 { 196 _M_dispose(); 197 __throw_exception_again; 198 } 199 200 _M_set_length(__len); 201 } 202 203 template<typename _CharT, typename _Traits, typename _Alloc> 204 template<typename _InIterator> 205 void 206 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(_InIterator __beg,_InIterator __end,std::forward_iterator_tag)207 _M_construct(_InIterator __beg, _InIterator __end, 208 std::forward_iterator_tag) 209 { 210 // NB: Not required, but considered best practice. 211 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 212 std::__throw_logic_error(__N("basic_string::" 213 "_M_construct null not valid")); 214 215 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 216 217 if (__dnew > size_type(_S_local_capacity)) 218 { 219 _M_data(_M_create(__dnew, size_type(0))); 220 _M_capacity(__dnew); 221 } 222 223 // Check for out_of_range and length_error exceptions. 224 __try 225 { this->_S_copy_chars(_M_data(), __beg, __end); } 226 __catch(...) 227 { 228 _M_dispose(); 229 __throw_exception_again; 230 } 231 232 _M_set_length(__dnew); 233 } 234 235 template<typename _CharT, typename _Traits, typename _Alloc> 236 void 237 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(size_type __n,_CharT __c)238 _M_construct(size_type __n, _CharT __c) 239 { 240 if (__n > size_type(_S_local_capacity)) 241 { 242 _M_data(_M_create(__n, size_type(0))); 243 _M_capacity(__n); 244 } 245 246 if (__n) 247 this->_S_assign(_M_data(), __n, __c); 248 249 _M_set_length(__n); 250 } 251 252 template<typename _CharT, typename _Traits, typename _Alloc> 253 void 254 basic_string<_CharT, _Traits, _Alloc>:: _M_assign(const basic_string & __str)255 _M_assign(const basic_string& __str) 256 { 257 if (this != &__str) 258 { 259 const size_type __rsize = __str.length(); 260 const size_type __capacity = capacity(); 261 262 if (__rsize > __capacity) 263 { 264 size_type __new_capacity = __rsize; 265 pointer __tmp = _M_create(__new_capacity, __capacity); 266 _M_dispose(); 267 _M_data(__tmp); 268 _M_capacity(__new_capacity); 269 } 270 271 if (__rsize) 272 this->_S_copy(_M_data(), __str._M_data(), __rsize); 273 274 _M_set_length(__rsize); 275 } 276 } 277 278 template<typename _CharT, typename _Traits, typename _Alloc> 279 void 280 basic_string<_CharT, _Traits, _Alloc>:: reserve(size_type __res)281 reserve(size_type __res) 282 { 283 const size_type __capacity = capacity(); 284 // _GLIBCXX_RESOLVE_LIB_DEFECTS 285 // 2968. Inconsistencies between basic_string reserve and 286 // vector/unordered_map/unordered_set reserve functions 287 // P0966 reserve should not shrink 288 if (__res <= __capacity) 289 return; 290 291 pointer __tmp = _M_create(__res, __capacity); 292 this->_S_copy(__tmp, _M_data(), length() + 1); 293 _M_dispose(); 294 _M_data(__tmp); 295 _M_capacity(__res); 296 } 297 298 template<typename _CharT, typename _Traits, typename _Alloc> 299 void 300 basic_string<_CharT, _Traits, _Alloc>:: _M_mutate(size_type __pos,size_type __len1,const _CharT * __s,size_type __len2)301 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 302 size_type __len2) 303 { 304 const size_type __how_much = length() - __pos - __len1; 305 306 size_type __new_capacity = length() + __len2 - __len1; 307 pointer __r = _M_create(__new_capacity, capacity()); 308 309 if (__pos) 310 this->_S_copy(__r, _M_data(), __pos); 311 if (__s && __len2) 312 this->_S_copy(__r + __pos, __s, __len2); 313 if (__how_much) 314 this->_S_copy(__r + __pos + __len2, 315 _M_data() + __pos + __len1, __how_much); 316 317 _M_dispose(); 318 _M_data(__r); 319 _M_capacity(__new_capacity); 320 } 321 322 template<typename _CharT, typename _Traits, typename _Alloc> 323 void 324 basic_string<_CharT, _Traits, _Alloc>:: _M_erase(size_type __pos,size_type __n)325 _M_erase(size_type __pos, size_type __n) 326 { 327 const size_type __how_much = length() - __pos - __n; 328 329 if (__how_much && __n) 330 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 331 332 _M_set_length(length() - __n); 333 } 334 335 template<typename _CharT, typename _Traits, typename _Alloc> 336 void 337 basic_string<_CharT, _Traits, _Alloc>:: reserve()338 reserve() 339 { 340 if (_M_is_local()) 341 return; 342 343 const size_type __length = length(); 344 const size_type __capacity = _M_allocated_capacity; 345 346 if (__length <= size_type(_S_local_capacity)) 347 { 348 this->_S_copy(_M_local_data(), _M_data(), __length + 1); 349 _M_destroy(__capacity); 350 _M_data(_M_local_data()); 351 } 352 #if __cpp_exceptions 353 else if (__length < __capacity) 354 try 355 { 356 pointer __tmp 357 = _Alloc_traits::allocate(_M_get_allocator(), __length + 1); 358 this->_S_copy(__tmp, _M_data(), __length + 1); 359 _M_dispose(); 360 _M_data(__tmp); 361 _M_capacity(__length); 362 } 363 catch (const __cxxabiv1::__forced_unwind&) 364 { throw; } 365 catch (...) 366 { /* swallow the exception */ } 367 #endif 368 } 369 370 template<typename _CharT, typename _Traits, typename _Alloc> 371 void 372 basic_string<_CharT, _Traits, _Alloc>:: resize(size_type __n,_CharT __c)373 resize(size_type __n, _CharT __c) 374 { 375 const size_type __size = this->size(); 376 if (__size < __n) 377 this->append(__n - __size, __c); 378 else if (__n < __size) 379 this->_M_set_length(__n); 380 } 381 382 template<typename _CharT, typename _Traits, typename _Alloc> 383 basic_string<_CharT, _Traits, _Alloc>& 384 basic_string<_CharT, _Traits, _Alloc>:: _M_append(const _CharT * __s,size_type __n)385 _M_append(const _CharT* __s, size_type __n) 386 { 387 const size_type __len = __n + this->size(); 388 389 if (__len <= this->capacity()) 390 { 391 if (__n) 392 this->_S_copy(this->_M_data() + this->size(), __s, __n); 393 } 394 else 395 this->_M_mutate(this->size(), size_type(0), __s, __n); 396 397 this->_M_set_length(__len); 398 return *this; 399 } 400 401 template<typename _CharT, typename _Traits, typename _Alloc> 402 template<typename _InputIterator> 403 basic_string<_CharT, _Traits, _Alloc>& 404 basic_string<_CharT, _Traits, _Alloc>:: _M_replace_dispatch(const_iterator __i1,const_iterator __i2,_InputIterator __k1,_InputIterator __k2,std::__false_type)405 _M_replace_dispatch(const_iterator __i1, const_iterator __i2, 406 _InputIterator __k1, _InputIterator __k2, 407 std::__false_type) 408 { 409 // _GLIBCXX_RESOLVE_LIB_DEFECTS 410 // 2788. unintentionally require a default constructible allocator 411 const basic_string __s(__k1, __k2, this->get_allocator()); 412 const size_type __n1 = __i2 - __i1; 413 return _M_replace(__i1 - begin(), __n1, __s._M_data(), 414 __s.size()); 415 } 416 417 template<typename _CharT, typename _Traits, typename _Alloc> 418 basic_string<_CharT, _Traits, _Alloc>& 419 basic_string<_CharT, _Traits, _Alloc>:: _M_replace_aux(size_type __pos1,size_type __n1,size_type __n2,_CharT __c)420 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 421 _CharT __c) 422 { 423 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 424 425 const size_type __old_size = this->size(); 426 const size_type __new_size = __old_size + __n2 - __n1; 427 428 if (__new_size <= this->capacity()) 429 { 430 pointer __p = this->_M_data() + __pos1; 431 432 const size_type __how_much = __old_size - __pos1 - __n1; 433 if (__how_much && __n1 != __n2) 434 this->_S_move(__p + __n2, __p + __n1, __how_much); 435 } 436 else 437 this->_M_mutate(__pos1, __n1, 0, __n2); 438 439 if (__n2) 440 this->_S_assign(this->_M_data() + __pos1, __n2, __c); 441 442 this->_M_set_length(__new_size); 443 return *this; 444 } 445 446 template<typename _CharT, typename _Traits, typename _Alloc> 447 basic_string<_CharT, _Traits, _Alloc>& 448 basic_string<_CharT, _Traits, _Alloc>:: _M_replace(size_type __pos,size_type __len1,const _CharT * __s,const size_type __len2)449 _M_replace(size_type __pos, size_type __len1, const _CharT* __s, 450 const size_type __len2) 451 { 452 _M_check_length(__len1, __len2, "basic_string::_M_replace"); 453 454 const size_type __old_size = this->size(); 455 const size_type __new_size = __old_size + __len2 - __len1; 456 457 if (__new_size <= this->capacity()) 458 { 459 pointer __p = this->_M_data() + __pos; 460 461 const size_type __how_much = __old_size - __pos - __len1; 462 if (_M_disjunct(__s)) 463 { 464 if (__how_much && __len1 != __len2) 465 this->_S_move(__p + __len2, __p + __len1, __how_much); 466 if (__len2) 467 this->_S_copy(__p, __s, __len2); 468 } 469 else 470 { 471 // Work in-place. 472 if (__len2 && __len2 <= __len1) 473 this->_S_move(__p, __s, __len2); 474 if (__how_much && __len1 != __len2) 475 this->_S_move(__p + __len2, __p + __len1, __how_much); 476 if (__len2 > __len1) 477 { 478 if (__s + __len2 <= __p + __len1) 479 this->_S_move(__p, __s, __len2); 480 else if (__s >= __p + __len1) 481 { 482 // Hint to middle end that __p and __s overlap 483 // (PR 98465). 484 const size_type __poff = (__s - __p) + (__len2 - __len1); 485 this->_S_copy(__p, __p + __poff, __len2); 486 } 487 else 488 { 489 const size_type __nleft = (__p + __len1) - __s; 490 this->_S_move(__p, __s, __nleft); 491 this->_S_copy(__p + __nleft, __p + __len2, 492 __len2 - __nleft); 493 } 494 } 495 } 496 } 497 else 498 this->_M_mutate(__pos, __len1, __s, __len2); 499 500 this->_M_set_length(__new_size); 501 return *this; 502 } 503 504 template<typename _CharT, typename _Traits, typename _Alloc> 505 typename basic_string<_CharT, _Traits, _Alloc>::size_type 506 basic_string<_CharT, _Traits, _Alloc>:: copy(_CharT * __s,size_type __n,size_type __pos) const507 copy(_CharT* __s, size_type __n, size_type __pos) const 508 { 509 _M_check(__pos, "basic_string::copy"); 510 __n = _M_limit(__pos, __n); 511 __glibcxx_requires_string_len(__s, __n); 512 if (__n) 513 _S_copy(__s, _M_data() + __pos, __n); 514 // 21.3.5.7 par 3: do not append null. (good.) 515 return __n; 516 } 517 518 #else // !_GLIBCXX_USE_CXX11_ABI 519 520 template<typename _CharT, typename _Traits, typename _Alloc> 521 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 522 basic_string<_CharT, _Traits, _Alloc>:: 523 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 524 525 template<typename _CharT, typename _Traits, typename _Alloc> 526 const _CharT 527 basic_string<_CharT, _Traits, _Alloc>:: 528 _Rep::_S_terminal = _CharT(); 529 530 template<typename _CharT, typename _Traits, typename _Alloc> 531 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 532 basic_string<_CharT, _Traits, _Alloc>::npos; 533 534 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 535 // at static init time (before static ctors are run). 536 template<typename _CharT, typename _Traits, typename _Alloc> 537 typename basic_string<_CharT, _Traits, _Alloc>::size_type 538 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 539 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 540 sizeof(size_type)]; 541 542 // NB: This is the special case for Input Iterators, used in 543 // istreambuf_iterators, etc. 544 // Input Iterators have a cost structure very different from 545 // pointers, calling for a different coding style. 546 template<typename _CharT, typename _Traits, typename _Alloc> 547 template<typename _InIterator> 548 _CharT* 549 basic_string<_CharT, _Traits, _Alloc>:: 550 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 551 input_iterator_tag) 552 { 553 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 554 if (__beg == __end && __a == _Alloc()) 555 return _S_empty_rep()._M_refdata(); 556 #endif 557 // Avoid reallocation for common case. 558 _CharT __buf[128]; 559 size_type __len = 0; 560 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 561 { 562 __buf[__len++] = *__beg; 563 ++__beg; 564 } 565 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 566 _M_copy(__r->_M_refdata(), __buf, __len); 567 __try 568 { 569 while (__beg != __end) 570 { 571 if (__len == __r->_M_capacity) 572 { 573 // Allocate more space. 574 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 575 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 576 __r->_M_destroy(__a); 577 __r = __another; 578 } 579 __r->_M_refdata()[__len++] = *__beg; 580 ++__beg; 581 } 582 } 583 __catch(...) 584 { 585 __r->_M_destroy(__a); 586 __throw_exception_again; 587 } 588 __r->_M_set_length_and_sharable(__len); 589 return __r->_M_refdata(); 590 } 591 592 template<typename _CharT, typename _Traits, typename _Alloc> 593 template <typename _InIterator> 594 _CharT* 595 basic_string<_CharT, _Traits, _Alloc>:: 596 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 597 forward_iterator_tag) 598 { 599 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 600 if (__beg == __end && __a == _Alloc()) 601 return _S_empty_rep()._M_refdata(); 602 #endif 603 // NB: Not required, but considered best practice. 604 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 605 __throw_logic_error(__N("basic_string::_S_construct null not valid")); 606 607 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 608 __end)); 609 // Check for out_of_range and length_error exceptions. 610 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 611 __try 612 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 613 __catch(...) 614 { 615 __r->_M_destroy(__a); 616 __throw_exception_again; 617 } 618 __r->_M_set_length_and_sharable(__dnew); 619 return __r->_M_refdata(); 620 } 621 622 template<typename _CharT, typename _Traits, typename _Alloc> 623 _CharT* 624 basic_string<_CharT, _Traits, _Alloc>:: 625 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 626 { 627 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 628 if (__n == 0 && __a == _Alloc()) 629 return _S_empty_rep()._M_refdata(); 630 #endif 631 // Check for out_of_range and length_error exceptions. 632 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 633 if (__n) 634 _M_assign(__r->_M_refdata(), __n, __c); 635 636 __r->_M_set_length_and_sharable(__n); 637 return __r->_M_refdata(); 638 } 639 640 template<typename _CharT, typename _Traits, typename _Alloc> 641 basic_string<_CharT, _Traits, _Alloc>:: 642 basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a) 643 : _M_dataplus(_S_construct(__str._M_data() 644 + __str._M_check(__pos, 645 "basic_string::basic_string"), 646 __str._M_data() + __str._M_limit(__pos, npos) 647 + __pos, __a), __a) 648 { } 649 650 template<typename _CharT, typename _Traits, typename _Alloc> 651 basic_string<_CharT, _Traits, _Alloc>:: 652 basic_string(const basic_string& __str, size_type __pos, size_type __n) 653 : _M_dataplus(_S_construct(__str._M_data() 654 + __str._M_check(__pos, 655 "basic_string::basic_string"), 656 __str._M_data() + __str._M_limit(__pos, __n) 657 + __pos, _Alloc()), _Alloc()) 658 { } 659 660 template<typename _CharT, typename _Traits, typename _Alloc> 661 basic_string<_CharT, _Traits, _Alloc>:: 662 basic_string(const basic_string& __str, size_type __pos, 663 size_type __n, const _Alloc& __a) 664 : _M_dataplus(_S_construct(__str._M_data() 665 + __str._M_check(__pos, 666 "basic_string::basic_string"), 667 __str._M_data() + __str._M_limit(__pos, __n) 668 + __pos, __a), __a) 669 { } 670 671 template<typename _CharT, typename _Traits, typename _Alloc> 672 basic_string<_CharT, _Traits, _Alloc>& 673 basic_string<_CharT, _Traits, _Alloc>:: 674 assign(const basic_string& __str) 675 { 676 if (_M_rep() != __str._M_rep()) 677 { 678 // XXX MT 679 const allocator_type __a = this->get_allocator(); 680 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 681 _M_rep()->_M_dispose(__a); 682 _M_data(__tmp); 683 } 684 return *this; 685 } 686 687 template<typename _CharT, typename _Traits, typename _Alloc> 688 basic_string<_CharT, _Traits, _Alloc>& 689 basic_string<_CharT, _Traits, _Alloc>:: 690 assign(const _CharT* __s, size_type __n) 691 { 692 __glibcxx_requires_string_len(__s, __n); 693 _M_check_length(this->size(), __n, "basic_string::assign"); 694 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 695 return _M_replace_safe(size_type(0), this->size(), __s, __n); 696 else 697 { 698 // Work in-place. 699 const size_type __pos = __s - _M_data(); 700 if (__pos >= __n) 701 _M_copy(_M_data(), __s, __n); 702 else if (__pos) 703 _M_move(_M_data(), __s, __n); 704 _M_rep()->_M_set_length_and_sharable(__n); 705 return *this; 706 } 707 } 708 709 template<typename _CharT, typename _Traits, typename _Alloc> 710 basic_string<_CharT, _Traits, _Alloc>& 711 basic_string<_CharT, _Traits, _Alloc>:: 712 append(size_type __n, _CharT __c) 713 { 714 if (__n) 715 { 716 _M_check_length(size_type(0), __n, "basic_string::append"); 717 const size_type __len = __n + this->size(); 718 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 719 this->reserve(__len); 720 _M_assign(_M_data() + this->size(), __n, __c); 721 _M_rep()->_M_set_length_and_sharable(__len); 722 } 723 return *this; 724 } 725 726 template<typename _CharT, typename _Traits, typename _Alloc> 727 basic_string<_CharT, _Traits, _Alloc>& 728 basic_string<_CharT, _Traits, _Alloc>:: 729 append(const _CharT* __s, size_type __n) 730 { 731 __glibcxx_requires_string_len(__s, __n); 732 if (__n) 733 { 734 _M_check_length(size_type(0), __n, "basic_string::append"); 735 const size_type __len = __n + this->size(); 736 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 737 { 738 if (_M_disjunct(__s)) 739 this->reserve(__len); 740 else 741 { 742 const size_type __off = __s - _M_data(); 743 this->reserve(__len); 744 __s = _M_data() + __off; 745 } 746 } 747 _M_copy(_M_data() + this->size(), __s, __n); 748 _M_rep()->_M_set_length_and_sharable(__len); 749 } 750 return *this; 751 } 752 753 template<typename _CharT, typename _Traits, typename _Alloc> 754 basic_string<_CharT, _Traits, _Alloc>& 755 basic_string<_CharT, _Traits, _Alloc>:: 756 append(const basic_string& __str) 757 { 758 const size_type __size = __str.size(); 759 if (__size) 760 { 761 const size_type __len = __size + this->size(); 762 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 763 this->reserve(__len); 764 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 765 _M_rep()->_M_set_length_and_sharable(__len); 766 } 767 return *this; 768 } 769 770 template<typename _CharT, typename _Traits, typename _Alloc> 771 basic_string<_CharT, _Traits, _Alloc>& 772 basic_string<_CharT, _Traits, _Alloc>:: 773 append(const basic_string& __str, size_type __pos, size_type __n) 774 { 775 __str._M_check(__pos, "basic_string::append"); 776 __n = __str._M_limit(__pos, __n); 777 if (__n) 778 { 779 const size_type __len = __n + this->size(); 780 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 781 this->reserve(__len); 782 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 783 _M_rep()->_M_set_length_and_sharable(__len); 784 } 785 return *this; 786 } 787 788 template<typename _CharT, typename _Traits, typename _Alloc> 789 basic_string<_CharT, _Traits, _Alloc>& 790 basic_string<_CharT, _Traits, _Alloc>:: 791 insert(size_type __pos, const _CharT* __s, size_type __n) 792 { 793 __glibcxx_requires_string_len(__s, __n); 794 _M_check(__pos, "basic_string::insert"); 795 _M_check_length(size_type(0), __n, "basic_string::insert"); 796 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 797 return _M_replace_safe(__pos, size_type(0), __s, __n); 798 else 799 { 800 // Work in-place. 801 const size_type __off = __s - _M_data(); 802 _M_mutate(__pos, 0, __n); 803 __s = _M_data() + __off; 804 _CharT* __p = _M_data() + __pos; 805 if (__s + __n <= __p) 806 _M_copy(__p, __s, __n); 807 else if (__s >= __p) 808 _M_copy(__p, __s + __n, __n); 809 else 810 { 811 const size_type __nleft = __p - __s; 812 _M_copy(__p, __s, __nleft); 813 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 814 } 815 return *this; 816 } 817 } 818 819 template<typename _CharT, typename _Traits, typename _Alloc> 820 typename basic_string<_CharT, _Traits, _Alloc>::iterator 821 basic_string<_CharT, _Traits, _Alloc>:: 822 erase(iterator __first, iterator __last) 823 { 824 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 825 && __last <= _M_iend()); 826 827 // NB: This isn't just an optimization (bail out early when 828 // there is nothing to do, really), it's also a correctness 829 // issue vs MT, see libstdc++/40518. 830 const size_type __size = __last - __first; 831 if (__size) 832 { 833 const size_type __pos = __first - _M_ibegin(); 834 _M_mutate(__pos, __size, size_type(0)); 835 _M_rep()->_M_set_leaked(); 836 return iterator(_M_data() + __pos); 837 } 838 else 839 return __first; 840 } 841 842 template<typename _CharT, typename _Traits, typename _Alloc> 843 basic_string<_CharT, _Traits, _Alloc>& 844 basic_string<_CharT, _Traits, _Alloc>:: 845 replace(size_type __pos, size_type __n1, const _CharT* __s, 846 size_type __n2) 847 { 848 __glibcxx_requires_string_len(__s, __n2); 849 _M_check(__pos, "basic_string::replace"); 850 __n1 = _M_limit(__pos, __n1); 851 _M_check_length(__n1, __n2, "basic_string::replace"); 852 bool __left; 853 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 854 return _M_replace_safe(__pos, __n1, __s, __n2); 855 else if ((__left = __s + __n2 <= _M_data() + __pos) 856 || _M_data() + __pos + __n1 <= __s) 857 { 858 // Work in-place: non-overlapping case. 859 size_type __off = __s - _M_data(); 860 __left ? __off : (__off += __n2 - __n1); 861 _M_mutate(__pos, __n1, __n2); 862 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 863 return *this; 864 } 865 else 866 { 867 // Todo: overlapping case. 868 const basic_string __tmp(__s, __n2); 869 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 870 } 871 } 872 873 template<typename _CharT, typename _Traits, typename _Alloc> 874 void 875 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 876 _M_destroy(const _Alloc& __a) throw () 877 { 878 const size_type __size = sizeof(_Rep_base) + 879 (this->_M_capacity + 1) * sizeof(_CharT); 880 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 881 } 882 883 template<typename _CharT, typename _Traits, typename _Alloc> 884 void 885 basic_string<_CharT, _Traits, _Alloc>:: 886 _M_leak_hard() 887 { 888 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 889 if (_M_rep() == &_S_empty_rep()) 890 return; 891 #endif 892 if (_M_rep()->_M_is_shared()) 893 _M_mutate(0, 0, 0); 894 _M_rep()->_M_set_leaked(); 895 } 896 897 template<typename _CharT, typename _Traits, typename _Alloc> 898 void 899 basic_string<_CharT, _Traits, _Alloc>:: 900 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 901 { 902 const size_type __old_size = this->size(); 903 const size_type __new_size = __old_size + __len2 - __len1; 904 const size_type __how_much = __old_size - __pos - __len1; 905 906 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 907 { 908 // Must reallocate. 909 const allocator_type __a = get_allocator(); 910 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 911 912 if (__pos) 913 _M_copy(__r->_M_refdata(), _M_data(), __pos); 914 if (__how_much) 915 _M_copy(__r->_M_refdata() + __pos + __len2, 916 _M_data() + __pos + __len1, __how_much); 917 918 _M_rep()->_M_dispose(__a); 919 _M_data(__r->_M_refdata()); 920 } 921 else if (__how_much && __len1 != __len2) 922 { 923 // Work in-place. 924 _M_move(_M_data() + __pos + __len2, 925 _M_data() + __pos + __len1, __how_much); 926 } 927 _M_rep()->_M_set_length_and_sharable(__new_size); 928 } 929 930 template<typename _CharT, typename _Traits, typename _Alloc> 931 void 932 basic_string<_CharT, _Traits, _Alloc>:: 933 reserve(size_type __res) 934 { 935 const size_type __capacity = capacity(); 936 937 // _GLIBCXX_RESOLVE_LIB_DEFECTS 938 // 2968. Inconsistencies between basic_string reserve and 939 // vector/unordered_map/unordered_set reserve functions 940 // P0966 reserve should not shrink 941 if (__res <= __capacity) 942 { 943 if (!_M_rep()->_M_is_shared()) 944 return; 945 946 // unshare, but keep same capacity 947 __res = __capacity; 948 } 949 950 const allocator_type __a = get_allocator(); 951 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 952 _M_rep()->_M_dispose(__a); 953 _M_data(__tmp); 954 } 955 956 template<typename _CharT, typename _Traits, typename _Alloc> 957 void 958 basic_string<_CharT, _Traits, _Alloc>:: 959 swap(basic_string& __s) 960 _GLIBCXX_NOEXCEPT_IF(allocator_traits<_Alloc>::is_always_equal::value) 961 { 962 if (_M_rep()->_M_is_leaked()) 963 _M_rep()->_M_set_sharable(); 964 if (__s._M_rep()->_M_is_leaked()) 965 __s._M_rep()->_M_set_sharable(); 966 if (this->get_allocator() == __s.get_allocator()) 967 { 968 _CharT* __tmp = _M_data(); 969 _M_data(__s._M_data()); 970 __s._M_data(__tmp); 971 } 972 // The code below can usually be optimized away. 973 else 974 { 975 const basic_string __tmp1(_M_ibegin(), _M_iend(), 976 __s.get_allocator()); 977 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 978 this->get_allocator()); 979 *this = __tmp2; 980 __s = __tmp1; 981 } 982 } 983 984 template<typename _CharT, typename _Traits, typename _Alloc> 985 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 986 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 987 _S_create(size_type __capacity, size_type __old_capacity, 988 const _Alloc& __alloc) 989 { 990 // _GLIBCXX_RESOLVE_LIB_DEFECTS 991 // 83. String::npos vs. string::max_size() 992 if (__capacity > _S_max_size) 993 __throw_length_error(__N("basic_string::_S_create")); 994 995 // The standard places no restriction on allocating more memory 996 // than is strictly needed within this layer at the moment or as 997 // requested by an explicit application call to reserve(n). 998 999 // Many malloc implementations perform quite poorly when an 1000 // application attempts to allocate memory in a stepwise fashion 1001 // growing each allocation size by only 1 char. Additionally, 1002 // it makes little sense to allocate less linear memory than the 1003 // natural blocking size of the malloc implementation. 1004 // Unfortunately, we would need a somewhat low-level calculation 1005 // with tuned parameters to get this perfect for any particular 1006 // malloc implementation. Fortunately, generalizations about 1007 // common features seen among implementations seems to suffice. 1008 1009 // __pagesize need not match the actual VM page size for good 1010 // results in practice, thus we pick a common value on the low 1011 // side. __malloc_header_size is an estimate of the amount of 1012 // overhead per memory allocation (in practice seen N * sizeof 1013 // (void*) where N is 0, 2 or 4). According to folklore, 1014 // picking this value on the high side is better than 1015 // low-balling it (especially when this algorithm is used with 1016 // malloc implementations that allocate memory blocks rounded up 1017 // to a size which is a power of 2). 1018 const size_type __pagesize = 4096; 1019 const size_type __malloc_header_size = 4 * sizeof(void*); 1020 1021 // The below implements an exponential growth policy, necessary to 1022 // meet amortized linear time requirements of the library: see 1023 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 1024 // It's active for allocations requiring an amount of memory above 1025 // system pagesize. This is consistent with the requirements of the 1026 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 1027 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 1028 __capacity = 2 * __old_capacity; 1029 1030 // NB: Need an array of char_type[__capacity], plus a terminating 1031 // null char_type() element, plus enough for the _Rep data structure. 1032 // Whew. Seemingly so needy, yet so elemental. 1033 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 1034 1035 const size_type __adj_size = __size + __malloc_header_size; 1036 if (__adj_size > __pagesize && __capacity > __old_capacity) 1037 { 1038 const size_type __extra = __pagesize - __adj_size % __pagesize; 1039 __capacity += __extra / sizeof(_CharT); 1040 // Never allocate a string bigger than _S_max_size. 1041 if (__capacity > _S_max_size) 1042 __capacity = _S_max_size; 1043 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 1044 } 1045 1046 // NB: Might throw, but no worries about a leak, mate: _Rep() 1047 // does not throw. 1048 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 1049 _Rep *__p = new (__place) _Rep; 1050 __p->_M_capacity = __capacity; 1051 // ABI compatibility - 3.4.x set in _S_create both 1052 // _M_refcount and _M_length. All callers of _S_create 1053 // in basic_string.tcc then set just _M_length. 1054 // In 4.0.x and later both _M_refcount and _M_length 1055 // are initialized in the callers, unfortunately we can 1056 // have 3.4.x compiled code with _S_create callers inlined 1057 // calling 4.0.x+ _S_create. 1058 __p->_M_set_sharable(); 1059 return __p; 1060 } 1061 1062 template<typename _CharT, typename _Traits, typename _Alloc> 1063 _CharT* 1064 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 1065 _M_clone(const _Alloc& __alloc, size_type __res) 1066 { 1067 // Requested capacity of the clone. 1068 const size_type __requested_cap = this->_M_length + __res; 1069 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 1070 __alloc); 1071 if (this->_M_length) 1072 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 1073 1074 __r->_M_set_length_and_sharable(this->_M_length); 1075 return __r->_M_refdata(); 1076 } 1077 1078 template<typename _CharT, typename _Traits, typename _Alloc> 1079 void 1080 basic_string<_CharT, _Traits, _Alloc>:: 1081 resize(size_type __n, _CharT __c) 1082 { 1083 const size_type __size = this->size(); 1084 _M_check_length(__size, __n, "basic_string::resize"); 1085 if (__size < __n) 1086 this->append(__n - __size, __c); 1087 else if (__n < __size) 1088 this->erase(__n); 1089 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 1090 } 1091 1092 template<typename _CharT, typename _Traits, typename _Alloc> 1093 template<typename _InputIterator> 1094 basic_string<_CharT, _Traits, _Alloc>& 1095 basic_string<_CharT, _Traits, _Alloc>:: 1096 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 1097 _InputIterator __k2, __false_type) 1098 { 1099 const basic_string __s(__k1, __k2); 1100 const size_type __n1 = __i2 - __i1; 1101 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 1102 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 1103 __s.size()); 1104 } 1105 1106 template<typename _CharT, typename _Traits, typename _Alloc> 1107 basic_string<_CharT, _Traits, _Alloc>& 1108 basic_string<_CharT, _Traits, _Alloc>:: 1109 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 1110 _CharT __c) 1111 { 1112 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 1113 _M_mutate(__pos1, __n1, __n2); 1114 if (__n2) 1115 _M_assign(_M_data() + __pos1, __n2, __c); 1116 return *this; 1117 } 1118 1119 template<typename _CharT, typename _Traits, typename _Alloc> 1120 basic_string<_CharT, _Traits, _Alloc>& 1121 basic_string<_CharT, _Traits, _Alloc>:: 1122 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 1123 size_type __n2) 1124 { 1125 _M_mutate(__pos1, __n1, __n2); 1126 if (__n2) 1127 _M_copy(_M_data() + __pos1, __s, __n2); 1128 return *this; 1129 } 1130 1131 template<typename _CharT, typename _Traits, typename _Alloc> 1132 void 1133 basic_string<_CharT, _Traits, _Alloc>:: 1134 reserve() 1135 { 1136 #if __cpp_exceptions 1137 if (length() < capacity() || _M_rep()->_M_is_shared()) 1138 try 1139 { 1140 const allocator_type __a = get_allocator(); 1141 _CharT* __tmp = _M_rep()->_M_clone(__a); 1142 _M_rep()->_M_dispose(__a); 1143 _M_data(__tmp); 1144 } 1145 catch (const __cxxabiv1::__forced_unwind&) 1146 { throw; } 1147 catch (...) 1148 { /* swallow the exception */ } 1149 #endif 1150 } 1151 1152 template<typename _CharT, typename _Traits, typename _Alloc> 1153 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1154 basic_string<_CharT, _Traits, _Alloc>:: 1155 copy(_CharT* __s, size_type __n, size_type __pos) const 1156 { 1157 _M_check(__pos, "basic_string::copy"); 1158 __n = _M_limit(__pos, __n); 1159 __glibcxx_requires_string_len(__s, __n); 1160 if (__n) 1161 _M_copy(__s, _M_data() + __pos, __n); 1162 // 21.3.5.7 par 3: do not append null. (good.) 1163 return __n; 1164 } 1165 #endif // !_GLIBCXX_USE_CXX11_ABI 1166 1167 template<typename _CharT, typename _Traits, typename _Alloc> 1168 basic_string<_CharT, _Traits, _Alloc> operator +(const _CharT * __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)1169 operator+(const _CharT* __lhs, 1170 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1171 { 1172 __glibcxx_requires_string(__lhs); 1173 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1174 typedef typename __string_type::size_type __size_type; 1175 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1176 rebind<_CharT>::other _Char_alloc_type; 1177 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits; 1178 const __size_type __len = _Traits::length(__lhs); 1179 __string_type __str(_Alloc_traits::_S_select_on_copy( 1180 __rhs.get_allocator())); 1181 __str.reserve(__len + __rhs.size()); 1182 __str.append(__lhs, __len); 1183 __str.append(__rhs); 1184 return __str; 1185 } 1186 1187 template<typename _CharT, typename _Traits, typename _Alloc> 1188 basic_string<_CharT, _Traits, _Alloc> operator +(_CharT __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)1189 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1190 { 1191 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1192 typedef typename __string_type::size_type __size_type; 1193 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1194 rebind<_CharT>::other _Char_alloc_type; 1195 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits; 1196 __string_type __str(_Alloc_traits::_S_select_on_copy( 1197 __rhs.get_allocator())); 1198 const __size_type __len = __rhs.size(); 1199 __str.reserve(__len + 1); 1200 __str.append(__size_type(1), __lhs); 1201 __str.append(__rhs); 1202 return __str; 1203 } 1204 1205 template<typename _CharT, typename _Traits, typename _Alloc> 1206 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1207 basic_string<_CharT, _Traits, _Alloc>:: find(const _CharT * __s,size_type __pos,size_type __n) const1208 find(const _CharT* __s, size_type __pos, size_type __n) const 1209 _GLIBCXX_NOEXCEPT 1210 { 1211 __glibcxx_requires_string_len(__s, __n); 1212 const size_type __size = this->size(); 1213 1214 if (__n == 0) 1215 return __pos <= __size ? __pos : npos; 1216 if (__pos >= __size) 1217 return npos; 1218 1219 const _CharT __elem0 = __s[0]; 1220 const _CharT* const __data = data(); 1221 const _CharT* __first = __data + __pos; 1222 const _CharT* const __last = __data + __size; 1223 size_type __len = __size - __pos; 1224 1225 while (__len >= __n) 1226 { 1227 // Find the first occurrence of __elem0: 1228 __first = traits_type::find(__first, __len - __n + 1, __elem0); 1229 if (!__first) 1230 return npos; 1231 // Compare the full strings from the first occurrence of __elem0. 1232 // We already know that __first[0] == __s[0] but compare them again 1233 // anyway because __s is probably aligned, which helps memcmp. 1234 if (traits_type::compare(__first, __s, __n) == 0) 1235 return __first - __data; 1236 __len = __last - ++__first; 1237 } 1238 return npos; 1239 } 1240 1241 template<typename _CharT, typename _Traits, typename _Alloc> 1242 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1243 basic_string<_CharT, _Traits, _Alloc>:: find(_CharT __c,size_type __pos) const1244 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1245 { 1246 size_type __ret = npos; 1247 const size_type __size = this->size(); 1248 if (__pos < __size) 1249 { 1250 const _CharT* __data = _M_data(); 1251 const size_type __n = __size - __pos; 1252 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 1253 if (__p) 1254 __ret = __p - __data; 1255 } 1256 return __ret; 1257 } 1258 1259 template<typename _CharT, typename _Traits, typename _Alloc> 1260 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1261 basic_string<_CharT, _Traits, _Alloc>:: rfind(const _CharT * __s,size_type __pos,size_type __n) const1262 rfind(const _CharT* __s, size_type __pos, size_type __n) const 1263 _GLIBCXX_NOEXCEPT 1264 { 1265 __glibcxx_requires_string_len(__s, __n); 1266 const size_type __size = this->size(); 1267 if (__n <= __size) 1268 { 1269 __pos = std::min(size_type(__size - __n), __pos); 1270 const _CharT* __data = _M_data(); 1271 do 1272 { 1273 if (traits_type::compare(__data + __pos, __s, __n) == 0) 1274 return __pos; 1275 } 1276 while (__pos-- > 0); 1277 } 1278 return npos; 1279 } 1280 1281 template<typename _CharT, typename _Traits, typename _Alloc> 1282 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1283 basic_string<_CharT, _Traits, _Alloc>:: rfind(_CharT __c,size_type __pos) const1284 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1285 { 1286 size_type __size = this->size(); 1287 if (__size) 1288 { 1289 if (--__size > __pos) 1290 __size = __pos; 1291 for (++__size; __size-- > 0; ) 1292 if (traits_type::eq(_M_data()[__size], __c)) 1293 return __size; 1294 } 1295 return npos; 1296 } 1297 1298 template<typename _CharT, typename _Traits, typename _Alloc> 1299 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1300 basic_string<_CharT, _Traits, _Alloc>:: find_first_of(const _CharT * __s,size_type __pos,size_type __n) const1301 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 1302 _GLIBCXX_NOEXCEPT 1303 { 1304 __glibcxx_requires_string_len(__s, __n); 1305 for (; __n && __pos < this->size(); ++__pos) 1306 { 1307 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 1308 if (__p) 1309 return __pos; 1310 } 1311 return npos; 1312 } 1313 1314 template<typename _CharT, typename _Traits, typename _Alloc> 1315 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1316 basic_string<_CharT, _Traits, _Alloc>:: find_last_of(const _CharT * __s,size_type __pos,size_type __n) const1317 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 1318 _GLIBCXX_NOEXCEPT 1319 { 1320 __glibcxx_requires_string_len(__s, __n); 1321 size_type __size = this->size(); 1322 if (__size && __n) 1323 { 1324 if (--__size > __pos) 1325 __size = __pos; 1326 do 1327 { 1328 if (traits_type::find(__s, __n, _M_data()[__size])) 1329 return __size; 1330 } 1331 while (__size-- != 0); 1332 } 1333 return npos; 1334 } 1335 1336 template<typename _CharT, typename _Traits, typename _Alloc> 1337 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1338 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(const _CharT * __s,size_type __pos,size_type __n) const1339 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 1340 _GLIBCXX_NOEXCEPT 1341 { 1342 __glibcxx_requires_string_len(__s, __n); 1343 for (; __pos < this->size(); ++__pos) 1344 if (!traits_type::find(__s, __n, _M_data()[__pos])) 1345 return __pos; 1346 return npos; 1347 } 1348 1349 template<typename _CharT, typename _Traits, typename _Alloc> 1350 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1351 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(_CharT __c,size_type __pos) const1352 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1353 { 1354 for (; __pos < this->size(); ++__pos) 1355 if (!traits_type::eq(_M_data()[__pos], __c)) 1356 return __pos; 1357 return npos; 1358 } 1359 1360 template<typename _CharT, typename _Traits, typename _Alloc> 1361 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1362 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(const _CharT * __s,size_type __pos,size_type __n) const1363 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 1364 _GLIBCXX_NOEXCEPT 1365 { 1366 __glibcxx_requires_string_len(__s, __n); 1367 size_type __size = this->size(); 1368 if (__size) 1369 { 1370 if (--__size > __pos) 1371 __size = __pos; 1372 do 1373 { 1374 if (!traits_type::find(__s, __n, _M_data()[__size])) 1375 return __size; 1376 } 1377 while (__size--); 1378 } 1379 return npos; 1380 } 1381 1382 template<typename _CharT, typename _Traits, typename _Alloc> 1383 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1384 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(_CharT __c,size_type __pos) const1385 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1386 { 1387 size_type __size = this->size(); 1388 if (__size) 1389 { 1390 if (--__size > __pos) 1391 __size = __pos; 1392 do 1393 { 1394 if (!traits_type::eq(_M_data()[__size], __c)) 1395 return __size; 1396 } 1397 while (__size--); 1398 } 1399 return npos; 1400 } 1401 1402 template<typename _CharT, typename _Traits, typename _Alloc> 1403 int 1404 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n,const basic_string & __str) const1405 compare(size_type __pos, size_type __n, const basic_string& __str) const 1406 { 1407 _M_check(__pos, "basic_string::compare"); 1408 __n = _M_limit(__pos, __n); 1409 const size_type __osize = __str.size(); 1410 const size_type __len = std::min(__n, __osize); 1411 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 1412 if (!__r) 1413 __r = _S_compare(__n, __osize); 1414 return __r; 1415 } 1416 1417 template<typename _CharT, typename _Traits, typename _Alloc> 1418 int 1419 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos1,size_type __n1,const basic_string & __str,size_type __pos2,size_type __n2) const1420 compare(size_type __pos1, size_type __n1, const basic_string& __str, 1421 size_type __pos2, size_type __n2) const 1422 { 1423 _M_check(__pos1, "basic_string::compare"); 1424 __str._M_check(__pos2, "basic_string::compare"); 1425 __n1 = _M_limit(__pos1, __n1); 1426 __n2 = __str._M_limit(__pos2, __n2); 1427 const size_type __len = std::min(__n1, __n2); 1428 int __r = traits_type::compare(_M_data() + __pos1, 1429 __str.data() + __pos2, __len); 1430 if (!__r) 1431 __r = _S_compare(__n1, __n2); 1432 return __r; 1433 } 1434 1435 template<typename _CharT, typename _Traits, typename _Alloc> 1436 int 1437 basic_string<_CharT, _Traits, _Alloc>:: compare(const _CharT * __s) const1438 compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT 1439 { 1440 __glibcxx_requires_string(__s); 1441 const size_type __size = this->size(); 1442 const size_type __osize = traits_type::length(__s); 1443 const size_type __len = std::min(__size, __osize); 1444 int __r = traits_type::compare(_M_data(), __s, __len); 1445 if (!__r) 1446 __r = _S_compare(__size, __osize); 1447 return __r; 1448 } 1449 1450 template<typename _CharT, typename _Traits, typename _Alloc> 1451 int 1452 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s) const1453 compare(size_type __pos, size_type __n1, const _CharT* __s) const 1454 { 1455 __glibcxx_requires_string(__s); 1456 _M_check(__pos, "basic_string::compare"); 1457 __n1 = _M_limit(__pos, __n1); 1458 const size_type __osize = traits_type::length(__s); 1459 const size_type __len = std::min(__n1, __osize); 1460 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1461 if (!__r) 1462 __r = _S_compare(__n1, __osize); 1463 return __r; 1464 } 1465 1466 template<typename _CharT, typename _Traits, typename _Alloc> 1467 int 1468 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s,size_type __n2) const1469 compare(size_type __pos, size_type __n1, const _CharT* __s, 1470 size_type __n2) const 1471 { 1472 __glibcxx_requires_string_len(__s, __n2); 1473 _M_check(__pos, "basic_string::compare"); 1474 __n1 = _M_limit(__pos, __n1); 1475 const size_type __len = std::min(__n1, __n2); 1476 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1477 if (!__r) 1478 __r = _S_compare(__n1, __n2); 1479 return __r; 1480 } 1481 1482 // 21.3.7.9 basic_string::getline and operators 1483 template<typename _CharT, typename _Traits, typename _Alloc> 1484 basic_istream<_CharT, _Traits>& operator >>(basic_istream<_CharT,_Traits> & __in,basic_string<_CharT,_Traits,_Alloc> & __str)1485 operator>>(basic_istream<_CharT, _Traits>& __in, 1486 basic_string<_CharT, _Traits, _Alloc>& __str) 1487 { 1488 typedef basic_istream<_CharT, _Traits> __istream_type; 1489 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1490 typedef typename __istream_type::ios_base __ios_base; 1491 typedef typename __istream_type::int_type __int_type; 1492 typedef typename __string_type::size_type __size_type; 1493 typedef ctype<_CharT> __ctype_type; 1494 typedef typename __ctype_type::ctype_base __ctype_base; 1495 1496 __size_type __extracted = 0; 1497 typename __ios_base::iostate __err = __ios_base::goodbit; 1498 typename __istream_type::sentry __cerb(__in, false); 1499 if (__cerb) 1500 { 1501 __try 1502 { 1503 // Avoid reallocation for common case. 1504 __str.erase(); 1505 _CharT __buf[128]; 1506 __size_type __len = 0; 1507 const streamsize __w = __in.width(); 1508 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 1509 : __str.max_size(); 1510 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 1511 const __int_type __eof = _Traits::eof(); 1512 __int_type __c = __in.rdbuf()->sgetc(); 1513 1514 while (__extracted < __n 1515 && !_Traits::eq_int_type(__c, __eof) 1516 && !__ct.is(__ctype_base::space, 1517 _Traits::to_char_type(__c))) 1518 { 1519 if (__len == sizeof(__buf) / sizeof(_CharT)) 1520 { 1521 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 1522 __len = 0; 1523 } 1524 __buf[__len++] = _Traits::to_char_type(__c); 1525 ++__extracted; 1526 __c = __in.rdbuf()->snextc(); 1527 } 1528 __str.append(__buf, __len); 1529 1530 if (__extracted < __n && _Traits::eq_int_type(__c, __eof)) 1531 __err |= __ios_base::eofbit; 1532 __in.width(0); 1533 } 1534 __catch(__cxxabiv1::__forced_unwind&) 1535 { 1536 __in._M_setstate(__ios_base::badbit); 1537 __throw_exception_again; 1538 } 1539 __catch(...) 1540 { 1541 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1542 // 91. Description of operator>> and getline() for string<> 1543 // might cause endless loop 1544 __in._M_setstate(__ios_base::badbit); 1545 } 1546 } 1547 // 211. operator>>(istream&, string&) doesn't set failbit 1548 if (!__extracted) 1549 __err |= __ios_base::failbit; 1550 if (__err) 1551 __in.setstate(__err); 1552 return __in; 1553 } 1554 1555 template<typename _CharT, typename _Traits, typename _Alloc> 1556 basic_istream<_CharT, _Traits>& getline(basic_istream<_CharT,_Traits> & __in,basic_string<_CharT,_Traits,_Alloc> & __str,_CharT __delim)1557 getline(basic_istream<_CharT, _Traits>& __in, 1558 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 1559 { 1560 typedef basic_istream<_CharT, _Traits> __istream_type; 1561 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1562 typedef typename __istream_type::ios_base __ios_base; 1563 typedef typename __istream_type::int_type __int_type; 1564 typedef typename __string_type::size_type __size_type; 1565 1566 __size_type __extracted = 0; 1567 const __size_type __n = __str.max_size(); 1568 typename __ios_base::iostate __err = __ios_base::goodbit; 1569 typename __istream_type::sentry __cerb(__in, true); 1570 if (__cerb) 1571 { 1572 __try 1573 { 1574 __str.erase(); 1575 const __int_type __idelim = _Traits::to_int_type(__delim); 1576 const __int_type __eof = _Traits::eof(); 1577 __int_type __c = __in.rdbuf()->sgetc(); 1578 1579 while (__extracted < __n 1580 && !_Traits::eq_int_type(__c, __eof) 1581 && !_Traits::eq_int_type(__c, __idelim)) 1582 { 1583 __str += _Traits::to_char_type(__c); 1584 ++__extracted; 1585 __c = __in.rdbuf()->snextc(); 1586 } 1587 1588 if (_Traits::eq_int_type(__c, __eof)) 1589 __err |= __ios_base::eofbit; 1590 else if (_Traits::eq_int_type(__c, __idelim)) 1591 { 1592 ++__extracted; 1593 __in.rdbuf()->sbumpc(); 1594 } 1595 else 1596 __err |= __ios_base::failbit; 1597 } 1598 __catch(__cxxabiv1::__forced_unwind&) 1599 { 1600 __in._M_setstate(__ios_base::badbit); 1601 __throw_exception_again; 1602 } 1603 __catch(...) 1604 { 1605 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1606 // 91. Description of operator>> and getline() for string<> 1607 // might cause endless loop 1608 __in._M_setstate(__ios_base::badbit); 1609 } 1610 } 1611 if (!__extracted) 1612 __err |= __ios_base::failbit; 1613 if (__err) 1614 __in.setstate(__err); 1615 return __in; 1616 } 1617 1618 // Inhibit implicit instantiations for required instantiations, 1619 // which are defined via explicit instantiations elsewhere. 1620 #if _GLIBCXX_EXTERN_TEMPLATE 1621 // The explicit instantiation definitions in src/c++11/string-inst.cc and 1622 // src/c++17/string-inst.cc only instantiate the members required for C++17 1623 // and earlier standards (so not C++20's starts_with and ends_with). 1624 // Suppress the explicit instantiation declarations for C++20, so C++20 1625 // code will implicitly instantiate std::string and std::wstring as needed. 1626 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 1627 extern template class basic_string<char>; 1628 # elif ! _GLIBCXX_USE_CXX11_ABI 1629 // Still need to prevent implicit instantiation of the COW empty rep, 1630 // to ensure the definition in libstdc++.so is unique (PR 86138). 1631 extern template basic_string<char>::size_type 1632 basic_string<char>::_Rep::_S_empty_rep_storage[]; 1633 # endif 1634 1635 extern template 1636 basic_istream<char>& 1637 operator>>(basic_istream<char>&, string&); 1638 extern template 1639 basic_ostream<char>& 1640 operator<<(basic_ostream<char>&, const string&); 1641 extern template 1642 basic_istream<char>& 1643 getline(basic_istream<char>&, string&, char); 1644 extern template 1645 basic_istream<char>& 1646 getline(basic_istream<char>&, string&); 1647 1648 #ifdef _GLIBCXX_USE_WCHAR_T 1649 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 1650 extern template class basic_string<wchar_t>; 1651 # elif ! _GLIBCXX_USE_CXX11_ABI 1652 extern template basic_string<wchar_t>::size_type 1653 basic_string<wchar_t>::_Rep::_S_empty_rep_storage[]; 1654 # endif 1655 1656 extern template 1657 basic_istream<wchar_t>& 1658 operator>>(basic_istream<wchar_t>&, wstring&); 1659 extern template 1660 basic_ostream<wchar_t>& 1661 operator<<(basic_ostream<wchar_t>&, const wstring&); 1662 extern template 1663 basic_istream<wchar_t>& 1664 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 1665 extern template 1666 basic_istream<wchar_t>& 1667 getline(basic_istream<wchar_t>&, wstring&); 1668 #endif // _GLIBCXX_USE_WCHAR_T 1669 #endif // _GLIBCXX_EXTERN_TEMPLATE 1670 1671 _GLIBCXX_END_NAMESPACE_VERSION 1672 } // namespace std 1673 1674 #endif 1675