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