libstdc++
|
00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/basic_string.tcc 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{string} 00028 */ 00029 00030 // 00031 // ISO C++ 14882: 21 Strings library 00032 // 00033 00034 // Written by Jason Merrill based upon the specification by Takanori Adachi 00035 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 00036 // Non-reference-counted implementation written by Paolo Carlini and 00037 // updated by Jonathan Wakely for ISO-14882-2011. 00038 00039 #ifndef _BASIC_STRING_TCC 00040 #define _BASIC_STRING_TCC 1 00041 00042 #pragma GCC system_header 00043 00044 #include <bits/cxxabi_forced.h> 00045 00046 namespace std _GLIBCXX_VISIBILITY(default) 00047 { 00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00049 00050 #if _GLIBCXX_USE_CXX11_ABI 00051 00052 template<typename _CharT, typename _Traits, typename _Alloc> 00053 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00054 basic_string<_CharT, _Traits, _Alloc>::npos; 00055 00056 template<typename _CharT, typename _Traits, typename _Alloc> 00057 void 00058 basic_string<_CharT, _Traits, _Alloc>:: 00059 swap(basic_string& __s) _GLIBCXX_NOEXCEPT 00060 { 00061 if (this == &__s) 00062 return; 00063 00064 _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator()); 00065 00066 if (_M_is_local()) 00067 if (__s._M_is_local()) 00068 { 00069 if (length() && __s.length()) 00070 { 00071 _CharT __tmp_data[_S_local_capacity + 1]; 00072 traits_type::copy(__tmp_data, __s._M_local_buf, 00073 _S_local_capacity + 1); 00074 traits_type::copy(__s._M_local_buf, _M_local_buf, 00075 _S_local_capacity + 1); 00076 traits_type::copy(_M_local_buf, __tmp_data, 00077 _S_local_capacity + 1); 00078 } 00079 else if (__s.length()) 00080 { 00081 traits_type::copy(_M_local_buf, __s._M_local_buf, 00082 _S_local_capacity + 1); 00083 _M_length(__s.length()); 00084 __s._M_set_length(0); 00085 return; 00086 } 00087 else if (length()) 00088 { 00089 traits_type::copy(__s._M_local_buf, _M_local_buf, 00090 _S_local_capacity + 1); 00091 __s._M_length(length()); 00092 _M_set_length(0); 00093 return; 00094 } 00095 } 00096 else 00097 { 00098 const size_type __tmp_capacity = __s._M_allocated_capacity; 00099 traits_type::copy(__s._M_local_buf, _M_local_buf, 00100 _S_local_capacity + 1); 00101 _M_data(__s._M_data()); 00102 __s._M_data(__s._M_local_buf); 00103 _M_capacity(__tmp_capacity); 00104 } 00105 else 00106 { 00107 const size_type __tmp_capacity = _M_allocated_capacity; 00108 if (__s._M_is_local()) 00109 { 00110 traits_type::copy(_M_local_buf, __s._M_local_buf, 00111 _S_local_capacity + 1); 00112 __s._M_data(_M_data()); 00113 _M_data(_M_local_buf); 00114 } 00115 else 00116 { 00117 pointer __tmp_ptr = _M_data(); 00118 _M_data(__s._M_data()); 00119 __s._M_data(__tmp_ptr); 00120 _M_capacity(__s._M_allocated_capacity); 00121 } 00122 __s._M_capacity(__tmp_capacity); 00123 } 00124 00125 const size_type __tmp_length = length(); 00126 _M_length(__s.length()); 00127 __s._M_length(__tmp_length); 00128 } 00129 00130 template<typename _CharT, typename _Traits, typename _Alloc> 00131 typename basic_string<_CharT, _Traits, _Alloc>::pointer 00132 basic_string<_CharT, _Traits, _Alloc>:: 00133 _M_create(size_type& __capacity, size_type __old_capacity) 00134 { 00135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00136 // 83. String::npos vs. string::max_size() 00137 if (__capacity > max_size()) 00138 std::__throw_length_error(__N("basic_string::_M_create")); 00139 00140 // The below implements an exponential growth policy, necessary to 00141 // meet amortized linear time requirements of the library: see 00142 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00143 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 00144 { 00145 __capacity = 2 * __old_capacity; 00146 // Never allocate a string bigger than max_size. 00147 if (__capacity > max_size()) 00148 __capacity = max_size(); 00149 } 00150 00151 // NB: Need an array of char_type[__capacity], plus a terminating 00152 // null char_type() element. 00153 return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1); 00154 } 00155 00156 // NB: This is the special case for Input Iterators, used in 00157 // istreambuf_iterators, etc. 00158 // Input Iterators have a cost structure very different from 00159 // pointers, calling for a different coding style. 00160 template<typename _CharT, typename _Traits, typename _Alloc> 00161 template<typename _InIterator> 00162 void 00163 basic_string<_CharT, _Traits, _Alloc>:: 00164 _M_construct(_InIterator __beg, _InIterator __end, 00165 std::input_iterator_tag) 00166 { 00167 size_type __len = 0; 00168 size_type __capacity = size_type(_S_local_capacity); 00169 00170 while (__beg != __end && __len < __capacity) 00171 { 00172 _M_data()[__len++] = *__beg; 00173 ++__beg; 00174 } 00175 00176 __try 00177 { 00178 while (__beg != __end) 00179 { 00180 if (__len == __capacity) 00181 { 00182 // Allocate more space. 00183 __capacity = __len + 1; 00184 pointer __another = _M_create(__capacity, __len); 00185 this->_S_copy(__another, _M_data(), __len); 00186 _M_dispose(); 00187 _M_data(__another); 00188 _M_capacity(__capacity); 00189 } 00190 _M_data()[__len++] = *__beg; 00191 ++__beg; 00192 } 00193 } 00194 __catch(...) 00195 { 00196 _M_dispose(); 00197 __throw_exception_again; 00198 } 00199 00200 _M_set_length(__len); 00201 } 00202 00203 template<typename _CharT, typename _Traits, typename _Alloc> 00204 template<typename _InIterator> 00205 void 00206 basic_string<_CharT, _Traits, _Alloc>:: 00207 _M_construct(_InIterator __beg, _InIterator __end, 00208 std::forward_iterator_tag) 00209 { 00210 // NB: Not required, but considered best practice. 00211 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 00212 std::__throw_logic_error(__N("basic_string::" 00213 "_M_construct null not valid")); 00214 00215 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 00216 00217 if (__dnew > size_type(_S_local_capacity)) 00218 { 00219 _M_data(_M_create(__dnew, size_type(0))); 00220 _M_capacity(__dnew); 00221 } 00222 00223 // Check for out_of_range and length_error exceptions. 00224 __try 00225 { this->_S_copy_chars(_M_data(), __beg, __end); } 00226 __catch(...) 00227 { 00228 _M_dispose(); 00229 __throw_exception_again; 00230 } 00231 00232 _M_set_length(__dnew); 00233 } 00234 00235 template<typename _CharT, typename _Traits, typename _Alloc> 00236 void 00237 basic_string<_CharT, _Traits, _Alloc>:: 00238 _M_construct(size_type __n, _CharT __c) 00239 { 00240 if (__n > size_type(_S_local_capacity)) 00241 { 00242 _M_data(_M_create(__n, size_type(0))); 00243 _M_capacity(__n); 00244 } 00245 00246 if (__n) 00247 this->_S_assign(_M_data(), __n, __c); 00248 00249 _M_set_length(__n); 00250 } 00251 00252 template<typename _CharT, typename _Traits, typename _Alloc> 00253 void 00254 basic_string<_CharT, _Traits, _Alloc>:: 00255 _M_assign(const basic_string& __str) 00256 { 00257 if (this != &__str) 00258 { 00259 const size_type __rsize = __str.length(); 00260 const size_type __capacity = capacity(); 00261 00262 if (__rsize > __capacity) 00263 { 00264 size_type __new_capacity = __rsize; 00265 pointer __tmp = _M_create(__new_capacity, __capacity); 00266 _M_dispose(); 00267 _M_data(__tmp); 00268 _M_capacity(__new_capacity); 00269 } 00270 00271 if (__rsize) 00272 this->_S_copy(_M_data(), __str._M_data(), __rsize); 00273 00274 _M_set_length(__rsize); 00275 } 00276 } 00277 00278 template<typename _CharT, typename _Traits, typename _Alloc> 00279 void 00280 basic_string<_CharT, _Traits, _Alloc>:: 00281 reserve(size_type __res) 00282 { 00283 // Make sure we don't shrink below the current size. 00284 if (__res < length()) 00285 __res = length(); 00286 00287 const size_type __capacity = capacity(); 00288 if (__res != __capacity) 00289 { 00290 if (__res > __capacity 00291 || __res > size_type(_S_local_capacity)) 00292 { 00293 pointer __tmp = _M_create(__res, __capacity); 00294 this->_S_copy(__tmp, _M_data(), length() + 1); 00295 _M_dispose(); 00296 _M_data(__tmp); 00297 _M_capacity(__res); 00298 } 00299 else if (!_M_is_local()) 00300 { 00301 this->_S_copy(_M_local_data(), _M_data(), length() + 1); 00302 _M_destroy(__capacity); 00303 _M_data(_M_local_data()); 00304 } 00305 } 00306 } 00307 00308 template<typename _CharT, typename _Traits, typename _Alloc> 00309 void 00310 basic_string<_CharT, _Traits, _Alloc>:: 00311 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 00312 size_type __len2) 00313 { 00314 const size_type __how_much = length() - __pos - __len1; 00315 00316 size_type __new_capacity = length() + __len2 - __len1; 00317 pointer __r = _M_create(__new_capacity, capacity()); 00318 00319 if (__pos) 00320 this->_S_copy(__r, _M_data(), __pos); 00321 if (__s && __len2) 00322 this->_S_copy(__r + __pos, __s, __len2); 00323 if (__how_much) 00324 this->_S_copy(__r + __pos + __len2, 00325 _M_data() + __pos + __len1, __how_much); 00326 00327 _M_dispose(); 00328 _M_data(__r); 00329 _M_capacity(__new_capacity); 00330 } 00331 00332 template<typename _CharT, typename _Traits, typename _Alloc> 00333 void 00334 basic_string<_CharT, _Traits, _Alloc>:: 00335 _M_erase(size_type __pos, size_type __n) 00336 { 00337 const size_type __how_much = length() - __pos - __n; 00338 00339 if (__how_much && __n) 00340 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 00341 00342 _M_set_length(length() - __n); 00343 } 00344 00345 template<typename _CharT, typename _Traits, typename _Alloc> 00346 void 00347 basic_string<_CharT, _Traits, _Alloc>:: 00348 resize(size_type __n, _CharT __c) 00349 { 00350 const size_type __size = this->size(); 00351 if (__size < __n) 00352 this->append(__n - __size, __c); 00353 else if (__n < __size) 00354 this->_M_set_length(__n); 00355 } 00356 00357 template<typename _CharT, typename _Traits, typename _Alloc> 00358 basic_string<_CharT, _Traits, _Alloc>& 00359 basic_string<_CharT, _Traits, _Alloc>:: 00360 _M_append(const _CharT* __s, size_type __n) 00361 { 00362 const size_type __len = __n + this->size(); 00363 00364 if (__len <= this->capacity()) 00365 { 00366 if (__n) 00367 this->_S_copy(this->_M_data() + this->size(), __s, __n); 00368 } 00369 else 00370 this->_M_mutate(this->size(), size_type(0), __s, __n); 00371 00372 this->_M_set_length(__len); 00373 return *this; 00374 } 00375 00376 template<typename _CharT, typename _Traits, typename _Alloc> 00377 template<typename _InputIterator> 00378 basic_string<_CharT, _Traits, _Alloc>& 00379 basic_string<_CharT, _Traits, _Alloc>:: 00380 _M_replace_dispatch(const_iterator __i1, const_iterator __i2, 00381 _InputIterator __k1, _InputIterator __k2, 00382 std::__false_type) 00383 { 00384 const basic_string __s(__k1, __k2); 00385 const size_type __n1 = __i2 - __i1; 00386 return _M_replace(__i1 - begin(), __n1, __s._M_data(), 00387 __s.size()); 00388 } 00389 00390 template<typename _CharT, typename _Traits, typename _Alloc> 00391 basic_string<_CharT, _Traits, _Alloc>& 00392 basic_string<_CharT, _Traits, _Alloc>:: 00393 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 00394 _CharT __c) 00395 { 00396 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 00397 00398 const size_type __old_size = this->size(); 00399 const size_type __new_size = __old_size + __n2 - __n1; 00400 00401 if (__new_size <= this->capacity()) 00402 { 00403 pointer __p = this->_M_data() + __pos1; 00404 00405 const size_type __how_much = __old_size - __pos1 - __n1; 00406 if (__how_much && __n1 != __n2) 00407 this->_S_move(__p + __n2, __p + __n1, __how_much); 00408 } 00409 else 00410 this->_M_mutate(__pos1, __n1, 0, __n2); 00411 00412 if (__n2) 00413 this->_S_assign(this->_M_data() + __pos1, __n2, __c); 00414 00415 this->_M_set_length(__new_size); 00416 return *this; 00417 } 00418 00419 template<typename _CharT, typename _Traits, typename _Alloc> 00420 basic_string<_CharT, _Traits, _Alloc>& 00421 basic_string<_CharT, _Traits, _Alloc>:: 00422 _M_replace(size_type __pos, size_type __len1, const _CharT* __s, 00423 const size_type __len2) 00424 { 00425 _M_check_length(__len1, __len2, "basic_string::_M_replace"); 00426 00427 const size_type __old_size = this->size(); 00428 const size_type __new_size = __old_size + __len2 - __len1; 00429 00430 if (__new_size <= this->capacity()) 00431 { 00432 pointer __p = this->_M_data() + __pos; 00433 00434 const size_type __how_much = __old_size - __pos - __len1; 00435 if (_M_disjunct(__s)) 00436 { 00437 if (__how_much && __len1 != __len2) 00438 this->_S_move(__p + __len2, __p + __len1, __how_much); 00439 if (__len2) 00440 this->_S_copy(__p, __s, __len2); 00441 } 00442 else 00443 { 00444 // Work in-place. 00445 if (__len2 && __len2 <= __len1) 00446 this->_S_move(__p, __s, __len2); 00447 if (__how_much && __len1 != __len2) 00448 this->_S_move(__p + __len2, __p + __len1, __how_much); 00449 if (__len2 > __len1) 00450 { 00451 if (__s + __len2 <= __p + __len1) 00452 this->_S_move(__p, __s, __len2); 00453 else if (__s >= __p + __len1) 00454 this->_S_copy(__p, __s + __len2 - __len1, __len2); 00455 else 00456 { 00457 const size_type __nleft = (__p + __len1) - __s; 00458 this->_S_move(__p, __s, __nleft); 00459 this->_S_copy(__p + __nleft, __p + __len2, 00460 __len2 - __nleft); 00461 } 00462 } 00463 } 00464 } 00465 else 00466 this->_M_mutate(__pos, __len1, __s, __len2); 00467 00468 this->_M_set_length(__new_size); 00469 return *this; 00470 } 00471 00472 template<typename _CharT, typename _Traits, typename _Alloc> 00473 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00474 basic_string<_CharT, _Traits, _Alloc>:: 00475 copy(_CharT* __s, size_type __n, size_type __pos) const 00476 { 00477 _M_check(__pos, "basic_string::copy"); 00478 __n = _M_limit(__pos, __n); 00479 __glibcxx_requires_string_len(__s, __n); 00480 if (__n) 00481 _S_copy(__s, _M_data() + __pos, __n); 00482 // 21.3.5.7 par 3: do not append null. (good.) 00483 return __n; 00484 } 00485 00486 #else // !_GLIBCXX_USE_CXX11_ABI 00487 00488 template<typename _CharT, typename _Traits, typename _Alloc> 00489 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00490 basic_string<_CharT, _Traits, _Alloc>:: 00491 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 00492 00493 template<typename _CharT, typename _Traits, typename _Alloc> 00494 const _CharT 00495 basic_string<_CharT, _Traits, _Alloc>:: 00496 _Rep::_S_terminal = _CharT(); 00497 00498 template<typename _CharT, typename _Traits, typename _Alloc> 00499 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00500 basic_string<_CharT, _Traits, _Alloc>::npos; 00501 00502 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 00503 // at static init time (before static ctors are run). 00504 template<typename _CharT, typename _Traits, typename _Alloc> 00505 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00506 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 00507 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 00508 sizeof(size_type)]; 00509 00510 // NB: This is the special case for Input Iterators, used in 00511 // istreambuf_iterators, etc. 00512 // Input Iterators have a cost structure very different from 00513 // pointers, calling for a different coding style. 00514 template<typename _CharT, typename _Traits, typename _Alloc> 00515 template<typename _InIterator> 00516 _CharT* 00517 basic_string<_CharT, _Traits, _Alloc>:: 00518 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00519 input_iterator_tag) 00520 { 00521 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00522 if (__beg == __end && __a == _Alloc()) 00523 return _S_empty_rep()._M_refdata(); 00524 #endif 00525 // Avoid reallocation for common case. 00526 _CharT __buf[128]; 00527 size_type __len = 0; 00528 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 00529 { 00530 __buf[__len++] = *__beg; 00531 ++__beg; 00532 } 00533 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 00534 _M_copy(__r->_M_refdata(), __buf, __len); 00535 __try 00536 { 00537 while (__beg != __end) 00538 { 00539 if (__len == __r->_M_capacity) 00540 { 00541 // Allocate more space. 00542 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 00543 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 00544 __r->_M_destroy(__a); 00545 __r = __another; 00546 } 00547 __r->_M_refdata()[__len++] = *__beg; 00548 ++__beg; 00549 } 00550 } 00551 __catch(...) 00552 { 00553 __r->_M_destroy(__a); 00554 __throw_exception_again; 00555 } 00556 __r->_M_set_length_and_sharable(__len); 00557 return __r->_M_refdata(); 00558 } 00559 00560 template<typename _CharT, typename _Traits, typename _Alloc> 00561 template <typename _InIterator> 00562 _CharT* 00563 basic_string<_CharT, _Traits, _Alloc>:: 00564 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00565 forward_iterator_tag) 00566 { 00567 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00568 if (__beg == __end && __a == _Alloc()) 00569 return _S_empty_rep()._M_refdata(); 00570 #endif 00571 // NB: Not required, but considered best practice. 00572 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 00573 __throw_logic_error(__N("basic_string::_S_construct null not valid")); 00574 00575 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 00576 __end)); 00577 // Check for out_of_range and length_error exceptions. 00578 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 00579 __try 00580 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 00581 __catch(...) 00582 { 00583 __r->_M_destroy(__a); 00584 __throw_exception_again; 00585 } 00586 __r->_M_set_length_and_sharable(__dnew); 00587 return __r->_M_refdata(); 00588 } 00589 00590 template<typename _CharT, typename _Traits, typename _Alloc> 00591 _CharT* 00592 basic_string<_CharT, _Traits, _Alloc>:: 00593 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 00594 { 00595 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00596 if (__n == 0 && __a == _Alloc()) 00597 return _S_empty_rep()._M_refdata(); 00598 #endif 00599 // Check for out_of_range and length_error exceptions. 00600 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 00601 if (__n) 00602 _M_assign(__r->_M_refdata(), __n, __c); 00603 00604 __r->_M_set_length_and_sharable(__n); 00605 return __r->_M_refdata(); 00606 } 00607 00608 template<typename _CharT, typename _Traits, typename _Alloc> 00609 basic_string<_CharT, _Traits, _Alloc>:: 00610 basic_string(const basic_string& __str) 00611 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 00612 __str.get_allocator()), 00613 __str.get_allocator()) 00614 { } 00615 00616 template<typename _CharT, typename _Traits, typename _Alloc> 00617 basic_string<_CharT, _Traits, _Alloc>:: 00618 basic_string(const _Alloc& __a) 00619 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 00620 { } 00621 00622 template<typename _CharT, typename _Traits, typename _Alloc> 00623 basic_string<_CharT, _Traits, _Alloc>:: 00624 basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a) 00625 : _M_dataplus(_S_construct(__str._M_data() 00626 + __str._M_check(__pos, 00627 "basic_string::basic_string"), 00628 __str._M_data() + __str._M_limit(__pos, npos) 00629 + __pos, __a), __a) 00630 { } 00631 00632 template<typename _CharT, typename _Traits, typename _Alloc> 00633 basic_string<_CharT, _Traits, _Alloc>:: 00634 basic_string(const basic_string& __str, size_type __pos, size_type __n) 00635 : _M_dataplus(_S_construct(__str._M_data() 00636 + __str._M_check(__pos, 00637 "basic_string::basic_string"), 00638 __str._M_data() + __str._M_limit(__pos, __n) 00639 + __pos, _Alloc()), _Alloc()) 00640 { } 00641 00642 template<typename _CharT, typename _Traits, typename _Alloc> 00643 basic_string<_CharT, _Traits, _Alloc>:: 00644 basic_string(const basic_string& __str, size_type __pos, 00645 size_type __n, const _Alloc& __a) 00646 : _M_dataplus(_S_construct(__str._M_data() 00647 + __str._M_check(__pos, 00648 "basic_string::basic_string"), 00649 __str._M_data() + __str._M_limit(__pos, __n) 00650 + __pos, __a), __a) 00651 { } 00652 00653 // TBD: DPG annotate 00654 template<typename _CharT, typename _Traits, typename _Alloc> 00655 basic_string<_CharT, _Traits, _Alloc>:: 00656 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00657 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00658 { } 00659 00660 // TBD: DPG annotate 00661 template<typename _CharT, typename _Traits, typename _Alloc> 00662 basic_string<_CharT, _Traits, _Alloc>:: 00663 basic_string(const _CharT* __s, const _Alloc& __a) 00664 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00665 __s + npos, __a), __a) 00666 { } 00667 00668 template<typename _CharT, typename _Traits, typename _Alloc> 00669 basic_string<_CharT, _Traits, _Alloc>:: 00670 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00671 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00672 { } 00673 00674 // TBD: DPG annotate 00675 template<typename _CharT, typename _Traits, typename _Alloc> 00676 template<typename _InputIterator> 00677 basic_string<_CharT, _Traits, _Alloc>:: 00678 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 00679 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00680 { } 00681 00682 #if __cplusplus >= 201103L 00683 template<typename _CharT, typename _Traits, typename _Alloc> 00684 basic_string<_CharT, _Traits, _Alloc>:: 00685 basic_string(initializer_list<_CharT> __l, const _Alloc& __a) 00686 : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a) 00687 { } 00688 #endif 00689 00690 template<typename _CharT, typename _Traits, typename _Alloc> 00691 basic_string<_CharT, _Traits, _Alloc>& 00692 basic_string<_CharT, _Traits, _Alloc>:: 00693 assign(const basic_string& __str) 00694 { 00695 if (_M_rep() != __str._M_rep()) 00696 { 00697 // XXX MT 00698 const allocator_type __a = this->get_allocator(); 00699 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00700 _M_rep()->_M_dispose(__a); 00701 _M_data(__tmp); 00702 } 00703 return *this; 00704 } 00705 00706 template<typename _CharT, typename _Traits, typename _Alloc> 00707 basic_string<_CharT, _Traits, _Alloc>& 00708 basic_string<_CharT, _Traits, _Alloc>:: 00709 assign(const _CharT* __s, size_type __n) 00710 { 00711 __glibcxx_requires_string_len(__s, __n); 00712 _M_check_length(this->size(), __n, "basic_string::assign"); 00713 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00714 return _M_replace_safe(size_type(0), this->size(), __s, __n); 00715 else 00716 { 00717 // Work in-place. 00718 const size_type __pos = __s - _M_data(); 00719 if (__pos >= __n) 00720 _M_copy(_M_data(), __s, __n); 00721 else if (__pos) 00722 _M_move(_M_data(), __s, __n); 00723 _M_rep()->_M_set_length_and_sharable(__n); 00724 return *this; 00725 } 00726 } 00727 00728 template<typename _CharT, typename _Traits, typename _Alloc> 00729 basic_string<_CharT, _Traits, _Alloc>& 00730 basic_string<_CharT, _Traits, _Alloc>:: 00731 append(size_type __n, _CharT __c) 00732 { 00733 if (__n) 00734 { 00735 _M_check_length(size_type(0), __n, "basic_string::append"); 00736 const size_type __len = __n + this->size(); 00737 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00738 this->reserve(__len); 00739 _M_assign(_M_data() + this->size(), __n, __c); 00740 _M_rep()->_M_set_length_and_sharable(__len); 00741 } 00742 return *this; 00743 } 00744 00745 template<typename _CharT, typename _Traits, typename _Alloc> 00746 basic_string<_CharT, _Traits, _Alloc>& 00747 basic_string<_CharT, _Traits, _Alloc>:: 00748 append(const _CharT* __s, size_type __n) 00749 { 00750 __glibcxx_requires_string_len(__s, __n); 00751 if (__n) 00752 { 00753 _M_check_length(size_type(0), __n, "basic_string::append"); 00754 const size_type __len = __n + this->size(); 00755 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00756 { 00757 if (_M_disjunct(__s)) 00758 this->reserve(__len); 00759 else 00760 { 00761 const size_type __off = __s - _M_data(); 00762 this->reserve(__len); 00763 __s = _M_data() + __off; 00764 } 00765 } 00766 _M_copy(_M_data() + this->size(), __s, __n); 00767 _M_rep()->_M_set_length_and_sharable(__len); 00768 } 00769 return *this; 00770 } 00771 00772 template<typename _CharT, typename _Traits, typename _Alloc> 00773 basic_string<_CharT, _Traits, _Alloc>& 00774 basic_string<_CharT, _Traits, _Alloc>:: 00775 append(const basic_string& __str) 00776 { 00777 const size_type __size = __str.size(); 00778 if (__size) 00779 { 00780 const size_type __len = __size + this->size(); 00781 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00782 this->reserve(__len); 00783 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 00784 _M_rep()->_M_set_length_and_sharable(__len); 00785 } 00786 return *this; 00787 } 00788 00789 template<typename _CharT, typename _Traits, typename _Alloc> 00790 basic_string<_CharT, _Traits, _Alloc>& 00791 basic_string<_CharT, _Traits, _Alloc>:: 00792 append(const basic_string& __str, size_type __pos, size_type __n) 00793 { 00794 __str._M_check(__pos, "basic_string::append"); 00795 __n = __str._M_limit(__pos, __n); 00796 if (__n) 00797 { 00798 const size_type __len = __n + this->size(); 00799 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00800 this->reserve(__len); 00801 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 00802 _M_rep()->_M_set_length_and_sharable(__len); 00803 } 00804 return *this; 00805 } 00806 00807 template<typename _CharT, typename _Traits, typename _Alloc> 00808 basic_string<_CharT, _Traits, _Alloc>& 00809 basic_string<_CharT, _Traits, _Alloc>:: 00810 insert(size_type __pos, const _CharT* __s, size_type __n) 00811 { 00812 __glibcxx_requires_string_len(__s, __n); 00813 _M_check(__pos, "basic_string::insert"); 00814 _M_check_length(size_type(0), __n, "basic_string::insert"); 00815 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00816 return _M_replace_safe(__pos, size_type(0), __s, __n); 00817 else 00818 { 00819 // Work in-place. 00820 const size_type __off = __s - _M_data(); 00821 _M_mutate(__pos, 0, __n); 00822 __s = _M_data() + __off; 00823 _CharT* __p = _M_data() + __pos; 00824 if (__s + __n <= __p) 00825 _M_copy(__p, __s, __n); 00826 else if (__s >= __p) 00827 _M_copy(__p, __s + __n, __n); 00828 else 00829 { 00830 const size_type __nleft = __p - __s; 00831 _M_copy(__p, __s, __nleft); 00832 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 00833 } 00834 return *this; 00835 } 00836 } 00837 00838 template<typename _CharT, typename _Traits, typename _Alloc> 00839 typename basic_string<_CharT, _Traits, _Alloc>::iterator 00840 basic_string<_CharT, _Traits, _Alloc>:: 00841 erase(iterator __first, iterator __last) 00842 { 00843 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 00844 && __last <= _M_iend()); 00845 00846 // NB: This isn't just an optimization (bail out early when 00847 // there is nothing to do, really), it's also a correctness 00848 // issue vs MT, see libstdc++/40518. 00849 const size_type __size = __last - __first; 00850 if (__size) 00851 { 00852 const size_type __pos = __first - _M_ibegin(); 00853 _M_mutate(__pos, __size, size_type(0)); 00854 _M_rep()->_M_set_leaked(); 00855 return iterator(_M_data() + __pos); 00856 } 00857 else 00858 return __first; 00859 } 00860 00861 template<typename _CharT, typename _Traits, typename _Alloc> 00862 basic_string<_CharT, _Traits, _Alloc>& 00863 basic_string<_CharT, _Traits, _Alloc>:: 00864 replace(size_type __pos, size_type __n1, const _CharT* __s, 00865 size_type __n2) 00866 { 00867 __glibcxx_requires_string_len(__s, __n2); 00868 _M_check(__pos, "basic_string::replace"); 00869 __n1 = _M_limit(__pos, __n1); 00870 _M_check_length(__n1, __n2, "basic_string::replace"); 00871 bool __left; 00872 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00873 return _M_replace_safe(__pos, __n1, __s, __n2); 00874 else if ((__left = __s + __n2 <= _M_data() + __pos) 00875 || _M_data() + __pos + __n1 <= __s) 00876 { 00877 // Work in-place: non-overlapping case. 00878 size_type __off = __s - _M_data(); 00879 __left ? __off : (__off += __n2 - __n1); 00880 _M_mutate(__pos, __n1, __n2); 00881 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 00882 return *this; 00883 } 00884 else 00885 { 00886 // Todo: overlapping case. 00887 const basic_string __tmp(__s, __n2); 00888 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 00889 } 00890 } 00891 00892 template<typename _CharT, typename _Traits, typename _Alloc> 00893 void 00894 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00895 _M_destroy(const _Alloc& __a) throw () 00896 { 00897 const size_type __size = sizeof(_Rep_base) + 00898 (this->_M_capacity + 1) * sizeof(_CharT); 00899 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00900 } 00901 00902 template<typename _CharT, typename _Traits, typename _Alloc> 00903 void 00904 basic_string<_CharT, _Traits, _Alloc>:: 00905 _M_leak_hard() 00906 { 00907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00908 if (_M_rep() == &_S_empty_rep()) 00909 return; 00910 #endif 00911 if (_M_rep()->_M_is_shared()) 00912 _M_mutate(0, 0, 0); 00913 _M_rep()->_M_set_leaked(); 00914 } 00915 00916 template<typename _CharT, typename _Traits, typename _Alloc> 00917 void 00918 basic_string<_CharT, _Traits, _Alloc>:: 00919 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00920 { 00921 const size_type __old_size = this->size(); 00922 const size_type __new_size = __old_size + __len2 - __len1; 00923 const size_type __how_much = __old_size - __pos - __len1; 00924 00925 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 00926 { 00927 // Must reallocate. 00928 const allocator_type __a = get_allocator(); 00929 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 00930 00931 if (__pos) 00932 _M_copy(__r->_M_refdata(), _M_data(), __pos); 00933 if (__how_much) 00934 _M_copy(__r->_M_refdata() + __pos + __len2, 00935 _M_data() + __pos + __len1, __how_much); 00936 00937 _M_rep()->_M_dispose(__a); 00938 _M_data(__r->_M_refdata()); 00939 } 00940 else if (__how_much && __len1 != __len2) 00941 { 00942 // Work in-place. 00943 _M_move(_M_data() + __pos + __len2, 00944 _M_data() + __pos + __len1, __how_much); 00945 } 00946 _M_rep()->_M_set_length_and_sharable(__new_size); 00947 } 00948 00949 template<typename _CharT, typename _Traits, typename _Alloc> 00950 void 00951 basic_string<_CharT, _Traits, _Alloc>:: 00952 reserve(size_type __res) 00953 { 00954 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 00955 { 00956 // Make sure we don't shrink below the current size 00957 if (__res < this->size()) 00958 __res = this->size(); 00959 const allocator_type __a = get_allocator(); 00960 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00961 _M_rep()->_M_dispose(__a); 00962 _M_data(__tmp); 00963 } 00964 } 00965 00966 template<typename _CharT, typename _Traits, typename _Alloc> 00967 void 00968 basic_string<_CharT, _Traits, _Alloc>:: 00969 swap(basic_string& __s) 00970 _GLIBCXX_NOEXCEPT_IF(allocator_traits<_Alloc>::is_always_equal::value) 00971 { 00972 if (_M_rep()->_M_is_leaked()) 00973 _M_rep()->_M_set_sharable(); 00974 if (__s._M_rep()->_M_is_leaked()) 00975 __s._M_rep()->_M_set_sharable(); 00976 if (this->get_allocator() == __s.get_allocator()) 00977 { 00978 _CharT* __tmp = _M_data(); 00979 _M_data(__s._M_data()); 00980 __s._M_data(__tmp); 00981 } 00982 // The code below can usually be optimized away. 00983 else 00984 { 00985 const basic_string __tmp1(_M_ibegin(), _M_iend(), 00986 __s.get_allocator()); 00987 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00988 this->get_allocator()); 00989 *this = __tmp2; 00990 __s = __tmp1; 00991 } 00992 } 00993 00994 template<typename _CharT, typename _Traits, typename _Alloc> 00995 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00996 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00997 _S_create(size_type __capacity, size_type __old_capacity, 00998 const _Alloc& __alloc) 00999 { 01000 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01001 // 83. String::npos vs. string::max_size() 01002 if (__capacity > _S_max_size) 01003 __throw_length_error(__N("basic_string::_S_create")); 01004 01005 // The standard places no restriction on allocating more memory 01006 // than is strictly needed within this layer at the moment or as 01007 // requested by an explicit application call to reserve(). 01008 01009 // Many malloc implementations perform quite poorly when an 01010 // application attempts to allocate memory in a stepwise fashion 01011 // growing each allocation size by only 1 char. Additionally, 01012 // it makes little sense to allocate less linear memory than the 01013 // natural blocking size of the malloc implementation. 01014 // Unfortunately, we would need a somewhat low-level calculation 01015 // with tuned parameters to get this perfect for any particular 01016 // malloc implementation. Fortunately, generalizations about 01017 // common features seen among implementations seems to suffice. 01018 01019 // __pagesize need not match the actual VM page size for good 01020 // results in practice, thus we pick a common value on the low 01021 // side. __malloc_header_size is an estimate of the amount of 01022 // overhead per memory allocation (in practice seen N * sizeof 01023 // (void*) where N is 0, 2 or 4). According to folklore, 01024 // picking this value on the high side is better than 01025 // low-balling it (especially when this algorithm is used with 01026 // malloc implementations that allocate memory blocks rounded up 01027 // to a size which is a power of 2). 01028 const size_type __pagesize = 4096; 01029 const size_type __malloc_header_size = 4 * sizeof(void*); 01030 01031 // The below implements an exponential growth policy, necessary to 01032 // meet amortized linear time requirements of the library: see 01033 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 01034 // It's active for allocations requiring an amount of memory above 01035 // system pagesize. This is consistent with the requirements of the 01036 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 01037 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 01038 __capacity = 2 * __old_capacity; 01039 01040 // NB: Need an array of char_type[__capacity], plus a terminating 01041 // null char_type() element, plus enough for the _Rep data structure. 01042 // Whew. Seemingly so needy, yet so elemental. 01043 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01044 01045 const size_type __adj_size = __size + __malloc_header_size; 01046 if (__adj_size > __pagesize && __capacity > __old_capacity) 01047 { 01048 const size_type __extra = __pagesize - __adj_size % __pagesize; 01049 __capacity += __extra / sizeof(_CharT); 01050 // Never allocate a string bigger than _S_max_size. 01051 if (__capacity > _S_max_size) 01052 __capacity = _S_max_size; 01053 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01054 } 01055 01056 // NB: Might throw, but no worries about a leak, mate: _Rep() 01057 // does not throw. 01058 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 01059 _Rep *__p = new (__place) _Rep; 01060 __p->_M_capacity = __capacity; 01061 // ABI compatibility - 3.4.x set in _S_create both 01062 // _M_refcount and _M_length. All callers of _S_create 01063 // in basic_string.tcc then set just _M_length. 01064 // In 4.0.x and later both _M_refcount and _M_length 01065 // are initialized in the callers, unfortunately we can 01066 // have 3.4.x compiled code with _S_create callers inlined 01067 // calling 4.0.x+ _S_create. 01068 __p->_M_set_sharable(); 01069 return __p; 01070 } 01071 01072 template<typename _CharT, typename _Traits, typename _Alloc> 01073 _CharT* 01074 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 01075 _M_clone(const _Alloc& __alloc, size_type __res) 01076 { 01077 // Requested capacity of the clone. 01078 const size_type __requested_cap = this->_M_length + __res; 01079 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 01080 __alloc); 01081 if (this->_M_length) 01082 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 01083 01084 __r->_M_set_length_and_sharable(this->_M_length); 01085 return __r->_M_refdata(); 01086 } 01087 01088 template<typename _CharT, typename _Traits, typename _Alloc> 01089 void 01090 basic_string<_CharT, _Traits, _Alloc>:: 01091 resize(size_type __n, _CharT __c) 01092 { 01093 const size_type __size = this->size(); 01094 _M_check_length(__size, __n, "basic_string::resize"); 01095 if (__size < __n) 01096 this->append(__n - __size, __c); 01097 else if (__n < __size) 01098 this->erase(__n); 01099 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 01100 } 01101 01102 template<typename _CharT, typename _Traits, typename _Alloc> 01103 template<typename _InputIterator> 01104 basic_string<_CharT, _Traits, _Alloc>& 01105 basic_string<_CharT, _Traits, _Alloc>:: 01106 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 01107 _InputIterator __k2, __false_type) 01108 { 01109 const basic_string __s(__k1, __k2); 01110 const size_type __n1 = __i2 - __i1; 01111 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 01112 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 01113 __s.size()); 01114 } 01115 01116 template<typename _CharT, typename _Traits, typename _Alloc> 01117 basic_string<_CharT, _Traits, _Alloc>& 01118 basic_string<_CharT, _Traits, _Alloc>:: 01119 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 01120 _CharT __c) 01121 { 01122 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 01123 _M_mutate(__pos1, __n1, __n2); 01124 if (__n2) 01125 _M_assign(_M_data() + __pos1, __n2, __c); 01126 return *this; 01127 } 01128 01129 template<typename _CharT, typename _Traits, typename _Alloc> 01130 basic_string<_CharT, _Traits, _Alloc>& 01131 basic_string<_CharT, _Traits, _Alloc>:: 01132 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 01133 size_type __n2) 01134 { 01135 _M_mutate(__pos1, __n1, __n2); 01136 if (__n2) 01137 _M_copy(_M_data() + __pos1, __s, __n2); 01138 return *this; 01139 } 01140 01141 template<typename _CharT, typename _Traits, typename _Alloc> 01142 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01143 basic_string<_CharT, _Traits, _Alloc>:: 01144 copy(_CharT* __s, size_type __n, size_type __pos) const 01145 { 01146 _M_check(__pos, "basic_string::copy"); 01147 __n = _M_limit(__pos, __n); 01148 __glibcxx_requires_string_len(__s, __n); 01149 if (__n) 01150 _M_copy(__s, _M_data() + __pos, __n); 01151 // 21.3.5.7 par 3: do not append null. (good.) 01152 return __n; 01153 } 01154 #endif // !_GLIBCXX_USE_CXX11_ABI 01155 01156 template<typename _CharT, typename _Traits, typename _Alloc> 01157 basic_string<_CharT, _Traits, _Alloc> 01158 operator+(const _CharT* __lhs, 01159 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01160 { 01161 __glibcxx_requires_string(__lhs); 01162 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01163 typedef typename __string_type::size_type __size_type; 01164 const __size_type __len = _Traits::length(__lhs); 01165 __string_type __str; 01166 __str.reserve(__len + __rhs.size()); 01167 __str.append(__lhs, __len); 01168 __str.append(__rhs); 01169 return __str; 01170 } 01171 01172 template<typename _CharT, typename _Traits, typename _Alloc> 01173 basic_string<_CharT, _Traits, _Alloc> 01174 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01175 { 01176 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01177 typedef typename __string_type::size_type __size_type; 01178 __string_type __str; 01179 const __size_type __len = __rhs.size(); 01180 __str.reserve(__len + 1); 01181 __str.append(__size_type(1), __lhs); 01182 __str.append(__rhs); 01183 return __str; 01184 } 01185 01186 template<typename _CharT, typename _Traits, typename _Alloc> 01187 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01188 basic_string<_CharT, _Traits, _Alloc>:: 01189 find(const _CharT* __s, size_type __pos, size_type __n) const 01190 _GLIBCXX_NOEXCEPT 01191 { 01192 __glibcxx_requires_string_len(__s, __n); 01193 const size_type __size = this->size(); 01194 01195 if (__n == 0) 01196 return __pos <= __size ? __pos : npos; 01197 if (__pos >= __size) 01198 return npos; 01199 01200 const _CharT __elem0 = __s[0]; 01201 const _CharT* const __data = data(); 01202 const _CharT* __first = __data + __pos; 01203 const _CharT* const __last = __data + __size; 01204 size_type __len = __size - __pos; 01205 01206 while (__len >= __n) 01207 { 01208 // Find the first occurrence of __elem0: 01209 __first = traits_type::find(__first, __len - __n + 1, __elem0); 01210 if (!__first) 01211 return npos; 01212 // Compare the full strings from the first occurrence of __elem0. 01213 // We already know that __first[0] == __s[0] but compare them again 01214 // anyway because __s is probably aligned, which helps memcmp. 01215 if (traits_type::compare(__first, __s, __n) == 0) 01216 return __first - __data; 01217 __len = __last - ++__first; 01218 } 01219 return npos; 01220 } 01221 01222 template<typename _CharT, typename _Traits, typename _Alloc> 01223 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01224 basic_string<_CharT, _Traits, _Alloc>:: 01225 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01226 { 01227 size_type __ret = npos; 01228 const size_type __size = this->size(); 01229 if (__pos < __size) 01230 { 01231 const _CharT* __data = _M_data(); 01232 const size_type __n = __size - __pos; 01233 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 01234 if (__p) 01235 __ret = __p - __data; 01236 } 01237 return __ret; 01238 } 01239 01240 template<typename _CharT, typename _Traits, typename _Alloc> 01241 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01242 basic_string<_CharT, _Traits, _Alloc>:: 01243 rfind(const _CharT* __s, size_type __pos, size_type __n) const 01244 _GLIBCXX_NOEXCEPT 01245 { 01246 __glibcxx_requires_string_len(__s, __n); 01247 const size_type __size = this->size(); 01248 if (__n <= __size) 01249 { 01250 __pos = std::min(size_type(__size - __n), __pos); 01251 const _CharT* __data = _M_data(); 01252 do 01253 { 01254 if (traits_type::compare(__data + __pos, __s, __n) == 0) 01255 return __pos; 01256 } 01257 while (__pos-- > 0); 01258 } 01259 return npos; 01260 } 01261 01262 template<typename _CharT, typename _Traits, typename _Alloc> 01263 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01264 basic_string<_CharT, _Traits, _Alloc>:: 01265 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01266 { 01267 size_type __size = this->size(); 01268 if (__size) 01269 { 01270 if (--__size > __pos) 01271 __size = __pos; 01272 for (++__size; __size-- > 0; ) 01273 if (traits_type::eq(_M_data()[__size], __c)) 01274 return __size; 01275 } 01276 return npos; 01277 } 01278 01279 template<typename _CharT, typename _Traits, typename _Alloc> 01280 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01281 basic_string<_CharT, _Traits, _Alloc>:: 01282 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 01283 _GLIBCXX_NOEXCEPT 01284 { 01285 __glibcxx_requires_string_len(__s, __n); 01286 for (; __n && __pos < this->size(); ++__pos) 01287 { 01288 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 01289 if (__p) 01290 return __pos; 01291 } 01292 return npos; 01293 } 01294 01295 template<typename _CharT, typename _Traits, typename _Alloc> 01296 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01297 basic_string<_CharT, _Traits, _Alloc>:: 01298 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 01299 _GLIBCXX_NOEXCEPT 01300 { 01301 __glibcxx_requires_string_len(__s, __n); 01302 size_type __size = this->size(); 01303 if (__size && __n) 01304 { 01305 if (--__size > __pos) 01306 __size = __pos; 01307 do 01308 { 01309 if (traits_type::find(__s, __n, _M_data()[__size])) 01310 return __size; 01311 } 01312 while (__size-- != 0); 01313 } 01314 return npos; 01315 } 01316 01317 template<typename _CharT, typename _Traits, typename _Alloc> 01318 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01319 basic_string<_CharT, _Traits, _Alloc>:: 01320 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01321 _GLIBCXX_NOEXCEPT 01322 { 01323 __glibcxx_requires_string_len(__s, __n); 01324 for (; __pos < this->size(); ++__pos) 01325 if (!traits_type::find(__s, __n, _M_data()[__pos])) 01326 return __pos; 01327 return npos; 01328 } 01329 01330 template<typename _CharT, typename _Traits, typename _Alloc> 01331 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01332 basic_string<_CharT, _Traits, _Alloc>:: 01333 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01334 { 01335 for (; __pos < this->size(); ++__pos) 01336 if (!traits_type::eq(_M_data()[__pos], __c)) 01337 return __pos; 01338 return npos; 01339 } 01340 01341 template<typename _CharT, typename _Traits, typename _Alloc> 01342 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01343 basic_string<_CharT, _Traits, _Alloc>:: 01344 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01345 _GLIBCXX_NOEXCEPT 01346 { 01347 __glibcxx_requires_string_len(__s, __n); 01348 size_type __size = this->size(); 01349 if (__size) 01350 { 01351 if (--__size > __pos) 01352 __size = __pos; 01353 do 01354 { 01355 if (!traits_type::find(__s, __n, _M_data()[__size])) 01356 return __size; 01357 } 01358 while (__size--); 01359 } 01360 return npos; 01361 } 01362 01363 template<typename _CharT, typename _Traits, typename _Alloc> 01364 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01365 basic_string<_CharT, _Traits, _Alloc>:: 01366 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01367 { 01368 size_type __size = this->size(); 01369 if (__size) 01370 { 01371 if (--__size > __pos) 01372 __size = __pos; 01373 do 01374 { 01375 if (!traits_type::eq(_M_data()[__size], __c)) 01376 return __size; 01377 } 01378 while (__size--); 01379 } 01380 return npos; 01381 } 01382 01383 template<typename _CharT, typename _Traits, typename _Alloc> 01384 int 01385 basic_string<_CharT, _Traits, _Alloc>:: 01386 compare(size_type __pos, size_type __n, const basic_string& __str) const 01387 { 01388 _M_check(__pos, "basic_string::compare"); 01389 __n = _M_limit(__pos, __n); 01390 const size_type __osize = __str.size(); 01391 const size_type __len = std::min(__n, __osize); 01392 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 01393 if (!__r) 01394 __r = _S_compare(__n, __osize); 01395 return __r; 01396 } 01397 01398 template<typename _CharT, typename _Traits, typename _Alloc> 01399 int 01400 basic_string<_CharT, _Traits, _Alloc>:: 01401 compare(size_type __pos1, size_type __n1, const basic_string& __str, 01402 size_type __pos2, size_type __n2) const 01403 { 01404 _M_check(__pos1, "basic_string::compare"); 01405 __str._M_check(__pos2, "basic_string::compare"); 01406 __n1 = _M_limit(__pos1, __n1); 01407 __n2 = __str._M_limit(__pos2, __n2); 01408 const size_type __len = std::min(__n1, __n2); 01409 int __r = traits_type::compare(_M_data() + __pos1, 01410 __str.data() + __pos2, __len); 01411 if (!__r) 01412 __r = _S_compare(__n1, __n2); 01413 return __r; 01414 } 01415 01416 template<typename _CharT, typename _Traits, typename _Alloc> 01417 int 01418 basic_string<_CharT, _Traits, _Alloc>:: 01419 compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT 01420 { 01421 __glibcxx_requires_string(__s); 01422 const size_type __size = this->size(); 01423 const size_type __osize = traits_type::length(__s); 01424 const size_type __len = std::min(__size, __osize); 01425 int __r = traits_type::compare(_M_data(), __s, __len); 01426 if (!__r) 01427 __r = _S_compare(__size, __osize); 01428 return __r; 01429 } 01430 01431 template<typename _CharT, typename _Traits, typename _Alloc> 01432 int 01433 basic_string <_CharT, _Traits, _Alloc>:: 01434 compare(size_type __pos, size_type __n1, const _CharT* __s) const 01435 { 01436 __glibcxx_requires_string(__s); 01437 _M_check(__pos, "basic_string::compare"); 01438 __n1 = _M_limit(__pos, __n1); 01439 const size_type __osize = traits_type::length(__s); 01440 const size_type __len = std::min(__n1, __osize); 01441 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01442 if (!__r) 01443 __r = _S_compare(__n1, __osize); 01444 return __r; 01445 } 01446 01447 template<typename _CharT, typename _Traits, typename _Alloc> 01448 int 01449 basic_string <_CharT, _Traits, _Alloc>:: 01450 compare(size_type __pos, size_type __n1, const _CharT* __s, 01451 size_type __n2) const 01452 { 01453 __glibcxx_requires_string_len(__s, __n2); 01454 _M_check(__pos, "basic_string::compare"); 01455 __n1 = _M_limit(__pos, __n1); 01456 const size_type __len = std::min(__n1, __n2); 01457 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01458 if (!__r) 01459 __r = _S_compare(__n1, __n2); 01460 return __r; 01461 } 01462 01463 // 21.3.7.9 basic_string::getline and operators 01464 template<typename _CharT, typename _Traits, typename _Alloc> 01465 basic_istream<_CharT, _Traits>& 01466 operator>>(basic_istream<_CharT, _Traits>& __in, 01467 basic_string<_CharT, _Traits, _Alloc>& __str) 01468 { 01469 typedef basic_istream<_CharT, _Traits> __istream_type; 01470 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01471 typedef typename __istream_type::ios_base __ios_base; 01472 typedef typename __istream_type::int_type __int_type; 01473 typedef typename __string_type::size_type __size_type; 01474 typedef ctype<_CharT> __ctype_type; 01475 typedef typename __ctype_type::ctype_base __ctype_base; 01476 01477 __size_type __extracted = 0; 01478 typename __ios_base::iostate __err = __ios_base::goodbit; 01479 typename __istream_type::sentry __cerb(__in, false); 01480 if (__cerb) 01481 { 01482 __try 01483 { 01484 // Avoid reallocation for common case. 01485 __str.erase(); 01486 _CharT __buf[128]; 01487 __size_type __len = 0; 01488 const streamsize __w = __in.width(); 01489 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 01490 : __str.max_size(); 01491 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 01492 const __int_type __eof = _Traits::eof(); 01493 __int_type __c = __in.rdbuf()->sgetc(); 01494 01495 while (__extracted < __n 01496 && !_Traits::eq_int_type(__c, __eof) 01497 && !__ct.is(__ctype_base::space, 01498 _Traits::to_char_type(__c))) 01499 { 01500 if (__len == sizeof(__buf) / sizeof(_CharT)) 01501 { 01502 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 01503 __len = 0; 01504 } 01505 __buf[__len++] = _Traits::to_char_type(__c); 01506 ++__extracted; 01507 __c = __in.rdbuf()->snextc(); 01508 } 01509 __str.append(__buf, __len); 01510 01511 if (_Traits::eq_int_type(__c, __eof)) 01512 __err |= __ios_base::eofbit; 01513 __in.width(0); 01514 } 01515 __catch(__cxxabiv1::__forced_unwind&) 01516 { 01517 __in._M_setstate(__ios_base::badbit); 01518 __throw_exception_again; 01519 } 01520 __catch(...) 01521 { 01522 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01523 // 91. Description of operator>> and getline() for string<> 01524 // might cause endless loop 01525 __in._M_setstate(__ios_base::badbit); 01526 } 01527 } 01528 // 211. operator>>(istream&, string&) doesn't set failbit 01529 if (!__extracted) 01530 __err |= __ios_base::failbit; 01531 if (__err) 01532 __in.setstate(__err); 01533 return __in; 01534 } 01535 01536 template<typename _CharT, typename _Traits, typename _Alloc> 01537 basic_istream<_CharT, _Traits>& 01538 getline(basic_istream<_CharT, _Traits>& __in, 01539 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 01540 { 01541 typedef basic_istream<_CharT, _Traits> __istream_type; 01542 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01543 typedef typename __istream_type::ios_base __ios_base; 01544 typedef typename __istream_type::int_type __int_type; 01545 typedef typename __string_type::size_type __size_type; 01546 01547 __size_type __extracted = 0; 01548 const __size_type __n = __str.max_size(); 01549 typename __ios_base::iostate __err = __ios_base::goodbit; 01550 typename __istream_type::sentry __cerb(__in, true); 01551 if (__cerb) 01552 { 01553 __try 01554 { 01555 __str.erase(); 01556 const __int_type __idelim = _Traits::to_int_type(__delim); 01557 const __int_type __eof = _Traits::eof(); 01558 __int_type __c = __in.rdbuf()->sgetc(); 01559 01560 while (__extracted < __n 01561 && !_Traits::eq_int_type(__c, __eof) 01562 && !_Traits::eq_int_type(__c, __idelim)) 01563 { 01564 __str += _Traits::to_char_type(__c); 01565 ++__extracted; 01566 __c = __in.rdbuf()->snextc(); 01567 } 01568 01569 if (_Traits::eq_int_type(__c, __eof)) 01570 __err |= __ios_base::eofbit; 01571 else if (_Traits::eq_int_type(__c, __idelim)) 01572 { 01573 ++__extracted; 01574 __in.rdbuf()->sbumpc(); 01575 } 01576 else 01577 __err |= __ios_base::failbit; 01578 } 01579 __catch(__cxxabiv1::__forced_unwind&) 01580 { 01581 __in._M_setstate(__ios_base::badbit); 01582 __throw_exception_again; 01583 } 01584 __catch(...) 01585 { 01586 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01587 // 91. Description of operator>> and getline() for string<> 01588 // might cause endless loop 01589 __in._M_setstate(__ios_base::badbit); 01590 } 01591 } 01592 if (!__extracted) 01593 __err |= __ios_base::failbit; 01594 if (__err) 01595 __in.setstate(__err); 01596 return __in; 01597 } 01598 01599 // Inhibit implicit instantiations for required instantiations, 01600 // which are defined via explicit instantiations elsewhere. 01601 #if _GLIBCXX_EXTERN_TEMPLATE 01602 // The explicit instantiations definitions in src/c++11/string-inst.cc 01603 // are compiled as C++14, so the new C++17 members aren't instantiated. 01604 // Until those definitions are compiled as C++17 suppress the declaration, 01605 // so C++17 code will implicitly instantiate std::string and std::wstring 01606 // as needed. 01607 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 01608 extern template class basic_string<char>; 01609 # elif ! _GLIBCXX_USE_CXX11_ABI 01610 // Still need to prevent implicit instantiation of the COW empty rep, 01611 // to ensure the definition in libstdc++.so is unique (PR 86138). 01612 extern template basic_string<char>::size_type 01613 basic_string<char>::_Rep::_S_empty_rep_storage[]; 01614 # endif 01615 01616 extern template 01617 basic_istream<char>& 01618 operator>>(basic_istream<char>&, string&); 01619 extern template 01620 basic_ostream<char>& 01621 operator<<(basic_ostream<char>&, const string&); 01622 extern template 01623 basic_istream<char>& 01624 getline(basic_istream<char>&, string&, char); 01625 extern template 01626 basic_istream<char>& 01627 getline(basic_istream<char>&, string&); 01628 01629 #ifdef _GLIBCXX_USE_WCHAR_T 01630 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 01631 extern template class basic_string<wchar_t>; 01632 # elif ! _GLIBCXX_USE_CXX11_ABI 01633 extern template basic_string<wchar_t>::size_type 01634 basic_string<wchar_t>::_Rep::_S_empty_rep_storage[]; 01635 # endif 01636 01637 extern template 01638 basic_istream<wchar_t>& 01639 operator>>(basic_istream<wchar_t>&, wstring&); 01640 extern template 01641 basic_ostream<wchar_t>& 01642 operator<<(basic_ostream<wchar_t>&, const wstring&); 01643 extern template 01644 basic_istream<wchar_t>& 01645 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 01646 extern template 01647 basic_istream<wchar_t>& 01648 getline(basic_istream<wchar_t>&, wstring&); 01649 #endif // _GLIBCXX_USE_WCHAR_T 01650 #endif // _GLIBCXX_EXTERN_TEMPLATE 01651 01652 _GLIBCXX_END_NAMESPACE_VERSION 01653 } // namespace std 01654 01655 #endif