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