1 // TR2 <dynamic_bitset> -*- C++ -*-
3 // Copyright (C) 2009-2019 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 (this->size() % bits_per_block == 0)
731 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
733 this->_M_unchecked_set(this->_M_Nb, __bit);
738 * @brief Append a block.
741 append(block_type __block)
743 this->_M_do_append_block(__block, this->_M_Nb);
744 this->_M_Nb += bits_per_block;
751 append(initializer_list<block_type> __il)
752 { this->append(__il.begin(), __il.end()); }
755 * @brief Append an iterator range of blocks.
757 template <typename _BlockInputIterator>
759 append(_BlockInputIterator __first, _BlockInputIterator __last)
761 for (; __first != __last; ++__first)
762 this->append(*__first);
765 // 23.3.5.2 dynamic_bitset operations:
768 * @brief Operations on dynamic_bitsets.
769 * @param __rhs A same-sized dynamic_bitset.
771 * These should be self-explanatory.
773 dynamic_bitset<_WordT, _Alloc>&
774 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
776 this->_M_do_and(__rhs);
780 dynamic_bitset<_WordT, _Alloc>&
781 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
783 this->_M_do_and(std::move(__rhs));
787 dynamic_bitset<_WordT, _Alloc>&
788 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
790 this->_M_do_or(__rhs);
794 dynamic_bitset<_WordT, _Alloc>&
795 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
797 this->_M_do_xor(__rhs);
801 dynamic_bitset<_WordT, _Alloc>&
802 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
804 this->_M_do_dif(__rhs);
811 * @brief Operations on dynamic_bitsets.
812 * @param __pos The number of places to shift.
814 * These should be self-explanatory.
816 dynamic_bitset<_WordT, _Alloc>&
817 operator<<=(size_type __pos)
819 if (__builtin_expect(__pos < this->_M_Nb, 1))
821 this->_M_do_left_shift(__pos);
822 this->_M_do_sanitize();
829 dynamic_bitset<_WordT, _Alloc>&
830 operator>>=(size_type __pos)
832 if (__builtin_expect(__pos < this->_M_Nb, 1))
834 this->_M_do_right_shift(__pos);
835 this->_M_do_sanitize();
843 // Set, reset, and flip.
845 * @brief Sets every bit to true.
847 dynamic_bitset<_WordT, _Alloc>&
851 this->_M_do_sanitize();
856 * @brief Sets a given bit to a particular value.
857 * @param __pos The index of the bit.
858 * @param __val Either true or false, defaults to true.
859 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
861 dynamic_bitset<_WordT, _Alloc>&
862 set(size_type __pos, bool __val = true)
865 __throw_out_of_range(__N("dynamic_bitset::set"));
866 return this->_M_unchecked_set(__pos, __val);
870 * @brief Sets every bit to false.
872 dynamic_bitset<_WordT, _Alloc>&
880 * @brief Sets a given bit to false.
881 * @param __pos The index of the bit.
882 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
884 * Same as writing @c set(__pos, false).
886 dynamic_bitset<_WordT, _Alloc>&
887 reset(size_type __pos)
890 __throw_out_of_range(__N("dynamic_bitset::reset"));
891 return this->_M_unchecked_reset(__pos);
895 * @brief Toggles every bit to its opposite value.
897 dynamic_bitset<_WordT, _Alloc>&
901 this->_M_do_sanitize();
906 * @brief Toggles a given bit to its opposite value.
907 * @param __pos The index of the bit.
908 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
910 dynamic_bitset<_WordT, _Alloc>&
911 flip(size_type __pos)
914 __throw_out_of_range(__N("dynamic_bitset::flip"));
915 return this->_M_unchecked_flip(__pos);
918 /// See the no-argument flip().
919 dynamic_bitset<_WordT, _Alloc>
921 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
925 * @brief Array-indexing support.
926 * @param __pos Index into the %dynamic_bitset.
927 * @return A bool for a 'const %dynamic_bitset'. For non-const
928 * bitsets, an instance of the reference proxy class.
929 * @note These operators do no range checking and throw no
930 * exceptions, as required by DR 11 to the standard.
933 operator[](size_type __pos)
934 { return reference(*this,__pos); }
937 operator[](size_type __pos) const
938 { return _M_unchecked_test(__pos); }
942 * @brief Returns a numerical interpretation of the %dynamic_bitset.
943 * @return The integral equivalent of the bits.
944 * @throw std::overflow_error If there are too many bits to be
945 * represented in an @c unsigned @c long.
949 { return this->_M_do_to_ulong(); }
952 * @brief Returns a numerical interpretation of the %dynamic_bitset.
953 * @return The integral equivalent of the bits.
954 * @throw std::overflow_error If there are too many bits to be
955 * represented in an @c unsigned @c long.
959 { return this->_M_do_to_ullong(); }
962 * @brief Returns a character interpretation of the %dynamic_bitset.
963 * @return The string equivalent of the bits.
965 * Note the ordering of the bits: decreasing character positions
966 * correspond to increasing bit positions (see the main class notes for
969 template<typename _CharT = char,
970 typename _Traits = std::char_traits<_CharT>,
971 typename _Alloc1 = std::allocator<_CharT>>
972 std::basic_string<_CharT, _Traits, _Alloc1>
973 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
975 std::basic_string<_CharT, _Traits, _Alloc1> __result;
976 _M_copy_to_string(__result, __zero, __one);
980 // Helper functions for string operations.
981 template<typename _CharT, typename _Traits>
983 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
986 template<typename _CharT, typename _Traits, typename _Alloc1>
988 _M_copy_from_string(const std::basic_string<_CharT,
989 _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
990 _CharT __zero = _CharT('0'),
991 _CharT __one = _CharT('1'))
992 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
993 __pos, __n, __zero, __one); }
995 template<typename _CharT, typename _Traits, typename _Alloc1>
997 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
998 _CharT __zero = _CharT('0'),
999 _CharT __one = _CharT('1')) const;
1001 /// Returns the number of bits which are set.
1003 count() const noexcept
1004 { return this->_M_do_count(); }
1006 /// Returns the total number of bits.
1008 size() const noexcept
1009 { return this->_M_Nb; }
1011 /// Returns the total number of blocks.
1013 num_blocks() const noexcept
1014 { return this->_M_size(); }
1016 /// Returns true if the dynamic_bitset is empty.
1017 _GLIBCXX_NODISCARD bool
1018 empty() const noexcept
1019 { return (this->_M_Nb == 0); }
1021 /// Returns the maximum size of a dynamic_bitset object having the same
1023 /// The real answer is max() * bits_per_block but is likely to overflow.
1026 { return std::numeric_limits<block_type>::max(); }
1029 * @brief Tests the value of a bit.
1030 * @param __pos The index of a bit.
1031 * @return The value at @a __pos.
1032 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1035 test(size_type __pos) const
1038 __throw_out_of_range(__N("dynamic_bitset::test"));
1039 return _M_unchecked_test(__pos);
1043 * @brief Tests whether all the bits are on.
1044 * @return True if all the bits are set.
1048 { return this->_M_are_all_aux() == _M_Nb; }
1051 * @brief Tests whether any of the bits are on.
1052 * @return True if at least one bit is set.
1056 { return this->_M_is_any(); }
1059 * @brief Tests whether any of the bits are on.
1060 * @return True if none of the bits are set.
1064 { return !this->_M_is_any(); }
1067 /// Self-explanatory.
1068 dynamic_bitset<_WordT, _Alloc>
1069 operator<<(size_type __pos) const
1070 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1072 dynamic_bitset<_WordT, _Alloc>
1073 operator>>(size_type __pos) const
1074 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1078 * @brief Finds the index of the first "on" bit.
1079 * @return The index of the first bit set, or size() if not found.
1084 { return this->_M_do_find_first(this->_M_Nb); }
1087 * @brief Finds the index of the next "on" bit after prev.
1088 * @return The index of the next bit set, or size() if not found.
1089 * @param __prev Where to start searching.
1093 find_next(size_t __prev) const
1094 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1097 is_subset_of(const dynamic_bitset& __b) const
1098 { return this->_M_is_subset_of(__b); }
1101 is_proper_subset_of(const dynamic_bitset& __b) const
1102 { return this->_M_is_proper_subset_of(__b); }
1105 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1106 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1107 { return __lhs._M_is_equal(__rhs); }
1110 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1111 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1112 { return __lhs._M_is_less(__rhs); }
1115 template<typename _WordT, typename _Alloc>
1116 template<typename _CharT, typename _Traits, typename _Alloc1>
1118 dynamic_bitset<_WordT, _Alloc>::
1119 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1120 _CharT __zero, _CharT __one) const
1122 __str.assign(_M_Nb, __zero);
1123 for (size_t __i = _M_Nb; __i > 0; --__i)
1124 if (_M_unchecked_test(__i - 1))
1125 _Traits::assign(__str[_M_Nb - __i], __one);
1130 /// These comparisons for equality/inequality are, well, @e bitwise.
1132 template<typename _WordT, typename _Alloc>
1134 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1135 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1136 { return !(__lhs == __rhs); }
1138 template<typename _WordT, typename _Alloc>
1140 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1141 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1142 { return !(__lhs > __rhs); }
1144 template<typename _WordT, typename _Alloc>
1146 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1147 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1148 { return __rhs < __lhs; }
1150 template<typename _WordT, typename _Alloc>
1152 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1153 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1154 { return !(__lhs < __rhs); }
1157 // 23.3.5.3 bitset operations:
1160 * @brief Global bitwise operations on bitsets.
1161 * @param __x A bitset.
1162 * @param __y A bitset of the same size as @a __x.
1163 * @return A new bitset.
1165 * These should be self-explanatory.
1167 template<typename _WordT, typename _Alloc>
1168 inline dynamic_bitset<_WordT, _Alloc>
1169 operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1170 const dynamic_bitset<_WordT, _Alloc>& __y)
1172 dynamic_bitset<_WordT, _Alloc> __result(__x);
1177 template<typename _WordT, typename _Alloc>
1178 inline dynamic_bitset<_WordT, _Alloc>
1179 operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1180 const dynamic_bitset<_WordT, _Alloc>& __y)
1182 dynamic_bitset<_WordT, _Alloc> __result(__x);
1187 template <typename _WordT, typename _Alloc>
1188 inline dynamic_bitset<_WordT, _Alloc>
1189 operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1190 const dynamic_bitset<_WordT, _Alloc>& __y)
1192 dynamic_bitset<_WordT, _Alloc> __result(__x);
1197 template <typename _WordT, typename _Alloc>
1198 inline dynamic_bitset<_WordT, _Alloc>
1199 operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1200 const dynamic_bitset<_WordT, _Alloc>& __y)
1202 dynamic_bitset<_WordT, _Alloc> __result(__x);
1208 /// Stream output operator for dynamic_bitset.
1209 template <typename _CharT, typename _Traits,
1210 typename _WordT, typename _Alloc>
1211 inline std::basic_ostream<_CharT, _Traits>&
1212 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1213 const dynamic_bitset<_WordT, _Alloc>& __x)
1215 std::basic_string<_CharT, _Traits> __tmp;
1217 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1218 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1219 return __os << __tmp;
1226 _GLIBCXX_END_NAMESPACE_VERSION
1229 #include <tr2/dynamic_bitset.tcc>
1231 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */