1 // bit_vector and vector<bool> specialization -*- C++ -*- 2 3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996-1999 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file stl_bvector.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef __GLIBCPP_INTERNAL_BVECTOR_H 62 #define __GLIBCPP_INTERNAL_BVECTOR_H 63 64 namespace std 65 { 66 typedef unsigned long _Bit_type; 67 enum { _M_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) }; 68 69 struct _Bit_reference { 70 71 _Bit_type * _M_p; 72 _Bit_type _M_mask; 73 _Bit_reference(_Bit_type * __x, _Bit_type __y) 74 : _M_p(__x), _M_mask(__y) {} 75 76 public: 77 _Bit_reference() : _M_p(0), _M_mask(0) {} 78 operator bool() const { return !!(*_M_p & _M_mask); } 79 _Bit_reference& operator=(bool __x) 80 { 81 if (__x) *_M_p |= _M_mask; 82 else *_M_p &= ~_M_mask; 83 return *this; 84 } 85 _Bit_reference& operator=(const _Bit_reference& __x) 86 { return *this = bool(__x); } 87 bool operator==(const _Bit_reference& __x) const 88 { return bool(*this) == bool(__x); } 89 bool operator<(const _Bit_reference& __x) const 90 { return !bool(*this) && bool(__x); } 91 void flip() { *_M_p ^= _M_mask; } 92 }; 93 94 inline void swap(_Bit_reference __x, _Bit_reference __y) 95 { 96 bool __tmp = __x; 97 __x = __y; 98 __y = __tmp; 99 } 100 101 struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool> 102 { 103 _Bit_type * _M_p; 104 unsigned int _M_offset; 105 106 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 107 : _M_p(__x), _M_offset(__y) {} 108 109 void _M_bump_up() { 110 if (_M_offset++ == _M_word_bit - 1) { 111 _M_offset = 0; 112 ++_M_p; 113 } 114 } 115 void _M_bump_down() { 116 if (_M_offset-- == 0) { 117 _M_offset = _M_word_bit - 1; 118 --_M_p; 119 } 120 } 121 122 void _M_incr(ptrdiff_t __i) { 123 difference_type __n = __i + _M_offset; 124 _M_p += __n / _M_word_bit; 125 __n = __n % _M_word_bit; 126 if (__n < 0) { 127 _M_offset = (unsigned int) __n + _M_word_bit; 128 --_M_p; 129 } else 130 _M_offset = (unsigned int) __n; 131 } 132 133 bool operator==(const _Bit_iterator_base& __i) const { 134 return _M_p == __i._M_p && _M_offset == __i._M_offset; 135 } 136 bool operator<(const _Bit_iterator_base& __i) const { 137 return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); 138 } 139 bool operator!=(const _Bit_iterator_base& __i) const { 140 return !(*this == __i); 141 } 142 bool operator>(const _Bit_iterator_base& __i) const { 143 return __i < *this; 144 } 145 bool operator<=(const _Bit_iterator_base& __i) const { 146 return !(__i < *this); 147 } 148 bool operator>=(const _Bit_iterator_base& __i) const { 149 return !(*this < __i); 150 } 151 }; 152 153 inline ptrdiff_t 154 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { 155 return _M_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; 156 } 157 158 159 struct _Bit_iterator : public _Bit_iterator_base 160 { 161 typedef _Bit_reference reference; 162 typedef _Bit_reference* pointer; 163 typedef _Bit_iterator iterator; 164 165 _Bit_iterator() : _Bit_iterator_base(0, 0) {} 166 _Bit_iterator(_Bit_type * __x, unsigned int __y) 167 : _Bit_iterator_base(__x, __y) {} 168 169 reference operator*() const { return reference(_M_p, 1UL << _M_offset); } 170 iterator& operator++() { 171 _M_bump_up(); 172 return *this; 173 } 174 iterator operator++(int) { 175 iterator __tmp = *this; 176 _M_bump_up(); 177 return __tmp; 178 } 179 iterator& operator--() { 180 _M_bump_down(); 181 return *this; 182 } 183 iterator operator--(int) { 184 iterator __tmp = *this; 185 _M_bump_down(); 186 return __tmp; 187 } 188 iterator& operator+=(difference_type __i) { 189 _M_incr(__i); 190 return *this; 191 } 192 iterator& operator-=(difference_type __i) { 193 *this += -__i; 194 return *this; 195 } 196 iterator operator+(difference_type __i) const { 197 iterator __tmp = *this; 198 return __tmp += __i; 199 } 200 iterator operator-(difference_type __i) const { 201 iterator __tmp = *this; 202 return __tmp -= __i; 203 } 204 205 reference operator[](difference_type __i) { return *(*this + __i); } 206 }; 207 208 inline _Bit_iterator 209 operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } 210 211 212 struct _Bit_const_iterator : public _Bit_iterator_base 213 { 214 typedef bool reference; 215 typedef bool const_reference; 216 typedef const bool* pointer; 217 typedef _Bit_const_iterator const_iterator; 218 219 _Bit_const_iterator() : _Bit_iterator_base(0, 0) {} 220 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 221 : _Bit_iterator_base(__x, __y) {} 222 _Bit_const_iterator(const _Bit_iterator& __x) 223 : _Bit_iterator_base(__x._M_p, __x._M_offset) {} 224 225 const_reference operator*() const { 226 return _Bit_reference(_M_p, 1UL << _M_offset); 227 } 228 const_iterator& operator++() { 229 _M_bump_up(); 230 return *this; 231 } 232 const_iterator operator++(int) { 233 const_iterator __tmp = *this; 234 _M_bump_up(); 235 return __tmp; 236 } 237 const_iterator& operator--() { 238 _M_bump_down(); 239 return *this; 240 } 241 const_iterator operator--(int) { 242 const_iterator __tmp = *this; 243 _M_bump_down(); 244 return __tmp; 245 } 246 const_iterator& operator+=(difference_type __i) { 247 _M_incr(__i); 248 return *this; 249 } 250 const_iterator& operator-=(difference_type __i) { 251 *this += -__i; 252 return *this; 253 } 254 const_iterator operator+(difference_type __i) const { 255 const_iterator __tmp = *this; 256 return __tmp += __i; 257 } 258 const_iterator operator-(difference_type __i) const { 259 const_iterator __tmp = *this; 260 return __tmp -= __i; 261 } 262 const_reference operator[](difference_type __i) { 263 return *(*this + __i); 264 } 265 }; 266 267 inline _Bit_const_iterator 268 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } 269 270 271 // Bit-vector base class, which encapsulates the difference between 272 // old SGI-style allocators and standard-conforming allocators. 273 274 // Base class for ordinary allocators. 275 template <class _Allocator, bool __is_static> 276 class _Bvector_alloc_base { 277 public: 278 typedef typename _Alloc_traits<bool, _Allocator>::allocator_type 279 allocator_type; 280 allocator_type get_allocator() const { return _M_data_allocator; } 281 282 _Bvector_alloc_base(const allocator_type& __a) 283 : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {} 284 285 protected: 286 _Bit_type * _M_bit_alloc(size_t __n) 287 { return _M_data_allocator.allocate((__n + _M_word_bit - 1)/_M_word_bit); } 288 void _M_deallocate() { 289 if (_M_start._M_p) 290 _M_data_allocator.deallocate(_M_start._M_p, 291 _M_end_of_storage - _M_start._M_p); 292 } 293 294 typename _Alloc_traits<_Bit_type, _Allocator>::allocator_type 295 _M_data_allocator; 296 _Bit_iterator _M_start; 297 _Bit_iterator _M_finish; 298 _Bit_type * _M_end_of_storage; 299 }; 300 301 // Specialization for instanceless allocators. 302 template <class _Allocator> 303 class _Bvector_alloc_base<_Allocator, true> { 304 public: 305 typedef typename _Alloc_traits<bool, _Allocator>::allocator_type 306 allocator_type; 307 allocator_type get_allocator() const { return allocator_type(); } 308 309 _Bvector_alloc_base(const allocator_type&) 310 : _M_start(), _M_finish(), _M_end_of_storage(0) {} 311 312 protected: 313 typedef typename _Alloc_traits<_Bit_type, _Allocator>::_Alloc_type 314 _Alloc_type; 315 316 _Bit_type * _M_bit_alloc(size_t __n) 317 { return _Alloc_type::allocate((__n + _M_word_bit - 1)/_M_word_bit); } 318 void _M_deallocate() { 319 if (_M_start._M_p) 320 _Alloc_type::deallocate(_M_start._M_p, 321 _M_end_of_storage - _M_start._M_p); 322 } 323 324 _Bit_iterator _M_start; 325 _Bit_iterator _M_finish; 326 _Bit_type * _M_end_of_storage; 327 }; 328 329 template <class _Alloc> 330 class _Bvector_base 331 : public _Bvector_alloc_base<_Alloc, 332 _Alloc_traits<bool, _Alloc>::_S_instanceless> 333 { 334 typedef _Bvector_alloc_base<_Alloc, 335 _Alloc_traits<bool, _Alloc>::_S_instanceless> 336 _Base; 337 public: 338 typedef typename _Base::allocator_type allocator_type; 339 340 _Bvector_base(const allocator_type& __a) : _Base(__a) {} 341 ~_Bvector_base() { _Base::_M_deallocate(); } 342 }; 343 344 } // namespace std 345 346 // Declare a partial specialization of vector<T, Alloc>. 347 #include <bits/stl_vector.h> 348 namespace std 349 { 350 351 template <typename _Alloc> 352 class vector<bool, _Alloc> : public _Bvector_base<_Alloc> 353 { 354 public: 355 typedef bool value_type; 356 typedef size_t size_type; 357 typedef ptrdiff_t difference_type; 358 typedef _Bit_reference reference; 359 typedef bool const_reference; 360 typedef _Bit_reference* pointer; 361 typedef const bool* const_pointer; 362 363 typedef _Bit_iterator iterator; 364 typedef _Bit_const_iterator const_iterator; 365 366 typedef reverse_iterator<const_iterator> const_reverse_iterator; 367 typedef reverse_iterator<iterator> reverse_iterator; 368 369 typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type; 370 allocator_type get_allocator() const { 371 return _Bvector_base<_Alloc>::get_allocator(); 372 } 373 374 protected: 375 using _Bvector_base<_Alloc>::_M_bit_alloc; 376 using _Bvector_base<_Alloc>::_M_deallocate; 377 using _Bvector_base<_Alloc>::_M_start; 378 using _Bvector_base<_Alloc>::_M_finish; 379 using _Bvector_base<_Alloc>::_M_end_of_storage; 380 381 protected: 382 void _M_initialize(size_type __n) { 383 _Bit_type * __q = _M_bit_alloc(__n); 384 _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit; 385 _M_start = iterator(__q, 0); 386 _M_finish = _M_start + difference_type(__n); 387 } 388 void _M_insert_aux(iterator __position, bool __x) { 389 if (_M_finish._M_p != _M_end_of_storage) { 390 copy_backward(__position, _M_finish, _M_finish + 1); 391 *__position = __x; 392 ++_M_finish; 393 } 394 else { 395 size_type __len = size() 396 ? 2 * size() : static_cast<size_type>(_M_word_bit); 397 _Bit_type * __q = _M_bit_alloc(__len); 398 iterator __i = copy(begin(), __position, iterator(__q, 0)); 399 *__i++ = __x; 400 _M_finish = copy(__position, end(), __i); 401 _M_deallocate(); 402 _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; 403 _M_start = iterator(__q, 0); 404 } 405 } 406 407 template <class _InputIterator> 408 void _M_initialize_range(_InputIterator __first, _InputIterator __last, 409 input_iterator_tag) { 410 _M_start = iterator(); 411 _M_finish = iterator(); 412 _M_end_of_storage = 0; 413 for ( ; __first != __last; ++__first) 414 push_back(*__first); 415 } 416 417 template <class _ForwardIterator> 418 void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 419 forward_iterator_tag) { 420 size_type __n = distance(__first, __last); 421 _M_initialize(__n); 422 copy(__first, __last, _M_start); 423 } 424 425 template <class _InputIterator> 426 void _M_insert_range(iterator __pos, 427 _InputIterator __first, _InputIterator __last, 428 input_iterator_tag) { 429 for ( ; __first != __last; ++__first) { 430 __pos = insert(__pos, *__first); 431 ++__pos; 432 } 433 } 434 435 template <class _ForwardIterator> 436 void _M_insert_range(iterator __position, 437 _ForwardIterator __first, _ForwardIterator __last, 438 forward_iterator_tag) { 439 if (__first != __last) { 440 size_type __n = distance(__first, __last); 441 if (capacity() - size() >= __n) { 442 copy_backward(__position, end(), _M_finish + difference_type(__n)); 443 copy(__first, __last, __position); 444 _M_finish += difference_type(__n); 445 } 446 else { 447 size_type __len = size() + max(size(), __n); 448 _Bit_type * __q = _M_bit_alloc(__len); 449 iterator __i = copy(begin(), __position, iterator(__q, 0)); 450 __i = copy(__first, __last, __i); 451 _M_finish = copy(__position, end(), __i); 452 _M_deallocate(); 453 _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; 454 _M_start = iterator(__q, 0); 455 } 456 } 457 } 458 459 public: 460 iterator begin() { return _M_start; } 461 const_iterator begin() const { return _M_start; } 462 iterator end() { return _M_finish; } 463 const_iterator end() const { return _M_finish; } 464 465 reverse_iterator rbegin() { return reverse_iterator(end()); } 466 const_reverse_iterator rbegin() const { 467 return const_reverse_iterator(end()); 468 } 469 reverse_iterator rend() { return reverse_iterator(begin()); } 470 const_reverse_iterator rend() const { 471 return const_reverse_iterator(begin()); 472 } 473 474 size_type size() const { return size_type(end() - begin()); } 475 size_type max_size() const { return size_type(-1); } 476 size_type capacity() const { 477 return size_type(const_iterator(_M_end_of_storage, 0) - begin()); 478 } 479 bool empty() const { return begin() == end(); } 480 481 reference operator[](size_type __n) 482 { return *(begin() + difference_type(__n)); } 483 const_reference operator[](size_type __n) const 484 { return *(begin() + difference_type(__n)); } 485 486 void _M_range_check(size_type __n) const { 487 if (__n >= this->size()) 488 __throw_out_of_range("vector<bool>"); 489 } 490 491 reference at(size_type __n) 492 { _M_range_check(__n); return (*this)[__n]; } 493 const_reference at(size_type __n) const 494 { _M_range_check(__n); return (*this)[__n]; } 495 496 explicit vector(const allocator_type& __a = allocator_type()) 497 : _Bvector_base<_Alloc>(__a) {} 498 499 vector(size_type __n, bool __value, 500 const allocator_type& __a = allocator_type()) 501 : _Bvector_base<_Alloc>(__a) 502 { 503 _M_initialize(__n); 504 fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0); 505 } 506 507 explicit vector(size_type __n) 508 : _Bvector_base<_Alloc>(allocator_type()) 509 { 510 _M_initialize(__n); 511 fill(_M_start._M_p, _M_end_of_storage, 0); 512 } 513 514 vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator()) { 515 _M_initialize(__x.size()); 516 copy(__x.begin(), __x.end(), _M_start); 517 } 518 519 // Check whether it's an integral type. If so, it's not an iterator. 520 521 template <class _Integer> 522 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { 523 _M_initialize(__n); 524 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 525 } 526 527 template <class _InputIterator> 528 void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 529 __false_type) { 530 _M_initialize_range(__first, __last, __iterator_category(__first)); 531 } 532 533 template <class _InputIterator> 534 vector(_InputIterator __first, _InputIterator __last, 535 const allocator_type& __a = allocator_type()) 536 : _Bvector_base<_Alloc>(__a) 537 { 538 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 539 _M_initialize_dispatch(__first, __last, _Integral()); 540 } 541 542 ~vector() { } 543 544 vector& operator=(const vector& __x) { 545 if (&__x == this) return *this; 546 if (__x.size() > capacity()) { 547 _M_deallocate(); 548 _M_initialize(__x.size()); 549 } 550 copy(__x.begin(), __x.end(), begin()); 551 _M_finish = begin() + difference_type(__x.size()); 552 return *this; 553 } 554 555 // assign(), a generalized assignment member function. Two 556 // versions: one that takes a count, and one that takes a range. 557 // The range version is a member template, so we dispatch on whether 558 // or not the type is an integer. 559 560 void _M_fill_assign(size_t __n, bool __x) { 561 if (__n > size()) { 562 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 563 insert(end(), __n - size(), __x); 564 } 565 else { 566 erase(begin() + __n, end()); 567 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 568 } 569 } 570 571 void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); } 572 573 template <class _InputIterator> 574 void assign(_InputIterator __first, _InputIterator __last) { 575 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 576 _M_assign_dispatch(__first, __last, _Integral()); 577 } 578 579 template <class _Integer> 580 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 581 { _M_fill_assign((size_t) __n, (bool) __val); } 582 583 template <class _InputIter> 584 void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) 585 { _M_assign_aux(__first, __last, __iterator_category(__first)); } 586 587 template <class _InputIterator> 588 void _M_assign_aux(_InputIterator __first, _InputIterator __last, 589 input_iterator_tag) { 590 iterator __cur = begin(); 591 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 592 *__cur = *__first; 593 if (__first == __last) 594 erase(__cur, end()); 595 else 596 insert(end(), __first, __last); 597 } 598 599 template <class _ForwardIterator> 600 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 601 forward_iterator_tag) { 602 size_type __len = distance(__first, __last); 603 if (__len < size()) 604 erase(copy(__first, __last, begin()), end()); 605 else { 606 _ForwardIterator __mid = __first; 607 advance(__mid, size()); 608 copy(__first, __mid, begin()); 609 insert(end(), __mid, __last); 610 } 611 } 612 613 void reserve(size_type __n) { 614 if (capacity() < __n) { 615 _Bit_type * __q = _M_bit_alloc(__n); 616 _M_finish = copy(begin(), end(), iterator(__q, 0)); 617 _M_deallocate(); 618 _M_start = iterator(__q, 0); 619 _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit; 620 } 621 } 622 623 reference front() { return *begin(); } 624 const_reference front() const { return *begin(); } 625 reference back() { return *(end() - 1); } 626 const_reference back() const { return *(end() - 1); } 627 void push_back(bool __x) { 628 if (_M_finish._M_p != _M_end_of_storage) 629 *_M_finish++ = __x; 630 else 631 _M_insert_aux(end(), __x); 632 } 633 void swap(vector<bool, _Alloc>& __x) { 634 std::swap(_M_start, __x._M_start); 635 std::swap(_M_finish, __x._M_finish); 636 std::swap(_M_end_of_storage, __x._M_end_of_storage); 637 } 638 iterator insert(iterator __position, bool __x = bool()) { 639 difference_type __n = __position - begin(); 640 if (_M_finish._M_p != _M_end_of_storage && __position == end()) 641 *_M_finish++ = __x; 642 else 643 _M_insert_aux(__position, __x); 644 return begin() + __n; 645 } 646 647 // Check whether it's an integral type. If so, it's not an iterator. 648 649 template <class _Integer> 650 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 651 __true_type) { 652 _M_fill_insert(__pos, __n, __x); 653 } 654 655 template <class _InputIterator> 656 void _M_insert_dispatch(iterator __pos, 657 _InputIterator __first, _InputIterator __last, 658 __false_type) { 659 _M_insert_range(__pos, __first, __last, __iterator_category(__first)); 660 } 661 662 template <class _InputIterator> 663 void insert(iterator __position, 664 _InputIterator __first, _InputIterator __last) { 665 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 666 _M_insert_dispatch(__position, __first, __last, _Integral()); 667 } 668 669 void _M_fill_insert(iterator __position, size_type __n, bool __x) { 670 if (__n == 0) return; 671 if (capacity() - size() >= __n) { 672 copy_backward(__position, end(), _M_finish + difference_type(__n)); 673 fill(__position, __position + difference_type(__n), __x); 674 _M_finish += difference_type(__n); 675 } 676 else { 677 size_type __len = size() + max(size(), __n); 678 _Bit_type * __q = _M_bit_alloc(__len); 679 iterator __i = copy(begin(), __position, iterator(__q, 0)); 680 fill_n(__i, __n, __x); 681 _M_finish = copy(__position, end(), __i + difference_type(__n)); 682 _M_deallocate(); 683 _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; 684 _M_start = iterator(__q, 0); 685 } 686 } 687 688 void insert(iterator __position, size_type __n, bool __x) { 689 _M_fill_insert(__position, __n, __x); 690 } 691 692 void pop_back() { --_M_finish; } 693 iterator erase(iterator __position) { 694 if (__position + 1 != end()) 695 copy(__position + 1, end(), __position); 696 --_M_finish; 697 return __position; 698 } 699 iterator erase(iterator __first, iterator __last) { 700 _M_finish = copy(__last, end(), __first); 701 return __first; 702 } 703 void resize(size_type __new_size, bool __x = bool()) { 704 if (__new_size < size()) 705 erase(begin() + difference_type(__new_size), end()); 706 else 707 insert(end(), __new_size - size(), __x); 708 } 709 void flip() { 710 for (_Bit_type * __p = _M_start._M_p; __p != _M_end_of_storage; ++__p) 711 *__p = ~*__p; 712 } 713 714 void clear() { erase(begin(), end()); } 715 }; 716 717 // This typedef is non-standard. It is provided for backward compatibility. 718 typedef vector<bool, __alloc> bit_vector; 719 720 } // namespace std 721 722 #endif /* __GLIBCPP_INTERNAL_BVECTOR_H */ 723 724 // Local Variables: 725 // mode:C++ 726 // End: 727