libstdc++
dynamic_bitset
Go to the documentation of this file.
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>>
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.
95 
96  explicit
97  __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
98  : _M_w(__alloc)
99  { }
100 
101  explicit
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>>
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 
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  */
603  _M_unchecked_set(size_type __pos)
604  {
605  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
606  return *this;
607  }
608 
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 
620  _M_unchecked_reset(size_type __pos)
621  {
622  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
623  return *this;
624  }
625 
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 
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
751  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
752  __pos = 0,
753  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
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  */
795  : _Base(__b), _M_Nb(__b.size())
796  { }
797 
798  /**
799  * @brief Move constructor.
800  */
802  : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
803  { }
804 
805  /**
806  * @brief Swap with another bitset.
807  */
808  void
810  {
811  this->_M_swap(__b);
812  std::swap(this->_M_Nb, __b._M_Nb);
813  }
814 
815  /**
816  * @brief Assignment.
817  */
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  */
833  {
834  this->swap(__b);
835  return *this;
836  }
837 
838  /**
839  * @brief Return the allocator for the bitset.
840  */
841  allocator_type
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
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
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  */
916  {
917  this->_M_do_and(__rhs);
918  return *this;
919  }
920 
923  {
924  this->_M_do_and(std::move(__rhs));
925  return *this;
926  }
927 
930  {
931  this->_M_do_or(__rhs);
932  return *this;
933  }
934 
937  {
938  this->_M_do_xor(__rhs);
939  return *this;
940  }
941 
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  */
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 
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  */
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  */
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  */
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  */
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  */
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  */
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().
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>>
1114  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
1115  {
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
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.
1209  operator<<(size_type __pos) const
1210  { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1211 
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
1286  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1287  { return __lhs._M_is_equal(__rhs); }
1288 
1289  template<typename _WordT, typename _Alloc>
1290  bool
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
1310  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1311  { return __rhs < __lhs; }
1312 
1313  template<typename _WordT, typename _Alloc>
1314  bool
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>
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>
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>
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>
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>
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 
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>
1455  operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1456  const dynamic_bitset<_WordT, _Alloc>& __x)
1457  {
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 */
initializer_list
bool empty() const
Returns true if the dynamic_bitset is empty.
bool operator==(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
dynamic_bitset< _WordT, _Alloc > operator~() const
See the no-argument flip().
void push_back(_CharT __c)
Append a single character.
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:149
void append(block_type __block)
Append a block.
Definition: dynamic_bitset:882
bool empty() const _GLIBCXX_NOEXCEPT
Definition: basic_string.h:808
The standard allocator, as per [20.4].
static constexpr _Tp max() _GLIBCXX_USE_NOEXCEPT
Definition: limits:313
dynamic_bitset< _WordT, _Alloc > operator&(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
dynamic_bitset & operator=(const dynamic_bitset &__b)
Assignment.
Definition: dynamic_bitset:819
Primary class template ctype facet.This template class defines classification and conversion function...
dynamic_bitset< _WordT, _Alloc > operator^(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
bitset< _Nb > & flip() _GLIBCXX_NOEXCEPT
Toggles every bit to its opposite value.
Definition: bitset:1106
dynamic_bitset< _WordT, _Alloc > & reset(size_type __pos)
Sets a given bit to false.
void clear()
Clear the bitset.
Definition: dynamic_bitset:860
dynamic_bitset< _WordT, _Alloc > operator<<(size_type __pos) const
Self-explanatory.
char_type widen(char __c) const
Widens characters.
Definition: basic_ios.h:441
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:77
Template class basic_ostream.This is the base class for all output streams. It provides text formatti...
Definition: iosfwd:88
bool operator!=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
size_type count() const
Returns the number of bits which are set.
bool none() const
Tests whether any of the bits are on.
dynamic_bitset< _WordT, _Alloc > & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
void swap(dynamic_bitset &__b)
Swap with another bitset.
Definition: dynamic_bitset:809
dynamic_bitset(dynamic_bitset &&__b)
Move constructor.
Definition: dynamic_bitset:801
void swap(vector &__x) noexcept(_Alloc_traits::_S_nothrow_swap())
Swaps data with another vector.
Definition: stl_vector.h:1079
The dynamic_bitset class represents a sequence of bits.
Definition: dynamic_bitset:570
size_type size() const _GLIBCXX_NOEXCEPT
Returns the number of characters in the string, not including any null-termination.
Definition: basic_string.h:712
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
Definition: dynamic_bitset:94
size_type find_first() const
Finds the index of the first "on" bit.
char_type widen(char __c) const
Widen char to char_type.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
bitset< _Nb > operator~() const _GLIBCXX_NOEXCEPT
See the no-argument flip().
Definition: bitset:1128
bool any() const
Tests whether any of the bits are on.
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
Definition: dynamic_bitset:870
dynamic_bitset< _WordT, _Alloc > operator|(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
void clear() _GLIBCXX_NOEXCEPT
Definition: stl_vector.h:1096
dynamic_bitset< _WordT, _Alloc > & operator&=(dynamic_bitset< _WordT, _Alloc > &&__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:922
void reserve(size_type __res_arg=0)
Attempt to preallocate enough memory for specified number of characters.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
bool test(size_type __pos) const
Tests the value of a bit.
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
Definition: dynamic_bitset:778
dynamic_bitset< _WordT, _Alloc > & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:971
Thrown as part of forced unwinding.A magic placeholder class that can be caught by reference to recog...
Definition: cxxabi_forced.h:48
size_type size() const _GLIBCXX_NOEXCEPT
Definition: stl_vector.h:625
bool all() const
Tests whether all the bits are on.
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:187
Template class basic_istream.This is the base class for all input streams. It provides text formattin...
Definition: iosfwd:85
dynamic_bitset< _WordT, _Alloc > & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:958
dynamic_bitset< _WordT, _Alloc > & set()
Sets every bit to true.
Definition: dynamic_bitset:989
dynamic_bitset & operator=(dynamic_bitset &&__b)
Move assignment.
Definition: dynamic_bitset:832
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
Definition: dynamic_bitset:849
Managing sequences of characters and character-like objects.
Definition: basic_string.h:109
dynamic_bitset< _WordT, _Alloc > operator>>(size_type __pos) const
Self-explanatory.
bitset< _Nb > & reset() _GLIBCXX_NOEXCEPT
Sets every bit to false.
Definition: bitset:1081
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:313
Basis for explicit traits specializations.
Definition: char_traits.h:229
reference operator[](size_type __pos)
Array-indexing support.
is_unsigned
Definition: type_traits:563
size_type size() const
Returns the total number of bits.
dynamic_bitset(size_type __nbits, unsigned long long __val=0ULL, const allocator_type &__alloc=allocator_type())
Initial bits bitwise-copied from a single word (others set to zero).
Definition: dynamic_bitset:728
dynamic_bitset(const dynamic_bitset &__b)
Copy constructor.
Definition: dynamic_bitset:794
std::basic_string< _CharT, _Traits, _Alloc1 > to_string(_CharT __zero=_CharT('0'), _CharT __one=_CharT('1')) const
Returns a character interpretation of the dynamic_bitset.
dynamic_bitset< _WordT, _Alloc > & operator&=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:915
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, dynamic_bitset< _WordT, _Alloc > &__x)
Global I/O operators for bitsets.
size_type num_blocks() const
Returns the total number of blocks.
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:881
size_type max_size() const
Returns the maximum size of a dynamic_bitset object having the same type as *this. The real answer is max() * bits_per_block but is likely to overflow.
dynamic_bitset< _WordT, _Alloc > & operator-=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:943
dynamic_bitset< _WordT, _Alloc > & reset()
Sets every bit to false.
dynamic_bitset< _WordT, _Alloc > & flip()
Toggles every bit to its opposite value.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
Definition: dynamic_bitset:900
dynamic_bitset< _WordT, _Alloc > & flip(size_type __pos)
Toggles a given bit to its opposite value.
dynamic_bitset(const std::basic_string< _CharT, _Traits, _Alloc1 > &__str, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __pos=0, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __n=std::basic_string< _CharT, _Traits, _Alloc1 >::npos, _CharT __zero=_CharT('0'), _CharT __one=_CharT('1'), const allocator_type &__alloc=allocator_type())
Use a subset of a string.
Definition: dynamic_bitset:750
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:644
dynamic_bitset< _WordT, _Alloc > & operator|=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:929
dynamic_bitset(const allocator_type &__alloc=allocator_type())
All bits set to zero.
Definition: dynamic_bitset:722
dynamic_bitset< _WordT, _Alloc > & operator^=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:936
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.
Definition: bitset:1284
allocator_type get_allocator() const
Return the allocator for the bitset.
Definition: dynamic_bitset:842
const_reference operator[](size_type __pos) const
Array-indexing support.
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.