libstdc++
dynamic_bitset
Go to the documentation of this file.
1 // TR2 <dynamic_bitset> -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 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 <string>
37 #include <memory> // For std::allocator
38 #include <bits/functexcept.h> // For invalid_argument, out_of_range,
39  // overflow_error
40 #include <iosfwd>
41 #include <bits/cxxabi_forced.h>
42 
43 namespace std _GLIBCXX_VISIBILITY(default)
44 {
45 namespace tr2
46 {
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
48 
49  /**
50  * @defgroup dynamic_bitset Dynamic Bitset.
51  * @ingroup extensions
52  *
53  * @{
54  */
55 
56  /**
57  * Base class, general case.
58  *
59  * See documentation for dynamic_bitset.
60  */
61  template<typename _WordT = unsigned long long,
62  typename _Alloc = std::allocator<_WordT>>
64  {
65  static_assert(std::is_unsigned<_WordT>::value, "template argument "
66  "_WordT not an unsigned integral type");
67 
68  typedef _WordT block_type;
69  typedef _Alloc allocator_type;
70  typedef size_t size_type;
71 
72  static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
73  static const size_type npos = static_cast<size_type>(-1);
74 
75  /// 0 is the least significant word.
77 
78  explicit
79  __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
80  : _M_w(__alloc)
81  { }
82 
83  explicit
85  { this->_M_w.swap(__b._M_w); }
86 
87  explicit
88  __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
89  const allocator_type& __alloc = allocator_type())
90  : _M_w(__nbits / _S_bits_per_block
91  + (__nbits % _S_bits_per_block > 0),
92  __val, __alloc)
93  {
94  unsigned long long __mask = ~static_cast<block_type>(0);
95  size_t __n = std::min(this->_M_w.size(),
96  sizeof(unsigned long long) / sizeof(block_type));
97  for (size_t __i = 0; __i < __n; ++__i)
98  {
99  this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
100  __mask <<= _S_bits_per_block;
101  }
102  }
103 
104  void
105  _M_assign(const __dynamic_bitset_base& __b)
106  { this->_M_w = __b._M_w; }
107 
108  void
109  _M_swap(__dynamic_bitset_base& __b)
110  { this->_M_w.swap(__b._M_w); }
111 
112  void
113  _M_clear()
114  { this->_M_w.clear(); }
115 
116  void
117  _M_resize(size_t __nbits, bool __value)
118  {
119  size_t __sz = __nbits / _S_bits_per_block;
120  if (__nbits % _S_bits_per_block > 0)
121  ++__sz;
122  if (__sz != this->_M_w.size())
123  {
124  block_type __val = 0;
125  if (__value)
127  this->_M_w.resize(__sz, __val);
128  }
129  }
130 
131  allocator_type
132  _M_get_allocator() const
133  { return this->_M_w.get_allocator(); }
134 
135  static size_type
136  _S_whichword(size_type __pos) noexcept
137  { return __pos / _S_bits_per_block; }
138 
139  static size_type
140  _S_whichbyte(size_type __pos) noexcept
141  { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
142 
143  static size_type
144  _S_whichbit(size_type __pos) noexcept
145  { return __pos % _S_bits_per_block; }
146 
147  static block_type
148  _S_maskbit(size_type __pos) noexcept
149  { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
150 
151  block_type&
152  _M_getword(size_type __pos)
153  { return this->_M_w[_S_whichword(__pos)]; }
154 
155  block_type
156  _M_getword(size_type __pos) const
157  { return this->_M_w[_S_whichword(__pos)]; }
158 
159  block_type&
160  _M_hiword()
161  { return this->_M_w[_M_w.size() - 1]; }
162 
163  block_type
164  _M_hiword() const
165  { return this->_M_w[_M_w.size() - 1]; }
166 
167  void
168  _M_do_and(const __dynamic_bitset_base& __x)
169  {
170  if (__x._M_w.size() == this->_M_w.size())
171  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
172  this->_M_w[__i] &= __x._M_w[__i];
173  else
174  return;
175  }
176 
177  void
178  _M_do_or(const __dynamic_bitset_base& __x)
179  {
180  if (__x._M_w.size() == this->_M_w.size())
181  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
182  this->_M_w[__i] |= __x._M_w[__i];
183  else
184  return;
185  }
186 
187  void
188  _M_do_xor(const __dynamic_bitset_base& __x)
189  {
190  if (__x._M_w.size() == this->_M_w.size())
191  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
192  this->_M_w[__i] ^= __x._M_w[__i];
193  else
194  return;
195  }
196 
197  void
198  _M_do_dif(const __dynamic_bitset_base& __x)
199  {
200  if (__x._M_w.size() == this->_M_w.size())
201  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
202  this->_M_w[__i] &= ~__x._M_w[__i];
203  else
204  return;
205  }
206 
207  void
208  _M_do_left_shift(size_t __shift);
209 
210  void
211  _M_do_right_shift(size_t __shift);
212 
213  void
214  _M_do_flip()
215  {
216  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
217  this->_M_w[__i] = ~this->_M_w[__i];
218  }
219 
220  void
221  _M_do_set()
222  {
223  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
224  this->_M_w[__i] = ~static_cast<block_type>(0);
225  }
226 
227  void
228  _M_do_reset()
229  {
230  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
231  this->_M_w[__i] = static_cast<block_type>(0);
232  }
233 
234  bool
235  _M_is_equal(const __dynamic_bitset_base& __x) const
236  {
237  if (__x._M_w.size() == this->_M_w.size())
238  {
239  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
240  if (this->_M_w[__i] != __x._M_w[__i])
241  return false;
242  return true;
243  }
244  else
245  return false;
246  }
247 
248  bool
249  _M_is_less(const __dynamic_bitset_base& __x) const
250  {
251  if (__x._M_w.size() == this->_M_w.size())
252  {
253  for (size_t __i = this->_M_w.size(); __i > 0; --__i)
254  {
255  if (this->_M_w[__i-1] < __x._M_w[__i-1])
256  return true;
257  else if (this->_M_w[__i-1] > __x._M_w[__i-1])
258  return false;
259  }
260  return false;
261  }
262  else
263  return false;
264  }
265 
266  size_t
267  _M_are_all_aux() const
268  {
269  for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
270  if (_M_w[__i] != ~static_cast<block_type>(0))
271  return 0;
272  return ((this->_M_w.size() - 1) * _S_bits_per_block
273  + __builtin_popcountll(this->_M_hiword()));
274  }
275 
276  bool
277  _M_is_any() const
278  {
279  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
280  if (this->_M_w[__i] != static_cast<block_type>(0))
281  return true;
282  return false;
283  }
284 
285  bool
286  _M_is_subset_of(const __dynamic_bitset_base& __b)
287  {
288  if (__b._M_w.size() == this->_M_w.size())
289  {
290  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
291  if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
292  return false;
293  return true;
294  }
295  else
296  return false;
297  }
298 
299  bool
300  _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
301  {
302  if (this->is_subset_of(__b))
303  {
304  if (*this == __b)
305  return false;
306  else
307  return true;
308  }
309  else
310  return false;
311  }
312 
313  size_t
314  _M_do_count() const
315  {
316  size_t __result = 0;
317  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
318  __result += __builtin_popcountll(this->_M_w[__i]);
319  return __result;
320  }
321 
322  size_type
323  _M_size() const noexcept
324  { return this->_M_w.size(); }
325 
326  unsigned long
327  _M_do_to_ulong() const;
328 
329  unsigned long long
330  _M_do_to_ullong() const;
331 
332  // find first "on" bit
333  size_type
334  _M_do_find_first(size_t __not_found) const;
335 
336  // find the next "on" bit that follows "prev"
337  size_type
338  _M_do_find_next(size_t __prev, size_t __not_found) const;
339 
340  // do append of block
341  void
342  _M_do_append_block(block_type __block, size_type __pos)
343  {
344  size_t __offset = __pos % _S_bits_per_block;
345  if (__offset == 0)
346  this->_M_w.push_back(__block);
347  else
348  {
349  this->_M_hiword() |= (__block << __offset);
350  this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
351  }
352  }
353  };
354 
355  /**
356  * @brief The %dynamic_bitset class represents a sequence of bits.
357  *
358  * See N2050,
359  * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
360  *
361  * In the general unoptimized case, storage is allocated in
362  * word-sized blocks. Let B be the number of bits in a word, then
363  * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are
364  * unused. (They are the high-order bits in the highest word.) It
365  * is a class invariant that those unused bits are always zero.
366  *
367  * If you think of %dynamic_bitset as "a simple array of bits," be
368  * aware that your mental picture is reversed: a %dynamic_bitset
369  * behaves the same way as bits in integers do, with the bit at
370  * index 0 in the "least significant / right-hand" position, and
371  * the bit at index Nb-1 in the "most significant / left-hand"
372  * position. Thus, unlike other containers, a %dynamic_bitset's
373  * index "counts from right to left," to put it very loosely.
374  *
375  * This behavior is preserved when translating to and from strings.
376  * For example, the first line of the following program probably
377  * prints "b('a') is 0001100001" on a modern ASCII system.
378  *
379  * @code
380  * #include <dynamic_bitset>
381  * #include <iostream>
382  * #include <sstream>
383  *
384  * using namespace std;
385  *
386  * int main()
387  * {
388  * long a = 'a';
389  * dynamic_bitset<> b(a);
390  *
391  * cout << "b('a') is " << b << endl;
392  *
393  * ostringstream s;
394  * s << b;
395  * string str = s.str();
396  * cout << "index 3 in the string is " << str[3] << " but\n"
397  * << "index 3 in the bitset is " << b[3] << endl;
398  * }
399  * @endcode
400  *
401  * Most of the actual code isn't contained in %dynamic_bitset<>
402  * itself, but in the base class __dynamic_bitset_base. The base
403  * class works with whole words, not with individual bits. This
404  * allows us to specialize __dynamic_bitset_base for the important
405  * special case where the %dynamic_bitset is only a single word.
406  *
407  * Extra confusion can result due to the fact that the storage for
408  * __dynamic_bitset_base @e is a vector, and is indexed as such. This is
409  * carefully encapsulated.
410  */
411  template<typename _WordT = unsigned long long,
412  typename _Alloc = std::allocator<_WordT>>
414  : private __dynamic_bitset_base<_WordT, _Alloc>
415  {
416  static_assert(std::is_unsigned<_WordT>::value, "template argument "
417  "_WordT not an unsigned integral type");
418 
419  public:
420 
422  typedef _WordT block_type;
423  typedef _Alloc allocator_type;
424  typedef size_t size_type;
425 
426  static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
427  // Use this: constexpr size_type std::numeric_limits<size_type>::max().
428  static const size_type npos = static_cast<size_type>(-1);
429 
430  private:
431 
432  // Clear the unused bits in the uppermost word.
433  void
434  _M_do_sanitize()
435  {
436  size_type __shift = this->_M_Nb % bits_per_block;
437  if (__shift > 0)
438  this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
439  }
440 
441  // Set the unused bits in the uppermost word.
442  void
443  _M_do_fill()
444  {
445  size_type __shift = this->_M_Nb % bits_per_block;
446  if (__shift > 0)
447  this->_M_hiword() |= ((~static_cast<block_type>(0)) << __shift);
448  }
449 
450  /**
451  * These versions of single-bit set, reset, flip, and test
452  * do no range checking.
453  */
455  _M_unchecked_set(size_type __pos)
456  {
457  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
458  return *this;
459  }
460 
462  _M_unchecked_set(size_type __pos, int __val)
463  {
464  if (__val)
465  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
466  else
467  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
468  return *this;
469  }
470 
472  _M_unchecked_reset(size_type __pos)
473  {
474  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
475  return *this;
476  }
477 
479  _M_unchecked_flip(size_type __pos)
480  {
481  this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
482  return *this;
483  }
484 
485  bool
486  _M_unchecked_test(size_type __pos) const
487  { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
488  != static_cast<_WordT>(0)); }
489 
490  size_type _M_Nb;
491 
492  public:
493  /**
494  * This encapsulates the concept of a single bit. An instance
495  * of this class is a proxy for an actual bit; this way the
496  * individual bit operations are done as faster word-size
497  * bitwise instructions.
498  *
499  * Most users will never need to use this class directly;
500  * conversions to and from bool are automatic and should be
501  * transparent. Overloaded operators help to preserve the
502  * illusion.
503  *
504  * (On a typical system, this "bit %reference" is 64 times the
505  * size of an actual bit. Ha.)
506  */
507  class reference
508  {
509  friend class dynamic_bitset;
510 
511  block_type *_M_wp;
512  size_type _M_bpos;
513 
514  // left undefined
515  reference();
516 
517  public:
518  reference(dynamic_bitset& __b, size_type __pos)
519  {
520  this->_M_wp = &__b._M_getword(__pos);
521  this->_M_bpos = _Base::_S_whichbit(__pos);
522  }
523 
524  ~reference()
525  { }
526 
527  // For b[i] = __x;
528  reference&
529  operator=(bool __x)
530  {
531  if (__x)
532  *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
533  else
534  *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
535  return *this;
536  }
537 
538  // For b[i] = b[__j];
539  reference&
540  operator=(const reference& __j)
541  {
542  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
543  *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
544  else
545  *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
546  return *this;
547  }
548 
549  // Flips the bit
550  bool
551  operator~() const
552  { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
553 
554  // For __x = b[i];
555  operator bool() const
556  { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
557 
558  // For b[i].flip();
559  reference&
560  flip()
561  {
562  *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
563  return *this;
564  }
565  };
566 
567  friend class reference;
568 
569  typedef bool const_reference;
570 
571  // 23.3.5.1 constructors:
572  /// All bits set to zero.
573  explicit
574  dynamic_bitset(const allocator_type& __alloc = allocator_type())
575  : _Base(__alloc), _M_Nb(0)
576  { }
577 
578  /// Initial bits bitwise-copied from a single word (others set to zero).
579  explicit
580  dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
581  const allocator_type& __alloc = allocator_type())
582  : _Base(__nbits, __val, __alloc),
583  _M_Nb(__nbits)
584  { }
585 
587  const allocator_type& __alloc = allocator_type())
588  : _Base(__alloc), _M_Nb(0)
589  { this->append(__il); }
590 
591  /**
592  * @brief Use a subset of a string.
593  * @param __str A string of '0' and '1' characters.
594  * @param __pos Index of the first character in @p __str to use.
595  * @param __n The number of characters to copy.
596  * @param __zero The character to use for unset bits.
597  * @param __one The character to use for set bits.
598  * @param __alloc An allocator.
599  * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
600  * @throw std::invalid_argument If a character appears in the string
601  * which is neither '0' nor '1'.
602  */
603  template<typename _CharT, typename _Traits, typename _Alloc1>
604  explicit
606  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
607  __pos = 0,
608  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
610  _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
611  const allocator_type& __alloc = allocator_type())
612  : _Base(__alloc),
613  _M_Nb(0) // Watch for npos.
614  {
615  if (__pos > __str.size())
616  __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
617  "not valid"));
618 
619  // Watch for npos.
620  this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
621  this->resize(this->_M_Nb);
622  this->_M_copy_from_string(__str, __pos, __n,
623  _CharT('0'), _CharT('1'));
624  }
625 
626  /**
627  * @brief Construct from a string.
628  * @param __str A string of '0' and '1' characters.
629  * @param __alloc An allocator.
630  * @throw std::invalid_argument If a character appears in the string
631  * which is neither '0' nor '1'.
632  */
633  explicit
634  dynamic_bitset(const char* __str,
635  const allocator_type& __alloc = allocator_type())
636  : _Base(__alloc)
637  {
638  size_t __len = 0;
639  if (__str)
640  while (__str[__len] != '\0')
641  ++__len;
642  this->resize(__len);
643  this->_M_copy_from_ptr<char,std::char_traits<char>>
644  (__str, __len, 0, __len, '0', '1');
645  }
646 
647  /**
648  * @brief Copy constructor.
649  */
651  : _Base(__b), _M_Nb(__b.size())
652  { }
653 
654  /**
655  * @brief Move constructor.
656  */
658  : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
659  { }
660 
661  /**
662  * @brief Swap with another bitset.
663  */
664  void
666  {
667  this->_M_swap(__b);
668  std::swap(this->_M_Nb, __b._M_Nb);
669  }
670 
671  /**
672  * @brief Assignment.
673  */
676  {
677  if (&__b != this)
678  {
679  this->_M_assign(__b);
680  this->_M_Nb = __b._M_Nb;
681  }
682  }
683 
684  /**
685  * @brief Move assignment.
686  */
689  {
690  this->swap(__b);
691  return *this;
692  }
693 
694  /**
695  * @brief Return the allocator for the bitset.
696  */
697  allocator_type
699  { return this->_M_get_allocator(); }
700 
701  /**
702  * @brief Resize the bitset.
703  */
704  void
705  resize(size_type __nbits, bool __value = false)
706  {
707  if (__value)
708  this->_M_do_fill();
709  this->_M_resize(__nbits, __value);
710  this->_M_Nb = __nbits;
711  this->_M_do_sanitize();
712  }
713 
714  /**
715  * @brief Clear the bitset.
716  */
717  void
719  {
720  this->_M_clear();
721  this->_M_Nb = 0;
722  }
723 
724  /**
725  * @brief Push a bit onto the high end of the bitset.
726  */
727  void
728  push_back(bool __bit)
729  {
730  if (size_t __offset = this->size() % bits_per_block == 0)
731  this->_M_do_append_block(block_type(0), this->_M_Nb);
732  ++this->_M_Nb;
733  this->_M_unchecked_set(this->_M_Nb, __bit);
734  }
735 
736  /**
737  * @brief Append a block.
738  */
739  void
740  append(block_type __block)
741  {
742  this->_M_do_append_block(__block, this->_M_Nb);
743  this->_M_Nb += bits_per_block;
744  }
745 
746  /**
747  * @brief
748  */
749  void
751  { this->append(__il.begin(), __il.end()); }
752 
753  /**
754  * @brief Append an iterator range of blocks.
755  */
756  template <typename _BlockInputIterator>
757  void
758  append(_BlockInputIterator __first, _BlockInputIterator __last)
759  {
760  for (; __first != __last; ++__first)
761  this->append(*__first);
762  }
763 
764  // 23.3.5.2 dynamic_bitset operations:
765  //@{
766  /**
767  * @brief Operations on dynamic_bitsets.
768  * @param __rhs A same-sized dynamic_bitset.
769  *
770  * These should be self-explanatory.
771  */
774  {
775  this->_M_do_and(__rhs);
776  return *this;
777  }
778 
781  {
782  this->_M_do_and(std::move(__rhs));
783  return *this;
784  }
785 
788  {
789  this->_M_do_or(__rhs);
790  return *this;
791  }
792 
795  {
796  this->_M_do_xor(__rhs);
797  return *this;
798  }
799 
802  {
803  this->_M_do_dif(__rhs);
804  return *this;
805  }
806  //@}
807 
808  //@{
809  /**
810  * @brief Operations on dynamic_bitsets.
811  * @param __pos The number of places to shift.
812  *
813  * These should be self-explanatory.
814  */
816  operator<<=(size_type __pos)
817  {
818  if (__builtin_expect(__pos < this->_M_Nb, 1))
819  {
820  this->_M_do_left_shift(__pos);
821  this->_M_do_sanitize();
822  }
823  else
824  this->_M_do_reset();
825  return *this;
826  }
827 
829  operator>>=(size_type __pos)
830  {
831  if (__builtin_expect(__pos < this->_M_Nb, 1))
832  {
833  this->_M_do_right_shift(__pos);
834  this->_M_do_sanitize();
835  }
836  else
837  this->_M_do_reset();
838  return *this;
839  }
840  //@}
841 
842  // Set, reset, and flip.
843  /**
844  * @brief Sets every bit to true.
845  */
847  set()
848  {
849  this->_M_do_set();
850  this->_M_do_sanitize();
851  return *this;
852  }
853 
854  /**
855  * @brief Sets a given bit to a particular value.
856  * @param __pos The index of the bit.
857  * @param __val Either true or false, defaults to true.
858  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
859  */
861  set(size_type __pos, bool __val = true)
862  {
863  if (__pos >= _M_Nb)
864  __throw_out_of_range(__N("dynamic_bitset::set"));
865  return this->_M_unchecked_set(__pos, __val);
866  }
867 
868  /**
869  * @brief Sets every bit to false.
870  */
873  {
874  this->_M_do_reset();
875  return *this;
876  }
877 
878  /**
879  * @brief Sets a given bit to false.
880  * @param __pos The index of the bit.
881  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
882  *
883  * Same as writing @c set(__pos, false).
884  */
886  reset(size_type __pos)
887  {
888  if (__pos >= _M_Nb)
889  __throw_out_of_range(__N("dynamic_bitset::reset"));
890  return this->_M_unchecked_reset(__pos);
891  }
892 
893  /**
894  * @brief Toggles every bit to its opposite value.
895  */
898  {
899  this->_M_do_flip();
900  this->_M_do_sanitize();
901  return *this;
902  }
903 
904  /**
905  * @brief Toggles a given bit to its opposite value.
906  * @param __pos The index of the bit.
907  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
908  */
910  flip(size_type __pos)
911  {
912  if (__pos >= _M_Nb)
913  __throw_out_of_range(__N("dynamic_bitset::flip"));
914  return this->_M_unchecked_flip(__pos);
915  }
916 
917  /// See the no-argument flip().
919  operator~() const
920  { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
921 
922  //@{
923  /**
924  * @brief Array-indexing support.
925  * @param __pos Index into the %dynamic_bitset.
926  * @return A bool for a 'const %dynamic_bitset'. For non-const
927  * bitsets, an instance of the reference proxy class.
928  * @note These operators do no range checking and throw no
929  * exceptions, as required by DR 11 to the standard.
930  */
931  reference
932  operator[](size_type __pos)
933  { return reference(*this,__pos); }
934 
935  const_reference
936  operator[](size_type __pos) const
937  { return _M_unchecked_test(__pos); }
938  //@}
939 
940  /**
941  * @brief Returns a numerical interpretation of the %dynamic_bitset.
942  * @return The integral equivalent of the bits.
943  * @throw std::overflow_error If there are too many bits to be
944  * represented in an @c unsigned @c long.
945  */
946  unsigned long
947  to_ulong() const
948  { return this->_M_do_to_ulong(); }
949 
950  /**
951  * @brief Returns a numerical interpretation of the %dynamic_bitset.
952  * @return The integral equivalent of the bits.
953  * @throw std::overflow_error If there are too many bits to be
954  * represented in an @c unsigned @c long.
955  */
956  unsigned long long
957  to_ullong() const
958  { return this->_M_do_to_ullong(); }
959 
960  /**
961  * @brief Returns a character interpretation of the %dynamic_bitset.
962  * @return The string equivalent of the bits.
963  *
964  * Note the ordering of the bits: decreasing character positions
965  * correspond to increasing bit positions (see the main class notes for
966  * an example).
967  */
968  template<typename _CharT = char,
969  typename _Traits = std::char_traits<_CharT>,
970  typename _Alloc1 = std::allocator<_CharT>>
972  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
973  {
975  _M_copy_to_string(__result, __zero, __one);
976  return __result;
977  }
978 
979  // Helper functions for string operations.
980  template<typename _CharT, typename _Traits>
981  void
982  _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
983  _CharT, _CharT);
984 
985  template<typename _CharT, typename _Traits, typename _Alloc1>
986  void
987  _M_copy_from_string(const std::basic_string<_CharT,
988  _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
989  _CharT __zero = _CharT('0'),
990  _CharT __one = _CharT('1'))
991  { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
992  __pos, __n, __zero, __one); }
993 
994  template<typename _CharT, typename _Traits, typename _Alloc1>
995  void
996  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
997  _CharT __zero = _CharT('0'),
998  _CharT __one = _CharT('1')) const;
999 
1000  /// Returns the number of bits which are set.
1001  size_type
1002  count() const noexcept
1003  { return this->_M_do_count(); }
1004 
1005  /// Returns the total number of bits.
1006  size_type
1007  size() const noexcept
1008  { return this->_M_Nb; }
1009 
1010  /// Returns the total number of blocks.
1011  size_type
1012  num_blocks() const noexcept
1013  { return this->_M_size(); }
1014 
1015  /// Returns true if the dynamic_bitset is empty.
1016  bool
1017  empty() const noexcept
1018  { return (this->_M_Nb == 0); }
1019 
1020  /// Returns the maximum size of a dynamic_bitset object having the same
1021  /// type as *this.
1022  /// The real answer is max() * bits_per_block but is likely to overflow.
1023  constexpr size_type
1024  max_size() noexcept
1026 
1027  /**
1028  * @brief Tests the value of a bit.
1029  * @param __pos The index of a bit.
1030  * @return The value at @a __pos.
1031  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1032  */
1033  bool
1034  test(size_type __pos) const
1035  {
1036  if (__pos >= _M_Nb)
1037  __throw_out_of_range(__N("dynamic_bitset::test"));
1038  return _M_unchecked_test(__pos);
1039  }
1040 
1041  /**
1042  * @brief Tests whether all the bits are on.
1043  * @return True if all the bits are set.
1044  */
1045  bool
1046  all() const
1047  { return this->_M_are_all_aux() == _M_Nb; }
1048 
1049  /**
1050  * @brief Tests whether any of the bits are on.
1051  * @return True if at least one bit is set.
1052  */
1053  bool
1054  any() const
1055  { return this->_M_is_any(); }
1056 
1057  /**
1058  * @brief Tests whether any of the bits are on.
1059  * @return True if none of the bits are set.
1060  */
1061  bool
1062  none() const
1063  { return !this->_M_is_any(); }
1064 
1065  //@{
1066  /// Self-explanatory.
1068  operator<<(size_type __pos) const
1069  { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1070 
1072  operator>>(size_type __pos) const
1073  { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1074  //@}
1075 
1076  /**
1077  * @brief Finds the index of the first "on" bit.
1078  * @return The index of the first bit set, or size() if not found.
1079  * @sa find_next
1080  */
1081  size_type
1082  find_first() const
1083  { return this->_M_do_find_first(this->_M_Nb); }
1084 
1085  /**
1086  * @brief Finds the index of the next "on" bit after prev.
1087  * @return The index of the next bit set, or size() if not found.
1088  * @param __prev Where to start searching.
1089  * @sa find_first
1090  */
1091  size_type
1092  find_next(size_t __prev) const
1093  { return this->_M_do_find_next(__prev, this->_M_Nb); }
1094 
1095  bool
1096  is_subset_of(const dynamic_bitset& __b) const
1097  { return this->_M_is_subset_of(__b); }
1098 
1099  bool
1100  is_proper_subset_of(const dynamic_bitset& __b) const
1101  { return this->_M_is_proper_subset_of(__b); }
1102 
1103  friend bool
1104  operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1105  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1106  { return __lhs._M_is_equal(__rhs); }
1107 
1108  friend bool
1109  operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1110  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1111  { return __lhs._M_is_less(__rhs); }
1112  };
1113 
1114  template<typename _WordT, typename _Alloc>
1115  template<typename _CharT, typename _Traits, typename _Alloc1>
1116  inline void
1117  dynamic_bitset<_WordT, _Alloc>::
1118  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1119  _CharT __zero, _CharT __one) const
1120  {
1121  __str.assign(_M_Nb, __zero);
1122  for (size_t __i = _M_Nb; __i > 0; --__i)
1123  if (_M_unchecked_test(__i - 1))
1124  _Traits::assign(__str[_M_Nb - __i], __one);
1125  }
1126 
1127 
1128  //@{
1129  /// These comparisons for equality/inequality are, well, @e bitwise.
1130 
1131  template<typename _WordT, typename _Alloc>
1132  inline bool
1133  operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1134  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1135  { return !(__lhs == __rhs); }
1136 
1137  template<typename _WordT, typename _Alloc>
1138  inline bool
1139  operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1140  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1141  { return !(__lhs > __rhs); }
1142 
1143  template<typename _WordT, typename _Alloc>
1144  inline bool
1146  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1147  { return __rhs < __lhs; }
1148 
1149  template<typename _WordT, typename _Alloc>
1150  inline bool
1152  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1153  { return !(__lhs < __rhs); }
1154  //@}
1155 
1156  // 23.3.5.3 bitset operations:
1157  //@{
1158  /**
1159  * @brief Global bitwise operations on bitsets.
1160  * @param __x A bitset.
1161  * @param __y A bitset of the same size as @a __x.
1162  * @return A new bitset.
1163  *
1164  * These should be self-explanatory.
1165  */
1166  template<typename _WordT, typename _Alloc>
1167  inline dynamic_bitset<_WordT, _Alloc>
1169  const dynamic_bitset<_WordT, _Alloc>& __y)
1170  {
1171  dynamic_bitset<_WordT, _Alloc> __result(__x);
1172  __result &= __y;
1173  return __result;
1174  }
1175 
1176  template<typename _WordT, typename _Alloc>
1177  inline dynamic_bitset<_WordT, _Alloc>
1179  const dynamic_bitset<_WordT, _Alloc>& __y)
1180  {
1181  dynamic_bitset<_WordT, _Alloc> __result(__x);
1182  __result |= __y;
1183  return __result;
1184  }
1185 
1186  template <typename _WordT, typename _Alloc>
1187  inline dynamic_bitset<_WordT, _Alloc>
1189  const dynamic_bitset<_WordT, _Alloc>& __y)
1190  {
1191  dynamic_bitset<_WordT, _Alloc> __result(__x);
1192  __result ^= __y;
1193  return __result;
1194  }
1195 
1196  template <typename _WordT, typename _Alloc>
1197  inline dynamic_bitset<_WordT, _Alloc>
1199  const dynamic_bitset<_WordT, _Alloc>& __y)
1200  {
1201  dynamic_bitset<_WordT, _Alloc> __result(__x);
1202  __result -= __y;
1203  return __result;
1204  }
1205  //@}
1206 
1207  /// Stream output operator for dynamic_bitset.
1208  template <typename _CharT, typename _Traits,
1209  typename _WordT, typename _Alloc>
1211  operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1212  const dynamic_bitset<_WordT, _Alloc>& __x)
1213  {
1215 
1216  const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1217  __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1218  return __os << __tmp;
1219  }
1220  /**
1221  * @}
1222  */
1223 
1224 _GLIBCXX_END_NAMESPACE_VERSION
1225 } // tr2
1226 } // std
1227 
1228 #include <tr2/dynamic_bitset.tcc>
1229 
1230 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
Definition: dynamic_bitset:957
size_type size() const noexcept
Definition: stl_vector.h:654
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
Managing sequences of characters and character-like objects.
dynamic_bitset(const dynamic_bitset &__b)
Copy constructor.
Definition: dynamic_bitset:650
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
Definition: dynamic_bitset:947
const_reference operator[](size_type __pos) const
Array-indexing support.
Definition: dynamic_bitset:936
char_type widen(char __c) const
Widen char to char_type.
void append(block_type __block)
Append a block.
Definition: dynamic_bitset:740
size_type size() const noexcept
Returns the total number of bits.
bool any() const
Tests whether any of the bits are on.
bool none() const
Tests whether any of the bits are on.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition: bitset:1425
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:673
dynamic_bitset< _WordT, _Alloc > & flip(size_type __pos)
Toggles a given bit to its opposite value.
Definition: dynamic_bitset:910
Primary class template ctype facet.This template class defines classification and conversion function...
size_type find_first() const
Finds the index of the first &quot;on&quot; bit.
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
Definition: dynamic_bitset:76
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:605
dynamic_bitset & operator=(const dynamic_bitset &__b)
Assignment.
Definition: dynamic_bitset:675
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:580
void swap(dynamic_bitset &__b)
Swap with another bitset.
Definition: dynamic_bitset:665
void clear()
Clear the bitset.
Definition: dynamic_bitset:718
dynamic_bitset< _WordT, _Alloc > & operator&=(dynamic_bitset< _WordT, _Alloc > &&__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:780
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
dynamic_bitset< _WordT, _Alloc > & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:816
dynamic_bitset< _WordT, _Alloc > & operator|=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:787
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
constexpr size_type max_size() noexcept
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.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
Definition: dynamic_bitset:634
bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition: bitset:1434
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
bool test(size_type __pos) const
Tests the value of a bit.
initializer_list
dynamic_bitset< _WordT, _Alloc > & operator-=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:801
The dynamic_bitset class represents a sequence of bits.
Definition: dynamic_bitset:413
reference operator[](size_type __pos)
Array-indexing support.
Definition: dynamic_bitset:932
size_type num_blocks() const noexcept
Returns the total number of blocks.
dynamic_bitset< _WordT, _Alloc > & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
Definition: dynamic_bitset:861
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:913
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
Definition: dynamic_bitset:705
dynamic_bitset< _WordT, _Alloc > & reset()
Sets every bit to false.
Definition: dynamic_bitset:872
Basis for explicit traits specializations.
Definition: char_traits.h:227
Template class basic_ostream.
Definition: iosfwd:86
dynamic_bitset & operator=(dynamic_bitset &&__b)
Move assignment.
Definition: dynamic_bitset:688
bool all() const
Tests whether all the bits are on.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
Definition: dynamic_bitset:728
bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition: bitset:1443
dynamic_bitset< _WordT, _Alloc > & operator^=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:794
dynamic_bitset< _WordT, _Alloc > & reset(size_type __pos)
Sets a given bit to false.
Definition: dynamic_bitset:886
dynamic_bitset< _WordT, _Alloc > & set()
Sets every bit to true.
Definition: dynamic_bitset:847
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
dynamic_bitset< _WordT, _Alloc > operator<<(size_type __pos) const
Self-explanatory.
dynamic_bitset(dynamic_bitset &&__b)
Move constructor.
Definition: dynamic_bitset:657
size_type find_next(size_t __prev) const
Finds the index of the next &quot;on&quot; bit after prev.
dynamic_bitset< _WordT, _Alloc > & operator&=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:773
dynamic_bitset< _WordT, _Alloc > & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
Definition: dynamic_bitset:829
dynamic_bitset< _WordT, _Alloc > operator~() const
See the no-argument flip().
Definition: dynamic_bitset:919
dynamic_bitset< _WordT, _Alloc > & flip()
Toggles every bit to its opposite value.
Definition: dynamic_bitset:897
dynamic_bitset< _WordT, _Alloc > operator>>(size_type __pos) const
Self-explanatory.
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.
Definition: dynamic_bitset:972
bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
static constexpr _Tp max() noexcept
Definition: limits:324
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
Definition: fstream:1052
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
Definition: dynamic_bitset:758
size_type count() const noexcept
Returns the number of bits which are set.
void clear() noexcept
Definition: stl_vector.h:1211
The standard allocator, as per [20.4].
Definition: allocator.h:92
allocator_type get_allocator() const
Return the allocator for the bitset.
Definition: dynamic_bitset:698