1 // vector<bool> specialization -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 4 // 2011 Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996-1999 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file bits/stl_bvector.h 53 * This is an internal header file, included by other library headers. 54 * Do not attempt to use it directly. @headername{vector} 55 */ 56 57 #ifndef _STL_BVECTOR_H 58 #define _STL_BVECTOR_H 1 59 60 #include <initializer_list> 61 62 namespace std _GLIBCXX_VISIBILITY(default) 63 { 64 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 65 66 typedef unsigned long _Bit_type; 67 enum { _S_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 74 _Bit_reference(_Bit_type * __x, _Bit_type __y) 75 : _M_p(__x), _M_mask(__y) { } 76 77 _Bit_reference() : _M_p(0), _M_mask(0) { } 78 79 operator bool() const 80 { return !!(*_M_p & _M_mask); } 81 82 _Bit_reference& 83 operator=(bool __x) 84 { 85 if (__x) 86 *_M_p |= _M_mask; 87 else 88 *_M_p &= ~_M_mask; 89 return *this; 90 } 91 92 _Bit_reference& 93 operator=(const _Bit_reference& __x) 94 { return *this = bool(__x); } 95 96 bool 97 operator==(const _Bit_reference& __x) const 98 { return bool(*this) == bool(__x); } 99 100 bool 101 operator<(const _Bit_reference& __x) const 102 { return !bool(*this) && bool(__x); } 103 104 void 105 flip() 106 { *_M_p ^= _M_mask; } 107 }; 108 109 struct _Bit_iterator_base 110 : public std::iterator<std::random_access_iterator_tag, bool> 111 { 112 _Bit_type * _M_p; 113 unsigned int _M_offset; 114 115 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 116 : _M_p(__x), _M_offset(__y) { } 117 118 void 119 _M_bump_up() 120 { 121 if (_M_offset++ == int(_S_word_bit) - 1) 122 { 123 _M_offset = 0; 124 ++_M_p; 125 } 126 } 127 128 void 129 _M_bump_down() 130 { 131 if (_M_offset-- == 0) 132 { 133 _M_offset = int(_S_word_bit) - 1; 134 --_M_p; 135 } 136 } 137 138 void 139 _M_incr(ptrdiff_t __i) 140 { 141 difference_type __n = __i + _M_offset; 142 _M_p += __n / int(_S_word_bit); 143 __n = __n % int(_S_word_bit); 144 if (__n < 0) 145 { 146 __n += int(_S_word_bit); 147 --_M_p; 148 } 149 _M_offset = static_cast<unsigned int>(__n); 150 } 151 152 bool 153 operator==(const _Bit_iterator_base& __i) const 154 { return _M_p == __i._M_p && _M_offset == __i._M_offset; } 155 156 bool 157 operator<(const _Bit_iterator_base& __i) const 158 { 159 return _M_p < __i._M_p 160 || (_M_p == __i._M_p && _M_offset < __i._M_offset); 161 } 162 163 bool 164 operator!=(const _Bit_iterator_base& __i) const 165 { return !(*this == __i); } 166 167 bool 168 operator>(const _Bit_iterator_base& __i) const 169 { return __i < *this; } 170 171 bool 172 operator<=(const _Bit_iterator_base& __i) const 173 { return !(__i < *this); } 174 175 bool 176 operator>=(const _Bit_iterator_base& __i) const 177 { return !(*this < __i); } 178 }; 179 180 inline ptrdiff_t 181 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 182 { 183 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 184 + __x._M_offset - __y._M_offset); 185 } 186 187 struct _Bit_iterator : public _Bit_iterator_base 188 { 189 typedef _Bit_reference reference; 190 typedef _Bit_reference* pointer; 191 typedef _Bit_iterator iterator; 192 193 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 194 195 _Bit_iterator(_Bit_type * __x, unsigned int __y) 196 : _Bit_iterator_base(__x, __y) { } 197 198 reference 199 operator*() const 200 { return reference(_M_p, 1UL << _M_offset); } 201 202 iterator& 203 operator++() 204 { 205 _M_bump_up(); 206 return *this; 207 } 208 209 iterator 210 operator++(int) 211 { 212 iterator __tmp = *this; 213 _M_bump_up(); 214 return __tmp; 215 } 216 217 iterator& 218 operator--() 219 { 220 _M_bump_down(); 221 return *this; 222 } 223 224 iterator 225 operator--(int) 226 { 227 iterator __tmp = *this; 228 _M_bump_down(); 229 return __tmp; 230 } 231 232 iterator& 233 operator+=(difference_type __i) 234 { 235 _M_incr(__i); 236 return *this; 237 } 238 239 iterator& 240 operator-=(difference_type __i) 241 { 242 *this += -__i; 243 return *this; 244 } 245 246 iterator 247 operator+(difference_type __i) const 248 { 249 iterator __tmp = *this; 250 return __tmp += __i; 251 } 252 253 iterator 254 operator-(difference_type __i) const 255 { 256 iterator __tmp = *this; 257 return __tmp -= __i; 258 } 259 260 reference 261 operator[](difference_type __i) const 262 { return *(*this + __i); } 263 }; 264 265 inline _Bit_iterator 266 operator+(ptrdiff_t __n, const _Bit_iterator& __x) 267 { return __x + __n; } 268 269 struct _Bit_const_iterator : public _Bit_iterator_base 270 { 271 typedef bool reference; 272 typedef bool const_reference; 273 typedef const bool* pointer; 274 typedef _Bit_const_iterator const_iterator; 275 276 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 277 278 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 279 : _Bit_iterator_base(__x, __y) { } 280 281 _Bit_const_iterator(const _Bit_iterator& __x) 282 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 283 284 const_reference 285 operator*() const 286 { return _Bit_reference(_M_p, 1UL << _M_offset); } 287 288 const_iterator& 289 operator++() 290 { 291 _M_bump_up(); 292 return *this; 293 } 294 295 const_iterator 296 operator++(int) 297 { 298 const_iterator __tmp = *this; 299 _M_bump_up(); 300 return __tmp; 301 } 302 303 const_iterator& 304 operator--() 305 { 306 _M_bump_down(); 307 return *this; 308 } 309 310 const_iterator 311 operator--(int) 312 { 313 const_iterator __tmp = *this; 314 _M_bump_down(); 315 return __tmp; 316 } 317 318 const_iterator& 319 operator+=(difference_type __i) 320 { 321 _M_incr(__i); 322 return *this; 323 } 324 325 const_iterator& 326 operator-=(difference_type __i) 327 { 328 *this += -__i; 329 return *this; 330 } 331 332 const_iterator 333 operator+(difference_type __i) const 334 { 335 const_iterator __tmp = *this; 336 return __tmp += __i; 337 } 338 339 const_iterator 340 operator-(difference_type __i) const 341 { 342 const_iterator __tmp = *this; 343 return __tmp -= __i; 344 } 345 346 const_reference 347 operator[](difference_type __i) const 348 { return *(*this + __i); } 349 }; 350 351 inline _Bit_const_iterator 352 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) 353 { return __x + __n; } 354 355 inline void 356 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) 357 { 358 for (; __first != __last; ++__first) 359 *__first = __x; 360 } 361 362 inline void 363 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) 364 { 365 if (__first._M_p != __last._M_p) 366 { 367 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); 368 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); 369 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); 370 } 371 else 372 __fill_bvector(__first, __last, __x); 373 } 374 375 template<typename _Alloc> 376 struct _Bvector_base 377 { 378 typedef typename _Alloc::template rebind<_Bit_type>::other 379 _Bit_alloc_type; 380 381 struct _Bvector_impl 382 : public _Bit_alloc_type 383 { 384 _Bit_iterator _M_start; 385 _Bit_iterator _M_finish; 386 _Bit_type* _M_end_of_storage; 387 388 _Bvector_impl() 389 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0) 390 { } 391 392 _Bvector_impl(const _Bit_alloc_type& __a) 393 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) 394 { } 395 }; 396 397 public: 398 typedef _Alloc allocator_type; 399 400 _Bit_alloc_type& 401 _M_get_Bit_allocator() 402 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } 403 404 const _Bit_alloc_type& 405 _M_get_Bit_allocator() const 406 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } 407 408 allocator_type 409 get_allocator() const 410 { return allocator_type(_M_get_Bit_allocator()); } 411 412 _Bvector_base() 413 : _M_impl() { } 414 415 _Bvector_base(const allocator_type& __a) 416 : _M_impl(__a) { } 417 418 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 419 _Bvector_base(_Bvector_base&& __x) 420 : _M_impl(__x._M_get_Bit_allocator()) 421 { 422 this->_M_impl._M_start = __x._M_impl._M_start; 423 this->_M_impl._M_finish = __x._M_impl._M_finish; 424 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 425 __x._M_impl._M_start = _Bit_iterator(); 426 __x._M_impl._M_finish = _Bit_iterator(); 427 __x._M_impl._M_end_of_storage = 0; 428 } 429 #endif 430 431 ~_Bvector_base() 432 { this->_M_deallocate(); } 433 434 protected: 435 _Bvector_impl _M_impl; 436 437 _Bit_type* 438 _M_allocate(size_t __n) 439 { return _M_impl.allocate((__n + int(_S_word_bit) - 1) 440 / int(_S_word_bit)); } 441 442 void 443 _M_deallocate() 444 { 445 if (_M_impl._M_start._M_p) 446 _M_impl.deallocate(_M_impl._M_start._M_p, 447 _M_impl._M_end_of_storage - _M_impl._M_start._M_p); 448 } 449 }; 450 451 _GLIBCXX_END_NAMESPACE_CONTAINER 452 } // namespace std 453 454 // Declare a partial specialization of vector<T, Alloc>. 455 #include <bits/stl_vector.h> 456 457 namespace std _GLIBCXX_VISIBILITY(default) 458 { 459 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 460 461 /** 462 * @brief A specialization of vector for booleans which offers fixed time 463 * access to individual elements in any order. 464 * 465 * Note that vector<bool> does not actually meet the requirements for being 466 * a container. This is because the reference and pointer types are not 467 * really references and pointers to bool. See DR96 for details. @see 468 * vector for function documentation. 469 * 470 * @ingroup sequences 471 * 472 * In some terminology a %vector can be described as a dynamic 473 * C-style array, it offers fast and efficient access to individual 474 * elements in any order and saves the user from worrying about 475 * memory and size allocation. Subscripting ( @c [] ) access is 476 * also provided as with C-style arrays. 477 */ 478 template<typename _Alloc> 479 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 480 { 481 typedef _Bvector_base<_Alloc> _Base; 482 483 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 484 template<typename> friend class hash; 485 #endif 486 487 public: 488 typedef bool value_type; 489 typedef size_t size_type; 490 typedef ptrdiff_t difference_type; 491 typedef _Bit_reference reference; 492 typedef bool const_reference; 493 typedef _Bit_reference* pointer; 494 typedef const bool* const_pointer; 495 typedef _Bit_iterator iterator; 496 typedef _Bit_const_iterator const_iterator; 497 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 498 typedef std::reverse_iterator<iterator> reverse_iterator; 499 typedef _Alloc allocator_type; 500 501 allocator_type get_allocator() const 502 { return _Base::get_allocator(); } 503 504 protected: 505 using _Base::_M_allocate; 506 using _Base::_M_deallocate; 507 using _Base::_M_get_Bit_allocator; 508 509 public: 510 vector() 511 : _Base() { } 512 513 explicit 514 vector(const allocator_type& __a) 515 : _Base(__a) { } 516 517 explicit 518 vector(size_type __n, const bool& __value = bool(), 519 const allocator_type& __a = allocator_type()) 520 : _Base(__a) 521 { 522 _M_initialize(__n); 523 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 524 __value ? ~0 : 0); 525 } 526 527 vector(const vector& __x) 528 : _Base(__x._M_get_Bit_allocator()) 529 { 530 _M_initialize(__x.size()); 531 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 532 } 533 534 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 535 vector(vector&& __x) 536 : _Base(std::move(__x)) { } 537 538 vector(initializer_list<bool> __l, 539 const allocator_type& __a = allocator_type()) 540 : _Base(__a) 541 { 542 _M_initialize_range(__l.begin(), __l.end(), 543 random_access_iterator_tag()); 544 } 545 #endif 546 547 template<typename _InputIterator> 548 vector(_InputIterator __first, _InputIterator __last, 549 const allocator_type& __a = allocator_type()) 550 : _Base(__a) 551 { 552 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 553 _M_initialize_dispatch(__first, __last, _Integral()); 554 } 555 556 ~vector() { } 557 558 vector& 559 operator=(const vector& __x) 560 { 561 if (&__x == this) 562 return *this; 563 if (__x.size() > capacity()) 564 { 565 this->_M_deallocate(); 566 _M_initialize(__x.size()); 567 } 568 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 569 begin()); 570 return *this; 571 } 572 573 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 574 vector& 575 operator=(vector&& __x) 576 { 577 // NB: DR 1204. 578 // NB: DR 675. 579 this->clear(); 580 this->swap(__x); 581 return *this; 582 } 583 584 vector& 585 operator=(initializer_list<bool> __l) 586 { 587 this->assign (__l.begin(), __l.end()); 588 return *this; 589 } 590 #endif 591 592 // assign(), a generalized assignment member function. Two 593 // versions: one that takes a count, and one that takes a range. 594 // The range version is a member template, so we dispatch on whether 595 // or not the type is an integer. 596 void 597 assign(size_type __n, const bool& __x) 598 { _M_fill_assign(__n, __x); } 599 600 template<typename _InputIterator> 601 void 602 assign(_InputIterator __first, _InputIterator __last) 603 { 604 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 605 _M_assign_dispatch(__first, __last, _Integral()); 606 } 607 608 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 609 void 610 assign(initializer_list<bool> __l) 611 { this->assign(__l.begin(), __l.end()); } 612 #endif 613 614 iterator 615 begin() 616 { return this->_M_impl._M_start; } 617 618 const_iterator 619 begin() const 620 { return this->_M_impl._M_start; } 621 622 iterator 623 end() 624 { return this->_M_impl._M_finish; } 625 626 const_iterator 627 end() const 628 { return this->_M_impl._M_finish; } 629 630 reverse_iterator 631 rbegin() 632 { return reverse_iterator(end()); } 633 634 const_reverse_iterator 635 rbegin() const 636 { return const_reverse_iterator(end()); } 637 638 reverse_iterator 639 rend() 640 { return reverse_iterator(begin()); } 641 642 const_reverse_iterator 643 rend() const 644 { return const_reverse_iterator(begin()); } 645 646 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 647 const_iterator 648 cbegin() const 649 { return this->_M_impl._M_start; } 650 651 const_iterator 652 cend() const 653 { return this->_M_impl._M_finish; } 654 655 const_reverse_iterator 656 crbegin() const 657 { return const_reverse_iterator(end()); } 658 659 const_reverse_iterator 660 crend() const 661 { return const_reverse_iterator(begin()); } 662 #endif 663 664 size_type 665 size() const 666 { return size_type(end() - begin()); } 667 668 size_type 669 max_size() const 670 { 671 const size_type __isize = 672 __gnu_cxx::__numeric_traits<difference_type>::__max 673 - int(_S_word_bit) + 1; 674 const size_type __asize = _M_get_Bit_allocator().max_size(); 675 return (__asize <= __isize / int(_S_word_bit) 676 ? __asize * int(_S_word_bit) : __isize); 677 } 678 679 size_type 680 capacity() const 681 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) 682 - begin()); } 683 684 bool 685 empty() const 686 { return begin() == end(); } 687 688 reference 689 operator[](size_type __n) 690 { 691 return *iterator(this->_M_impl._M_start._M_p 692 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 693 } 694 695 const_reference 696 operator[](size_type __n) const 697 { 698 return *const_iterator(this->_M_impl._M_start._M_p 699 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 700 } 701 702 protected: 703 void 704 _M_range_check(size_type __n) const 705 { 706 if (__n >= this->size()) 707 __throw_out_of_range(__N("vector<bool>::_M_range_check")); 708 } 709 710 public: 711 reference 712 at(size_type __n) 713 { _M_range_check(__n); return (*this)[__n]; } 714 715 const_reference 716 at(size_type __n) const 717 { _M_range_check(__n); return (*this)[__n]; } 718 719 void 720 reserve(size_type __n); 721 722 reference 723 front() 724 { return *begin(); } 725 726 const_reference 727 front() const 728 { return *begin(); } 729 730 reference 731 back() 732 { return *(end() - 1); } 733 734 const_reference 735 back() const 736 { return *(end() - 1); } 737 738 // _GLIBCXX_RESOLVE_LIB_DEFECTS 739 // DR 464. Suggestion for new member functions in standard containers. 740 // N.B. DR 464 says nothing about vector<bool> but we need something 741 // here due to the way we are implementing DR 464 in the debug-mode 742 // vector class. 743 void 744 data() { } 745 746 void 747 push_back(bool __x) 748 { 749 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 750 *this->_M_impl._M_finish++ = __x; 751 else 752 _M_insert_aux(end(), __x); 753 } 754 755 void 756 swap(vector& __x) 757 { 758 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 759 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 760 std::swap(this->_M_impl._M_end_of_storage, 761 __x._M_impl._M_end_of_storage); 762 763 // _GLIBCXX_RESOLVE_LIB_DEFECTS 764 // 431. Swapping containers with unequal allocators. 765 std::__alloc_swap<typename _Base::_Bit_alloc_type>:: 766 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); 767 } 768 769 // [23.2.5]/1, third-to-last entry in synopsis listing 770 static void 771 swap(reference __x, reference __y) 772 { 773 bool __tmp = __x; 774 __x = __y; 775 __y = __tmp; 776 } 777 778 iterator 779 insert(iterator __position, const bool& __x = bool()) 780 { 781 const difference_type __n = __position - begin(); 782 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 783 && __position == end()) 784 *this->_M_impl._M_finish++ = __x; 785 else 786 _M_insert_aux(__position, __x); 787 return begin() + __n; 788 } 789 790 template<typename _InputIterator> 791 void 792 insert(iterator __position, 793 _InputIterator __first, _InputIterator __last) 794 { 795 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 796 _M_insert_dispatch(__position, __first, __last, _Integral()); 797 } 798 799 void 800 insert(iterator __position, size_type __n, const bool& __x) 801 { _M_fill_insert(__position, __n, __x); } 802 803 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 804 void insert(iterator __p, initializer_list<bool> __l) 805 { this->insert(__p, __l.begin(), __l.end()); } 806 #endif 807 808 void 809 pop_back() 810 { --this->_M_impl._M_finish; } 811 812 iterator 813 erase(iterator __position) 814 { 815 if (__position + 1 != end()) 816 std::copy(__position + 1, end(), __position); 817 --this->_M_impl._M_finish; 818 return __position; 819 } 820 821 iterator 822 erase(iterator __first, iterator __last) 823 { 824 if (__first != __last) 825 _M_erase_at_end(std::copy(__last, end(), __first)); 826 return __first; 827 } 828 829 void 830 resize(size_type __new_size, bool __x = bool()) 831 { 832 if (__new_size < size()) 833 _M_erase_at_end(begin() + difference_type(__new_size)); 834 else 835 insert(end(), __new_size - size(), __x); 836 } 837 838 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 839 void 840 shrink_to_fit() 841 { std::__shrink_to_fit<vector>::_S_do_it(*this); } 842 #endif 843 844 void 845 flip() 846 { 847 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 848 __p != this->_M_impl._M_end_of_storage; ++__p) 849 *__p = ~*__p; 850 } 851 852 void 853 clear() 854 { _M_erase_at_end(begin()); } 855 856 857 protected: 858 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 859 iterator 860 _M_copy_aligned(const_iterator __first, const_iterator __last, 861 iterator __result) 862 { 863 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 864 return std::copy(const_iterator(__last._M_p, 0), __last, 865 iterator(__q, 0)); 866 } 867 868 void 869 _M_initialize(size_type __n) 870 { 871 _Bit_type* __q = this->_M_allocate(__n); 872 this->_M_impl._M_end_of_storage = (__q 873 + ((__n + int(_S_word_bit) - 1) 874 / int(_S_word_bit))); 875 this->_M_impl._M_start = iterator(__q, 0); 876 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 877 } 878 879 // Check whether it's an integral type. If so, it's not an iterator. 880 881 // _GLIBCXX_RESOLVE_LIB_DEFECTS 882 // 438. Ambiguity in the "do the right thing" clause 883 template<typename _Integer> 884 void 885 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 886 { 887 _M_initialize(static_cast<size_type>(__n)); 888 std::fill(this->_M_impl._M_start._M_p, 889 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 890 } 891 892 template<typename _InputIterator> 893 void 894 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 895 __false_type) 896 { _M_initialize_range(__first, __last, 897 std::__iterator_category(__first)); } 898 899 template<typename _InputIterator> 900 void 901 _M_initialize_range(_InputIterator __first, _InputIterator __last, 902 std::input_iterator_tag) 903 { 904 for (; __first != __last; ++__first) 905 push_back(*__first); 906 } 907 908 template<typename _ForwardIterator> 909 void 910 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 911 std::forward_iterator_tag) 912 { 913 const size_type __n = std::distance(__first, __last); 914 _M_initialize(__n); 915 std::copy(__first, __last, this->_M_impl._M_start); 916 } 917 918 // _GLIBCXX_RESOLVE_LIB_DEFECTS 919 // 438. Ambiguity in the "do the right thing" clause 920 template<typename _Integer> 921 void 922 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 923 { _M_fill_assign(__n, __val); } 924 925 template<class _InputIterator> 926 void 927 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 928 __false_type) 929 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 930 931 void 932 _M_fill_assign(size_t __n, bool __x) 933 { 934 if (__n > size()) 935 { 936 std::fill(this->_M_impl._M_start._M_p, 937 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 938 insert(end(), __n - size(), __x); 939 } 940 else 941 { 942 _M_erase_at_end(begin() + __n); 943 std::fill(this->_M_impl._M_start._M_p, 944 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 945 } 946 } 947 948 template<typename _InputIterator> 949 void 950 _M_assign_aux(_InputIterator __first, _InputIterator __last, 951 std::input_iterator_tag) 952 { 953 iterator __cur = begin(); 954 for (; __first != __last && __cur != end(); ++__cur, ++__first) 955 *__cur = *__first; 956 if (__first == __last) 957 _M_erase_at_end(__cur); 958 else 959 insert(end(), __first, __last); 960 } 961 962 template<typename _ForwardIterator> 963 void 964 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 965 std::forward_iterator_tag) 966 { 967 const size_type __len = std::distance(__first, __last); 968 if (__len < size()) 969 _M_erase_at_end(std::copy(__first, __last, begin())); 970 else 971 { 972 _ForwardIterator __mid = __first; 973 std::advance(__mid, size()); 974 std::copy(__first, __mid, begin()); 975 insert(end(), __mid, __last); 976 } 977 } 978 979 // Check whether it's an integral type. If so, it's not an iterator. 980 981 // _GLIBCXX_RESOLVE_LIB_DEFECTS 982 // 438. Ambiguity in the "do the right thing" clause 983 template<typename _Integer> 984 void 985 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 986 __true_type) 987 { _M_fill_insert(__pos, __n, __x); } 988 989 template<typename _InputIterator> 990 void 991 _M_insert_dispatch(iterator __pos, 992 _InputIterator __first, _InputIterator __last, 993 __false_type) 994 { _M_insert_range(__pos, __first, __last, 995 std::__iterator_category(__first)); } 996 997 void 998 _M_fill_insert(iterator __position, size_type __n, bool __x); 999 1000 template<typename _InputIterator> 1001 void 1002 _M_insert_range(iterator __pos, _InputIterator __first, 1003 _InputIterator __last, std::input_iterator_tag) 1004 { 1005 for (; __first != __last; ++__first) 1006 { 1007 __pos = insert(__pos, *__first); 1008 ++__pos; 1009 } 1010 } 1011 1012 template<typename _ForwardIterator> 1013 void 1014 _M_insert_range(iterator __position, _ForwardIterator __first, 1015 _ForwardIterator __last, std::forward_iterator_tag); 1016 1017 void 1018 _M_insert_aux(iterator __position, bool __x); 1019 1020 size_type 1021 _M_check_len(size_type __n, const char* __s) const 1022 { 1023 if (max_size() - size() < __n) 1024 __throw_length_error(__N(__s)); 1025 1026 const size_type __len = size() + std::max(size(), __n); 1027 return (__len < size() || __len > max_size()) ? max_size() : __len; 1028 } 1029 1030 void 1031 _M_erase_at_end(iterator __pos) 1032 { this->_M_impl._M_finish = __pos; } 1033 }; 1034 1035 _GLIBCXX_END_NAMESPACE_CONTAINER 1036 } // namespace std 1037 1038 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1039 1040 #include <bits/functional_hash.h> 1041 1042 namespace std _GLIBCXX_VISIBILITY(default) 1043 { 1044 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1045 1046 // DR 1182. 1047 /// std::hash specialization for vector<bool>. 1048 template<typename _Alloc> 1049 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 1050 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 1051 { 1052 size_t 1053 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 1054 }; 1055 1056 _GLIBCXX_END_NAMESPACE_VERSION 1057 }// namespace std 1058 1059 #endif // __GXX_EXPERIMENTAL_CXX0X__ 1060 1061 #endif 1062
