stl_bvector.h

Go to the documentation of this file.
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996-1999 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file stl_bvector.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef _BVECTOR_H 00062 #define _BVECTOR_H 1 00063 00064 namespace _GLIBCXX_STD 00065 { 00066 typedef unsigned long _Bit_type; 00067 enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) }; 00068 00069 struct _Bit_reference 00070 { 00071 _Bit_type * _M_p; 00072 _Bit_type _M_mask; 00073 00074 _Bit_reference(_Bit_type * __x, _Bit_type __y) 00075 : _M_p(__x), _M_mask(__y) { } 00076 00077 _Bit_reference() : _M_p(0), _M_mask(0) { } 00078 00079 operator bool() const 00080 { return !!(*_M_p & _M_mask); } 00081 00082 _Bit_reference& 00083 operator=(bool __x) 00084 { 00085 if (__x) 00086 *_M_p |= _M_mask; 00087 else 00088 *_M_p &= ~_M_mask; 00089 return *this; 00090 } 00091 00092 _Bit_reference& 00093 operator=(const _Bit_reference& __x) 00094 { return *this = bool(__x); } 00095 00096 bool 00097 operator==(const _Bit_reference& __x) const 00098 { return bool(*this) == bool(__x); } 00099 00100 bool 00101 operator<(const _Bit_reference& __x) const 00102 { return !bool(*this) && bool(__x); } 00103 00104 void 00105 flip() 00106 { *_M_p ^= _M_mask; } 00107 }; 00108 00109 struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool> 00110 { 00111 _Bit_type * _M_p; 00112 unsigned int _M_offset; 00113 00114 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 00115 : _M_p(__x), _M_offset(__y) { } 00116 00117 void 00118 _M_bump_up() 00119 { 00120 if (_M_offset++ == _S_word_bit - 1) 00121 { 00122 _M_offset = 0; 00123 ++_M_p; 00124 } 00125 } 00126 00127 void 00128 _M_bump_down() 00129 { 00130 if (_M_offset-- == 0) 00131 { 00132 _M_offset = _S_word_bit - 1; 00133 --_M_p; 00134 } 00135 } 00136 00137 void 00138 _M_incr(ptrdiff_t __i) 00139 { 00140 difference_type __n = __i + _M_offset; 00141 _M_p += __n / _S_word_bit; 00142 __n = __n % _S_word_bit; 00143 if (__n < 0) 00144 { 00145 _M_offset = static_cast<unsigned int>(__n + _S_word_bit); 00146 --_M_p; 00147 } 00148 else 00149 _M_offset = static_cast<unsigned int>(__n); 00150 } 00151 00152 bool 00153 operator==(const _Bit_iterator_base& __i) const 00154 { return _M_p == __i._M_p && _M_offset == __i._M_offset; } 00155 00156 bool 00157 operator<(const _Bit_iterator_base& __i) const 00158 { 00159 return _M_p < __i._M_p 00160 || (_M_p == __i._M_p && _M_offset < __i._M_offset); 00161 } 00162 00163 bool 00164 operator!=(const _Bit_iterator_base& __i) const 00165 { return !(*this == __i); } 00166 00167 bool 00168 operator>(const _Bit_iterator_base& __i) const 00169 { return __i < *this; } 00170 00171 bool 00172 operator<=(const _Bit_iterator_base& __i) const 00173 { return !(__i < *this); } 00174 00175 bool 00176 operator>=(const _Bit_iterator_base& __i) const 00177 { return !(*this < __i); } 00178 }; 00179 00180 inline ptrdiff_t 00181 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 00182 { 00183 return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; 00184 } 00185 00186 struct _Bit_iterator : public _Bit_iterator_base 00187 { 00188 typedef _Bit_reference reference; 00189 typedef _Bit_reference* pointer; 00190 typedef _Bit_iterator iterator; 00191 00192 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 00193 00194 _Bit_iterator(_Bit_type * __x, unsigned int __y) 00195 : _Bit_iterator_base(__x, __y) { } 00196 00197 reference 00198 operator*() const 00199 { return reference(_M_p, 1UL << _M_offset); } 00200 00201 iterator& 00202 operator++() 00203 { 00204 _M_bump_up(); 00205 return *this; 00206 } 00207 00208 iterator 00209 operator++(int) 00210 { 00211 iterator __tmp = *this; 00212 _M_bump_up(); 00213 return __tmp; 00214 } 00215 00216 iterator& 00217 operator--() 00218 { 00219 _M_bump_down(); 00220 return *this; 00221 } 00222 00223 iterator 00224 operator--(int) 00225 { 00226 iterator __tmp = *this; 00227 _M_bump_down(); 00228 return __tmp; 00229 } 00230 00231 iterator& 00232 operator+=(difference_type __i) 00233 { 00234 _M_incr(__i); 00235 return *this; 00236 } 00237 00238 iterator& 00239 operator-=(difference_type __i) 00240 { 00241 *this += -__i; 00242 return *this; 00243 } 00244 00245 iterator 00246 operator+(difference_type __i) const 00247 { 00248 iterator __tmp = *this; 00249 return __tmp += __i; 00250 } 00251 00252 iterator 00253 operator-(difference_type __i) const 00254 { 00255 iterator __tmp = *this; 00256 return __tmp -= __i; 00257 } 00258 00259 reference 00260 operator[](difference_type __i) 00261 { return *(*this + __i); } 00262 }; 00263 00264 inline _Bit_iterator 00265 operator+(ptrdiff_t __n, const _Bit_iterator& __x) 00266 { return __x + __n; } 00267 00268 struct _Bit_const_iterator : public _Bit_iterator_base 00269 { 00270 typedef bool reference; 00271 typedef bool const_reference; 00272 typedef const bool* pointer; 00273 typedef _Bit_const_iterator const_iterator; 00274 00275 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 00276 00277 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 00278 : _Bit_iterator_base(__x, __y) { } 00279 00280 _Bit_const_iterator(const _Bit_iterator& __x) 00281 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 00282 00283 const_reference 00284 operator*() const 00285 { return _Bit_reference(_M_p, 1UL << _M_offset); } 00286 00287 const_iterator& 00288 operator++() 00289 { 00290 _M_bump_up(); 00291 return *this; 00292 } 00293 00294 const_iterator 00295 operator++(int) 00296 { 00297 const_iterator __tmp = *this; 00298 _M_bump_up(); 00299 return __tmp; 00300 } 00301 00302 const_iterator& 00303 operator--() 00304 { 00305 _M_bump_down(); 00306 return *this; 00307 } 00308 00309 const_iterator 00310 operator--(int) 00311 { 00312 const_iterator __tmp = *this; 00313 _M_bump_down(); 00314 return __tmp; 00315 } 00316 00317 const_iterator& 00318 operator+=(difference_type __i) 00319 { 00320 _M_incr(__i); 00321 return *this; 00322 } 00323 00324 const_iterator& 00325 operator-=(difference_type __i) 00326 { 00327 *this += -__i; 00328 return *this; 00329 } 00330 00331 const_iterator 00332 operator+(difference_type __i) const 00333 { 00334 const_iterator __tmp = *this; 00335 return __tmp += __i; 00336 } 00337 00338 const_iterator 00339 operator-(difference_type __i) const 00340 { 00341 const_iterator __tmp = *this; 00342 return __tmp -= __i; 00343 } 00344 00345 const_reference 00346 operator[](difference_type __i) 00347 { return *(*this + __i); } 00348 }; 00349 00350 inline _Bit_const_iterator 00351 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) 00352 { return __x + __n; } 00353 00354 template<class _Alloc> 00355 class _Bvector_base 00356 { 00357 typedef typename _Alloc::template rebind<_Bit_type>::other 00358 _Bit_alloc_type; 00359 00360 struct _Bvector_impl : public _Bit_alloc_type 00361 { 00362 _Bit_iterator _M_start; 00363 _Bit_iterator _M_finish; 00364 _Bit_type* _M_end_of_storage; 00365 _Bvector_impl(const _Bit_alloc_type& __a) 00366 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) 00367 { } 00368 }; 00369 00370 public: 00371 typedef _Alloc allocator_type; 00372 00373 allocator_type 00374 get_allocator() const 00375 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } 00376 00377 _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } 00378 00379 ~_Bvector_base() 00380 { this->_M_deallocate(); } 00381 00382 protected: 00383 _Bvector_impl _M_impl; 00384 00385 _Bit_type* 00386 _M_allocate(size_t __n) 00387 { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); } 00388 00389 void 00390 _M_deallocate() 00391 { 00392 if (_M_impl._M_start._M_p) 00393 _M_impl.deallocate(_M_impl._M_start._M_p, 00394 _M_impl._M_end_of_storage - _M_impl._M_start._M_p); 00395 } 00396 }; 00397 } // namespace std 00398 00399 // Declare a partial specialization of vector<T, Alloc>. 00400 #include <bits/stl_vector.h> 00401 00402 namespace _GLIBCXX_STD 00403 { 00404 /** 00405 * @brief A specialization of vector for booleans which offers fixed time 00406 * access to individual elements in any order. 00407 * 00408 * Note that vector<bool> does not actually meet the requirements for being 00409 * a container. This is because the reference and pointer types are not 00410 * really references and pointers to bool. See DR96 for details. @see 00411 * vector for function documentation. 00412 * 00413 * @ingroup Containers 00414 * @ingroup Sequences 00415 * 00416 * In some terminology a %vector can be described as a dynamic 00417 * C-style array, it offers fast and efficient access to individual 00418 * elements in any order and saves the user from worrying about 00419 * memory and size allocation. Subscripting ( @c [] ) access is 00420 * also provided as with C-style arrays. 00421 */ 00422 template<typename _Alloc> 00423 class vector<bool, _Alloc> : public _Bvector_base<_Alloc> 00424 { 00425 public: 00426 typedef bool value_type; 00427 typedef size_t size_type; 00428 typedef ptrdiff_t difference_type; 00429 typedef _Bit_reference reference; 00430 typedef bool const_reference; 00431 typedef _Bit_reference* pointer; 00432 typedef const bool* const_pointer; 00433 00434 typedef _Bit_iterator iterator; 00435 typedef _Bit_const_iterator const_iterator; 00436 00437 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00438 typedef std::reverse_iterator<iterator> reverse_iterator; 00439 00440 typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type; 00441 00442 allocator_type get_allocator() const 00443 { return _Bvector_base<_Alloc>::get_allocator(); } 00444 00445 protected: 00446 using _Bvector_base<_Alloc>::_M_allocate; 00447 using _Bvector_base<_Alloc>::_M_deallocate; 00448 00449 protected: 00450 void 00451 _M_initialize(size_type __n) 00452 { 00453 _Bit_type* __q = this->_M_allocate(__n); 00454 this->_M_impl._M_end_of_storage = (__q 00455 + ((__n + _S_word_bit - 1) 00456 / _S_word_bit)); 00457 this->_M_impl._M_start = iterator(__q, 0); 00458 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 00459 } 00460 00461 void 00462 _M_insert_aux(iterator __position, bool __x) 00463 { 00464 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 00465 { 00466 std::copy_backward(__position, this->_M_impl._M_finish, 00467 this->_M_impl._M_finish + 1); 00468 *__position = __x; 00469 ++this->_M_impl._M_finish; 00470 } 00471 else 00472 { 00473 const size_type __len = size() ? 2 * size() 00474 : static_cast<size_type>(_S_word_bit); 00475 _Bit_type * __q = this->_M_allocate(__len); 00476 iterator __i = std::copy(begin(), __position, iterator(__q, 0)); 00477 *__i++ = __x; 00478 this->_M_impl._M_finish = std::copy(__position, end(), __i); 00479 this->_M_deallocate(); 00480 this->_M_impl._M_end_of_storage = (__q + ((__len + _S_word_bit - 1) 00481 / _S_word_bit)); 00482 this->_M_impl._M_start = iterator(__q, 0); 00483 } 00484 } 00485 00486 template<class _InputIterator> 00487 void 00488 _M_initialize_range(_InputIterator __first, _InputIterator __last, 00489 input_iterator_tag) 00490 { 00491 this->_M_impl._M_start = iterator(); 00492 this->_M_impl._M_finish = iterator(); 00493 this->_M_impl._M_end_of_storage = 0; 00494 for (; __first != __last; ++__first) 00495 push_back(*__first); 00496 } 00497 00498 template<class _ForwardIterator> 00499 void 00500 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 00501 forward_iterator_tag) 00502 { 00503 const size_type __n = std::distance(__first, __last); 00504 _M_initialize(__n); 00505 std::copy(__first, __last, this->_M_impl._M_start); 00506 } 00507 00508 template<class _InputIterator> 00509 void 00510 _M_insert_range(iterator __pos, _InputIterator __first, 00511 _InputIterator __last, input_iterator_tag) 00512 { 00513 for (; __first != __last; ++__first) 00514 { 00515 __pos = insert(__pos, *__first); 00516 ++__pos; 00517 } 00518 } 00519 00520 template<class _ForwardIterator> 00521 void 00522 _M_insert_range(iterator __position, _ForwardIterator __first, 00523 _ForwardIterator __last, forward_iterator_tag) 00524 { 00525 if (__first != __last) 00526 { 00527 size_type __n = std::distance(__first, __last); 00528 if (capacity() - size() >= __n) 00529 { 00530 std::copy_backward(__position, end(), 00531 this->_M_impl._M_finish 00532 + difference_type(__n)); 00533 std::copy(__first, __last, __position); 00534 this->_M_impl._M_finish += difference_type(__n); 00535 } 00536 else 00537 { 00538 const size_type __len = size() + std::max(size(), __n); 00539 _Bit_type * __q = this->_M_allocate(__len); 00540 iterator __i = std::copy(begin(), __position, 00541 iterator(__q, 0)); 00542 __i = std::copy(__first, __last, __i); 00543 this->_M_impl._M_finish = std::copy(__position, end(), __i); 00544 this->_M_deallocate(); 00545 this->_M_impl._M_end_of_storage = (__q 00546 + ((__len + _S_word_bit - 1) 00547 / _S_word_bit)); 00548 this->_M_impl._M_start = iterator(__q, 0); 00549 } 00550 } 00551 } 00552 00553 public: 00554 iterator 00555 begin() 00556 { return this->_M_impl._M_start; } 00557 00558 const_iterator 00559 begin() const 00560 { return this->_M_impl._M_start; } 00561 00562 iterator 00563 end() 00564 { return this->_M_impl._M_finish; } 00565 00566 const_iterator 00567 end() const 00568 { return this->_M_impl._M_finish; } 00569 00570 reverse_iterator 00571 rbegin() 00572 { return reverse_iterator(end()); } 00573 00574 const_reverse_iterator 00575 rbegin() const 00576 { return const_reverse_iterator(end()); } 00577 00578 reverse_iterator 00579 rend() 00580 { return reverse_iterator(begin()); } 00581 00582 const_reverse_iterator 00583 rend() const 00584 { return const_reverse_iterator(begin()); } 00585 00586 size_type 00587 size() const 00588 { return size_type(end() - begin()); } 00589 00590 size_type 00591 max_size() const 00592 { return size_type(-1); } 00593 00594 size_type 00595 capacity() const 00596 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) 00597 - begin()); } 00598 bool 00599 empty() const 00600 { return begin() == end(); } 00601 00602 reference 00603 operator[](size_type __n) 00604 { return *(begin() + difference_type(__n)); } 00605 00606 const_reference 00607 operator[](size_type __n) const 00608 { return *(begin() + difference_type(__n)); } 00609 00610 void 00611 _M_range_check(size_type __n) const 00612 { 00613 if (__n >= this->size()) 00614 __throw_out_of_range(__N("vector<bool>::_M_range_check")); 00615 } 00616 00617 reference 00618 at(size_type __n) 00619 { _M_range_check(__n); return (*this)[__n]; } 00620 00621 const_reference 00622 at(size_type __n) const 00623 { _M_range_check(__n); return (*this)[__n]; } 00624 00625 explicit 00626 vector(const allocator_type& __a = allocator_type()) 00627 : _Bvector_base<_Alloc>(__a) { } 00628 00629 vector(size_type __n, bool __value, 00630 const allocator_type& __a = allocator_type()) 00631 : _Bvector_base<_Alloc>(__a) 00632 { 00633 _M_initialize(__n); 00634 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 00635 __value ? ~0 : 0); 00636 } 00637 00638 explicit 00639 vector(size_type __n) 00640 : _Bvector_base<_Alloc>(allocator_type()) 00641 { 00642 _M_initialize(__n); 00643 std::fill(this->_M_impl._M_start._M_p, 00644 this->_M_impl._M_end_of_storage, 0); 00645 } 00646 00647 vector(const vector& __x) 00648 : _Bvector_base<_Alloc>(__x.get_allocator()) 00649 { 00650 _M_initialize(__x.size()); 00651 std::copy(__x.begin(), __x.end(), this->_M_impl._M_start); 00652 } 00653 00654 // Check whether it's an integral type. If so, it's not an iterator. 00655 template<class _Integer> 00656 void 00657 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 00658 { 00659 _M_initialize(__n); 00660 std::fill(this->_M_impl._M_start._M_p, 00661 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00662 } 00663 00664 template<class _InputIterator> 00665 void 00666 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 00667 __false_type) 00668 { _M_initialize_range(__first, __last, 00669 std::__iterator_category(__first)); } 00670 00671 template<class _InputIterator> 00672 vector(_InputIterator __first, _InputIterator __last, 00673 const allocator_type& __a = allocator_type()) 00674 : _Bvector_base<_Alloc>(__a) 00675 { 00676 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00677 _M_initialize_dispatch(__first, __last, _Integral()); 00678 } 00679 00680 ~vector() { } 00681 00682 vector& 00683 operator=(const vector& __x) 00684 { 00685 if (&__x == this) 00686 return *this; 00687 if (__x.size() > capacity()) 00688 { 00689 this->_M_deallocate(); 00690 _M_initialize(__x.size()); 00691 } 00692 std::copy(__x.begin(), __x.end(), begin()); 00693 this->_M_impl._M_finish = begin() + difference_type(__x.size()); 00694 return *this; 00695 } 00696 00697 // assign(), a generalized assignment member function. Two 00698 // versions: one that takes a count, and one that takes a range. 00699 // The range version is a member template, so we dispatch on whether 00700 // or not the type is an integer. 00701 00702 void 00703 _M_fill_assign(size_t __n, bool __x) 00704 { 00705 if (__n > size()) 00706 { 00707 std::fill(this->_M_impl._M_start._M_p, 00708 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00709 insert(end(), __n - size(), __x); 00710 } 00711 else 00712 { 00713 erase(begin() + __n, end()); 00714 std::fill(this->_M_impl._M_start._M_p, 00715 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00716 } 00717 } 00718 00719 void 00720 assign(size_t __n, bool __x) 00721 { _M_fill_assign(__n, __x); } 00722 00723 template<class _InputIterator> 00724 void 00725 assign(_InputIterator __first, _InputIterator __last) 00726 { 00727 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00728 _M_assign_dispatch(__first, __last, _Integral()); 00729 } 00730 00731 template<class _Integer> 00732 void 00733 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00734 { _M_fill_assign((size_t) __n, (bool) __val); } 00735 00736 template<class _InputIterator> 00737 void 00738 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00739 __false_type) 00740 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 00741 00742 template<class _InputIterator> 00743 void 00744 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00745 input_iterator_tag) 00746 { 00747 iterator __cur = begin(); 00748 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00749 *__cur = *__first; 00750 if (__first == __last) 00751 erase(__cur, end()); 00752 else 00753 insert(end(), __first, __last); 00754 } 00755 00756 template<class _ForwardIterator> 00757 void 00758 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00759 forward_iterator_tag) 00760 { 00761 const size_type __len = std::distance(__first, __last); 00762 if (__len < size()) 00763 erase(std::copy(__first, __last, begin()), end()); 00764 else 00765 { 00766 _ForwardIterator __mid = __first; 00767 std::advance(__mid, size()); 00768 std::copy(__first, __mid, begin()); 00769 insert(end(), __mid, __last); 00770 } 00771 } 00772 00773 void 00774 reserve(size_type __n) 00775 { 00776 if (__n > this->max_size()) 00777 __throw_length_error(__N("vector::reserve")); 00778 if (this->capacity() < __n) 00779 { 00780 _Bit_type* __q = this->_M_allocate(__n); 00781 this->_M_impl._M_finish = std::copy(begin(), end(), 00782 iterator(__q, 0)); 00783 this->_M_deallocate(); 00784 this->_M_impl._M_start = iterator(__q, 0); 00785 this->_M_impl._M_end_of_storage = (__q + (__n + _S_word_bit - 1) 00786 / _S_word_bit); 00787 } 00788 } 00789 00790 reference 00791 front() 00792 { return *begin(); } 00793 00794 const_reference 00795 front() const 00796 { return *begin(); } 00797 00798 reference 00799 back() 00800 { return *(end() - 1); } 00801 00802 const_reference 00803 back() const 00804 { return *(end() - 1); } 00805 00806 void 00807 push_back(bool __x) 00808 { 00809 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 00810 *this->_M_impl._M_finish++ = __x; 00811 else 00812 _M_insert_aux(end(), __x); 00813 } 00814 00815 void 00816 swap(vector<bool, _Alloc>& __x) 00817 { 00818 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00819 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00820 std::swap(this->_M_impl._M_end_of_storage, 00821 __x._M_impl._M_end_of_storage); 00822 } 00823 00824 // [23.2.5]/1, third-to-last entry in synopsis listing 00825 static void 00826 swap(reference __x, reference __y) 00827 { 00828 bool __tmp = __x; 00829 __x = __y; 00830 __y = __tmp; 00831 } 00832 00833 iterator 00834 insert(iterator __position, bool __x = bool()) 00835 { 00836 const difference_type __n = __position - begin(); 00837 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 00838 && __position == end()) 00839 *this->_M_impl._M_finish++ = __x; 00840 else 00841 _M_insert_aux(__position, __x); 00842 return begin() + __n; 00843 } 00844 00845 // Check whether it's an integral type. If so, it's not an iterator. 00846 00847 template<class _Integer> 00848 void 00849 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 00850 __true_type) 00851 { _M_fill_insert(__pos, __n, __x); } 00852 00853 template<class _InputIterator> 00854 void 00855 _M_insert_dispatch(iterator __pos, 00856 _InputIterator __first, _InputIterator __last, 00857 __false_type) 00858 { _M_insert_range(__pos, __first, __last, 00859 std::__iterator_category(__first)); } 00860 00861 template<class _InputIterator> 00862 void 00863 insert(iterator __position, 00864 _InputIterator __first, _InputIterator __last) 00865 { 00866 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00867 _M_insert_dispatch(__position, __first, __last, _Integral()); 00868 } 00869 00870 void 00871 _M_fill_insert(iterator __position, size_type __n, bool __x) 00872 { 00873 if (__n == 0) 00874 return; 00875 if (capacity() - size() >= __n) 00876 { 00877 std::copy_backward(__position, end(), 00878 this->_M_impl._M_finish + difference_type(__n)); 00879 std::fill(__position, __position + difference_type(__n), __x); 00880 this->_M_impl._M_finish += difference_type(__n); 00881 } 00882 else 00883 { 00884 const size_type __len = size() + std::max(size(), __n); 00885 _Bit_type * __q = this->_M_allocate(__len); 00886 iterator __i = std::copy(begin(), __position, iterator(__q, 0)); 00887 std::fill_n(__i, __n, __x); 00888 this->_M_impl._M_finish = std::copy(__position, end(), 00889 __i + difference_type(__n)); 00890 this->_M_deallocate(); 00891 this->_M_impl._M_end_of_storage = (__q + ((__len + _S_word_bit - 1) 00892 / _S_word_bit)); 00893 this->_M_impl._M_start = iterator(__q, 0); 00894 } 00895 } 00896 00897 void 00898 insert(iterator __position, size_type __n, bool __x) 00899 { _M_fill_insert(__position, __n, __x); } 00900 00901 void 00902 pop_back() 00903 { --this->_M_impl._M_finish; } 00904 00905 iterator 00906 erase(iterator __position) 00907 { 00908 if (__position + 1 != end()) 00909 std::copy(__position + 1, end(), __position); 00910 --this->_M_impl._M_finish; 00911 return __position; 00912 } 00913 00914 iterator 00915 erase(iterator __first, iterator __last) 00916 { 00917 this->_M_impl._M_finish = std::copy(__last, end(), __first); 00918 return __first; 00919 } 00920 00921 void 00922 resize(size_type __new_size, bool __x = bool()) 00923 { 00924 if (__new_size < size()) 00925 erase(begin() + difference_type(__new_size), end()); 00926 else 00927 insert(end(), __new_size - size(), __x); 00928 } 00929 00930 void 00931 flip() 00932 { 00933 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 00934 __p != this->_M_impl._M_end_of_storage; ++__p) 00935 *__p = ~*__p; 00936 } 00937 00938 void 00939 clear() 00940 { erase(begin(), end()); } 00941 }; 00942 } // namespace std 00943 00944 #endif

Generated on Sun Sep 12 15:49:59 2004 for libstdc++ source by doxygen 1.3.8