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

Generated on Wed Sep 8 10:19:42 2004 for libstdc++-v3 Source by doxygen 1.3.8