1 // TR2 <dynamic_bitset> -*- C++ -*-
3 // Copyright (C) 2009-2017 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file tr2/dynamic_bitset
26 * This is a TR2 C++ Library header.
29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
32 #pragma GCC system_header
37 #include <memory> // For std::allocator
38 #include <bits/functexcept.h> // For invalid_argument, out_of_range,
41 #include <bits/cxxabi_forced.h>
43 namespace std _GLIBCXX_VISIBILITY(default)
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
50 * @defgroup dynamic_bitset Dynamic Bitset.
57 * Base class, general case.
59 * See documentation for dynamic_bitset.
61 template<typename _WordT = unsigned long long,
62 typename _Alloc = std::allocator<_WordT>>
63 struct __dynamic_bitset_base
65 static_assert(std::is_unsigned<_WordT>::value, "template argument "
66 "_WordT not an unsigned integral type");
68 typedef _WordT block_type;
69 typedef _Alloc allocator_type;
70 typedef size_t size_type;
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);
75 /// 0 is the least significant word.
76 std::vector<block_type, allocator_type> _M_w;
79 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
84 __dynamic_bitset_base(__dynamic_bitset_base&& __b)
85 { this->_M_w.swap(__b._M_w); }
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),
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)
99 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
100 __mask <<= _S_bits_per_block;
105 _M_assign(const __dynamic_bitset_base& __b)
106 { this->_M_w = __b._M_w; }
109 _M_swap(__dynamic_bitset_base& __b)
110 { this->_M_w.swap(__b._M_w); }
114 { this->_M_w.clear(); }
117 _M_resize(size_t __nbits, bool __value)
119 size_t __sz = __nbits / _S_bits_per_block;
120 if (__nbits % _S_bits_per_block > 0)
122 if (__sz != this->_M_w.size())
124 block_type __val = 0;
126 __val = std::numeric_limits<block_type>::max();
127 this->_M_w.resize(__sz, __val);
132 _M_get_allocator() const
133 { return this->_M_w.get_allocator(); }
136 _S_whichword(size_type __pos) noexcept
137 { return __pos / _S_bits_per_block; }
140 _S_whichbyte(size_type __pos) noexcept
141 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
144 _S_whichbit(size_type __pos) noexcept
145 { return __pos % _S_bits_per_block; }
148 _S_maskbit(size_type __pos) noexcept
149 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
152 _M_getword(size_type __pos)
153 { return this->_M_w[_S_whichword(__pos)]; }
156 _M_getword(size_type __pos) const
157 { return this->_M_w[_S_whichword(__pos)]; }
161 { return this->_M_w[_M_w.size() - 1]; }
165 { return this->_M_w[_M_w.size() - 1]; }
168 _M_do_and(const __dynamic_bitset_base& __x)
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];
178 _M_do_or(const __dynamic_bitset_base& __x)
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];
188 _M_do_xor(const __dynamic_bitset_base& __x)
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];
198 _M_do_dif(const __dynamic_bitset_base& __x)
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];
208 _M_do_left_shift(size_t __shift);
211 _M_do_right_shift(size_t __shift);
216 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
217 this->_M_w[__i] = ~this->_M_w[__i];
223 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
224 this->_M_w[__i] = ~static_cast<block_type>(0);
230 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
231 this->_M_w[__i] = static_cast<block_type>(0);
235 _M_is_equal(const __dynamic_bitset_base& __x) const
237 if (__x._M_w.size() == this->_M_w.size())
239 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
240 if (this->_M_w[__i] != __x._M_w[__i])
249 _M_is_less(const __dynamic_bitset_base& __x) const
251 if (__x._M_w.size() == this->_M_w.size())
253 for (size_t __i = this->_M_w.size(); __i > 0; --__i)
255 if (this->_M_w[__i-1] < __x._M_w[__i-1])
257 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
267 _M_are_all_aux() const
269 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
270 if (_M_w[__i] != ~static_cast<block_type>(0))
272 return ((this->_M_w.size() - 1) * _S_bits_per_block
273 + __builtin_popcountll(this->_M_hiword()));
279 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
280 if (this->_M_w[__i] != static_cast<block_type>(0))
286 _M_is_subset_of(const __dynamic_bitset_base& __b)
288 if (__b._M_w.size() == this->_M_w.size())
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]))
300 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
302 if (this->is_subset_of(__b))
317 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
318 __result += __builtin_popcountll(this->_M_w[__i]);
323 _M_size() const noexcept
324 { return this->_M_w.size(); }
327 _M_do_to_ulong() const;
330 _M_do_to_ullong() const;
332 // find first "on" bit
334 _M_do_find_first(size_t __not_found) const;
336 // find the next "on" bit that follows "prev"
338 _M_do_find_next(size_t __prev, size_t __not_found) const;
340 // do append of block
342 _M_do_append_block(block_type __block, size_type __pos)
344 size_t __offset = __pos % _S_bits_per_block;
346 this->_M_w.push_back(__block);
349 this->_M_hiword() |= (__block << __offset);
350 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
356 * @brief The %dynamic_bitset class represents a sequence of bits.
359 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
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.
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.
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.
380 * #include <dynamic_bitset>
381 * #include <iostream>
384 * using namespace std;
389 * dynamic_bitset<> b(a);
391 * cout << "b('a') is " << b << endl;
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;
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.
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.
411 template<typename _WordT = unsigned long long,
412 typename _Alloc = std::allocator<_WordT>>
414 : private __dynamic_bitset_base<_WordT, _Alloc>
416 static_assert(std::is_unsigned<_WordT>::value, "template argument "
417 "_WordT not an unsigned integral type");
421 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
422 typedef _WordT block_type;
423 typedef _Alloc allocator_type;
424 typedef size_t size_type;
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);
432 // Clear the unused bits in the uppermost word.
436 size_type __shift = this->_M_Nb % bits_per_block;
438 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
441 // Set the unused bits in the uppermost word.
445 size_type __shift = this->_M_Nb % bits_per_block;
447 this->_M_hiword() |= ((~static_cast<block_type>(0)) << __shift);
451 * These versions of single-bit set, reset, flip, and test
452 * do no range checking.
454 dynamic_bitset<_WordT, _Alloc>&
455 _M_unchecked_set(size_type __pos)
457 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
461 dynamic_bitset<_WordT, _Alloc>&
462 _M_unchecked_set(size_type __pos, int __val)
465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
467 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
471 dynamic_bitset<_WordT, _Alloc>&
472 _M_unchecked_reset(size_type __pos)
474 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
478 dynamic_bitset<_WordT, _Alloc>&
479 _M_unchecked_flip(size_type __pos)
481 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
486 _M_unchecked_test(size_type __pos) const
487 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
488 != static_cast<_WordT>(0)); }
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.
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
504 * (On a typical system, this "bit %reference" is 64 times the
505 * size of an actual bit. Ha.)
509 friend class dynamic_bitset;
518 reference(dynamic_bitset& __b, size_type __pos)
520 this->_M_wp = &__b._M_getword(__pos);
521 this->_M_bpos = _Base::_S_whichbit(__pos);
532 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
534 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
538 // For b[i] = b[__j];
540 operator=(const reference& __j)
542 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
543 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
545 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
552 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
555 operator bool() const
556 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
562 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
567 friend class reference;
569 typedef bool const_reference;
571 // 23.3.5.1 constructors:
572 /// All bits set to zero.
574 dynamic_bitset(const allocator_type& __alloc = allocator_type())
575 : _Base(__alloc), _M_Nb(0)
578 /// Initial bits bitwise-copied from a single word (others set to zero).
580 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
581 const allocator_type& __alloc = allocator_type())
582 : _Base(__nbits, __val, __alloc),
586 dynamic_bitset(initializer_list<block_type> __il,
587 const allocator_type& __alloc = allocator_type())
588 : _Base(__alloc), _M_Nb(0)
589 { this->append(__il); }
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'.
603 template<typename _CharT, typename _Traits, typename _Alloc1>
605 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
606 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
608 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
609 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
610 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
611 const allocator_type& __alloc = allocator_type())
613 _M_Nb(0) // Watch for npos.
615 if (__pos > __str.size())
616 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
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'));
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'.
634 dynamic_bitset(const char* __str,
635 const allocator_type& __alloc = allocator_type())
640 while (__str[__len] != '\0')
643 this->_M_copy_from_ptr<char,std::char_traits<char>>
644 (__str, __len, 0, __len, '0', '1');
648 * @brief Copy constructor.
650 dynamic_bitset(const dynamic_bitset& __b)
651 : _Base(__b), _M_Nb(__b.size())
655 * @brief Move constructor.
657 dynamic_bitset(dynamic_bitset&& __b)
658 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
662 * @brief Swap with another bitset.
665 swap(dynamic_bitset& __b)
668 std::swap(this->_M_Nb, __b._M_Nb);
675 operator=(const dynamic_bitset& __b)
679 this->_M_assign(__b);
680 this->_M_Nb = __b._M_Nb;
685 * @brief Move assignment.
688 operator=(dynamic_bitset&& __b)
695 * @brief Return the allocator for the bitset.
698 get_allocator() const
699 { return this->_M_get_allocator(); }
702 * @brief Resize the bitset.
705 resize(size_type __nbits, bool __value = false)
709 this->_M_resize(__nbits, __value);
710 this->_M_Nb = __nbits;
711 this->_M_do_sanitize();
715 * @brief Clear the bitset.
725 * @brief Push a bit onto the high end of the bitset.
728 push_back(bool __bit)
730 if (size_t __offset = this->size() % bits_per_block == 0)
731 this->_M_do_append_block(block_type(0), this->_M_Nb);
733 this->_M_unchecked_set(this->_M_Nb, __bit);
737 * @brief Append a block.
740 append(block_type __block)
742 this->_M_do_append_block(__block, this->_M_Nb);
743 this->_M_Nb += bits_per_block;
750 append(initializer_list<block_type> __il)
751 { this->append(__il.begin(), __il.end()); }
754 * @brief Append an iterator range of blocks.
756 template <typename _BlockInputIterator>
758 append(_BlockInputIterator __first, _BlockInputIterator __last)
760 for (; __first != __last; ++__first)
761 this->append(*__first);
764 // 23.3.5.2 dynamic_bitset operations:
767 * @brief Operations on dynamic_bitsets.
768 * @param __rhs A same-sized dynamic_bitset.
770 * These should be self-explanatory.
772 dynamic_bitset<_WordT, _Alloc>&
773 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
775 this->_M_do_and(__rhs);
779 dynamic_bitset<_WordT, _Alloc>&
780 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
782 this->_M_do_and(std::move(__rhs));
786 dynamic_bitset<_WordT, _Alloc>&
787 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
789 this->_M_do_or(__rhs);
793 dynamic_bitset<_WordT, _Alloc>&
794 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
796 this->_M_do_xor(__rhs);
800 dynamic_bitset<_WordT, _Alloc>&
801 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
803 this->_M_do_dif(__rhs);
810 * @brief Operations on dynamic_bitsets.
811 * @param __pos The number of places to shift.
813 * These should be self-explanatory.
815 dynamic_bitset<_WordT, _Alloc>&
816 operator<<=(size_type __pos)
818 if (__builtin_expect(__pos < this->_M_Nb, 1))
820 this->_M_do_left_shift(__pos);
821 this->_M_do_sanitize();
828 dynamic_bitset<_WordT, _Alloc>&
829 operator>>=(size_type __pos)
831 if (__builtin_expect(__pos < this->_M_Nb, 1))
833 this->_M_do_right_shift(__pos);
834 this->_M_do_sanitize();
842 // Set, reset, and flip.
844 * @brief Sets every bit to true.
846 dynamic_bitset<_WordT, _Alloc>&
850 this->_M_do_sanitize();
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.
860 dynamic_bitset<_WordT, _Alloc>&
861 set(size_type __pos, bool __val = true)
864 __throw_out_of_range(__N("dynamic_bitset::set"));
865 return this->_M_unchecked_set(__pos, __val);
869 * @brief Sets every bit to false.
871 dynamic_bitset<_WordT, _Alloc>&
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.
883 * Same as writing @c set(__pos, false).
885 dynamic_bitset<_WordT, _Alloc>&
886 reset(size_type __pos)
889 __throw_out_of_range(__N("dynamic_bitset::reset"));
890 return this->_M_unchecked_reset(__pos);
894 * @brief Toggles every bit to its opposite value.
896 dynamic_bitset<_WordT, _Alloc>&
900 this->_M_do_sanitize();
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.
909 dynamic_bitset<_WordT, _Alloc>&
910 flip(size_type __pos)
913 __throw_out_of_range(__N("dynamic_bitset::flip"));
914 return this->_M_unchecked_flip(__pos);
917 /// See the no-argument flip().
918 dynamic_bitset<_WordT, _Alloc>
920 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
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.
932 operator[](size_type __pos)
933 { return reference(*this,__pos); }
936 operator[](size_type __pos) const
937 { return _M_unchecked_test(__pos); }
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.
948 { return this->_M_do_to_ulong(); }
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.
958 { return this->_M_do_to_ullong(); }
961 * @brief Returns a character interpretation of the %dynamic_bitset.
962 * @return The string equivalent of the bits.
964 * Note the ordering of the bits: decreasing character positions
965 * correspond to increasing bit positions (see the main class notes for
968 template<typename _CharT = char,
969 typename _Traits = std::char_traits<_CharT>,
970 typename _Alloc1 = std::allocator<_CharT>>
971 std::basic_string<_CharT, _Traits, _Alloc1>
972 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
974 std::basic_string<_CharT, _Traits, _Alloc1> __result;
975 _M_copy_to_string(__result, __zero, __one);
979 // Helper functions for string operations.
980 template<typename _CharT, typename _Traits>
982 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
985 template<typename _CharT, typename _Traits, typename _Alloc1>
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); }
994 template<typename _CharT, typename _Traits, typename _Alloc1>
996 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
997 _CharT __zero = _CharT('0'),
998 _CharT __one = _CharT('1')) const;
1000 /// Returns the number of bits which are set.
1002 count() const noexcept
1003 { return this->_M_do_count(); }
1005 /// Returns the total number of bits.
1007 size() const noexcept
1008 { return this->_M_Nb; }
1010 /// Returns the total number of blocks.
1012 num_blocks() const noexcept
1013 { return this->_M_size(); }
1015 /// Returns true if the dynamic_bitset is empty.
1017 empty() const noexcept
1018 { return (this->_M_Nb == 0); }
1020 /// Returns the maximum size of a dynamic_bitset object having the same
1022 /// The real answer is max() * bits_per_block but is likely to overflow.
1025 { return std::numeric_limits<block_type>::max(); }
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.
1034 test(size_type __pos) const
1037 __throw_out_of_range(__N("dynamic_bitset::test"));
1038 return _M_unchecked_test(__pos);
1042 * @brief Tests whether all the bits are on.
1043 * @return True if all the bits are set.
1047 { return this->_M_are_all_aux() == _M_Nb; }
1050 * @brief Tests whether any of the bits are on.
1051 * @return True if at least one bit is set.
1055 { return this->_M_is_any(); }
1058 * @brief Tests whether any of the bits are on.
1059 * @return True if none of the bits are set.
1063 { return !this->_M_is_any(); }
1066 /// Self-explanatory.
1067 dynamic_bitset<_WordT, _Alloc>
1068 operator<<(size_type __pos) const
1069 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1071 dynamic_bitset<_WordT, _Alloc>
1072 operator>>(size_type __pos) const
1073 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1077 * @brief Finds the index of the first "on" bit.
1078 * @return The index of the first bit set, or size() if not found.
1083 { return this->_M_do_find_first(this->_M_Nb); }
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.
1092 find_next(size_t __prev) const
1093 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1096 is_subset_of(const dynamic_bitset& __b) const
1097 { return this->_M_is_subset_of(__b); }
1100 is_proper_subset_of(const dynamic_bitset& __b) const
1101 { return this->_M_is_proper_subset_of(__b); }
1104 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1105 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1106 { return __lhs._M_is_equal(__rhs); }
1109 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1110 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1111 { return __lhs._M_is_less(__rhs); }
1114 template<typename _WordT, typename _Alloc>
1115 template<typename _CharT, typename _Traits, typename _Alloc1>
1117 dynamic_bitset<_WordT, _Alloc>::
1118 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1119 _CharT __zero, _CharT __one) const
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);
1129 /// These comparisons for equality/inequality are, well, @e bitwise.
1131 template<typename _WordT, typename _Alloc>
1133 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1134 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1135 { return !(__lhs == __rhs); }
1137 template<typename _WordT, typename _Alloc>
1139 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1140 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1141 { return !(__lhs > __rhs); }
1143 template<typename _WordT, typename _Alloc>
1145 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1146 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1147 { return __rhs < __lhs; }
1149 template<typename _WordT, typename _Alloc>
1151 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1152 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1153 { return !(__lhs < __rhs); }
1156 // 23.3.5.3 bitset operations:
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.
1164 * These should be self-explanatory.
1166 template<typename _WordT, typename _Alloc>
1167 inline dynamic_bitset<_WordT, _Alloc>
1168 operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1169 const dynamic_bitset<_WordT, _Alloc>& __y)
1171 dynamic_bitset<_WordT, _Alloc> __result(__x);
1176 template<typename _WordT, typename _Alloc>
1177 inline dynamic_bitset<_WordT, _Alloc>
1178 operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1179 const dynamic_bitset<_WordT, _Alloc>& __y)
1181 dynamic_bitset<_WordT, _Alloc> __result(__x);
1186 template <typename _WordT, typename _Alloc>
1187 inline dynamic_bitset<_WordT, _Alloc>
1188 operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1189 const dynamic_bitset<_WordT, _Alloc>& __y)
1191 dynamic_bitset<_WordT, _Alloc> __result(__x);
1196 template <typename _WordT, typename _Alloc>
1197 inline dynamic_bitset<_WordT, _Alloc>
1198 operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1199 const dynamic_bitset<_WordT, _Alloc>& __y)
1201 dynamic_bitset<_WordT, _Alloc> __result(__x);
1207 /// Stream output operator for dynamic_bitset.
1208 template <typename _CharT, typename _Traits,
1209 typename _WordT, typename _Alloc>
1210 inline std::basic_ostream<_CharT, _Traits>&
1211 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1212 const dynamic_bitset<_WordT, _Alloc>& __x)
1214 std::basic_string<_CharT, _Traits> __tmp;
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;
1225 _GLIBCXX_END_NAMESPACE_VERSION
1228 #include <tr2/dynamic_bitset.tcc>
1230 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */