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