STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Macros | Functions
dynamic_bitset File Reference
#include <limits>
#include <vector>
#include <string>
#include <memory>
#include <bits/functexcept.h>
#include <iosfwd>
#include <bits/cxxabi_forced.h>

Macros

#define _GLIBCXX_TR2_DYNAMIC_BITSET   1
 

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

This is a TR2 C++ Library header.

Macro Definition Documentation

#define _GLIBCXX_TR2_DYNAMIC_BITSET   1

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )

Dynamic Bitset.

See N2050, Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.

Base class, general case.

See documentation for dynamic_bitset.

0 is the least significant word.

The dynamic_bitset class represents a sequence of bits.

(Note that dynamic_bitset does not meet the formal requirements of a container. Mainly, it lacks iterators.)

The template argument, Nb, may be any non-negative number, specifying the number of bits (e.g., "0", "12", "1024*1024").

In the general unoptimized case, storage is allocated in word-sized blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B words will be used for storage. B - NbB bits are unused. (They are the high-order bits in the highest word.) It is a class invariant that those unused bits are always zero.

If you think of dynamic_bitset as "a simple array of bits," be aware that your mental picture is reversed: a dynamic_bitset behaves the same way as bits in integers do, with the bit at index 0 in the "least significant / right-hand" position, and the bit at index Nb-1 in the "most significant / left-hand" position. Thus, unlike other containers, a dynamic_bitset's index "counts from right to left," to put it very loosely.

This behavior is preserved when translating to and from strings. For example, the first line of the following program probably prints "b('a') is 0001100001" on a modern ASCII system.

#include <dynamic_bitset>
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
long a = 'a';
dynamic_bitset b(a);
cout << "b('a') is " << b << endl;
ostringstream s;
s << b;
string str = s.str();
cout << "index 3 in the string is " << str[3] << " but\n"
<< "index 3 in the bitset is " << b[3] << endl;
}

Also see: http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html for a description of extensions.

Most of the actual code isn't contained in dynamic_bitset<> itself, but in the base class __dynamic_bitset_base. The base class works with whole words, not with individual bits. This allows us to specialize __dynamic_bitset_base for the important special case where the dynamic_bitset is only a single word.

Extra confusion can result due to the fact that the storage for __dynamic_bitset_base is a vector, and is indexed as such. This is carefully encapsulated.

These versions of single-bit set, reset, flip, and test do no range checking.

This encapsulates the concept of a single bit. An instance of this class is a proxy for an actual bit; this way the individual bit operations are done as faster word-size bitwise instructions.

Most users will never need to use this class directly; conversions to and from bool are automatic and should be transparent. Overloaded operators help to preserve the illusion.

(On a typical system, this "bit %reference" is 64 times the size of an actual bit. Ha.)

All bits set to zero.

Initial bits bitwise-copied from a single word (others set to zero).

Use a subset of a string.

Parameters
__strA string of '0' and '1' characters.
__posIndex of the first character in __str to use.
__nThe number of characters to copy.
Exceptions
std::out_of_rangeIf __pos is bigger the size of __str.
std::invalid_argumentIf a character appears in the string which is neither '0' nor '1'.

Construct from a string.

Parameters
__strA string of '0' and '1' characters.
Exceptions
std::invalid_argumentIf a character appears in the string which is neither '0' nor '1'.

Copy constructor.

Move constructor.

Swap with another bitset.

Assignment.

Move assignment.

Return the allocator for the bitset.

Resize the bitset.

Clear the bitset.

Push a bit onto the high end of the bitset.

Append a block.

Append an iterator range of blocks.

Operations on dynamic_bitsets.

Parameters
__rhsA same-sized dynamic_bitset.

These should be self-explanatory.

Operations on dynamic_bitsets.

Parameters
__posThe number of places to shift.

These should be self-explanatory.

Sets every bit to true.

Sets a given bit to a particular value.

Parameters
__posThe index of the bit.
__valEither true or false, defaults to true.
Exceptions
std::out_of_rangeIf __pos is bigger the size of the set.

Sets every bit to false.

Sets a given bit to false.

Parameters
__posThe index of the bit.
Exceptions
std::out_of_rangeIf __pos is bigger the size of the set.

Same as writing set(__pos, false).

Toggles every bit to its opposite value.

Toggles a given bit to its opposite value.

Parameters
__posThe index of the bit.
Exceptions
std::out_of_rangeIf __pos is bigger the size of the set.

See the no-argument flip().

Array-indexing support.

Parameters
__posIndex into the dynamic_bitset.
Returns
A bool for a 'const dynamic_bitset'. For non-const bitsets, an instance of the reference proxy class.
Note
These operators do no range checking and throw no exceptions, as required by DR 11 to the standard.

Returns a numerical interpretation of the dynamic_bitset.

Returns
The integral equivalent of the bits.
Exceptions
std::overflow_errorIf there are too many bits to be represented in an unsigned long.

Returns a numerical interpretation of the dynamic_bitset.

Returns
The integral equivalent of the bits.
Exceptions
std::overflow_errorIf there are too many bits to be represented in an unsigned long.

Returns a character interpretation of the dynamic_bitset.

Returns
The string equivalent of the bits.

Note the ordering of the bits: decreasing character positions correspond to increasing bit positions (see the main class notes for an example).

Returns the number of bits which are set.

Returns the total number of bits.

Returns the total number of blocks.

Returns true if the dynamic_bitset is empty.

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.

Tests the value of a bit.

Parameters
__posThe index of a bit.
Returns
The value at __pos.
Exceptions
std::out_of_rangeIf __pos is bigger the size of the set.

Tests whether all the bits are on.

Returns
True if all the bits are set.

Tests whether any of the bits are on.

Returns
True if at least one bit is set.

Tests whether any of the bits are on.

Returns
True if none of the bits are set.

Self-explanatory.

Finds the index of the first "on" bit.

Returns
The index of the first bit set, or size() if not found.
See Also
find_next

Finds the index of the next "on" bit after prev.

Returns
The index of the next bit set, or size() if not found.
Parameters
__prevWhere to start searching.
See Also
find_first

These comparisons for equality/inequality are, well, bitwise.

Global bitwise operations on bitsets.

Parameters
__xA bitset.
__yA bitset of the same size as __x.
Returns
A new bitset.

These should be self-explanatory.

Global I/O operators for bitsets.

Direct I/O between streams and bitsets is supported. Output is straightforward. Input will skip whitespace and only accept '0' and '1' characters. The dynamic_bitset will grow as necessary to hold the string of bits.

44 {
45 namespace tr2
46 {
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
48 
55 namespace __detail
56 {
57 
58 template<typename T>
59 class _Bool2UChar
60 {
61  typedef T type;
62 };
63 
64 template<>
65 class _Bool2UChar<bool>
66 {
67 public:
68  typedef unsigned char type;
69 };
70 
71 }
72 
78  template<typename _WordT = unsigned long long,
79  typename _Alloc = std::allocator<_WordT>>
80  struct __dynamic_bitset_base
81  {
82  static_assert(std::is_unsigned<_WordT>::value, "template argument "
83  "_WordT not an unsigned integral type");
84 
85  typedef _WordT block_type;
86  typedef _Alloc allocator_type;
87  typedef size_t size_type;
88 
89  static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
90  static const size_type npos = static_cast<size_type>(-1);
91 
93  std::vector<block_type, allocator_type> _M_w;
94 
95  explicit
96  __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
97  : _M_w(__alloc)
98  { }
99 
100  explicit
101  __dynamic_bitset_base(__dynamic_bitset_base&& __b)
102  { this->_M_w.swap(__b._M_w); }
103 
104  explicit
105  __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
106  const allocator_type& __alloc = allocator_type())
107  : _M_w(__nbits / _S_bits_per_block
108  + (__nbits % _S_bits_per_block > 0),
109  __val, __alloc)
110  {
111  unsigned long long __mask = ~static_cast<block_type>(0);
112  size_t __n = std::min(this->_M_w.size(),
113  sizeof(unsigned long long) / sizeof(block_type));
114  for (size_t __i = 0; __i < __n; ++__i)
115  {
116  this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
117  __mask <<= _S_bits_per_block;
118  }
119  }
120 
121  void
122  _M_assign(const __dynamic_bitset_base& __b)
123  { this->_M_w = __b._M_w; }
124 
125  void
126  _M_swap(__dynamic_bitset_base& __b)
127  { this->_M_w.swap(__b._M_w); }
128 
129  void
130  _M_clear()
131  { this->_M_w.clear(); }
132 
133  void
134  _M_resize(size_t __nbits, bool __value)
135  {
136  size_t __sz = __nbits / _S_bits_per_block;
137  if (__nbits % _S_bits_per_block > 0)
138  ++__sz;
139  if (__sz != this->_M_w.size())
140  this->_M_w.resize(__sz);
141  }
142 
143  allocator_type
144  _M_get_allocator() const
145  { return this->_M_w.get_allocator(); }
146 
147  static size_type
148  _S_whichword(size_type __pos) noexcept
149  { return __pos / _S_bits_per_block; }
150 
151  static size_type
152  _S_whichbyte(size_type __pos) noexcept
153  { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
154 
155  static size_type
156  _S_whichbit(size_type __pos) noexcept
157  { return __pos % _S_bits_per_block; }
158 
159  static block_type
160  _S_maskbit(size_type __pos) noexcept
161  { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
162 
163  block_type&
164  _M_getword(size_type __pos)
165  { return this->_M_w[_S_whichword(__pos)]; }
166 
167  block_type
168  _M_getword(size_type __pos) const
169  { return this->_M_w[_S_whichword(__pos)]; }
170 
171  block_type&
172  _M_hiword()
173  { return this->_M_w[_M_w.size() - 1]; }
174 
175  block_type
176  _M_hiword() const
177  { return this->_M_w[_M_w.size() - 1]; }
178 
179  void
180  _M_do_and(const __dynamic_bitset_base& __x)
181  {
182  if (__x._M_w.size() == this->_M_w.size())
183  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
184  this->_M_w[__i] &= __x._M_w[__i];
185  else
186  return;
187  }
188 
189  void
190  _M_do_or(const __dynamic_bitset_base& __x)
191  {
192  if (__x._M_w.size() == this->_M_w.size())
193  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
194  this->_M_w[__i] |= __x._M_w[__i];
195  else
196  return;
197  }
198 
199  void
200  _M_do_xor(const __dynamic_bitset_base& __x)
201  {
202  if (__x._M_w.size() == this->_M_w.size())
203  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
204  this->_M_w[__i] ^= __x._M_w[__i];
205  else
206  return;
207  }
208 
209  void
210  _M_do_dif(const __dynamic_bitset_base& __x)
211  {
212  if (__x._M_w.size() == this->_M_w.size())
213  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
214  this->_M_w[__i] &= ~__x._M_w[__i];
215  else
216  return;
217  }
218 
219  void
220  _M_do_left_shift(size_t __shift);
221 
222  void
223  _M_do_right_shift(size_t __shift);
224 
225  void
226  _M_do_flip()
227  {
228  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
229  this->_M_w[__i] = ~this->_M_w[__i];
230  }
231 
232  void
233  _M_do_set()
234  {
235  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
236  this->_M_w[__i] = ~static_cast<block_type>(0);
237  }
238 
239  void
240  _M_do_reset()
241  {
242  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
243  this->_M_w[__i] = static_cast<block_type>(0);
244  }
245 
246  bool
247  _M_is_equal(const __dynamic_bitset_base& __x) const
248  {
249  if (__x.size() == this->size())
250  {
251  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
252  if (this->_M_w[__i] != __x._M_w[__i])
253  return false;
254  return true;
255  }
256  else
257  return false;
258  }
259 
260  bool
261  _M_is_less(const __dynamic_bitset_base& __x) const
262  {
263  if (__x.size() == this->size())
264  {
265  for (size_t __i = this->_M_w.size(); __i > 0; --__i)
266  {
267  if (this->_M_w[__i-1] < __x._M_w[__i-1])
268  return true;
269  else if (this->_M_w[__i-1] > __x._M_w[__i-1])
270  return false;
271  }
272  return false;
273  }
274  else
275  return false;
276  }
277 
278  size_t
279  _M_are_all_aux() const
280  {
281  for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
282  if (_M_w[__i] != ~static_cast<block_type>(0))
283  return 0;
284  return ((this->_M_w.size() - 1) * _S_bits_per_block
285  + __builtin_popcountl(this->_M_hiword()));
286  }
287 
288  bool
289  _M_is_any() const
290  {
291  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
292  if (this->_M_w[__i] != static_cast<block_type>(0))
293  return true;
294  return false;
295  }
296 
297  bool
298  _M_is_subset_of(const __dynamic_bitset_base& __b)
299  {
300  if (__b.size() == this->size())
301  {
302  for (size_t __i = 0; __i < _M_w.size(); ++__i)
303  if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
304  return false;
305  return true;
306  }
307  else
308  return false;
309  }
310 
311  bool
312  _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
313  {
314  if (this->is_subset_of(__b))
315  {
316  if (*this == __b)
317  return false;
318  else
319  return true;
320  }
321  else
322  return false;
323  }
324 
325  size_t
326  _M_do_count() const
327  {
328  size_t __result = 0;
329  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
330  __result += __builtin_popcountl(this->_M_w[__i]);
331  return __result;
332  }
333 
334  size_type
335  _M_size() const noexcept
336  { return this->_M_w.size(); }
337 
338  unsigned long
339  _M_do_to_ulong() const;
340 
341  unsigned long long
342  _M_do_to_ullong() const;
343 
344  // find first "on" bit
345  size_type
346  _M_do_find_first(size_t __not_found) const;
347 
348  // find the next "on" bit that follows "prev"
349  size_type
350  _M_do_find_next(size_t __prev, size_t __not_found) const;
351 
352  // do append of block
353  void
354  _M_do_append_block(block_type __block, size_type __pos)
355  {
356  size_t __offset = __pos % _S_bits_per_block;
357  if (__offset == 0)
358  this->_M_w.push_back(__block);
359  else
360  {
361  this->_M_hiword() |= (__block << __offset);
362  this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
363  }
364  }
365  };
366 
367  // Definitions of non-inline functions from __dynamic_bitset_base.
368  template<typename _WordT, typename _Alloc>
369  void
370  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
371  {
372  if (__builtin_expect(__shift != 0, 1))
373  {
374  const size_t __wshift = __shift / _S_bits_per_block;
375  const size_t __offset = __shift % _S_bits_per_block;
376 
377  if (__offset == 0)
378  for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
379  this->_M_w[__n] = this->_M_w[__n - __wshift];
380  else
381  {
382  const size_t __sub_offset = _S_bits_per_block - __offset;
383  for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
384  this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
385  | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
386  this->_M_w[__wshift] = this->_M_w[0] << __offset;
387  }
388 
391  }
392  }
393 
394  template<typename _WordT, typename _Alloc>
395  void
396  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
397  {
398  if (__builtin_expect(__shift != 0, 1))
399  {
400  const size_t __wshift = __shift / _S_bits_per_block;
401  const size_t __offset = __shift % _S_bits_per_block;
402  const size_t __limit = this->_M_w.size() - __wshift - 1;
403 
404  if (__offset == 0)
405  for (size_t __n = 0; __n <= __limit; ++__n)
406  this->_M_w[__n] = this->_M_w[__n + __wshift];
407  else
408  {
409  const size_t __sub_offset = (_S_bits_per_block
410  - __offset);
411  for (size_t __n = 0; __n < __limit; ++__n)
412  this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
413  | (this->_M_w[__n + __wshift + 1] << __sub_offset));
414  this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
415  }
416 
419  }
420  }
421 
422  template<typename _WordT, typename _Alloc>
423  unsigned long
424  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
425  {
426  size_t __n = sizeof(unsigned long) / sizeof(block_type);
427  for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
428  if (this->_M_w[__i])
429  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
430  unsigned long __res = 0UL;
431  for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
432  __res += this->_M_w[__i] << (__i * _S_bits_per_block);
433  return __res;
434  }
435 
436  template<typename _WordT, typename _Alloc>
437  unsigned long long
438  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
439  {
440  size_t __n = sizeof(unsigned long long) / sizeof(block_type);
441  for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
442  if (this->_M_w[__i])
443  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
444  unsigned long long __res = 0ULL;
445  for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
446  __res += this->_M_w[__i] << (__i * _S_bits_per_block);
447  return __res;
448  }
449 
450  template<typename _WordT, typename _Alloc>
451  size_t
452  __dynamic_bitset_base<_WordT, _Alloc>
453  ::_M_do_find_first(size_t __not_found) const
454  {
455  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
456  {
457  _WordT __thisword = this->_M_w[__i];
458  if (__thisword != static_cast<_WordT>(0))
459  return (__i * _S_bits_per_block
460  + __builtin_ctzl(__thisword));
461  }
462  // not found, so return an indication of failure.
463  return __not_found;
464  }
465 
466  template<typename _WordT, typename _Alloc>
467  size_t
468  __dynamic_bitset_base<_WordT, _Alloc>
469  ::_M_do_find_next(size_t __prev, size_t __not_found) const
470  {
471  // make bound inclusive
472  ++__prev;
473 
474  // check out of bounds
475  if (__prev >= this->_M_w.size() * _S_bits_per_block)
476  return __not_found;
477 
478  // search first word
479  size_t __i = _S_whichword(__prev);
480  _WordT __thisword = this->_M_w[__i];
481 
482  // mask off bits below bound
483  __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
484 
485  if (__thisword != static_cast<_WordT>(0))
486  return (__i * _S_bits_per_block
487  + __builtin_ctzl(__thisword));
488 
489  // check subsequent words
490  for (++__i; __i < this->_M_w.size(); ++__i)
491  {
492  __thisword = this->_M_w[__i];
493  if (__thisword != static_cast<_WordT>(0))
494  return (__i * _S_bits_per_block
495  + __builtin_ctzl(__thisword));
496  }
497  // not found, so return an indication of failure.
498  return __not_found;
499  } // end _M_do_find_next
500 
567  template<typename _WordT = unsigned long long,
568  typename _Alloc = std::allocator<_WordT>>
569  class dynamic_bitset
570  : private __dynamic_bitset_base<_WordT, _Alloc>
571  {
572  static_assert(std::is_unsigned<_WordT>::value, "template argument "
573  "_WordT not an unsigned integral type");
574 
575  public:
576 
577  typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
578  typedef _WordT block_type;
579  typedef _Alloc allocator_type;
580  typedef size_t size_type;
581 
582  static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
583  // Use this: constexpr size_type std::numeric_limits<size_type>::max().
584  static const size_type npos = static_cast<size_type>(-1);
585 
586  private:
587 
588  // Clear the unused bits in the uppermost word.
589  void
590  _M_do_sanitize()
591  {
592  size_type __shift = this->_M_Nb % bits_per_block;
593  if (__shift > 0)
594  this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
595  }
596 
601  dynamic_bitset<_WordT, _Alloc>&
602  _M_unchecked_set(size_type __pos)
603  {
604  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
605  return *this;
606  }
607 
608  dynamic_bitset<_WordT, _Alloc>&
609  _M_unchecked_set(size_type __pos, int __val)
610  {
611  if (__val)
612  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
613  else
614  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
615  return *this;
616  }
617 
618  dynamic_bitset<_WordT, _Alloc>&
619  _M_unchecked_reset(size_type __pos)
620  {
621  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
622  return *this;
623  }
624 
625  dynamic_bitset<_WordT, _Alloc>&
626  _M_unchecked_flip(size_type __pos)
627  {
628  this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
629  return *this;
630  }
631 
632  bool
633  _M_unchecked_test(size_type __pos) const
634  { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
635  != static_cast<_WordT>(0)); }
636 
637  size_type _M_Nb;
638 
639  public:
654  class reference
655  {
656  friend class dynamic_bitset;
657 
658  block_type *_M_wp;
659  size_type _M_bpos;
660 
661  // left undefined
662  reference();
663 
664  public:
665  reference(dynamic_bitset& __b, size_type __pos)
666  {
667  this->_M_wp = &__b._M_getword(__pos);
668  this->_M_bpos = _Base::_S_whichbit(__pos);
669  }
670 
671  ~reference()
672  { }
673 
674  // For b[i] = __x;
675  reference&
676  operator=(bool __x)
677  {
678  if (__x)
679  *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
680  else
681  *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
682  return *this;
683  }
684 
685  // For b[i] = b[__j];
686  reference&
687  operator=(const reference& __j)
688  {
689  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
690  *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
691  else
692  *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
693  return *this;
694  }
695 
696  // Flips the bit
697  bool
698  operator~() const
699  { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
700 
701  // For __x = b[i];
702  operator bool() const
703  { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
704 
705  // For b[i].flip();
706  reference&
707  flip()
708  {
709  *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
710  return *this;
711  }
712  };
713 
714  friend class reference;
715 
716  typedef bool const_reference;
717 
718  // 23.3.5.1 constructors:
720  explicit
721  dynamic_bitset(const allocator_type& __alloc = allocator_type())
722  : _Base(__alloc), _M_Nb(0)
723  { }
724 
726  explicit
727  dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
728  const allocator_type& __alloc = allocator_type())
729  : _Base(__nbits, __val, __alloc),
730  _M_Nb(__nbits)
731  { }
732 
733  dynamic_bitset(initializer_list<block_type> __il,
734  const allocator_type& __alloc = allocator_type())
735  : _Base(__alloc), _M_Nb(0)
736  { this->append(__il); }
737 
747  template<typename _CharT, typename _Traits, typename _Alloc1>
748  explicit
749  dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
750  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
751  __pos = 0,
752  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
753  __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
754  _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
755  const allocator_type& __alloc = allocator_type())
756  : _Base(__alloc),
757  _M_Nb(0) // Watch for npos.
758  {
759  if (__pos > __str.size())
760  __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
761  "not valid"));
762 
763  // Watch for npos.
764  this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
765  this->resize(this->_M_Nb);
766  this->_M_copy_from_string(__str, __pos, __n,
767  _CharT('0'), _CharT('1'));
768  }
769 
776  explicit
777  dynamic_bitset(const char* __str,
778  const allocator_type& __alloc = allocator_type())
779  : _Base(__alloc)
780  {
781  size_t __len = 0;
782  if (__str)
783  while (__str[__len] != '\0')
784  ++__len;
785  this->resize(__len);
786  this->_M_copy_from_ptr<char,std::char_traits<char>>
787  (__str, __len, 0, __len, '0', '1');
788  }
789 
793  dynamic_bitset(const dynamic_bitset& __b)
794  : _Base(__b), _M_Nb(__b.size())
795  { }
796 
800  dynamic_bitset(dynamic_bitset&& __b)
801  : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
802  { }
803 
807  void
808  swap(dynamic_bitset& __b)
809  {
810  this->_M_swap(__b);
811  std::swap(this->_M_Nb, __b._M_Nb);
812  }
813 
817  dynamic_bitset&
818  operator=(const dynamic_bitset& __b)
819  {
820  if (&__b != this)
821  {
822  this->_M_assign(__b);
823  this->_M_Nb = __b._M_Nb;
824  }
825  }
826 
830  dynamic_bitset&
831  operator=(dynamic_bitset&& __b)
832  {
833  this->swap(__b);
834  return *this;
835  }
836 
840  allocator_type
841  get_allocator() const
842  { return this->_M_get_allocator(); }
843 
847  void
848  resize(size_type __nbits, bool __value = false)
849  {
850  this->_M_resize(__nbits, __value);
851  this->_M_Nb = __nbits;
852  this->_M_do_sanitize();
853  }
854 
858  void
859  clear()
860  {
861  this->_M_clear();
862  this->_M_Nb = 0;
863  }
864 
868  void
869  push_back(bool __bit)
870  {
871  if (size_t __offset = this->size() % bits_per_block == 0)
872  this->_M_do_append_block(block_type(0), this->_M_Nb);
873  ++this->_M_Nb;
874  this->_M_unchecked_set(this->_M_Nb, __bit);
875  }
876 
880  void
881  append(block_type __block)
882  {
883  this->_M_do_append_block(__block, this->_M_Nb);
884  this->_M_Nb += bits_per_block;
885  }
886 
890  void
891  append(initializer_list<block_type> __il)
892  { this->append(__il.begin(), __il.end()); }
893 
897  template <typename _BlockInputIterator>
898  void
899  append(_BlockInputIterator __first, _BlockInputIterator __last)
900  {
901  for (; __first != __last; ++__first)
902  this->append(*__first);
903  }
904 
905  // 23.3.5.2 dynamic_bitset operations:
907 
913  dynamic_bitset<_WordT, _Alloc>&
914  operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
915  {
916  this->_M_do_and(__rhs);
917  return *this;
918  }
919 
920  dynamic_bitset<_WordT, _Alloc>&
921  operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
922  {
923  this->_M_do_and(std::move(__rhs));
924  return *this;
925  }
926 
927  dynamic_bitset<_WordT, _Alloc>&
928  operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
929  {
930  this->_M_do_or(__rhs);
931  return *this;
932  }
933 
934  dynamic_bitset<_WordT, _Alloc>&
935  operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
936  {
937  this->_M_do_xor(__rhs);
938  return *this;
939  }
940 
941  dynamic_bitset<_WordT, _Alloc>&
942  operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
943  {
944  this->_M_do_dif(__rhs);
945  return *this;
946  }
948 
950 
956  dynamic_bitset<_WordT, _Alloc>&
957  operator<<=(size_type __pos)
958  {
959  if (__builtin_expect(__pos < this->_M_Nb, 1))
960  {
961  this->_M_do_left_shift(__pos);
962  this->_M_do_sanitize();
963  }
964  else
965  this->_M_do_reset();
966  return *this;
967  }
968 
969  dynamic_bitset<_WordT, _Alloc>&
970  operator>>=(size_type __pos)
971  {
972  if (__builtin_expect(__pos < this->_M_Nb, 1))
973  {
974  this->_M_do_right_shift(__pos);
975  this->_M_do_sanitize();
976  }
977  else
978  this->_M_do_reset();
979  return *this;
980  }
982 
983  // Set, reset, and flip.
987  dynamic_bitset<_WordT, _Alloc>&
988  set()
989  {
990  this->_M_do_set();
991  this->_M_do_sanitize();
992  return *this;
993  }
994 
1001  dynamic_bitset<_WordT, _Alloc>&
1002  set(size_type __pos, bool __val = true)
1003  {
1004  if (__pos >= _M_Nb)
1005  __throw_out_of_range(__N("dynamic_bitset::set"));
1006  return this->_M_unchecked_set(__pos, __val);
1007  }
1008 
1012  dynamic_bitset<_WordT, _Alloc>&
1013  reset()
1014  {
1015  this->_M_do_reset();
1016  return *this;
1017  }
1018 
1026  dynamic_bitset<_WordT, _Alloc>&
1027  reset(size_type __pos)
1028  {
1029  if (__pos >= _M_Nb)
1030  __throw_out_of_range(__N("dynamic_bitset::reset"));
1031  return this->_M_unchecked_reset(__pos);
1032  }
1033 
1037  dynamic_bitset<_WordT, _Alloc>&
1038  flip()
1039  {
1040  this->_M_do_flip();
1041  this->_M_do_sanitize();
1042  return *this;
1043  }
1044 
1050  dynamic_bitset<_WordT, _Alloc>&
1051  flip(size_type __pos)
1052  {
1053  if (__pos >= _M_Nb)
1054  __throw_out_of_range(__N("dynamic_bitset::flip"));
1055  return this->_M_unchecked_flip(__pos);
1056  }
1057 
1059  dynamic_bitset<_WordT, _Alloc>
1060  operator~() const
1061  { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
1062 
1064 
1072  reference
1073  operator[](size_type __pos)
1074  { return reference(*this,__pos); }
1075 
1076  const_reference
1077  operator[](size_type __pos) const
1078  { return _M_unchecked_test(__pos); }
1080 
1087  unsigned long
1088  to_ulong() const
1089  { return this->_M_do_to_ulong(); }
1090 
1097  unsigned long long
1098  to_ullong() const
1099  { return this->_M_do_to_ullong(); }
1100 
1109  template<typename _CharT = char,
1110  typename _Traits = std::char_traits<_CharT>,
1111  typename _Alloc1 = std::allocator<_CharT>>
1112  std::basic_string<_CharT, _Traits, _Alloc1>
1113  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
1114  {
1115  std::basic_string<_CharT, _Traits, _Alloc1> __result;
1116  _M_copy_to_string(__result, __zero, __one);
1117  return __result;
1118  }
1119 
1120  // Helper functions for string operations.
1121  template<typename _CharT, typename _Traits>
1122  void
1123  _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1124  _CharT, _CharT);
1125 
1126  template<typename _CharT, typename _Traits, typename _Alloc1>
1127  void
1128  _M_copy_from_string(const std::basic_string<_CharT,
1129  _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
1130  _CharT __zero = _CharT('0'),
1131  _CharT __one = _CharT('1'))
1132  { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
1133  __pos, __n, __zero, __one); }
1134 
1135  template<typename _CharT, typename _Traits, typename _Alloc1>
1136  void
1137  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1138  _CharT __zero = _CharT('0'),
1139  _CharT __one = _CharT('1')) const;
1140 
1142  size_type
1143  count() const noexcept
1144  { return this->_M_do_count(); }
1145 
1147  size_type
1148  size() const noexcept
1149  { return this->_M_Nb; }
1150 
1152  size_type
1153  num_blocks() const noexcept
1154  { return this->_M_size(); }
1155 
1157  bool
1158  empty() const noexcept
1159  { return (this->_M_Nb == 0); }
1160 
1164  constexpr size_type
1165  max_size() noexcept
1166  { return std::numeric_limits<block_type>::max(); }
1167 
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 
1186  bool
1187  all() const
1188  { return this->_M_are_all_aux() == _M_Nb; }
1189 
1194  bool
1195  any() const
1196  { return this->_M_is_any(); }
1197 
1202  bool
1203  none() const
1204  { return !this->_M_is_any(); }
1205 
1207  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; }
1216 
1222  size_type
1223  find_first() const
1224  { return this->_M_do_find_first(this->_M_Nb); }
1225 
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 
1282  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); }
1319 
1320  // 23.3.5.3 bitset operations:
1322 
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  }
1370 
1372 
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  }
1465 
1466 _GLIBCXX_END_NAMESPACE_VERSION
1467 } // tr2
1468 } // std
__gnu_debug::operator>=
bool operator>=(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:644
std::__exception_ptr::operator==
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
__try
#define __try
Definition: exception_defines.h:35
__throw_exception_again
#define __throw_exception_again
Definition: exception_defines.h:37
bool
#define bool
Definition: stdbool.h:33
__gnu_parallel::min
const _Tp & min(const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
Definition: base.h:144
__gnu_debug::operator>>
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, basic_string< _CharT, _Traits, _Allocator > &__str)
Definition: string:1122
__gnu_debug::operator<<
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const basic_string< _CharT, _Traits, _Allocator > &__str)
Definition: string:1116
__gnu_debug::operator>
bool operator>(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:612
__gnu_debug::operator-
_Safe_iterator< _IteratorL, _Sequence >::difference_type operator-(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:680
std::__exception_ptr::operator!=
bool operator!=(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
__gnu_parallel::max
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
__catch
#define __catch(X)
Definition: exception_defines.h:36
basic_string
Definition: basic_string.h:45
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
Generated on Sat Jul 22 2017 14:42:42 for STLdoc by   doxygen 1.8.6