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