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