libstdc++
|
00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997-2015 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_erase(__n, __size - __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, size_type __n) 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, __n) 00629 + __pos, _Alloc()), _Alloc()) 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, 00635 size_type __n, const _Alloc& __a) 00636 : _M_dataplus(_S_construct(__str._M_data() 00637 + __str._M_check(__pos, 00638 "basic_string::basic_string"), 00639 __str._M_data() + __str._M_limit(__pos, __n) 00640 + __pos, __a), __a) 00641 { } 00642 00643 // TBD: DPG annotate 00644 template<typename _CharT, typename _Traits, typename _Alloc> 00645 basic_string<_CharT, _Traits, _Alloc>:: 00646 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00647 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00648 { } 00649 00650 // TBD: DPG annotate 00651 template<typename _CharT, typename _Traits, typename _Alloc> 00652 basic_string<_CharT, _Traits, _Alloc>:: 00653 basic_string(const _CharT* __s, const _Alloc& __a) 00654 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00655 __s + npos, __a), __a) 00656 { } 00657 00658 template<typename _CharT, typename _Traits, typename _Alloc> 00659 basic_string<_CharT, _Traits, _Alloc>:: 00660 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00661 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00662 { } 00663 00664 // TBD: DPG annotate 00665 template<typename _CharT, typename _Traits, typename _Alloc> 00666 template<typename _InputIterator> 00667 basic_string<_CharT, _Traits, _Alloc>:: 00668 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 00669 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00670 { } 00671 00672 #if __cplusplus >= 201103L 00673 template<typename _CharT, typename _Traits, typename _Alloc> 00674 basic_string<_CharT, _Traits, _Alloc>:: 00675 basic_string(initializer_list<_CharT> __l, const _Alloc& __a) 00676 : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a) 00677 { } 00678 #endif 00679 00680 template<typename _CharT, typename _Traits, typename _Alloc> 00681 basic_string<_CharT, _Traits, _Alloc>& 00682 basic_string<_CharT, _Traits, _Alloc>:: 00683 assign(const basic_string& __str) 00684 { 00685 if (_M_rep() != __str._M_rep()) 00686 { 00687 // XXX MT 00688 const allocator_type __a = this->get_allocator(); 00689 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00690 _M_rep()->_M_dispose(__a); 00691 _M_data(__tmp); 00692 } 00693 return *this; 00694 } 00695 00696 template<typename _CharT, typename _Traits, typename _Alloc> 00697 basic_string<_CharT, _Traits, _Alloc>& 00698 basic_string<_CharT, _Traits, _Alloc>:: 00699 assign(const _CharT* __s, size_type __n) 00700 { 00701 __glibcxx_requires_string_len(__s, __n); 00702 _M_check_length(this->size(), __n, "basic_string::assign"); 00703 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00704 return _M_replace_safe(size_type(0), this->size(), __s, __n); 00705 else 00706 { 00707 // Work in-place. 00708 const size_type __pos = __s - _M_data(); 00709 if (__pos >= __n) 00710 _M_copy(_M_data(), __s, __n); 00711 else if (__pos) 00712 _M_move(_M_data(), __s, __n); 00713 _M_rep()->_M_set_length_and_sharable(__n); 00714 return *this; 00715 } 00716 } 00717 00718 template<typename _CharT, typename _Traits, typename _Alloc> 00719 basic_string<_CharT, _Traits, _Alloc>& 00720 basic_string<_CharT, _Traits, _Alloc>:: 00721 append(size_type __n, _CharT __c) 00722 { 00723 if (__n) 00724 { 00725 _M_check_length(size_type(0), __n, "basic_string::append"); 00726 const size_type __len = __n + this->size(); 00727 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00728 this->reserve(__len); 00729 _M_assign(_M_data() + this->size(), __n, __c); 00730 _M_rep()->_M_set_length_and_sharable(__len); 00731 } 00732 return *this; 00733 } 00734 00735 template<typename _CharT, typename _Traits, typename _Alloc> 00736 basic_string<_CharT, _Traits, _Alloc>& 00737 basic_string<_CharT, _Traits, _Alloc>:: 00738 append(const _CharT* __s, size_type __n) 00739 { 00740 __glibcxx_requires_string_len(__s, __n); 00741 if (__n) 00742 { 00743 _M_check_length(size_type(0), __n, "basic_string::append"); 00744 const size_type __len = __n + this->size(); 00745 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00746 { 00747 if (_M_disjunct(__s)) 00748 this->reserve(__len); 00749 else 00750 { 00751 const size_type __off = __s - _M_data(); 00752 this->reserve(__len); 00753 __s = _M_data() + __off; 00754 } 00755 } 00756 _M_copy(_M_data() + this->size(), __s, __n); 00757 _M_rep()->_M_set_length_and_sharable(__len); 00758 } 00759 return *this; 00760 } 00761 00762 template<typename _CharT, typename _Traits, typename _Alloc> 00763 basic_string<_CharT, _Traits, _Alloc>& 00764 basic_string<_CharT, _Traits, _Alloc>:: 00765 append(const basic_string& __str) 00766 { 00767 const size_type __size = __str.size(); 00768 if (__size) 00769 { 00770 const size_type __len = __size + this->size(); 00771 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00772 this->reserve(__len); 00773 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 00774 _M_rep()->_M_set_length_and_sharable(__len); 00775 } 00776 return *this; 00777 } 00778 00779 template<typename _CharT, typename _Traits, typename _Alloc> 00780 basic_string<_CharT, _Traits, _Alloc>& 00781 basic_string<_CharT, _Traits, _Alloc>:: 00782 append(const basic_string& __str, size_type __pos, size_type __n) 00783 { 00784 __str._M_check(__pos, "basic_string::append"); 00785 __n = __str._M_limit(__pos, __n); 00786 if (__n) 00787 { 00788 const size_type __len = __n + this->size(); 00789 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00790 this->reserve(__len); 00791 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 00792 _M_rep()->_M_set_length_and_sharable(__len); 00793 } 00794 return *this; 00795 } 00796 00797 template<typename _CharT, typename _Traits, typename _Alloc> 00798 basic_string<_CharT, _Traits, _Alloc>& 00799 basic_string<_CharT, _Traits, _Alloc>:: 00800 insert(size_type __pos, const _CharT* __s, size_type __n) 00801 { 00802 __glibcxx_requires_string_len(__s, __n); 00803 _M_check(__pos, "basic_string::insert"); 00804 _M_check_length(size_type(0), __n, "basic_string::insert"); 00805 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00806 return _M_replace_safe(__pos, size_type(0), __s, __n); 00807 else 00808 { 00809 // Work in-place. 00810 const size_type __off = __s - _M_data(); 00811 _M_mutate(__pos, 0, __n); 00812 __s = _M_data() + __off; 00813 _CharT* __p = _M_data() + __pos; 00814 if (__s + __n <= __p) 00815 _M_copy(__p, __s, __n); 00816 else if (__s >= __p) 00817 _M_copy(__p, __s + __n, __n); 00818 else 00819 { 00820 const size_type __nleft = __p - __s; 00821 _M_copy(__p, __s, __nleft); 00822 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 00823 } 00824 return *this; 00825 } 00826 } 00827 00828 template<typename _CharT, typename _Traits, typename _Alloc> 00829 typename basic_string<_CharT, _Traits, _Alloc>::iterator 00830 basic_string<_CharT, _Traits, _Alloc>:: 00831 erase(iterator __first, iterator __last) 00832 { 00833 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 00834 && __last <= _M_iend()); 00835 00836 // NB: This isn't just an optimization (bail out early when 00837 // there is nothing to do, really), it's also a correctness 00838 // issue vs MT, see libstdc++/40518. 00839 const size_type __size = __last - __first; 00840 if (__size) 00841 { 00842 const size_type __pos = __first - _M_ibegin(); 00843 _M_mutate(__pos, __size, size_type(0)); 00844 _M_rep()->_M_set_leaked(); 00845 return iterator(_M_data() + __pos); 00846 } 00847 else 00848 return __first; 00849 } 00850 00851 template<typename _CharT, typename _Traits, typename _Alloc> 00852 basic_string<_CharT, _Traits, _Alloc>& 00853 basic_string<_CharT, _Traits, _Alloc>:: 00854 replace(size_type __pos, size_type __n1, const _CharT* __s, 00855 size_type __n2) 00856 { 00857 __glibcxx_requires_string_len(__s, __n2); 00858 _M_check(__pos, "basic_string::replace"); 00859 __n1 = _M_limit(__pos, __n1); 00860 _M_check_length(__n1, __n2, "basic_string::replace"); 00861 bool __left; 00862 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00863 return _M_replace_safe(__pos, __n1, __s, __n2); 00864 else if ((__left = __s + __n2 <= _M_data() + __pos) 00865 || _M_data() + __pos + __n1 <= __s) 00866 { 00867 // Work in-place: non-overlapping case. 00868 size_type __off = __s - _M_data(); 00869 __left ? __off : (__off += __n2 - __n1); 00870 _M_mutate(__pos, __n1, __n2); 00871 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 00872 return *this; 00873 } 00874 else 00875 { 00876 // Todo: overlapping case. 00877 const basic_string __tmp(__s, __n2); 00878 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 00879 } 00880 } 00881 00882 template<typename _CharT, typename _Traits, typename _Alloc> 00883 void 00884 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00885 _M_destroy(const _Alloc& __a) throw () 00886 { 00887 const size_type __size = sizeof(_Rep_base) + 00888 (this->_M_capacity + 1) * sizeof(_CharT); 00889 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00890 } 00891 00892 template<typename _CharT, typename _Traits, typename _Alloc> 00893 void 00894 basic_string<_CharT, _Traits, _Alloc>:: 00895 _M_leak_hard() 00896 { 00897 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00898 if (_M_rep() == &_S_empty_rep()) 00899 return; 00900 #endif 00901 if (_M_rep()->_M_is_shared()) 00902 _M_mutate(0, 0, 0); 00903 _M_rep()->_M_set_leaked(); 00904 } 00905 00906 template<typename _CharT, typename _Traits, typename _Alloc> 00907 void 00908 basic_string<_CharT, _Traits, _Alloc>:: 00909 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00910 { 00911 const size_type __old_size = this->size(); 00912 const size_type __new_size = __old_size + __len2 - __len1; 00913 const size_type __how_much = __old_size - __pos - __len1; 00914 00915 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 00916 { 00917 // Must reallocate. 00918 const allocator_type __a = get_allocator(); 00919 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 00920 00921 if (__pos) 00922 _M_copy(__r->_M_refdata(), _M_data(), __pos); 00923 if (__how_much) 00924 _M_copy(__r->_M_refdata() + __pos + __len2, 00925 _M_data() + __pos + __len1, __how_much); 00926 00927 _M_rep()->_M_dispose(__a); 00928 _M_data(__r->_M_refdata()); 00929 } 00930 else if (__how_much && __len1 != __len2) 00931 { 00932 // Work in-place. 00933 _M_move(_M_data() + __pos + __len2, 00934 _M_data() + __pos + __len1, __how_much); 00935 } 00936 _M_rep()->_M_set_length_and_sharable(__new_size); 00937 } 00938 00939 template<typename _CharT, typename _Traits, typename _Alloc> 00940 void 00941 basic_string<_CharT, _Traits, _Alloc>:: 00942 reserve(size_type __res) 00943 { 00944 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 00945 { 00946 // Make sure we don't shrink below the current size 00947 if (__res < this->size()) 00948 __res = this->size(); 00949 const allocator_type __a = get_allocator(); 00950 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00951 _M_rep()->_M_dispose(__a); 00952 _M_data(__tmp); 00953 } 00954 } 00955 00956 template<typename _CharT, typename _Traits, typename _Alloc> 00957 void 00958 basic_string<_CharT, _Traits, _Alloc>:: 00959 swap(basic_string& __s) 00960 { 00961 if (_M_rep()->_M_is_leaked()) 00962 _M_rep()->_M_set_sharable(); 00963 if (__s._M_rep()->_M_is_leaked()) 00964 __s._M_rep()->_M_set_sharable(); 00965 if (this->get_allocator() == __s.get_allocator()) 00966 { 00967 _CharT* __tmp = _M_data(); 00968 _M_data(__s._M_data()); 00969 __s._M_data(__tmp); 00970 } 00971 // The code below can usually be optimized away. 00972 else 00973 { 00974 const basic_string __tmp1(_M_ibegin(), _M_iend(), 00975 __s.get_allocator()); 00976 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00977 this->get_allocator()); 00978 *this = __tmp2; 00979 __s = __tmp1; 00980 } 00981 } 00982 00983 template<typename _CharT, typename _Traits, typename _Alloc> 00984 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00985 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00986 _S_create(size_type __capacity, size_type __old_capacity, 00987 const _Alloc& __alloc) 00988 { 00989 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00990 // 83. String::npos vs. string::max_size() 00991 if (__capacity > _S_max_size) 00992 __throw_length_error(__N("basic_string::_S_create")); 00993 00994 // The standard places no restriction on allocating more memory 00995 // than is strictly needed within this layer at the moment or as 00996 // requested by an explicit application call to reserve(). 00997 00998 // Many malloc implementations perform quite poorly when an 00999 // application attempts to allocate memory in a stepwise fashion 01000 // growing each allocation size by only 1 char. Additionally, 01001 // it makes little sense to allocate less linear memory than the 01002 // natural blocking size of the malloc implementation. 01003 // Unfortunately, we would need a somewhat low-level calculation 01004 // with tuned parameters to get this perfect for any particular 01005 // malloc implementation. Fortunately, generalizations about 01006 // common features seen among implementations seems to suffice. 01007 01008 // __pagesize need not match the actual VM page size for good 01009 // results in practice, thus we pick a common value on the low 01010 // side. __malloc_header_size is an estimate of the amount of 01011 // overhead per memory allocation (in practice seen N * sizeof 01012 // (void*) where N is 0, 2 or 4). According to folklore, 01013 // picking this value on the high side is better than 01014 // low-balling it (especially when this algorithm is used with 01015 // malloc implementations that allocate memory blocks rounded up 01016 // to a size which is a power of 2). 01017 const size_type __pagesize = 4096; 01018 const size_type __malloc_header_size = 4 * sizeof(void*); 01019 01020 // The below implements an exponential growth policy, necessary to 01021 // meet amortized linear time requirements of the library: see 01022 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 01023 // It's active for allocations requiring an amount of memory above 01024 // system pagesize. This is consistent with the requirements of the 01025 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 01026 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 01027 __capacity = 2 * __old_capacity; 01028 01029 // NB: Need an array of char_type[__capacity], plus a terminating 01030 // null char_type() element, plus enough for the _Rep data structure. 01031 // Whew. Seemingly so needy, yet so elemental. 01032 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01033 01034 const size_type __adj_size = __size + __malloc_header_size; 01035 if (__adj_size > __pagesize && __capacity > __old_capacity) 01036 { 01037 const size_type __extra = __pagesize - __adj_size % __pagesize; 01038 __capacity += __extra / sizeof(_CharT); 01039 // Never allocate a string bigger than _S_max_size. 01040 if (__capacity > _S_max_size) 01041 __capacity = _S_max_size; 01042 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01043 } 01044 01045 // NB: Might throw, but no worries about a leak, mate: _Rep() 01046 // does not throw. 01047 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 01048 _Rep *__p = new (__place) _Rep; 01049 __p->_M_capacity = __capacity; 01050 // ABI compatibility - 3.4.x set in _S_create both 01051 // _M_refcount and _M_length. All callers of _S_create 01052 // in basic_string.tcc then set just _M_length. 01053 // In 4.0.x and later both _M_refcount and _M_length 01054 // are initialized in the callers, unfortunately we can 01055 // have 3.4.x compiled code with _S_create callers inlined 01056 // calling 4.0.x+ _S_create. 01057 __p->_M_set_sharable(); 01058 return __p; 01059 } 01060 01061 template<typename _CharT, typename _Traits, typename _Alloc> 01062 _CharT* 01063 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 01064 _M_clone(const _Alloc& __alloc, size_type __res) 01065 { 01066 // Requested capacity of the clone. 01067 const size_type __requested_cap = this->_M_length + __res; 01068 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 01069 __alloc); 01070 if (this->_M_length) 01071 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 01072 01073 __r->_M_set_length_and_sharable(this->_M_length); 01074 return __r->_M_refdata(); 01075 } 01076 01077 template<typename _CharT, typename _Traits, typename _Alloc> 01078 void 01079 basic_string<_CharT, _Traits, _Alloc>:: 01080 resize(size_type __n, _CharT __c) 01081 { 01082 const size_type __size = this->size(); 01083 _M_check_length(__size, __n, "basic_string::resize"); 01084 if (__size < __n) 01085 this->append(__n - __size, __c); 01086 else if (__n < __size) 01087 this->erase(__n); 01088 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 01089 } 01090 01091 template<typename _CharT, typename _Traits, typename _Alloc> 01092 template<typename _InputIterator> 01093 basic_string<_CharT, _Traits, _Alloc>& 01094 basic_string<_CharT, _Traits, _Alloc>:: 01095 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 01096 _InputIterator __k2, __false_type) 01097 { 01098 const basic_string __s(__k1, __k2); 01099 const size_type __n1 = __i2 - __i1; 01100 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 01101 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 01102 __s.size()); 01103 } 01104 01105 template<typename _CharT, typename _Traits, typename _Alloc> 01106 basic_string<_CharT, _Traits, _Alloc>& 01107 basic_string<_CharT, _Traits, _Alloc>:: 01108 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 01109 _CharT __c) 01110 { 01111 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 01112 _M_mutate(__pos1, __n1, __n2); 01113 if (__n2) 01114 _M_assign(_M_data() + __pos1, __n2, __c); 01115 return *this; 01116 } 01117 01118 template<typename _CharT, typename _Traits, typename _Alloc> 01119 basic_string<_CharT, _Traits, _Alloc>& 01120 basic_string<_CharT, _Traits, _Alloc>:: 01121 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 01122 size_type __n2) 01123 { 01124 _M_mutate(__pos1, __n1, __n2); 01125 if (__n2) 01126 _M_copy(_M_data() + __pos1, __s, __n2); 01127 return *this; 01128 } 01129 01130 template<typename _CharT, typename _Traits, typename _Alloc> 01131 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01132 basic_string<_CharT, _Traits, _Alloc>:: 01133 copy(_CharT* __s, size_type __n, size_type __pos) const 01134 { 01135 _M_check(__pos, "basic_string::copy"); 01136 __n = _M_limit(__pos, __n); 01137 __glibcxx_requires_string_len(__s, __n); 01138 if (__n) 01139 _M_copy(__s, _M_data() + __pos, __n); 01140 // 21.3.5.7 par 3: do not append null. (good.) 01141 return __n; 01142 } 01143 #endif // !_GLIBCXX_USE_CXX11_ABI 01144 01145 template<typename _CharT, typename _Traits, typename _Alloc> 01146 basic_string<_CharT, _Traits, _Alloc> 01147 operator+(const _CharT* __lhs, 01148 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01149 { 01150 __glibcxx_requires_string(__lhs); 01151 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01152 typedef typename __string_type::size_type __size_type; 01153 const __size_type __len = _Traits::length(__lhs); 01154 __string_type __str; 01155 __str.reserve(__len + __rhs.size()); 01156 __str.append(__lhs, __len); 01157 __str.append(__rhs); 01158 return __str; 01159 } 01160 01161 template<typename _CharT, typename _Traits, typename _Alloc> 01162 basic_string<_CharT, _Traits, _Alloc> 01163 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01164 { 01165 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01166 typedef typename __string_type::size_type __size_type; 01167 __string_type __str; 01168 const __size_type __len = __rhs.size(); 01169 __str.reserve(__len + 1); 01170 __str.append(__size_type(1), __lhs); 01171 __str.append(__rhs); 01172 return __str; 01173 } 01174 01175 template<typename _CharT, typename _Traits, typename _Alloc> 01176 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01177 basic_string<_CharT, _Traits, _Alloc>:: 01178 find(const _CharT* __s, size_type __pos, size_type __n) const 01179 { 01180 __glibcxx_requires_string_len(__s, __n); 01181 const size_type __size = this->size(); 01182 const _CharT* __data = _M_data(); 01183 01184 if (__n == 0) 01185 return __pos <= __size ? __pos : npos; 01186 01187 if (__n <= __size) 01188 { 01189 for (; __pos <= __size - __n; ++__pos) 01190 if (traits_type::eq(__data[__pos], __s[0]) 01191 && traits_type::compare(__data + __pos + 1, 01192 __s + 1, __n - 1) == 0) 01193 return __pos; 01194 } 01195 return npos; 01196 } 01197 01198 template<typename _CharT, typename _Traits, typename _Alloc> 01199 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01200 basic_string<_CharT, _Traits, _Alloc>:: 01201 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01202 { 01203 size_type __ret = npos; 01204 const size_type __size = this->size(); 01205 if (__pos < __size) 01206 { 01207 const _CharT* __data = _M_data(); 01208 const size_type __n = __size - __pos; 01209 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 01210 if (__p) 01211 __ret = __p - __data; 01212 } 01213 return __ret; 01214 } 01215 01216 template<typename _CharT, typename _Traits, typename _Alloc> 01217 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01218 basic_string<_CharT, _Traits, _Alloc>:: 01219 rfind(const _CharT* __s, size_type __pos, size_type __n) const 01220 { 01221 __glibcxx_requires_string_len(__s, __n); 01222 const size_type __size = this->size(); 01223 if (__n <= __size) 01224 { 01225 __pos = std::min(size_type(__size - __n), __pos); 01226 const _CharT* __data = _M_data(); 01227 do 01228 { 01229 if (traits_type::compare(__data + __pos, __s, __n) == 0) 01230 return __pos; 01231 } 01232 while (__pos-- > 0); 01233 } 01234 return npos; 01235 } 01236 01237 template<typename _CharT, typename _Traits, typename _Alloc> 01238 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01239 basic_string<_CharT, _Traits, _Alloc>:: 01240 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01241 { 01242 size_type __size = this->size(); 01243 if (__size) 01244 { 01245 if (--__size > __pos) 01246 __size = __pos; 01247 for (++__size; __size-- > 0; ) 01248 if (traits_type::eq(_M_data()[__size], __c)) 01249 return __size; 01250 } 01251 return npos; 01252 } 01253 01254 template<typename _CharT, typename _Traits, typename _Alloc> 01255 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01256 basic_string<_CharT, _Traits, _Alloc>:: 01257 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 01258 { 01259 __glibcxx_requires_string_len(__s, __n); 01260 for (; __n && __pos < this->size(); ++__pos) 01261 { 01262 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 01263 if (__p) 01264 return __pos; 01265 } 01266 return npos; 01267 } 01268 01269 template<typename _CharT, typename _Traits, typename _Alloc> 01270 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01271 basic_string<_CharT, _Traits, _Alloc>:: 01272 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 01273 { 01274 __glibcxx_requires_string_len(__s, __n); 01275 size_type __size = this->size(); 01276 if (__size && __n) 01277 { 01278 if (--__size > __pos) 01279 __size = __pos; 01280 do 01281 { 01282 if (traits_type::find(__s, __n, _M_data()[__size])) 01283 return __size; 01284 } 01285 while (__size-- != 0); 01286 } 01287 return npos; 01288 } 01289 01290 template<typename _CharT, typename _Traits, typename _Alloc> 01291 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01292 basic_string<_CharT, _Traits, _Alloc>:: 01293 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01294 { 01295 __glibcxx_requires_string_len(__s, __n); 01296 for (; __pos < this->size(); ++__pos) 01297 if (!traits_type::find(__s, __n, _M_data()[__pos])) 01298 return __pos; 01299 return npos; 01300 } 01301 01302 template<typename _CharT, typename _Traits, typename _Alloc> 01303 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01304 basic_string<_CharT, _Traits, _Alloc>:: 01305 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01306 { 01307 for (; __pos < this->size(); ++__pos) 01308 if (!traits_type::eq(_M_data()[__pos], __c)) 01309 return __pos; 01310 return npos; 01311 } 01312 01313 template<typename _CharT, typename _Traits, typename _Alloc> 01314 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01315 basic_string<_CharT, _Traits, _Alloc>:: 01316 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01317 { 01318 __glibcxx_requires_string_len(__s, __n); 01319 size_type __size = this->size(); 01320 if (__size) 01321 { 01322 if (--__size > __pos) 01323 __size = __pos; 01324 do 01325 { 01326 if (!traits_type::find(__s, __n, _M_data()[__size])) 01327 return __size; 01328 } 01329 while (__size--); 01330 } 01331 return npos; 01332 } 01333 01334 template<typename _CharT, typename _Traits, typename _Alloc> 01335 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01336 basic_string<_CharT, _Traits, _Alloc>:: 01337 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01338 { 01339 size_type __size = this->size(); 01340 if (__size) 01341 { 01342 if (--__size > __pos) 01343 __size = __pos; 01344 do 01345 { 01346 if (!traits_type::eq(_M_data()[__size], __c)) 01347 return __size; 01348 } 01349 while (__size--); 01350 } 01351 return npos; 01352 } 01353 01354 template<typename _CharT, typename _Traits, typename _Alloc> 01355 int 01356 basic_string<_CharT, _Traits, _Alloc>:: 01357 compare(size_type __pos, size_type __n, const basic_string& __str) const 01358 { 01359 _M_check(__pos, "basic_string::compare"); 01360 __n = _M_limit(__pos, __n); 01361 const size_type __osize = __str.size(); 01362 const size_type __len = std::min(__n, __osize); 01363 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 01364 if (!__r) 01365 __r = _S_compare(__n, __osize); 01366 return __r; 01367 } 01368 01369 template<typename _CharT, typename _Traits, typename _Alloc> 01370 int 01371 basic_string<_CharT, _Traits, _Alloc>:: 01372 compare(size_type __pos1, size_type __n1, const basic_string& __str, 01373 size_type __pos2, size_type __n2) const 01374 { 01375 _M_check(__pos1, "basic_string::compare"); 01376 __str._M_check(__pos2, "basic_string::compare"); 01377 __n1 = _M_limit(__pos1, __n1); 01378 __n2 = __str._M_limit(__pos2, __n2); 01379 const size_type __len = std::min(__n1, __n2); 01380 int __r = traits_type::compare(_M_data() + __pos1, 01381 __str.data() + __pos2, __len); 01382 if (!__r) 01383 __r = _S_compare(__n1, __n2); 01384 return __r; 01385 } 01386 01387 template<typename _CharT, typename _Traits, typename _Alloc> 01388 int 01389 basic_string<_CharT, _Traits, _Alloc>:: 01390 compare(const _CharT* __s) const 01391 { 01392 __glibcxx_requires_string(__s); 01393 const size_type __size = this->size(); 01394 const size_type __osize = traits_type::length(__s); 01395 const size_type __len = std::min(__size, __osize); 01396 int __r = traits_type::compare(_M_data(), __s, __len); 01397 if (!__r) 01398 __r = _S_compare(__size, __osize); 01399 return __r; 01400 } 01401 01402 template<typename _CharT, typename _Traits, typename _Alloc> 01403 int 01404 basic_string <_CharT, _Traits, _Alloc>:: 01405 compare(size_type __pos, size_type __n1, const _CharT* __s) const 01406 { 01407 __glibcxx_requires_string(__s); 01408 _M_check(__pos, "basic_string::compare"); 01409 __n1 = _M_limit(__pos, __n1); 01410 const size_type __osize = traits_type::length(__s); 01411 const size_type __len = std::min(__n1, __osize); 01412 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01413 if (!__r) 01414 __r = _S_compare(__n1, __osize); 01415 return __r; 01416 } 01417 01418 template<typename _CharT, typename _Traits, typename _Alloc> 01419 int 01420 basic_string <_CharT, _Traits, _Alloc>:: 01421 compare(size_type __pos, size_type __n1, const _CharT* __s, 01422 size_type __n2) const 01423 { 01424 __glibcxx_requires_string_len(__s, __n2); 01425 _M_check(__pos, "basic_string::compare"); 01426 __n1 = _M_limit(__pos, __n1); 01427 const size_type __len = std::min(__n1, __n2); 01428 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01429 if (!__r) 01430 __r = _S_compare(__n1, __n2); 01431 return __r; 01432 } 01433 01434 // 21.3.7.9 basic_string::getline and operators 01435 template<typename _CharT, typename _Traits, typename _Alloc> 01436 basic_istream<_CharT, _Traits>& 01437 operator>>(basic_istream<_CharT, _Traits>& __in, 01438 basic_string<_CharT, _Traits, _Alloc>& __str) 01439 { 01440 typedef basic_istream<_CharT, _Traits> __istream_type; 01441 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01442 typedef typename __istream_type::ios_base __ios_base; 01443 typedef typename __istream_type::int_type __int_type; 01444 typedef typename __string_type::size_type __size_type; 01445 typedef ctype<_CharT> __ctype_type; 01446 typedef typename __ctype_type::ctype_base __ctype_base; 01447 01448 __size_type __extracted = 0; 01449 typename __ios_base::iostate __err = __ios_base::goodbit; 01450 typename __istream_type::sentry __cerb(__in, false); 01451 if (__cerb) 01452 { 01453 __try 01454 { 01455 // Avoid reallocation for common case. 01456 __str.erase(); 01457 _CharT __buf[128]; 01458 __size_type __len = 0; 01459 const streamsize __w = __in.width(); 01460 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 01461 : __str.max_size(); 01462 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 01463 const __int_type __eof = _Traits::eof(); 01464 __int_type __c = __in.rdbuf()->sgetc(); 01465 01466 while (__extracted < __n 01467 && !_Traits::eq_int_type(__c, __eof) 01468 && !__ct.is(__ctype_base::space, 01469 _Traits::to_char_type(__c))) 01470 { 01471 if (__len == sizeof(__buf) / sizeof(_CharT)) 01472 { 01473 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 01474 __len = 0; 01475 } 01476 __buf[__len++] = _Traits::to_char_type(__c); 01477 ++__extracted; 01478 __c = __in.rdbuf()->snextc(); 01479 } 01480 __str.append(__buf, __len); 01481 01482 if (_Traits::eq_int_type(__c, __eof)) 01483 __err |= __ios_base::eofbit; 01484 __in.width(0); 01485 } 01486 __catch(__cxxabiv1::__forced_unwind&) 01487 { 01488 __in._M_setstate(__ios_base::badbit); 01489 __throw_exception_again; 01490 } 01491 __catch(...) 01492 { 01493 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01494 // 91. Description of operator>> and getline() for string<> 01495 // might cause endless loop 01496 __in._M_setstate(__ios_base::badbit); 01497 } 01498 } 01499 // 211. operator>>(istream&, string&) doesn't set failbit 01500 if (!__extracted) 01501 __err |= __ios_base::failbit; 01502 if (__err) 01503 __in.setstate(__err); 01504 return __in; 01505 } 01506 01507 template<typename _CharT, typename _Traits, typename _Alloc> 01508 basic_istream<_CharT, _Traits>& 01509 getline(basic_istream<_CharT, _Traits>& __in, 01510 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 01511 { 01512 typedef basic_istream<_CharT, _Traits> __istream_type; 01513 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01514 typedef typename __istream_type::ios_base __ios_base; 01515 typedef typename __istream_type::int_type __int_type; 01516 typedef typename __string_type::size_type __size_type; 01517 01518 __size_type __extracted = 0; 01519 const __size_type __n = __str.max_size(); 01520 typename __ios_base::iostate __err = __ios_base::goodbit; 01521 typename __istream_type::sentry __cerb(__in, true); 01522 if (__cerb) 01523 { 01524 __try 01525 { 01526 __str.erase(); 01527 const __int_type __idelim = _Traits::to_int_type(__delim); 01528 const __int_type __eof = _Traits::eof(); 01529 __int_type __c = __in.rdbuf()->sgetc(); 01530 01531 while (__extracted < __n 01532 && !_Traits::eq_int_type(__c, __eof) 01533 && !_Traits::eq_int_type(__c, __idelim)) 01534 { 01535 __str += _Traits::to_char_type(__c); 01536 ++__extracted; 01537 __c = __in.rdbuf()->snextc(); 01538 } 01539 01540 if (_Traits::eq_int_type(__c, __eof)) 01541 __err |= __ios_base::eofbit; 01542 else if (_Traits::eq_int_type(__c, __idelim)) 01543 { 01544 ++__extracted; 01545 __in.rdbuf()->sbumpc(); 01546 } 01547 else 01548 __err |= __ios_base::failbit; 01549 } 01550 __catch(__cxxabiv1::__forced_unwind&) 01551 { 01552 __in._M_setstate(__ios_base::badbit); 01553 __throw_exception_again; 01554 } 01555 __catch(...) 01556 { 01557 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01558 // 91. Description of operator>> and getline() for string<> 01559 // might cause endless loop 01560 __in._M_setstate(__ios_base::badbit); 01561 } 01562 } 01563 if (!__extracted) 01564 __err |= __ios_base::failbit; 01565 if (__err) 01566 __in.setstate(__err); 01567 return __in; 01568 } 01569 01570 // Inhibit implicit instantiations for required instantiations, 01571 // which are defined via explicit instantiations elsewhere. 01572 #if _GLIBCXX_EXTERN_TEMPLATE > 0 01573 extern template class basic_string<char>; 01574 extern template 01575 basic_istream<char>& 01576 operator>>(basic_istream<char>&, string&); 01577 extern template 01578 basic_ostream<char>& 01579 operator<<(basic_ostream<char>&, const string&); 01580 extern template 01581 basic_istream<char>& 01582 getline(basic_istream<char>&, string&, char); 01583 extern template 01584 basic_istream<char>& 01585 getline(basic_istream<char>&, string&); 01586 01587 #ifdef _GLIBCXX_USE_WCHAR_T 01588 extern template class basic_string<wchar_t>; 01589 extern template 01590 basic_istream<wchar_t>& 01591 operator>>(basic_istream<wchar_t>&, wstring&); 01592 extern template 01593 basic_ostream<wchar_t>& 01594 operator<<(basic_ostream<wchar_t>&, const wstring&); 01595 extern template 01596 basic_istream<wchar_t>& 01597 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 01598 extern template 01599 basic_istream<wchar_t>& 01600 getline(basic_istream<wchar_t>&, wstring&); 01601 #endif 01602 #endif 01603 01604 _GLIBCXX_END_NAMESPACE_VERSION 01605 } // namespace std 01606 01607 #endif