1 // vector<bool> specialization -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 public: 479 typedef bool value_type; 480 typedef size_t size_type; 481 typedef ptrdiff_t difference_type; 482 typedef _Bit_reference reference; 483 typedef bool const_reference; 484 typedef _Bit_reference* pointer; 485 typedef const bool* const_pointer; 486 typedef _Bit_iterator iterator; 487 typedef _Bit_const_iterator const_iterator; 488 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 489 typedef std::reverse_iterator<iterator> reverse_iterator; 490 typedef _Alloc allocator_type; 491 492 allocator_type get_allocator() const 493 { return _Base::get_allocator(); } 494 495 protected: 496 using _Base::_M_allocate; 497 using _Base::_M_deallocate; 498 using _Base::_M_get_Bit_allocator; 499 500 public: 501 vector() 502 : _Base() { } 503 504 explicit 505 vector(const allocator_type& __a) 506 : _Base(__a) { } 507 508 explicit 509 vector(size_type __n, const bool& __value = bool(), 510 const allocator_type& __a = allocator_type()) 511 : _Base(__a) 512 { 513 _M_initialize(__n); 514 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 515 __value ? ~0 : 0); 516 } 517 518 vector(const vector& __x) 519 : _Base(__x._M_get_Bit_allocator()) 520 { 521 _M_initialize(__x.size()); 522 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 523 } 524 525 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 526 vector(vector&& __x) 527 : _Base(std::forward<_Base>(__x)) { } 528 529 vector(initializer_list<bool> __l, 530 const allocator_type& __a = allocator_type()) 531 : _Base(__a) 532 { 533 _M_initialize_range(__l.begin(), __l.end(), 534 random_access_iterator_tag()); 535 } 536 #endif 537 538 template<typename _InputIterator> 539 vector(_InputIterator __first, _InputIterator __last, 540 const allocator_type& __a = allocator_type()) 541 : _Base(__a) 542 { 543 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 544 _M_initialize_dispatch(__first, __last, _Integral()); 545 } 546 547 ~vector() { } 548 549 vector& 550 operator=(const vector& __x) 551 { 552 if (&__x == this) 553 return *this; 554 if (__x.size() > capacity()) 555 { 556 this->_M_deallocate(); 557 _M_initialize(__x.size()); 558 } 559 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 560 begin()); 561 return *this; 562 } 563 564 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 565 vector& 566 operator=(vector&& __x) 567 { 568 // NB: DR 675. 569 this->clear(); 570 this->swap(__x); 571 return *this; 572 } 573 574 vector& 575 operator=(initializer_list<bool> __l) 576 { 577 this->assign (__l.begin(), __l.end()); 578 return *this; 579 } 580 #endif 581 582 // assign(), a generalized assignment member function. Two 583 // versions: one that takes a count, and one that takes a range. 584 // The range version is a member template, so we dispatch on whether 585 // or not the type is an integer. 586 void 587 assign(size_type __n, const bool& __x) 588 { _M_fill_assign(__n, __x); } 589 590 template<typename _InputIterator> 591 void 592 assign(_InputIterator __first, _InputIterator __last) 593 { 594 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 595 _M_assign_dispatch(__first, __last, _Integral()); 596 } 597 598 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 599 void 600 assign(initializer_list<bool> __l) 601 { this->assign(__l.begin(), __l.end()); } 602 #endif 603 604 iterator 605 begin() 606 { return this->_M_impl._M_start; } 607 608 const_iterator 609 begin() const 610 { return this->_M_impl._M_start; } 611 612 iterator 613 end() 614 { return this->_M_impl._M_finish; } 615 616 const_iterator 617 end() const 618 { return this->_M_impl._M_finish; } 619 620 reverse_iterator 621 rbegin() 622 { return reverse_iterator(end()); } 623 624 const_reverse_iterator 625 rbegin() const 626 { return const_reverse_iterator(end()); } 627 628 reverse_iterator 629 rend() 630 { return reverse_iterator(begin()); } 631 632 const_reverse_iterator 633 rend() const 634 { return const_reverse_iterator(begin()); } 635 636 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 637 const_iterator 638 cbegin() const 639 { return this->_M_impl._M_start; } 640 641 const_iterator 642 cend() const 643 { return this->_M_impl._M_finish; } 644 645 const_reverse_iterator 646 crbegin() const 647 { return const_reverse_iterator(end()); } 648 649 const_reverse_iterator 650 crend() const 651 { return const_reverse_iterator(begin()); } 652 #endif 653 654 size_type 655 size() const 656 { return size_type(end() - begin()); } 657 658 size_type 659 max_size() const 660 { 661 const size_type __isize = 662 __gnu_cxx::__numeric_traits<difference_type>::__max 663 - int(_S_word_bit) + 1; 664 const size_type __asize = _M_get_Bit_allocator().max_size(); 665 return (__asize <= __isize / int(_S_word_bit) 666 ? __asize * int(_S_word_bit) : __isize); 667 } 668 669 size_type 670 capacity() const 671 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) 672 - begin()); } 673 674 bool 675 empty() const 676 { return begin() == end(); } 677 678 reference 679 operator[](size_type __n) 680 { 681 return *iterator(this->_M_impl._M_start._M_p 682 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 683 } 684 685 const_reference 686 operator[](size_type __n) const 687 { 688 return *const_iterator(this->_M_impl._M_start._M_p 689 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 690 } 691 692 protected: 693 void 694 _M_range_check(size_type __n) const 695 { 696 if (__n >= this->size()) 697 __throw_out_of_range(__N("vector<bool>::_M_range_check")); 698 } 699 700 public: 701 reference 702 at(size_type __n) 703 { _M_range_check(__n); return (*this)[__n]; } 704 705 const_reference 706 at(size_type __n) const 707 { _M_range_check(__n); return (*this)[__n]; } 708 709 void 710 reserve(size_type __n); 711 712 reference 713 front() 714 { return *begin(); } 715 716 const_reference 717 front() const 718 { return *begin(); } 719 720 reference 721 back() 722 { return *(end() - 1); } 723 724 const_reference 725 back() const 726 { return *(end() - 1); } 727 728 // _GLIBCXX_RESOLVE_LIB_DEFECTS 729 // DR 464. Suggestion for new member functions in standard containers. 730 // N.B. DR 464 says nothing about vector<bool> but we need something 731 // here due to the way we are implementing DR 464 in the debug-mode 732 // vector class. 733 void 734 data() { } 735 736 void 737 push_back(bool __x) 738 { 739 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 740 *this->_M_impl._M_finish++ = __x; 741 else 742 _M_insert_aux(end(), __x); 743 } 744 745 void 746 swap(vector& __x) 747 { 748 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 749 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 750 std::swap(this->_M_impl._M_end_of_storage, 751 __x._M_impl._M_end_of_storage); 752 753 // _GLIBCXX_RESOLVE_LIB_DEFECTS 754 // 431. Swapping containers with unequal allocators. 755 std::__alloc_swap<typename _Base::_Bit_alloc_type>:: 756 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); 757 } 758 759 // [23.2.5]/1, third-to-last entry in synopsis listing 760 static void 761 swap(reference __x, reference __y) 762 { 763 bool __tmp = __x; 764 __x = __y; 765 __y = __tmp; 766 } 767 768 iterator 769 insert(iterator __position, const bool& __x = bool()) 770 { 771 const difference_type __n = __position - begin(); 772 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 773 && __position == end()) 774 *this->_M_impl._M_finish++ = __x; 775 else 776 _M_insert_aux(__position, __x); 777 return begin() + __n; 778 } 779 780 template<typename _InputIterator> 781 void 782 insert(iterator __position, 783 _InputIterator __first, _InputIterator __last) 784 { 785 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 786 _M_insert_dispatch(__position, __first, __last, _Integral()); 787 } 788 789 void 790 insert(iterator __position, size_type __n, const bool& __x) 791 { _M_fill_insert(__position, __n, __x); } 792 793 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 794 void insert(iterator __p, initializer_list<bool> __l) 795 { this->insert(__p, __l.begin(), __l.end()); } 796 #endif 797 798 void 799 pop_back() 800 { --this->_M_impl._M_finish; } 801 802 iterator 803 erase(iterator __position) 804 { 805 if (__position + 1 != end()) 806 std::copy(__position + 1, end(), __position); 807 --this->_M_impl._M_finish; 808 return __position; 809 } 810 811 iterator 812 erase(iterator __first, iterator __last) 813 { 814 _M_erase_at_end(std::copy(__last, end(), __first)); 815 return __first; 816 } 817 818 void 819 resize(size_type __new_size, bool __x = bool()) 820 { 821 if (__new_size < size()) 822 _M_erase_at_end(begin() + difference_type(__new_size)); 823 else 824 insert(end(), __new_size - size(), __x); 825 } 826 827 void 828 flip() 829 { 830 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 831 __p != this->_M_impl._M_end_of_storage; ++__p) 832 *__p = ~*__p; 833 } 834 835 void 836 clear() 837 { _M_erase_at_end(begin()); } 838 839 840 protected: 841 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 842 iterator 843 _M_copy_aligned(const_iterator __first, const_iterator __last, 844 iterator __result) 845 { 846 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 847 return std::copy(const_iterator(__last._M_p, 0), __last, 848 iterator(__q, 0)); 849 } 850 851 void 852 _M_initialize(size_type __n) 853 { 854 _Bit_type* __q = this->_M_allocate(__n); 855 this->_M_impl._M_end_of_storage = (__q 856 + ((__n + int(_S_word_bit) - 1) 857 / int(_S_word_bit))); 858 this->_M_impl._M_start = iterator(__q, 0); 859 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 860 } 861 862 // Check whether it's an integral type. If so, it's not an iterator. 863 864 // _GLIBCXX_RESOLVE_LIB_DEFECTS 865 // 438. Ambiguity in the "do the right thing" clause 866 template<typename _Integer> 867 void 868 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 869 { 870 _M_initialize(static_cast<size_type>(__n)); 871 std::fill(this->_M_impl._M_start._M_p, 872 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 873 } 874 875 template<typename _InputIterator> 876 void 877 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 878 __false_type) 879 { _M_initialize_range(__first, __last, 880 std::__iterator_category(__first)); } 881 882 template<typename _InputIterator> 883 void 884 _M_initialize_range(_InputIterator __first, _InputIterator __last, 885 std::input_iterator_tag) 886 { 887 for (; __first != __last; ++__first) 888 push_back(*__first); 889 } 890 891 template<typename _ForwardIterator> 892 void 893 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 894 std::forward_iterator_tag) 895 { 896 const size_type __n = std::distance(__first, __last); 897 _M_initialize(__n); 898 std::copy(__first, __last, this->_M_impl._M_start); 899 } 900 901 // _GLIBCXX_RESOLVE_LIB_DEFECTS 902 // 438. Ambiguity in the "do the right thing" clause 903 template<typename _Integer> 904 void 905 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 906 { _M_fill_assign(__n, __val); } 907 908 template<class _InputIterator> 909 void 910 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 911 __false_type) 912 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 913 914 void 915 _M_fill_assign(size_t __n, bool __x) 916 { 917 if (__n > size()) 918 { 919 std::fill(this->_M_impl._M_start._M_p, 920 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 921 insert(end(), __n - size(), __x); 922 } 923 else 924 { 925 _M_erase_at_end(begin() + __n); 926 std::fill(this->_M_impl._M_start._M_p, 927 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 928 } 929 } 930 931 template<typename _InputIterator> 932 void 933 _M_assign_aux(_InputIterator __first, _InputIterator __last, 934 std::input_iterator_tag) 935 { 936 iterator __cur = begin(); 937 for (; __first != __last && __cur != end(); ++__cur, ++__first) 938 *__cur = *__first; 939 if (__first == __last) 940 _M_erase_at_end(__cur); 941 else 942 insert(end(), __first, __last); 943 } 944 945 template<typename _ForwardIterator> 946 void 947 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 948 std::forward_iterator_tag) 949 { 950 const size_type __len = std::distance(__first, __last); 951 if (__len < size()) 952 _M_erase_at_end(std::copy(__first, __last, begin())); 953 else 954 { 955 _ForwardIterator __mid = __first; 956 std::advance(__mid, size()); 957 std::copy(__first, __mid, begin()); 958 insert(end(), __mid, __last); 959 } 960 } 961 962 // Check whether it's an integral type. If so, it's not an iterator. 963 964 // _GLIBCXX_RESOLVE_LIB_DEFECTS 965 // 438. Ambiguity in the "do the right thing" clause 966 template<typename _Integer> 967 void 968 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 969 __true_type) 970 { _M_fill_insert(__pos, __n, __x); } 971 972 template<typename _InputIterator> 973 void 974 _M_insert_dispatch(iterator __pos, 975 _InputIterator __first, _InputIterator __last, 976 __false_type) 977 { _M_insert_range(__pos, __first, __last, 978 std::__iterator_category(__first)); } 979 980 void 981 _M_fill_insert(iterator __position, size_type __n, bool __x); 982 983 template<typename _InputIterator> 984 void 985 _M_insert_range(iterator __pos, _InputIterator __first, 986 _InputIterator __last, std::input_iterator_tag) 987 { 988 for (; __first != __last; ++__first) 989 { 990 __pos = insert(__pos, *__first); 991 ++__pos; 992 } 993 } 994 995 template<typename _ForwardIterator> 996 void 997 _M_insert_range(iterator __position, _ForwardIterator __first, 998 _ForwardIterator __last, std::forward_iterator_tag); 999 1000 void 1001 _M_insert_aux(iterator __position, bool __x); 1002 1003 size_type 1004 _M_check_len(size_type __n, const char* __s) const 1005 { 1006 if (max_size() - size() < __n) 1007 __throw_length_error(__N(__s)); 1008 1009 const size_type __len = size() + std::max(size(), __n); 1010 return (__len < size() || __len > max_size()) ? max_size() : __len; 1011 } 1012 1013 void 1014 _M_erase_at_end(iterator __pos) 1015 { this->_M_impl._M_finish = __pos; } 1016 }; 1017 1018 _GLIBCXX_END_NESTED_NAMESPACE 1019 1020 #endif 1021