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