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