libstdc++
|
00001 // Vector implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001-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 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/vector.tcc 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{vector} 00054 */ 00055 00056 #ifndef _VECTOR_TCC 00057 #define _VECTOR_TCC 1 00058 00059 namespace std _GLIBCXX_VISIBILITY(default) 00060 { 00061 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00063 00064 template<typename _Tp, typename _Alloc> 00065 void 00066 vector<_Tp, _Alloc>:: 00067 reserve(size_type __n) 00068 { 00069 if (__n > this->max_size()) 00070 __throw_length_error(__N("vector::reserve")); 00071 if (this->capacity() < __n) 00072 { 00073 const size_type __old_size = size(); 00074 pointer __tmp; 00075 #if __cplusplus >= 201103L 00076 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 00077 { 00078 __tmp = this->_M_allocate(__n); 00079 _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, 00080 __tmp, _M_get_Tp_allocator()); 00081 } 00082 else 00083 #endif 00084 { 00085 __tmp = _M_allocate_and_copy(__n, 00086 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), 00087 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); 00088 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00089 _M_get_Tp_allocator()); 00090 } 00091 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00092 _M_deallocate(this->_M_impl._M_start, 00093 this->_M_impl._M_end_of_storage 00094 - this->_M_impl._M_start); 00095 this->_M_impl._M_start = __tmp; 00096 this->_M_impl._M_finish = __tmp + __old_size; 00097 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00098 } 00099 } 00100 00101 #if __cplusplus >= 201103L 00102 template<typename _Tp, typename _Alloc> 00103 template<typename... _Args> 00104 #if __cplusplus > 201402L 00105 typename vector<_Tp, _Alloc>::reference 00106 #else 00107 void 00108 #endif 00109 vector<_Tp, _Alloc>:: 00110 emplace_back(_Args&&... __args) 00111 { 00112 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00113 { 00114 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 00115 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00116 std::forward<_Args>(__args)...); 00117 ++this->_M_impl._M_finish; 00118 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 00119 } 00120 else 00121 _M_realloc_insert(end(), std::forward<_Args>(__args)...); 00122 #if __cplusplus > 201402L 00123 return back(); 00124 #endif 00125 } 00126 #endif 00127 00128 template<typename _Tp, typename _Alloc> 00129 typename vector<_Tp, _Alloc>::iterator 00130 vector<_Tp, _Alloc>:: 00131 #if __cplusplus >= 201103L 00132 insert(const_iterator __position, const value_type& __x) 00133 #else 00134 insert(iterator __position, const value_type& __x) 00135 #endif 00136 { 00137 const size_type __n = __position - begin(); 00138 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00139 if (__position == end()) 00140 { 00141 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 00142 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00143 __x); 00144 ++this->_M_impl._M_finish; 00145 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 00146 } 00147 else 00148 { 00149 #if __cplusplus >= 201103L 00150 const auto __pos = begin() + (__position - cbegin()); 00151 // __x could be an existing element of this vector, so make a 00152 // copy of it before _M_insert_aux moves elements around. 00153 _Temporary_value __x_copy(this, __x); 00154 _M_insert_aux(__pos, std::move(__x_copy._M_val())); 00155 #else 00156 _M_insert_aux(__position, __x); 00157 #endif 00158 } 00159 else 00160 #if __cplusplus >= 201103L 00161 _M_realloc_insert(begin() + (__position - cbegin()), __x); 00162 #else 00163 _M_realloc_insert(__position, __x); 00164 #endif 00165 00166 return iterator(this->_M_impl._M_start + __n); 00167 } 00168 00169 template<typename _Tp, typename _Alloc> 00170 typename vector<_Tp, _Alloc>::iterator 00171 vector<_Tp, _Alloc>:: 00172 _M_erase(iterator __position) 00173 { 00174 if (__position + 1 != end()) 00175 _GLIBCXX_MOVE3(__position + 1, end(), __position); 00176 --this->_M_impl._M_finish; 00177 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 00178 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); 00179 return __position; 00180 } 00181 00182 template<typename _Tp, typename _Alloc> 00183 typename vector<_Tp, _Alloc>::iterator 00184 vector<_Tp, _Alloc>:: 00185 _M_erase(iterator __first, iterator __last) 00186 { 00187 if (__first != __last) 00188 { 00189 if (__last != end()) 00190 _GLIBCXX_MOVE3(__last, end(), __first); 00191 _M_erase_at_end(__first.base() + (end() - __last)); 00192 } 00193 return __first; 00194 } 00195 00196 template<typename _Tp, typename _Alloc> 00197 vector<_Tp, _Alloc>& 00198 vector<_Tp, _Alloc>:: 00199 operator=(const vector<_Tp, _Alloc>& __x) 00200 { 00201 if (&__x != this) 00202 { 00203 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00204 #if __cplusplus >= 201103L 00205 if (_Alloc_traits::_S_propagate_on_copy_assign()) 00206 { 00207 if (!_Alloc_traits::_S_always_equal() 00208 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 00209 { 00210 // replacement allocator cannot free existing storage 00211 this->clear(); 00212 _M_deallocate(this->_M_impl._M_start, 00213 this->_M_impl._M_end_of_storage 00214 - this->_M_impl._M_start); 00215 this->_M_impl._M_start = nullptr; 00216 this->_M_impl._M_finish = nullptr; 00217 this->_M_impl._M_end_of_storage = nullptr; 00218 } 00219 std::__alloc_on_copy(_M_get_Tp_allocator(), 00220 __x._M_get_Tp_allocator()); 00221 } 00222 #endif 00223 const size_type __xlen = __x.size(); 00224 if (__xlen > capacity()) 00225 { 00226 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), 00227 __x.end()); 00228 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00229 _M_get_Tp_allocator()); 00230 _M_deallocate(this->_M_impl._M_start, 00231 this->_M_impl._M_end_of_storage 00232 - this->_M_impl._M_start); 00233 this->_M_impl._M_start = __tmp; 00234 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 00235 } 00236 else if (size() >= __xlen) 00237 { 00238 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), 00239 end(), _M_get_Tp_allocator()); 00240 } 00241 else 00242 { 00243 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), 00244 this->_M_impl._M_start); 00245 std::__uninitialized_copy_a(__x._M_impl._M_start + size(), 00246 __x._M_impl._M_finish, 00247 this->_M_impl._M_finish, 00248 _M_get_Tp_allocator()); 00249 } 00250 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 00251 } 00252 return *this; 00253 } 00254 00255 template<typename _Tp, typename _Alloc> 00256 void 00257 vector<_Tp, _Alloc>:: 00258 _M_fill_assign(size_t __n, const value_type& __val) 00259 { 00260 if (__n > capacity()) 00261 { 00262 vector __tmp(__n, __val, _M_get_Tp_allocator()); 00263 __tmp._M_impl._M_swap_data(this->_M_impl); 00264 } 00265 else if (__n > size()) 00266 { 00267 std::fill(begin(), end(), __val); 00268 const size_type __add = __n - size(); 00269 _GLIBCXX_ASAN_ANNOTATE_GROW(__add); 00270 this->_M_impl._M_finish = 00271 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 00272 __add, __val, _M_get_Tp_allocator()); 00273 _GLIBCXX_ASAN_ANNOTATE_GREW(__add); 00274 } 00275 else 00276 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); 00277 } 00278 00279 template<typename _Tp, typename _Alloc> 00280 template<typename _InputIterator> 00281 void 00282 vector<_Tp, _Alloc>:: 00283 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00284 std::input_iterator_tag) 00285 { 00286 pointer __cur(this->_M_impl._M_start); 00287 for (; __first != __last && __cur != this->_M_impl._M_finish; 00288 ++__cur, (void)++__first) 00289 *__cur = *__first; 00290 if (__first == __last) 00291 _M_erase_at_end(__cur); 00292 else 00293 _M_range_insert(end(), __first, __last, 00294 std::__iterator_category(__first)); 00295 } 00296 00297 template<typename _Tp, typename _Alloc> 00298 template<typename _ForwardIterator> 00299 void 00300 vector<_Tp, _Alloc>:: 00301 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00302 std::forward_iterator_tag) 00303 { 00304 const size_type __len = std::distance(__first, __last); 00305 00306 if (__len > capacity()) 00307 { 00308 _S_check_init_len(__len, _M_get_Tp_allocator()); 00309 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 00310 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00311 _M_get_Tp_allocator()); 00312 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00313 _M_deallocate(this->_M_impl._M_start, 00314 this->_M_impl._M_end_of_storage 00315 - this->_M_impl._M_start); 00316 this->_M_impl._M_start = __tmp; 00317 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 00318 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 00319 } 00320 else if (size() >= __len) 00321 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); 00322 else 00323 { 00324 _ForwardIterator __mid = __first; 00325 std::advance(__mid, size()); 00326 std::copy(__first, __mid, this->_M_impl._M_start); 00327 const size_type __attribute__((__unused__)) __n = __len - size(); 00328 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00329 this->_M_impl._M_finish = 00330 std::__uninitialized_copy_a(__mid, __last, 00331 this->_M_impl._M_finish, 00332 _M_get_Tp_allocator()); 00333 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 00334 } 00335 } 00336 00337 #if __cplusplus >= 201103L 00338 template<typename _Tp, typename _Alloc> 00339 auto 00340 vector<_Tp, _Alloc>:: 00341 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator 00342 { 00343 const auto __n = __position - cbegin(); 00344 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00345 if (__position == cend()) 00346 { 00347 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 00348 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00349 std::move(__v)); 00350 ++this->_M_impl._M_finish; 00351 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 00352 } 00353 else 00354 _M_insert_aux(begin() + __n, std::move(__v)); 00355 else 00356 _M_realloc_insert(begin() + __n, std::move(__v)); 00357 00358 return iterator(this->_M_impl._M_start + __n); 00359 } 00360 00361 template<typename _Tp, typename _Alloc> 00362 template<typename... _Args> 00363 auto 00364 vector<_Tp, _Alloc>:: 00365 _M_emplace_aux(const_iterator __position, _Args&&... __args) 00366 -> iterator 00367 { 00368 const auto __n = __position - cbegin(); 00369 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00370 if (__position == cend()) 00371 { 00372 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 00373 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00374 std::forward<_Args>(__args)...); 00375 ++this->_M_impl._M_finish; 00376 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 00377 } 00378 else 00379 { 00380 // We need to construct a temporary because something in __args... 00381 // could alias one of the elements of the container and so we 00382 // need to use it before _M_insert_aux moves elements around. 00383 _Temporary_value __tmp(this, std::forward<_Args>(__args)...); 00384 _M_insert_aux(begin() + __n, std::move(__tmp._M_val())); 00385 } 00386 else 00387 _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...); 00388 00389 return iterator(this->_M_impl._M_start + __n); 00390 } 00391 00392 template<typename _Tp, typename _Alloc> 00393 template<typename _Arg> 00394 void 00395 vector<_Tp, _Alloc>:: 00396 _M_insert_aux(iterator __position, _Arg&& __arg) 00397 #else 00398 template<typename _Tp, typename _Alloc> 00399 void 00400 vector<_Tp, _Alloc>:: 00401 _M_insert_aux(iterator __position, const _Tp& __x) 00402 #endif 00403 { 00404 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 00405 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00406 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1))); 00407 ++this->_M_impl._M_finish; 00408 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 00409 #if __cplusplus < 201103L 00410 _Tp __x_copy = __x; 00411 #endif 00412 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 00413 this->_M_impl._M_finish - 2, 00414 this->_M_impl._M_finish - 1); 00415 #if __cplusplus < 201103L 00416 *__position = __x_copy; 00417 #else 00418 *__position = std::forward<_Arg>(__arg); 00419 #endif 00420 } 00421 00422 #if __cplusplus >= 201103L 00423 template<typename _Tp, typename _Alloc> 00424 template<typename... _Args> 00425 void 00426 vector<_Tp, _Alloc>:: 00427 _M_realloc_insert(iterator __position, _Args&&... __args) 00428 #else 00429 template<typename _Tp, typename _Alloc> 00430 void 00431 vector<_Tp, _Alloc>:: 00432 _M_realloc_insert(iterator __position, const _Tp& __x) 00433 #endif 00434 { 00435 const size_type __len = 00436 _M_check_len(size_type(1), "vector::_M_realloc_insert"); 00437 pointer __old_start = this->_M_impl._M_start; 00438 pointer __old_finish = this->_M_impl._M_finish; 00439 const size_type __elems_before = __position - begin(); 00440 pointer __new_start(this->_M_allocate(__len)); 00441 pointer __new_finish(__new_start); 00442 __try 00443 { 00444 // The order of the three operations is dictated by the C++11 00445 // case, where the moves could alter a new element belonging 00446 // to the existing vector. This is an issue only for callers 00447 // taking the element by lvalue ref (see last bullet of C++11 00448 // [res.on.arguments]). 00449 _Alloc_traits::construct(this->_M_impl, 00450 __new_start + __elems_before, 00451 #if __cplusplus >= 201103L 00452 std::forward<_Args>(__args)...); 00453 #else 00454 __x); 00455 #endif 00456 __new_finish = pointer(); 00457 00458 #if __cplusplus >= 201103L 00459 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 00460 { 00461 __new_finish = _S_relocate(__old_start, __position.base(), 00462 __new_start, _M_get_Tp_allocator()); 00463 00464 ++__new_finish; 00465 00466 __new_finish = _S_relocate(__position.base(), __old_finish, 00467 __new_finish, _M_get_Tp_allocator()); 00468 } 00469 else 00470 #endif 00471 { 00472 __new_finish 00473 = std::__uninitialized_move_if_noexcept_a 00474 (__old_start, __position.base(), 00475 __new_start, _M_get_Tp_allocator()); 00476 00477 ++__new_finish; 00478 00479 __new_finish 00480 = std::__uninitialized_move_if_noexcept_a 00481 (__position.base(), __old_finish, 00482 __new_finish, _M_get_Tp_allocator()); 00483 } 00484 } 00485 __catch(...) 00486 { 00487 if (!__new_finish) 00488 _Alloc_traits::destroy(this->_M_impl, 00489 __new_start + __elems_before); 00490 else 00491 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); 00492 _M_deallocate(__new_start, __len); 00493 __throw_exception_again; 00494 } 00495 #if __cplusplus >= 201103L 00496 if _GLIBCXX17_CONSTEXPR (!_S_use_relocate()) 00497 #endif 00498 std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator()); 00499 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00500 _M_deallocate(__old_start, 00501 this->_M_impl._M_end_of_storage - __old_start); 00502 this->_M_impl._M_start = __new_start; 00503 this->_M_impl._M_finish = __new_finish; 00504 this->_M_impl._M_end_of_storage = __new_start + __len; 00505 } 00506 00507 template<typename _Tp, typename _Alloc> 00508 void 00509 vector<_Tp, _Alloc>:: 00510 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 00511 { 00512 if (__n != 0) 00513 { 00514 if (size_type(this->_M_impl._M_end_of_storage 00515 - this->_M_impl._M_finish) >= __n) 00516 { 00517 #if __cplusplus < 201103L 00518 value_type __x_copy = __x; 00519 #else 00520 _Temporary_value __tmp(this, __x); 00521 value_type& __x_copy = __tmp._M_val(); 00522 #endif 00523 const size_type __elems_after = end() - __position; 00524 pointer __old_finish(this->_M_impl._M_finish); 00525 if (__elems_after > __n) 00526 { 00527 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00528 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 00529 this->_M_impl._M_finish, 00530 this->_M_impl._M_finish, 00531 _M_get_Tp_allocator()); 00532 this->_M_impl._M_finish += __n; 00533 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 00534 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 00535 __old_finish - __n, __old_finish); 00536 std::fill(__position.base(), __position.base() + __n, 00537 __x_copy); 00538 } 00539 else 00540 { 00541 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00542 this->_M_impl._M_finish = 00543 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 00544 __n - __elems_after, 00545 __x_copy, 00546 _M_get_Tp_allocator()); 00547 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 00548 std::__uninitialized_move_a(__position.base(), __old_finish, 00549 this->_M_impl._M_finish, 00550 _M_get_Tp_allocator()); 00551 this->_M_impl._M_finish += __elems_after; 00552 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 00553 std::fill(__position.base(), __old_finish, __x_copy); 00554 } 00555 } 00556 else 00557 { 00558 const size_type __len = 00559 _M_check_len(__n, "vector::_M_fill_insert"); 00560 const size_type __elems_before = __position - begin(); 00561 pointer __new_start(this->_M_allocate(__len)); 00562 pointer __new_finish(__new_start); 00563 __try 00564 { 00565 // See _M_realloc_insert above. 00566 std::__uninitialized_fill_n_a(__new_start + __elems_before, 00567 __n, __x, 00568 _M_get_Tp_allocator()); 00569 __new_finish = pointer(); 00570 00571 __new_finish 00572 = std::__uninitialized_move_if_noexcept_a 00573 (this->_M_impl._M_start, __position.base(), 00574 __new_start, _M_get_Tp_allocator()); 00575 00576 __new_finish += __n; 00577 00578 __new_finish 00579 = std::__uninitialized_move_if_noexcept_a 00580 (__position.base(), this->_M_impl._M_finish, 00581 __new_finish, _M_get_Tp_allocator()); 00582 } 00583 __catch(...) 00584 { 00585 if (!__new_finish) 00586 std::_Destroy(__new_start + __elems_before, 00587 __new_start + __elems_before + __n, 00588 _M_get_Tp_allocator()); 00589 else 00590 std::_Destroy(__new_start, __new_finish, 00591 _M_get_Tp_allocator()); 00592 _M_deallocate(__new_start, __len); 00593 __throw_exception_again; 00594 } 00595 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00596 _M_get_Tp_allocator()); 00597 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00598 _M_deallocate(this->_M_impl._M_start, 00599 this->_M_impl._M_end_of_storage 00600 - this->_M_impl._M_start); 00601 this->_M_impl._M_start = __new_start; 00602 this->_M_impl._M_finish = __new_finish; 00603 this->_M_impl._M_end_of_storage = __new_start + __len; 00604 } 00605 } 00606 } 00607 00608 #if __cplusplus >= 201103L 00609 template<typename _Tp, typename _Alloc> 00610 void 00611 vector<_Tp, _Alloc>:: 00612 _M_default_append(size_type __n) 00613 { 00614 if (__n != 0) 00615 { 00616 const size_type __size = size(); 00617 size_type __navail = size_type(this->_M_impl._M_end_of_storage 00618 - this->_M_impl._M_finish); 00619 00620 if (__size > max_size() || __navail > max_size() - __size) 00621 __builtin_unreachable(); 00622 00623 if (__navail >= __n) 00624 { 00625 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00626 this->_M_impl._M_finish = 00627 std::__uninitialized_default_n_a(this->_M_impl._M_finish, 00628 __n, _M_get_Tp_allocator()); 00629 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 00630 } 00631 else 00632 { 00633 const size_type __len = 00634 _M_check_len(__n, "vector::_M_default_append"); 00635 pointer __new_start(this->_M_allocate(__len)); 00636 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 00637 { 00638 __try 00639 { 00640 std::__uninitialized_default_n_a(__new_start + __size, 00641 __n, _M_get_Tp_allocator()); 00642 } 00643 __catch(...) 00644 { 00645 _M_deallocate(__new_start, __len); 00646 __throw_exception_again; 00647 } 00648 _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, 00649 __new_start, _M_get_Tp_allocator()); 00650 } 00651 else 00652 { 00653 pointer __destroy_from = pointer(); 00654 __try 00655 { 00656 std::__uninitialized_default_n_a(__new_start + __size, 00657 __n, _M_get_Tp_allocator()); 00658 __destroy_from = __new_start + __size; 00659 std::__uninitialized_move_if_noexcept_a( 00660 this->_M_impl._M_start, this->_M_impl._M_finish, 00661 __new_start, _M_get_Tp_allocator()); 00662 } 00663 __catch(...) 00664 { 00665 if (__destroy_from) 00666 std::_Destroy(__destroy_from, __destroy_from + __n, 00667 _M_get_Tp_allocator()); 00668 _M_deallocate(__new_start, __len); 00669 __throw_exception_again; 00670 } 00671 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00672 _M_get_Tp_allocator()); 00673 } 00674 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00675 _M_deallocate(this->_M_impl._M_start, 00676 this->_M_impl._M_end_of_storage 00677 - this->_M_impl._M_start); 00678 this->_M_impl._M_start = __new_start; 00679 this->_M_impl._M_finish = __new_start + __size + __n; 00680 this->_M_impl._M_end_of_storage = __new_start + __len; 00681 } 00682 } 00683 } 00684 00685 template<typename _Tp, typename _Alloc> 00686 bool 00687 vector<_Tp, _Alloc>:: 00688 _M_shrink_to_fit() 00689 { 00690 if (capacity() == size()) 00691 return false; 00692 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00693 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); 00694 } 00695 #endif 00696 00697 template<typename _Tp, typename _Alloc> 00698 template<typename _InputIterator> 00699 void 00700 vector<_Tp, _Alloc>:: 00701 _M_range_insert(iterator __pos, _InputIterator __first, 00702 _InputIterator __last, std::input_iterator_tag) 00703 { 00704 if (__pos == end()) 00705 { 00706 for (; __first != __last; ++__first) 00707 insert(end(), *__first); 00708 } 00709 else if (__first != __last) 00710 { 00711 vector __tmp(__first, __last, _M_get_Tp_allocator()); 00712 insert(__pos, 00713 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), 00714 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end())); 00715 } 00716 } 00717 00718 template<typename _Tp, typename _Alloc> 00719 template<typename _ForwardIterator> 00720 void 00721 vector<_Tp, _Alloc>:: 00722 _M_range_insert(iterator __position, _ForwardIterator __first, 00723 _ForwardIterator __last, std::forward_iterator_tag) 00724 { 00725 if (__first != __last) 00726 { 00727 const size_type __n = std::distance(__first, __last); 00728 if (size_type(this->_M_impl._M_end_of_storage 00729 - this->_M_impl._M_finish) >= __n) 00730 { 00731 const size_type __elems_after = end() - __position; 00732 pointer __old_finish(this->_M_impl._M_finish); 00733 if (__elems_after > __n) 00734 { 00735 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00736 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 00737 this->_M_impl._M_finish, 00738 this->_M_impl._M_finish, 00739 _M_get_Tp_allocator()); 00740 this->_M_impl._M_finish += __n; 00741 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 00742 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 00743 __old_finish - __n, __old_finish); 00744 std::copy(__first, __last, __position); 00745 } 00746 else 00747 { 00748 _ForwardIterator __mid = __first; 00749 std::advance(__mid, __elems_after); 00750 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 00751 std::__uninitialized_copy_a(__mid, __last, 00752 this->_M_impl._M_finish, 00753 _M_get_Tp_allocator()); 00754 this->_M_impl._M_finish += __n - __elems_after; 00755 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 00756 std::__uninitialized_move_a(__position.base(), 00757 __old_finish, 00758 this->_M_impl._M_finish, 00759 _M_get_Tp_allocator()); 00760 this->_M_impl._M_finish += __elems_after; 00761 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 00762 std::copy(__first, __mid, __position); 00763 } 00764 } 00765 else 00766 { 00767 const size_type __len = 00768 _M_check_len(__n, "vector::_M_range_insert"); 00769 pointer __new_start(this->_M_allocate(__len)); 00770 pointer __new_finish(__new_start); 00771 __try 00772 { 00773 __new_finish 00774 = std::__uninitialized_move_if_noexcept_a 00775 (this->_M_impl._M_start, __position.base(), 00776 __new_start, _M_get_Tp_allocator()); 00777 __new_finish 00778 = std::__uninitialized_copy_a(__first, __last, 00779 __new_finish, 00780 _M_get_Tp_allocator()); 00781 __new_finish 00782 = std::__uninitialized_move_if_noexcept_a 00783 (__position.base(), this->_M_impl._M_finish, 00784 __new_finish, _M_get_Tp_allocator()); 00785 } 00786 __catch(...) 00787 { 00788 std::_Destroy(__new_start, __new_finish, 00789 _M_get_Tp_allocator()); 00790 _M_deallocate(__new_start, __len); 00791 __throw_exception_again; 00792 } 00793 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00794 _M_get_Tp_allocator()); 00795 _GLIBCXX_ASAN_ANNOTATE_REINIT; 00796 _M_deallocate(this->_M_impl._M_start, 00797 this->_M_impl._M_end_of_storage 00798 - this->_M_impl._M_start); 00799 this->_M_impl._M_start = __new_start; 00800 this->_M_impl._M_finish = __new_finish; 00801 this->_M_impl._M_end_of_storage = __new_start + __len; 00802 } 00803 } 00804 } 00805 00806 00807 // vector<bool> 00808 template<typename _Alloc> 00809 void 00810 vector<bool, _Alloc>:: 00811 _M_reallocate(size_type __n) 00812 { 00813 _Bit_pointer __q = this->_M_allocate(__n); 00814 iterator __start(std::__addressof(*__q), 0); 00815 iterator __finish(_M_copy_aligned(begin(), end(), __start)); 00816 this->_M_deallocate(); 00817 this->_M_impl._M_start = __start; 00818 this->_M_impl._M_finish = __finish; 00819 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 00820 } 00821 00822 template<typename _Alloc> 00823 void 00824 vector<bool, _Alloc>:: 00825 _M_fill_insert(iterator __position, size_type __n, bool __x) 00826 { 00827 if (__n == 0) 00828 return; 00829 if (capacity() - size() >= __n) 00830 { 00831 std::copy_backward(__position, end(), 00832 this->_M_impl._M_finish + difference_type(__n)); 00833 std::fill(__position, __position + difference_type(__n), __x); 00834 this->_M_impl._M_finish += difference_type(__n); 00835 } 00836 else 00837 { 00838 const size_type __len = 00839 _M_check_len(__n, "vector<bool>::_M_fill_insert"); 00840 _Bit_pointer __q = this->_M_allocate(__len); 00841 iterator __start(std::__addressof(*__q), 0); 00842 iterator __i = _M_copy_aligned(begin(), __position, __start); 00843 std::fill(__i, __i + difference_type(__n), __x); 00844 iterator __finish = std::copy(__position, end(), 00845 __i + difference_type(__n)); 00846 this->_M_deallocate(); 00847 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 00848 this->_M_impl._M_start = __start; 00849 this->_M_impl._M_finish = __finish; 00850 } 00851 } 00852 00853 template<typename _Alloc> 00854 template<typename _ForwardIterator> 00855 void 00856 vector<bool, _Alloc>:: 00857 _M_insert_range(iterator __position, _ForwardIterator __first, 00858 _ForwardIterator __last, std::forward_iterator_tag) 00859 { 00860 if (__first != __last) 00861 { 00862 size_type __n = std::distance(__first, __last); 00863 if (capacity() - size() >= __n) 00864 { 00865 std::copy_backward(__position, end(), 00866 this->_M_impl._M_finish 00867 + difference_type(__n)); 00868 std::copy(__first, __last, __position); 00869 this->_M_impl._M_finish += difference_type(__n); 00870 } 00871 else 00872 { 00873 const size_type __len = 00874 _M_check_len(__n, "vector<bool>::_M_insert_range"); 00875 _Bit_pointer __q = this->_M_allocate(__len); 00876 iterator __start(std::__addressof(*__q), 0); 00877 iterator __i = _M_copy_aligned(begin(), __position, __start); 00878 __i = std::copy(__first, __last, __i); 00879 iterator __finish = std::copy(__position, end(), __i); 00880 this->_M_deallocate(); 00881 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 00882 this->_M_impl._M_start = __start; 00883 this->_M_impl._M_finish = __finish; 00884 } 00885 } 00886 } 00887 00888 template<typename _Alloc> 00889 void 00890 vector<bool, _Alloc>:: 00891 _M_insert_aux(iterator __position, bool __x) 00892 { 00893 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 00894 { 00895 std::copy_backward(__position, this->_M_impl._M_finish, 00896 this->_M_impl._M_finish + 1); 00897 *__position = __x; 00898 ++this->_M_impl._M_finish; 00899 } 00900 else 00901 { 00902 const size_type __len = 00903 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); 00904 _Bit_pointer __q = this->_M_allocate(__len); 00905 iterator __start(std::__addressof(*__q), 0); 00906 iterator __i = _M_copy_aligned(begin(), __position, __start); 00907 *__i++ = __x; 00908 iterator __finish = std::copy(__position, end(), __i); 00909 this->_M_deallocate(); 00910 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 00911 this->_M_impl._M_start = __start; 00912 this->_M_impl._M_finish = __finish; 00913 } 00914 } 00915 00916 template<typename _Alloc> 00917 typename vector<bool, _Alloc>::iterator 00918 vector<bool, _Alloc>:: 00919 _M_erase(iterator __position) 00920 { 00921 if (__position + 1 != end()) 00922 std::copy(__position + 1, end(), __position); 00923 --this->_M_impl._M_finish; 00924 return __position; 00925 } 00926 00927 template<typename _Alloc> 00928 typename vector<bool, _Alloc>::iterator 00929 vector<bool, _Alloc>:: 00930 _M_erase(iterator __first, iterator __last) 00931 { 00932 if (__first != __last) 00933 _M_erase_at_end(std::copy(__last, end(), __first)); 00934 return __first; 00935 } 00936 00937 #if __cplusplus >= 201103L 00938 template<typename _Alloc> 00939 bool 00940 vector<bool, _Alloc>:: 00941 _M_shrink_to_fit() 00942 { 00943 if (capacity() - size() < int(_S_word_bit)) 00944 return false; 00945 __try 00946 { 00947 _M_reallocate(size()); 00948 return true; 00949 } 00950 __catch(...) 00951 { return false; } 00952 } 00953 #endif 00954 00955 _GLIBCXX_END_NAMESPACE_CONTAINER 00956 _GLIBCXX_END_NAMESPACE_VERSION 00957 } // namespace std 00958 00959 #if __cplusplus >= 201103L 00960 00961 namespace std _GLIBCXX_VISIBILITY(default) 00962 { 00963 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00964 00965 template<typename _Alloc> 00966 size_t 00967 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: 00968 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept 00969 { 00970 size_t __hash = 0; 00971 using _GLIBCXX_STD_C::_S_word_bit; 00972 using _GLIBCXX_STD_C::_Bit_type; 00973 00974 const size_t __words = __b.size() / _S_word_bit; 00975 if (__words) 00976 { 00977 const size_t __clength = __words * sizeof(_Bit_type); 00978 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); 00979 } 00980 00981 const size_t __extrabits = __b.size() % _S_word_bit; 00982 if (__extrabits) 00983 { 00984 _Bit_type __hiword = *__b._M_impl._M_finish._M_p; 00985 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); 00986 00987 const size_t __clength 00988 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; 00989 if (__words) 00990 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); 00991 else 00992 __hash = std::_Hash_impl::hash(&__hiword, __clength); 00993 } 00994 00995 return __hash; 00996 } 00997 00998 _GLIBCXX_END_NAMESPACE_VERSION 00999 } // namespace std 01000 01001 #endif // C++11 01002 01003 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT 01004 #undef _GLIBCXX_ASAN_ANNOTATE_GROW 01005 #undef _GLIBCXX_ASAN_ANNOTATE_GREW 01006 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK 01007 01008 #endif /* _VECTOR_TCC */