OSDN Git Service

2011-12-10 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / tr2 / dynamic_bitset
1 // TR2 <dynamic_bitset> -*- C++ -*-
2
3 // Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file tr2/dynamic_bitset
26  *  This is a TR2 C++ Library header.
27  */
28
29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
31
32 #pragma GCC system_header
33
34 #include <limits>
35 #include <vector>
36 #include <cstddef> // For size_t
37 #include <string>
38 #include <memory> // For std::allocator
39 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
40                                 // overflow_error
41 #include <iosfwd>
42 #include <cxxabi_forced.h>
43
44 namespace std _GLIBCXX_VISIBILITY(default)
45 {
46 namespace tr2
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49
50   /**
51    *  Dynamic Bitset.
52    *
53    *  See N2050,
54    *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
55    */
56 namespace __detail
57 {
58
59 template<typename T>
60 class _Bool2UChar
61 {
62   typedef T type;
63 };
64
65 template<>
66 class _Bool2UChar<bool>
67 {
68 public:
69   typedef unsigned char type;
70 };
71
72 }
73
74   /**
75    *  Base class, general case.
76    *
77    *  See documentation for dynamic_bitset.
78    */
79   template<typename _WordT = unsigned long long,
80            typename _Alloc = std::allocator<_WordT>>
81     struct __dynamic_bitset_base
82     {
83       static_assert(std::is_unsigned<_WordT>::value, "template argument "
84                     "_WordT not an unsigned integral type");
85
86       typedef _WordT block_type;
87       typedef _Alloc allocator_type;
88       typedef size_t size_type;
89
90       static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
91       static const size_type npos = static_cast<size_type>(-1);
92
93       /// 0 is the least significant word.
94       std::vector<block_type, allocator_type> _M_w;
95
96       explicit
97       __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
98       : _M_w(__alloc)
99       { }
100
101       explicit
102       __dynamic_bitset_base(__dynamic_bitset_base&& __b)
103       { this->_M_w.swap(__b._M_w); }
104
105       explicit
106       __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
107                            const allocator_type& __alloc = allocator_type())
108       : _M_w(__nbits / _S_bits_per_block
109              + (__nbits % _S_bits_per_block > 0),
110              __val, __alloc)
111       {
112         unsigned long long __mask = ~static_cast<block_type>(0);
113         size_t __n = std::min(this->_M_w.size(),
114                               sizeof(unsigned long long) / sizeof(block_type));
115         for (size_t __i = 0; __i < __n; ++__i)
116           {
117             this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
118             __mask <<= _S_bits_per_block;
119           }
120       }
121
122       void
123       _M_assign(const __dynamic_bitset_base& __b)
124       { this->_M_w = __b._M_w; }
125
126       void
127       _M_swap(__dynamic_bitset_base& __b)
128       { this->_M_w.swap(__b._M_w); }
129
130       void
131       _M_clear()
132       { this->_M_w.clear(); }
133
134       void
135       _M_resize(size_t __nbits, bool __value)
136       {
137         size_t __sz = __nbits / _S_bits_per_block;
138         if (__nbits % _S_bits_per_block > 0)
139           ++__sz;
140         if (__sz != this->_M_w.size())
141           this->_M_w.resize(__sz);
142       }
143
144       allocator_type
145       _M_get_allocator() const
146       { return this->_M_w.get_allocator(); }
147
148       static size_type
149       _S_whichword(size_type __pos)
150       { return __pos / _S_bits_per_block; }
151
152       static size_type
153       _S_whichbyte(size_type __pos)
154       { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
155
156       static size_type
157       _S_whichbit(size_type __pos)
158       { return __pos % _S_bits_per_block; }
159
160       static block_type
161       _S_maskbit(size_type __pos)
162       { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
163
164       block_type&
165       _M_getword(size_type __pos)
166       { return this->_M_w[_S_whichword(__pos)]; }
167
168       block_type
169       _M_getword(size_type __pos) const
170       { return this->_M_w[_S_whichword(__pos)]; }
171
172       block_type&
173       _M_hiword()
174       { return this->_M_w[_M_w.size() - 1]; }
175
176       block_type
177       _M_hiword() const
178       { return this->_M_w[_M_w.size() - 1]; }
179
180       void
181       _M_do_and(const __dynamic_bitset_base& __x)
182       {
183         if (__x._M_w.size() == this->_M_w.size())
184           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
185             this->_M_w[__i] &= __x._M_w[__i];
186         else
187           return;
188       }
189
190       void
191       _M_do_or(const __dynamic_bitset_base& __x)
192       {
193         if (__x._M_w.size() == this->_M_w.size())
194           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
195             this->_M_w[__i] |= __x._M_w[__i];
196         else
197           return;
198       }
199
200       void
201       _M_do_xor(const __dynamic_bitset_base& __x)
202       {
203         if (__x._M_w.size() == this->_M_w.size())
204           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
205             this->_M_w[__i] ^= __x._M_w[__i];
206         else
207           return;
208       }
209
210       void
211       _M_do_dif(const __dynamic_bitset_base& __x)
212       {
213         if (__x._M_w.size() == this->_M_w.size())
214           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
215             this->_M_w[__i] &= ~__x._M_w[__i];
216         else
217           return;
218       }
219
220       void
221       _M_do_left_shift(size_t __shift);
222
223       void
224       _M_do_right_shift(size_t __shift);
225
226       void
227       _M_do_flip()
228       {
229         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
230           this->_M_w[__i] = ~this->_M_w[__i];
231       }
232
233       void
234       _M_do_set()
235       {
236         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
237           this->_M_w[__i] = ~static_cast<block_type>(0);
238       }
239
240       void
241       _M_do_reset()
242       {
243         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
244           this->_M_w[__i] = static_cast<block_type>(0);
245       }
246
247       bool
248       _M_is_equal(const __dynamic_bitset_base& __x) const
249       {
250         if (__x.size() == this->size())
251           {
252             for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
253               if (this->_M_w[__i] != __x._M_w[__i])
254                 return false;
255             return true;
256           }
257         else
258           return false;
259       }
260
261       bool
262       _M_is_less(const __dynamic_bitset_base& __x) const
263       {
264         if (__x.size() == this->size())
265           {
266             for (size_t __i = this->_M_w.size(); __i > 0; --__i)
267               {
268                 if (this->_M_w[__i-1] < __x._M_w[__i-1])
269                   return true;
270                 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
271                   return false;
272               }
273             return false;
274           }
275         else
276           return false;
277       }
278
279       size_t
280       _M_are_all_aux() const
281       {
282         for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
283           if (_M_w[__i] != ~static_cast<block_type>(0))
284             return 0;
285         return ((this->_M_w.size() - 1) * _S_bits_per_block
286                 + __builtin_popcountl(this->_M_hiword()));
287       }
288
289       bool
290       _M_is_any() const
291       {
292         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
293           if (this->_M_w[__i] != static_cast<block_type>(0))
294             return true;
295         return false;
296       }
297
298       bool
299       _M_is_subset_of(const __dynamic_bitset_base& __b)
300       {
301         if (__b.size() == this->size())
302           {
303             for (size_t __i = 0; __i < _M_w.size(); ++__i)
304               if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
305                 return false;
306             return true;
307           }
308         else
309           return false;
310       }
311
312       bool
313       _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
314       {
315         if (this->is_subset_of(__b))
316           {
317             if (*this == __b)
318               return false;
319             else
320               return true;
321           }
322         else
323           return false;
324       }
325
326       size_t
327       _M_do_count() const
328       {
329         size_t __result = 0;
330         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
331           __result += __builtin_popcountl(this->_M_w[__i]);
332         return __result;
333       }
334
335       size_type
336       _M_size() const
337       { return this->_M_w.size(); }
338
339       unsigned long
340       _M_do_to_ulong() const;
341
342       unsigned long long
343       _M_do_to_ullong() const;
344
345       // find first "on" bit
346       size_type
347       _M_do_find_first(size_t __not_found) const;
348
349       // find the next "on" bit that follows "prev"
350       size_type
351       _M_do_find_next(size_t __prev, size_t __not_found) const;
352
353       // do append of block
354       void
355       _M_do_append_block(block_type __block, size_type __pos)
356       {
357         size_t __offset = __pos % _S_bits_per_block;
358         if (__offset == 0)
359           this->_M_w.push_back(__block);
360         else
361           {
362             this->_M_hiword() |= (__block << __offset);
363             this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
364           }
365       }
366     };
367
368   // Definitions of non-inline functions from __dynamic_bitset_base.
369   template<typename _WordT, typename _Alloc>
370     void
371     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
372     {
373       if (__builtin_expect(__shift != 0, 1))
374         {
375           const size_t __wshift = __shift / _S_bits_per_block;
376           const size_t __offset = __shift % _S_bits_per_block;
377
378           if (__offset == 0)
379             for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
380               this->_M_w[__n] = this->_M_w[__n - __wshift];
381           else
382             {
383               const size_t __sub_offset = _S_bits_per_block - __offset;
384               for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
385                 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
386                              | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
387               this->_M_w[__wshift] = this->_M_w[0] << __offset;
388             }
389
390           //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
391           ////          static_cast<_WordT>(0));
392         }
393     }
394
395   template<typename _WordT, typename _Alloc>
396     void
397     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
398     {
399       if (__builtin_expect(__shift != 0, 1))
400         {
401           const size_t __wshift = __shift / _S_bits_per_block;
402           const size_t __offset = __shift % _S_bits_per_block;
403           const size_t __limit = this->_M_w.size() - __wshift - 1;
404
405           if (__offset == 0)
406             for (size_t __n = 0; __n <= __limit; ++__n)
407               this->_M_w[__n] = this->_M_w[__n + __wshift];
408           else
409             {
410               const size_t __sub_offset = (_S_bits_per_block
411                                            - __offset);
412               for (size_t __n = 0; __n < __limit; ++__n)
413                 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
414                              | (this->_M_w[__n + __wshift + 1] << __sub_offset));
415               this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
416             }
417
418           ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
419           ////          static_cast<_WordT>(0));
420         }
421     }
422
423   template<typename _WordT, typename _Alloc>
424     unsigned long
425     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
426     {
427       size_t __n = sizeof(unsigned long) / sizeof(block_type);
428       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
429         if (this->_M_w[__i])
430           __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
431       unsigned long __res = 0UL;
432       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
433         __res += this->_M_w[__i] << (__i * _S_bits_per_block);
434       return __res;
435     }
436
437   template<typename _WordT, typename _Alloc>
438     unsigned long long
439     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
440     {
441       size_t __n = sizeof(unsigned long long) / sizeof(block_type);
442       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
443         if (this->_M_w[__i])
444           __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
445       unsigned long long __res = 0ULL;
446       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
447         __res += this->_M_w[__i] << (__i * _S_bits_per_block);
448       return __res;
449     }
450
451   template<typename _WordT, typename _Alloc>
452     size_t
453     __dynamic_bitset_base<_WordT, _Alloc>
454     ::_M_do_find_first(size_t __not_found) const
455     {
456       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
457         {
458           _WordT __thisword = this->_M_w[__i];
459           if (__thisword != static_cast<_WordT>(0))
460             return (__i * _S_bits_per_block
461                     + __builtin_ctzl(__thisword));
462         }
463       // not found, so return an indication of failure.
464       return __not_found;
465     }
466
467   template<typename _WordT, typename _Alloc>
468     size_t
469     __dynamic_bitset_base<_WordT, _Alloc>
470     ::_M_do_find_next(size_t __prev, size_t __not_found) const
471     {
472       // make bound inclusive
473       ++__prev;
474
475       // check out of bounds
476       if (__prev >= this->_M_w.size() * _S_bits_per_block)
477         return __not_found;
478
479       // search first word
480       size_t __i = _S_whichword(__prev);
481       _WordT __thisword = this->_M_w[__i];
482
483       // mask off bits below bound
484       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
485
486       if (__thisword != static_cast<_WordT>(0))
487         return (__i * _S_bits_per_block
488                 + __builtin_ctzl(__thisword));
489
490       // check subsequent words
491       for (++__i; __i < this->_M_w.size(); ++__i)
492         {
493           __thisword = this->_M_w[__i];
494           if (__thisword != static_cast<_WordT>(0))
495             return (__i * _S_bits_per_block
496                     + __builtin_ctzl(__thisword));
497         }
498       // not found, so return an indication of failure.
499       return __not_found;
500     } // end _M_do_find_next
501
502   /**
503    *  @brief  The %dynamic_bitset class represents a sequence of bits.
504    *
505    *  @ingroup containers
506    *
507    *  (Note that %dynamic_bitset does @e not meet the formal
508    *  requirements of a <a href="tables.html#65">container</a>.
509    *  Mainly, it lacks iterators.)
510    *
511    *  The template argument, @a Nb, may be any non-negative number,
512    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
513    *
514    *  In the general unoptimized case, storage is allocated in
515    *  word-sized blocks.  Let B be the number of bits in a word, then
516    *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
517    *  unused.  (They are the high-order bits in the highest word.)  It
518    *  is a class invariant that those unused bits are always zero.
519    *
520    *  If you think of %dynamic_bitset as "a simple array of bits," be
521    *  aware that your mental picture is reversed: a %dynamic_bitset
522    *  behaves the same way as bits in integers do, with the bit at
523    *  index 0 in the "least significant / right-hand" position, and
524    *  the bit at index Nb-1 in the "most significant / left-hand"
525    *  position.  Thus, unlike other containers, a %dynamic_bitset's
526    *  index "counts from right to left," to put it very loosely.
527    *
528    *  This behavior is preserved when translating to and from strings.
529    *  For example, the first line of the following program probably
530    *  prints "b('a') is 0001100001" on a modern ASCII system.
531    *
532    *  @code
533    *     #include <dynamic_bitset>
534    *     #include <iostream>
535    *     #include <sstream>
536    *
537    *     using namespace std;
538    *
539    *     int main()
540    *     {
541    *         long         a = 'a';
542    *         dynamic_bitset   b(a);
543    *
544    *         cout << "b('a') is " << b << endl;
545    *
546    *         ostringstream s;
547    *         s << b;
548    *         string  str = s.str();
549    *         cout << "index 3 in the string is " << str[3] << " but\n"
550    *              << "index 3 in the bitset is " << b[3] << endl;
551    *     }
552    *  @endcode
553    *
554    *  Also see:
555    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
556    *  for a description of extensions.
557    *
558    *  Most of the actual code isn't contained in %dynamic_bitset<>
559    *  itself, but in the base class __dynamic_bitset_base.  The base
560    *  class works with whole words, not with individual bits.  This
561    *  allows us to specialize __dynamic_bitset_base for the important
562    *  special case where the %dynamic_bitset is only a single word.
563    *
564    *  Extra confusion can result due to the fact that the storage for
565    *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
566    *  carefully encapsulated.
567    */
568   template<typename _WordT = unsigned long long,
569            typename _Alloc = std::allocator<_WordT>>
570     class dynamic_bitset
571     : private __dynamic_bitset_base<_WordT, _Alloc>
572     {
573       static_assert(std::is_unsigned<_WordT>::value, "template argument "
574                     "_WordT not an unsigned integral type");
575
576     public:
577
578       typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
579       typedef _WordT block_type;
580       typedef _Alloc allocator_type;
581       typedef size_t size_type;
582
583       static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
584       // Use this: constexpr size_type std::numeric_limits<size_type>::max().
585       static const size_type npos = static_cast<size_type>(-1);
586
587     private:
588
589       //  Clear the unused bits in the uppermost word.
590       void
591       _M_do_sanitize()
592       {
593         size_type __shift = this->_M_Nb % bits_per_block;
594         if (__shift > 0)
595           this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
596       }
597
598       /**
599        *  These versions of single-bit set, reset, flip, and test
600        *  do no range checking.
601        */
602       dynamic_bitset<_WordT, _Alloc>&
603       _M_unchecked_set(size_type __pos)
604       {
605         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
606         return *this;
607       }
608
609       dynamic_bitset<_WordT, _Alloc>&
610       _M_unchecked_set(size_type __pos, int __val)
611       {
612         if (__val)
613           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
614         else
615           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
616         return *this;
617       }
618
619       dynamic_bitset<_WordT, _Alloc>&
620       _M_unchecked_reset(size_type __pos)
621       {
622         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
623         return *this;
624       }
625
626       dynamic_bitset<_WordT, _Alloc>&
627       _M_unchecked_flip(size_type __pos)
628       {
629         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
630         return *this;
631       }
632
633       bool
634       _M_unchecked_test(size_type __pos) const
635       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
636                 != static_cast<_WordT>(0)); }
637
638       size_type _M_Nb;
639
640     public:
641       /**
642        *  This encapsulates the concept of a single bit.  An instance
643        *  of this class is a proxy for an actual bit; this way the
644        *  individual bit operations are done as faster word-size
645        *  bitwise instructions.
646        *
647        *  Most users will never need to use this class directly;
648        *  conversions to and from bool are automatic and should be
649        *  transparent.  Overloaded operators help to preserve the
650        *  illusion.
651        *
652        *  (On a typical system, this "bit %reference" is 64 times the
653        *  size of an actual bit.  Ha.)
654        */
655       class reference
656       {
657         friend class dynamic_bitset;
658
659         block_type *_M_wp;
660         size_type _M_bpos;
661
662         // left undefined
663         reference();
664
665       public:
666         reference(dynamic_bitset& __b, size_type __pos)
667         {
668           this->_M_wp = &__b._M_getword(__pos);
669           this->_M_bpos = _Base::_S_whichbit(__pos);
670         }
671
672         ~reference()
673         { }
674
675         // For b[i] = __x;
676         reference&
677         operator=(bool __x)
678         {
679           if (__x)
680             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
681           else
682             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
683           return *this;
684         }
685
686         // For b[i] = b[__j];
687         reference&
688         operator=(const reference& __j)
689         {
690           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
691             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
692           else
693             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
694           return *this;
695         }
696
697         // Flips the bit
698         bool
699         operator~() const
700         { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
701
702         // For __x = b[i];
703         operator bool() const
704         { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
705
706         // For b[i].flip();
707         reference&
708         flip()
709         {
710           *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
711           return *this;
712         }
713       };
714
715       friend class reference;
716
717       typedef bool const_reference;
718
719       // 23.3.5.1 constructors:
720       /// All bits set to zero.
721       explicit
722       dynamic_bitset(const allocator_type& __alloc = allocator_type())
723       : _Base(__alloc), _M_Nb(0)
724       { }
725
726       /// Initial bits bitwise-copied from a single word (others set to zero).
727       explicit
728       dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
729                      const allocator_type& __alloc = allocator_type())
730       : _Base(__nbits, __val, __alloc),
731         _M_Nb(__nbits)
732       { }
733
734       dynamic_bitset(initializer_list<block_type> __il,
735                      const allocator_type& __alloc = allocator_type())
736       : _Base(__alloc), _M_Nb(0)
737       { this->append(__il); }
738
739       /**
740        *  @brief  Use a subset of a string.
741        *  @param  __str  A string of '0' and '1' characters.
742        *  @param  __pos  Index of the first character in @p __str to use.
743        *  @param  __n    The number of characters to copy.
744        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
745        *  @throw  std::invalid_argument  If a character appears in the string
746        *                                 which is neither '0' nor '1'.
747        */
748       template<typename _CharT, typename _Traits, typename _Alloc1>
749         explicit
750         dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
751                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
752                        __pos = 0,
753                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
754                        __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
755                        _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
756                        const allocator_type& __alloc = allocator_type())
757         : _Base(__alloc),
758           _M_Nb(0) // Watch for npos.
759         {
760           if (__pos > __str.size())
761             __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
762                                      "not valid"));
763
764           // Watch for npos.
765           this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
766           this->resize(this->_M_Nb);
767           this->_M_copy_from_string(__str, __pos, __n,
768                                     _CharT('0'), _CharT('1'));
769         }
770
771       /**
772        *  @brief  Construct from a string.
773        *  @param  __str  A string of '0' and '1' characters.
774        *  @throw  std::invalid_argument  If a character appears in the string
775        *                                 which is neither '0' nor '1'.
776        */
777       explicit
778       dynamic_bitset(const char* __str,
779                      const allocator_type& __alloc = allocator_type())
780       : _Base(__alloc)
781       {
782         size_t __len = 0;
783         if (__str)
784           while (__str[__len] != '\0')
785             ++__len;
786         this->resize(__len);
787         this->_M_copy_from_ptr<char,std::char_traits<char>>
788                    (__str, __len, 0, __len, '0', '1');
789       }
790
791       /**
792        *  @brief  Copy constructor.
793        */
794       dynamic_bitset(const dynamic_bitset& __b)
795       : _Base(__b), _M_Nb(__b.size())
796       { }
797
798       /**
799        *  @brief  Move constructor.
800        */
801       dynamic_bitset(dynamic_bitset&& __b)
802       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
803       { }
804
805       /**
806        *  @brief  Swap with another bitset.
807        */
808       void
809       swap(dynamic_bitset& __b)
810       {
811         this->_M_swap(__b);
812         std::swap(this->_M_Nb, __b._M_Nb);
813       }
814
815       /**
816        *  @brief  Assignment.
817        */
818       dynamic_bitset&
819       operator=(const dynamic_bitset& __b)
820       {
821         if (&__b != this)
822           {
823             this->_M_assign(__b);
824             this->_M_Nb = __b._M_Nb;
825           }
826       }
827
828       /**
829        *  @brief  Move assignment.
830        */
831       dynamic_bitset&
832       operator=(dynamic_bitset&& __b)
833       {
834         this->swap(__b);
835         return *this;
836       }
837
838       /**
839        *  @brief  Return the allocator for the bitset.
840        */
841       allocator_type
842       get_allocator() const
843       { return this->_M_get_allocator(); }
844
845       /**
846        *  @brief  Resize the bitset.
847        */
848       void
849       resize(size_type __nbits, bool __value = false)
850       {
851         this->_M_resize(__nbits, __value);
852         this->_M_Nb = __nbits;
853         this->_M_do_sanitize();
854       }
855
856       /**
857        *  @brief  Clear the bitset.
858        */
859       void
860       clear()
861       {
862         this->_M_clear();
863         this->_M_Nb = 0;
864       }
865
866       /**
867        *  @brief  Push a bit onto the high end of the bitset.
868        */
869       void
870       push_back(bool __bit)
871       {
872         if (size_t __offset = this->size() % bits_per_block == 0)
873           this->_M_do_append_block(block_type(0), this->_M_Nb);
874         ++this->_M_Nb;
875         this->_M_unchecked_set(this->_M_Nb, __bit);
876       }
877
878       /**
879        *  @brief  Append a block.
880        */
881       void
882       append(block_type __block)
883       {
884         this->_M_do_append_block(__block, this->_M_Nb);
885         this->_M_Nb += bits_per_block;
886       }
887
888       /**
889        *  @brief
890        */
891       void
892       append(initializer_list<block_type> __il)
893       { this->append(__il.begin(), __il.end()); }
894
895       /**
896        *  @brief  Append an iterator range of blocks.
897        */
898       template <typename _BlockInputIterator>
899         void
900         append(_BlockInputIterator __first, _BlockInputIterator __last)
901         {
902           for (; __first != __last; ++__first)
903             this->append(*__first);
904         }
905
906       // 23.3.5.2 dynamic_bitset operations:
907       //@{
908       /**
909        *  @brief  Operations on dynamic_bitsets.
910        *  @param  __rhs  A same-sized dynamic_bitset.
911        *
912        *  These should be self-explanatory.
913        */
914       dynamic_bitset<_WordT, _Alloc>&
915       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
916       {
917         this->_M_do_and(__rhs);
918         return *this;
919       }
920
921       dynamic_bitset<_WordT, _Alloc>&
922       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
923       {
924         this->_M_do_and(std::move(__rhs));
925         return *this;
926       }
927
928       dynamic_bitset<_WordT, _Alloc>&
929       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
930       {
931         this->_M_do_or(__rhs);
932         return *this;
933       }
934
935       dynamic_bitset<_WordT, _Alloc>&
936       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
937       {
938         this->_M_do_xor(__rhs);
939         return *this;
940       }
941
942       dynamic_bitset<_WordT, _Alloc>&
943       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
944       {
945         this->_M_do_dif(__rhs);
946         return *this;
947       }
948       //@}
949
950       //@{
951       /**
952        *  @brief  Operations on dynamic_bitsets.
953        *  @param  __pos The number of places to shift.
954        *
955        *  These should be self-explanatory.
956        */
957       dynamic_bitset<_WordT, _Alloc>&
958       operator<<=(size_type __pos)
959       {
960         if (__builtin_expect(__pos < this->_M_Nb, 1))
961           {
962             this->_M_do_left_shift(__pos);
963             this->_M_do_sanitize();
964           }
965         else
966           this->_M_do_reset();
967         return *this;
968       }
969
970       dynamic_bitset<_WordT, _Alloc>&
971       operator>>=(size_type __pos)
972       {
973         if (__builtin_expect(__pos < this->_M_Nb, 1))
974           {
975             this->_M_do_right_shift(__pos);
976             this->_M_do_sanitize();
977           }
978         else
979           this->_M_do_reset();
980         return *this;
981       }
982       //@}
983
984       // Set, reset, and flip.
985       /**
986        *  @brief Sets every bit to true.
987        */
988       dynamic_bitset<_WordT, _Alloc>&
989       set()
990       {
991         this->_M_do_set();
992         this->_M_do_sanitize();
993         return *this;
994       }
995
996       /**
997        *  @brief Sets a given bit to a particular value.
998        *  @param  __pos  The index of the bit.
999        *  @param  __val  Either true or false, defaults to true.
1000        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
1001        */
1002       dynamic_bitset<_WordT, _Alloc>&
1003       set(size_type __pos, bool __val = true)
1004       {
1005         if (__pos >= _M_Nb)
1006           __throw_out_of_range(__N("dynamic_bitset::set"));
1007         return this->_M_unchecked_set(__pos, __val);
1008       }
1009
1010       /**
1011        *  @brief Sets every bit to false.
1012        */
1013       dynamic_bitset<_WordT, _Alloc>&
1014       reset()
1015       {
1016         this->_M_do_reset();
1017         return *this;
1018       }
1019
1020       /**
1021        *  @brief Sets a given bit to false.
1022        *  @param  __pos  The index of the bit.
1023        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
1024        *
1025        *  Same as writing @c set(__pos, false).
1026        */
1027       dynamic_bitset<_WordT, _Alloc>&
1028       reset(size_type __pos)
1029       {
1030         if (__pos >= _M_Nb)
1031           __throw_out_of_range(__N("dynamic_bitset::reset"));
1032         return this->_M_unchecked_reset(__pos);
1033       }
1034
1035       /**
1036        *  @brief Toggles every bit to its opposite value.
1037        */
1038       dynamic_bitset<_WordT, _Alloc>&
1039       flip()
1040       {
1041         this->_M_do_flip();
1042         this->_M_do_sanitize();
1043         return *this;
1044       }
1045
1046       /**
1047        *  @brief Toggles a given bit to its opposite value.
1048        *  @param  __pos  The index of the bit.
1049        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
1050        */
1051       dynamic_bitset<_WordT, _Alloc>&
1052       flip(size_type __pos)
1053       {
1054         if (__pos >= _M_Nb)
1055           __throw_out_of_range(__N("dynamic_bitset::flip"));
1056         return this->_M_unchecked_flip(__pos);
1057       }
1058
1059       /// See the no-argument flip().
1060       dynamic_bitset<_WordT, _Alloc>
1061       operator~() const
1062       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
1063
1064       //@{
1065       /**
1066        *  @brief  Array-indexing support.
1067        *  @param  __pos  Index into the %dynamic_bitset.
1068        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
1069        *           bitsets, an instance of the reference proxy class.
1070        *  @note These operators do no range checking and throw no
1071        *         exceptions, as required by DR 11 to the standard.
1072        */
1073       reference
1074       operator[](size_type __pos)
1075       { return reference(*this,__pos); }
1076
1077       const_reference
1078       operator[](size_type __pos) const
1079       { return _M_unchecked_test(__pos); }
1080       //@}
1081
1082       /**
1083        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
1084        *  @return  The integral equivalent of the bits.
1085        *  @throw  std::overflow_error  If there are too many bits to be
1086        *                               represented in an @c unsigned @c long.
1087        */
1088       unsigned long
1089       to_ulong() const
1090       { return this->_M_do_to_ulong(); }
1091
1092       /**
1093        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
1094        *  @return  The integral equivalent of the bits.
1095        *  @throw  std::overflow_error  If there are too many bits to be
1096        *                               represented in an @c unsigned @c long.
1097        */
1098       unsigned long long
1099       to_ullong() const
1100       { return this->_M_do_to_ullong(); }
1101
1102       /**
1103        *  @brief Returns a character interpretation of the %dynamic_bitset.
1104        *  @return  The string equivalent of the bits.
1105        *
1106        *  Note the ordering of the bits:  decreasing character positions
1107        *  correspond to increasing bit positions (see the main class notes for
1108        *  an example).
1109        */
1110       template<typename _CharT = char,
1111                typename _Traits = std::char_traits<_CharT>,
1112                typename _Alloc1 = std::allocator<_CharT>>
1113         std::basic_string<_CharT, _Traits, _Alloc1>
1114         to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
1115         {
1116           std::basic_string<_CharT, _Traits, _Alloc1> __result;
1117           _M_copy_to_string(__result, __zero, __one);
1118           return __result;
1119         }
1120
1121       // Helper functions for string operations.
1122       template<typename _CharT, typename _Traits>
1123         void
1124         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1125                          _CharT, _CharT);
1126
1127       template<typename _CharT, typename _Traits, typename _Alloc1>
1128         void
1129         _M_copy_from_string(const std::basic_string<_CharT,
1130                             _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
1131                             _CharT __zero = _CharT('0'),
1132                             _CharT __one = _CharT('1'))
1133         { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
1134                                             __pos, __n, __zero, __one); }
1135
1136       template<typename _CharT, typename _Traits, typename _Alloc1>
1137         void
1138         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1139                           _CharT __zero = _CharT('0'),
1140                           _CharT __one = _CharT('1')) const;
1141
1142       /// Returns the number of bits which are set.
1143       size_type
1144       count() const
1145       { return this->_M_do_count(); }
1146
1147       /// Returns the total number of bits.
1148       size_type
1149       size() const
1150       { return this->_M_Nb; }
1151
1152       /// Returns the total number of blocks.
1153       size_type num_blocks() const
1154       { return this->_M_size(); }
1155
1156       /// Returns true if the dynamic_bitset is empty.
1157       bool
1158       empty() const
1159       { return (this->_M_Nb == 0); }
1160
1161       /// Returns the maximum size of a dynamic_bitset object having the same
1162       /// type as *this.
1163       /// The real answer is max() * bits_per_block but is likely to overflow.
1164       /*constexpr*/ size_type
1165       max_size() const
1166       { return std::numeric_limits<block_type>::max(); }
1167
1168       /**
1169        *  @brief Tests the value of a bit.
1170        *  @param  __pos  The index of a bit.
1171        *  @return  The value at @a __pos.
1172        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
1173        */
1174       bool
1175       test(size_type __pos) const
1176       {
1177         if (__pos >= _M_Nb)
1178           __throw_out_of_range(__N("dynamic_bitset::test"));
1179         return _M_unchecked_test(__pos);
1180       }
1181
1182       /**
1183        *  @brief Tests whether all the bits are on.
1184        *  @return  True if all the bits are set.
1185        */
1186       bool
1187       all() const
1188       { return this->_M_are_all_aux() == _M_Nb; }
1189
1190       /**
1191        *  @brief Tests whether any of the bits are on.
1192        *  @return  True if at least one bit is set.
1193        */
1194       bool
1195       any() const
1196       { return this->_M_is_any(); }
1197
1198       /**
1199        *  @brief Tests whether any of the bits are on.
1200        *  @return  True if none of the bits are set.
1201        */
1202       bool
1203       none() const
1204       { return !this->_M_is_any(); }
1205
1206       //@{
1207       /// Self-explanatory.
1208       dynamic_bitset<_WordT, _Alloc>
1209       operator<<(size_type __pos) const
1210       { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1211
1212       dynamic_bitset<_WordT, _Alloc>
1213       operator>>(size_type __pos) const
1214       { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1215       //@}
1216
1217       /**
1218        *  @brief  Finds the index of the first "on" bit.
1219        *  @return  The index of the first bit set, or size() if not found.
1220        *  @sa  find_next
1221        */
1222       size_type
1223       find_first() const
1224       { return this->_M_do_find_first(this->_M_Nb); }
1225
1226       /**
1227        *  @brief  Finds the index of the next "on" bit after prev.
1228        *  @return  The index of the next bit set, or size() if not found.
1229        *  @param  __prev  Where to start searching.
1230        *  @sa  find_first
1231        */
1232       size_type
1233       find_next(size_t __prev) const
1234       { return this->_M_do_find_next(__prev, this->_M_Nb); }
1235
1236       bool
1237       is_subset_of(const dynamic_bitset& __b) const
1238       { return this->_M_is_subset_of(__b); }
1239
1240       bool
1241       is_proper_subset_of(const dynamic_bitset& __b) const
1242       { return this->_M_is_proper_subset_of(__b); }
1243     };
1244
1245   // Definitions of non-inline member functions.
1246   template<typename _WordT, typename _Alloc>
1247     template<typename _CharT, typename _Traits>
1248       void
1249       dynamic_bitset<_WordT, _Alloc>::
1250       _M_copy_from_ptr(const _CharT* __str, size_t __len,
1251                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1252       {
1253         reset();
1254         const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
1255         for (size_t __i = __nbits; __i > 0; --__i)
1256           {
1257             const _CharT __c = __str[__pos + __nbits - __i];
1258             if (_Traits::eq(__c, __zero))
1259               ;
1260             else if (_Traits::eq(__c, __one))
1261               _M_unchecked_set(__i - 1);
1262             else
1263               __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
1264           }
1265       }
1266
1267   template<typename _WordT, typename _Alloc>
1268     template<typename _CharT, typename _Traits, typename _Alloc1>
1269       void
1270       dynamic_bitset<_WordT, _Alloc>::
1271       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1272                         _CharT __zero, _CharT __one) const
1273       {
1274         __str.assign(_M_Nb, __zero);
1275         for (size_t __i = _M_Nb; __i > 0; --__i)
1276           if (_M_unchecked_test(__i - 1))
1277             _Traits::assign(__str[_M_Nb - __i], __one);
1278       }
1279
1280
1281   //@{
1282   /// These comparisons for equality/inequality are, well, @e bitwise.
1283   template<typename _WordT, typename _Alloc>
1284     bool
1285     operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1286                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1287     { return __lhs._M_is_equal(__rhs); }
1288
1289   template<typename _WordT, typename _Alloc>
1290     bool
1291     operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1292                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1293     { return !__lhs._M_is_equal(__rhs); }
1294
1295   template<typename _WordT, typename _Alloc>
1296     bool
1297     operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1298               const dynamic_bitset<_WordT, _Alloc>& __rhs)
1299     { return __lhs._M_is_less(__rhs); }
1300
1301   template<typename _WordT, typename _Alloc>
1302     bool
1303     operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1304                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1305     { return !(__lhs > __rhs); }
1306
1307   template<typename _WordT, typename _Alloc>
1308     bool
1309     operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1310               const dynamic_bitset<_WordT, _Alloc>& __rhs)
1311     { return __rhs < __lhs; }
1312
1313   template<typename _WordT, typename _Alloc>
1314     bool
1315     operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1316                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1317     { return !(__lhs < __rhs); }
1318   //@}
1319
1320   // 23.3.5.3 bitset operations:
1321   //@{
1322   /**
1323    *  @brief  Global bitwise operations on bitsets.
1324    *  @param  __x  A bitset.
1325    *  @param  __y  A bitset of the same size as @a __x.
1326    *  @return  A new bitset.
1327    *
1328    *  These should be self-explanatory.
1329    */
1330   template<typename _WordT, typename _Alloc>
1331     inline dynamic_bitset<_WordT, _Alloc>
1332     operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1333               const dynamic_bitset<_WordT, _Alloc>& __y)
1334     {
1335       dynamic_bitset<_WordT, _Alloc> __result(__x);
1336       __result &= __y;
1337       return __result;
1338     }
1339
1340   template<typename _WordT, typename _Alloc>
1341     inline dynamic_bitset<_WordT, _Alloc>
1342     operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1343               const dynamic_bitset<_WordT, _Alloc>& __y)
1344     {
1345       dynamic_bitset<_WordT, _Alloc> __result(__x);
1346       __result |= __y;
1347       return __result;
1348     }
1349
1350   template <typename _WordT, typename _Alloc>
1351     inline dynamic_bitset<_WordT, _Alloc>
1352     operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1353               const dynamic_bitset<_WordT, _Alloc>& __y)
1354     {
1355       dynamic_bitset<_WordT, _Alloc> __result(__x);
1356       __result ^= __y;
1357       return __result;
1358     }
1359
1360   template <typename _WordT, typename _Alloc>
1361     inline dynamic_bitset<_WordT, _Alloc>
1362     operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1363               const dynamic_bitset<_WordT, _Alloc>& __y)
1364     {
1365       dynamic_bitset<_WordT, _Alloc> __result(__x);
1366       __result -= __y;
1367       return __result;
1368     }
1369   //@}
1370
1371   //@{
1372   /**
1373    *  @brief Global I/O operators for bitsets.
1374    *
1375    *  Direct I/O between streams and bitsets is supported.  Output is
1376    *  straightforward.  Input will skip whitespace and only accept '0'
1377    *  and '1' characters.  The %dynamic_bitset will grow as necessary
1378    *  to hold the string of bits.
1379    */
1380   template<typename _CharT, typename _Traits,
1381            typename _WordT, typename _Alloc>
1382     std::basic_istream<_CharT, _Traits>&
1383     operator>>(std::basic_istream<_CharT, _Traits>& __is,
1384                dynamic_bitset<_WordT, _Alloc>& __x)
1385     {
1386       typedef typename _Traits::char_type          char_type;
1387       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
1388       typedef typename __istream_type::ios_base    __ios_base;
1389
1390       std::basic_string<_CharT, _Traits> __tmp;
1391       __tmp.reserve(__x.size());
1392
1393       const char_type __zero = __is.widen('0');
1394       const char_type __one = __is.widen('1');
1395
1396       typename __ios_base::iostate __state = __ios_base::goodbit;
1397       typename __istream_type::sentry __sentry(__is);
1398       if (__sentry)
1399         {
1400           __try
1401             {
1402               while (1)
1403                 {
1404                   static typename _Traits::int_type __eof = _Traits::eof();
1405
1406                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1407                   if (_Traits::eq_int_type(__c1, __eof))
1408                     {
1409                       __state |= __ios_base::eofbit;
1410                       break;
1411                     }
1412                   else
1413                     {
1414                       const char_type __c2 = _Traits::to_char_type(__c1);
1415                       if (_Traits::eq(__c2, __zero))
1416                         __tmp.push_back(__zero);
1417                       else if (_Traits::eq(__c2, __one))
1418                         __tmp.push_back(__one);
1419                       else if (_Traits::
1420                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
1421                                            __eof))
1422                         {
1423                           __state |= __ios_base::failbit;
1424                           break;
1425                         }
1426                       else
1427                         break;
1428                     }
1429                 }
1430             }
1431           __catch(__cxxabiv1::__forced_unwind&)
1432             {
1433               __is._M_setstate(__ios_base::badbit);
1434               __throw_exception_again;
1435             }
1436           __catch(...)
1437             { __is._M_setstate(__ios_base::badbit); }
1438         }
1439
1440       __x.resize(__tmp.size());
1441
1442       if (__tmp.empty() && __x.size())
1443         __state |= __ios_base::failbit;
1444       else
1445         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
1446                                 __zero, __one);
1447       if (__state)
1448         __is.setstate(__state);
1449       return __is;
1450     }
1451
1452   template <typename _CharT, typename _Traits,
1453             typename _WordT, typename _Alloc>
1454     std::basic_ostream<_CharT, _Traits>&
1455     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1456                const dynamic_bitset<_WordT, _Alloc>& __x)
1457     {
1458       std::basic_string<_CharT, _Traits> __tmp;
1459
1460       const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1461       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1462       return __os << __tmp;
1463     }
1464   //@}
1465
1466 _GLIBCXX_END_NAMESPACE_VERSION
1467 } // tr2
1468 } // std
1469
1470 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1471
1472 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */