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