OSDN Git Service

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