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