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 */ 473template<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#ifdef __GXX_EXPERIMENTAL_CXX0X__ 747 swap(vector&& __x) 748#else 749 swap(vector& __x) 750#endif 751 { 752 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 753 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 754 std::swap(this->_M_impl._M_end_of_storage, 755 __x._M_impl._M_end_of_storage); 756 757 // _GLIBCXX_RESOLVE_LIB_DEFECTS 758 // 431. Swapping containers with unequal allocators. 759 std::__alloc_swap<typename _Base::_Bit_alloc_type>:: 760 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); 761 } 762 763 // [23.2.5]/1, third-to-last entry in synopsis listing 764 static void 765 swap(reference __x, reference __y) 766 { 767 bool __tmp = __x; 768 __x = __y; 769 __y = __tmp; 770 } 771 772 iterator 773 insert(iterator __position, const bool& __x = bool()) 774 { 775 const difference_type __n = __position - begin(); 776 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 777 && __position == end()) 778 *this->_M_impl._M_finish++ = __x; 779 else 780 _M_insert_aux(__position, __x); 781 return begin() + __n; 782 } 783 784 template<typename _InputIterator> 785 void 786 insert(iterator __position, 787 _InputIterator __first, _InputIterator __last) 788 { 789 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 790 _M_insert_dispatch(__position, __first, __last, _Integral()); 791 } 792 793 void 794 insert(iterator __position, size_type __n, const bool& __x) 795 { _M_fill_insert(__position, __n, __x); } 796 797#ifdef __GXX_EXPERIMENTAL_CXX0X__ 798 void insert(iterator __p, initializer_list<bool> __l) 799 { this->insert(__p, __l.begin(), __l.end()); } 800#endif 801 802 void 803 pop_back() 804 { --this->_M_impl._M_finish; } 805 806 iterator 807 erase(iterator __position) 808 { 809 if (__position + 1 != end()) 810 std::copy(__position + 1, end(), __position); 811 --this->_M_impl._M_finish; 812 return __position; 813 } 814 815 iterator 816 erase(iterator __first, iterator __last) 817 { 818 _M_erase_at_end(std::copy(__last, end(), __first)); 819 return __first; 820 } 821 822 void 823 resize(size_type __new_size, bool __x = bool()) 824 { 825 if (__new_size < size()) 826 _M_erase_at_end(begin() + difference_type(__new_size)); 827 else 828 insert(end(), __new_size - size(), __x); 829 } 830 831 void 832 flip() 833 { 834 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 835 __p != this->_M_impl._M_end_of_storage; ++__p) 836 *__p = ~*__p; 837 } 838 839 void 840 clear() 841 { _M_erase_at_end(begin()); } 842 843 844 protected: 845 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 846 iterator 847 _M_copy_aligned(const_iterator __first, const_iterator __last, 848 iterator __result) 849 { 850 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 851 return std::copy(const_iterator(__last._M_p, 0), __last, 852 iterator(__q, 0)); 853 } 854 855 void 856 _M_initialize(size_type __n) 857 { 858 _Bit_type* __q = this->_M_allocate(__n); 859 this->_M_impl._M_end_of_storage = (__q 860 + ((__n + int(_S_word_bit) - 1) 861 / int(_S_word_bit))); 862 this->_M_impl._M_start = iterator(__q, 0); 863 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 864 } 865 866 // Check whether it's an integral type. If so, it's not an iterator. 867 868 // _GLIBCXX_RESOLVE_LIB_DEFECTS 869 // 438. Ambiguity in the "do the right thing" clause 870 template<typename _Integer> 871 void 872 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 873 { 874 _M_initialize(static_cast<size_type>(__n)); 875 std::fill(this->_M_impl._M_start._M_p, 876 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 877 } 878 879 template<typename _InputIterator> 880 void 881 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 882 __false_type) 883 { _M_initialize_range(__first, __last, 884 std::__iterator_category(__first)); } 885 886 template<typename _InputIterator> 887 void 888 _M_initialize_range(_InputIterator __first, _InputIterator __last, 889 std::input_iterator_tag) 890 { 891 for (; __first != __last; ++__first) 892 push_back(*__first); 893 } 894 895 template<typename _ForwardIterator> 896 void 897 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 898 std::forward_iterator_tag) 899 { 900 const size_type __n = std::distance(__first, __last); 901 _M_initialize(__n); 902 std::copy(__first, __last, this->_M_impl._M_start); 903 } 904 905 // _GLIBCXX_RESOLVE_LIB_DEFECTS 906 // 438. Ambiguity in the "do the right thing" clause 907 template<typename _Integer> 908 void 909 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 910 { _M_fill_assign(__n, __val); } 911 912 template<class _InputIterator> 913 void 914 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 915 __false_type) 916 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 917 918 void 919 _M_fill_assign(size_t __n, bool __x) 920 { 921 if (__n > size()) 922 { 923 std::fill(this->_M_impl._M_start._M_p, 924 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 925 insert(end(), __n - size(), __x); 926 } 927 else 928 { 929 _M_erase_at_end(begin() + __n); 930 std::fill(this->_M_impl._M_start._M_p, 931 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 932 } 933 } 934 935 template<typename _InputIterator> 936 void 937 _M_assign_aux(_InputIterator __first, _InputIterator __last, 938 std::input_iterator_tag) 939 { 940 iterator __cur = begin(); 941 for (; __first != __last && __cur != end(); ++__cur, ++__first) 942 *__cur = *__first; 943 if (__first == __last) 944 _M_erase_at_end(__cur); 945 else 946 insert(end(), __first, __last); 947 } 948 949 template<typename _ForwardIterator> 950 void 951 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 952 std::forward_iterator_tag) 953 { 954 const size_type __len = std::distance(__first, __last); 955 if (__len < size()) 956 _M_erase_at_end(std::copy(__first, __last, begin())); 957 else 958 { 959 _ForwardIterator __mid = __first; 960 std::advance(__mid, size()); 961 std::copy(__first, __mid, begin()); 962 insert(end(), __mid, __last); 963 } 964 } 965 966 // Check whether it's an integral type. If so, it's not an iterator. 967 968 // _GLIBCXX_RESOLVE_LIB_DEFECTS 969 // 438. Ambiguity in the "do the right thing" clause 970 template<typename _Integer> 971 void 972 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 973 __true_type) 974 { _M_fill_insert(__pos, __n, __x); } 975 976 template<typename _InputIterator> 977 void 978 _M_insert_dispatch(iterator __pos, 979 _InputIterator __first, _InputIterator __last, 980 __false_type) 981 { _M_insert_range(__pos, __first, __last, 982 std::__iterator_category(__first)); } 983 984 void 985 _M_fill_insert(iterator __position, size_type __n, bool __x); 986 987 template<typename _InputIterator> 988 void 989 _M_insert_range(iterator __pos, _InputIterator __first, 990 _InputIterator __last, std::input_iterator_tag) 991 { 992 for (; __first != __last; ++__first) 993 { 994 __pos = insert(__pos, *__first); 995 ++__pos; 996 } 997 } 998 999 template<typename _ForwardIterator> 1000 void 1001 _M_insert_range(iterator __position, _ForwardIterator __first, 1002 _ForwardIterator __last, std::forward_iterator_tag); 1003 1004 void 1005 _M_insert_aux(iterator __position, bool __x); 1006 1007 size_type 1008 _M_check_len(size_type __n, const char* __s) const 1009 { 1010 if (max_size() - size() < __n) 1011 __throw_length_error(__N(__s)); 1012 1013 const size_type __len = size() + std::max(size(), __n); 1014 return (__len < size() || __len > max_size()) ? max_size() : __len; 1015 } 1016 1017 void 1018 _M_erase_at_end(iterator __pos) 1019 { this->_M_impl._M_finish = __pos; } 1020 }; 1021 1022_GLIBCXX_END_NESTED_NAMESPACE 1023 1024#endif 1025