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