1 // TR2 <dynamic_bitset> -*- C++ -*-
3 // Copyright (C) 2009-2014 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)
47 _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 * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
597 * @throw std::invalid_argument If a character appears in the string
598 * which is neither '0' nor '1'.
600 template<typename _CharT, typename _Traits, typename _Alloc1>
602 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
603 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
605 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
606 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
607 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
608 const allocator_type& __alloc = allocator_type())
610 _M_Nb(0) // Watch for npos.
612 if (__pos > __str.size())
613 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
617 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
618 this->resize(this->_M_Nb);
619 this->_M_copy_from_string(__str, __pos, __n,
620 _CharT('0'), _CharT('1'));
624 * @brief Construct from a string.
625 * @param __str A string of '0' and '1' characters.
626 * @param __alloc An allocator.
627 * @throw std::invalid_argument If a character appears in the string
628 * which is neither '0' nor '1'.
631 dynamic_bitset(const char* __str,
632 const allocator_type& __alloc = allocator_type())
637 while (__str[__len] != '\0')
640 this->_M_copy_from_ptr<char,std::char_traits<char>>
641 (__str, __len, 0, __len, '0', '1');
645 * @brief Copy constructor.
647 dynamic_bitset(const dynamic_bitset& __b)
648 : _Base(__b), _M_Nb(__b.size())
652 * @brief Move constructor.
654 dynamic_bitset(dynamic_bitset&& __b)
655 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
659 * @brief Swap with another bitset.
662 swap(dynamic_bitset& __b)
665 std::swap(this->_M_Nb, __b._M_Nb);
672 operator=(const dynamic_bitset& __b)
676 this->_M_assign(__b);
677 this->_M_Nb = __b._M_Nb;
682 * @brief Move assignment.
685 operator=(dynamic_bitset&& __b)
692 * @brief Return the allocator for the bitset.
695 get_allocator() const
696 { return this->_M_get_allocator(); }
699 * @brief Resize the bitset.
702 resize(size_type __nbits, bool __value = false)
706 this->_M_resize(__nbits, __value);
707 this->_M_Nb = __nbits;
708 this->_M_do_sanitize();
712 * @brief Clear the bitset.
722 * @brief Push a bit onto the high end of the bitset.
725 push_back(bool __bit)
727 if (size_t __offset = this->size() % bits_per_block == 0)
728 this->_M_do_append_block(block_type(0), this->_M_Nb);
730 this->_M_unchecked_set(this->_M_Nb, __bit);
734 * @brief Append a block.
737 append(block_type __block)
739 this->_M_do_append_block(__block, this->_M_Nb);
740 this->_M_Nb += bits_per_block;
747 append(initializer_list<block_type> __il)
748 { this->append(__il.begin(), __il.end()); }
751 * @brief Append an iterator range of blocks.
753 template <typename _BlockInputIterator>
755 append(_BlockInputIterator __first, _BlockInputIterator __last)
757 for (; __first != __last; ++__first)
758 this->append(*__first);
761 // 23.3.5.2 dynamic_bitset operations:
764 * @brief Operations on dynamic_bitsets.
765 * @param __rhs A same-sized dynamic_bitset.
767 * These should be self-explanatory.
769 dynamic_bitset<_WordT, _Alloc>&
770 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
772 this->_M_do_and(__rhs);
776 dynamic_bitset<_WordT, _Alloc>&
777 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
779 this->_M_do_and(std::move(__rhs));
783 dynamic_bitset<_WordT, _Alloc>&
784 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
786 this->_M_do_or(__rhs);
790 dynamic_bitset<_WordT, _Alloc>&
791 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
793 this->_M_do_xor(__rhs);
797 dynamic_bitset<_WordT, _Alloc>&
798 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
800 this->_M_do_dif(__rhs);
807 * @brief Operations on dynamic_bitsets.
808 * @param __pos The number of places to shift.
810 * These should be self-explanatory.
812 dynamic_bitset<_WordT, _Alloc>&
813 operator<<=(size_type __pos)
815 if (__builtin_expect(__pos < this->_M_Nb, 1))
817 this->_M_do_left_shift(__pos);
818 this->_M_do_sanitize();
825 dynamic_bitset<_WordT, _Alloc>&
826 operator>>=(size_type __pos)
828 if (__builtin_expect(__pos < this->_M_Nb, 1))
830 this->_M_do_right_shift(__pos);
831 this->_M_do_sanitize();
839 // Set, reset, and flip.
841 * @brief Sets every bit to true.
843 dynamic_bitset<_WordT, _Alloc>&
847 this->_M_do_sanitize();
852 * @brief Sets a given bit to a particular value.
853 * @param __pos The index of the bit.
854 * @param __val Either true or false, defaults to true.
855 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
857 dynamic_bitset<_WordT, _Alloc>&
858 set(size_type __pos, bool __val = true)
861 __throw_out_of_range(__N("dynamic_bitset::set"));
862 return this->_M_unchecked_set(__pos, __val);
866 * @brief Sets every bit to false.
868 dynamic_bitset<_WordT, _Alloc>&
876 * @brief Sets a given bit to false.
877 * @param __pos The index of the bit.
878 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
880 * Same as writing @c set(__pos, false).
882 dynamic_bitset<_WordT, _Alloc>&
883 reset(size_type __pos)
886 __throw_out_of_range(__N("dynamic_bitset::reset"));
887 return this->_M_unchecked_reset(__pos);
891 * @brief Toggles every bit to its opposite value.
893 dynamic_bitset<_WordT, _Alloc>&
897 this->_M_do_sanitize();
902 * @brief Toggles a given bit to its opposite value.
903 * @param __pos The index of the bit.
904 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
906 dynamic_bitset<_WordT, _Alloc>&
907 flip(size_type __pos)
910 __throw_out_of_range(__N("dynamic_bitset::flip"));
911 return this->_M_unchecked_flip(__pos);
914 /// See the no-argument flip().
915 dynamic_bitset<_WordT, _Alloc>
917 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
921 * @brief Array-indexing support.
922 * @param __pos Index into the %dynamic_bitset.
923 * @return A bool for a 'const %dynamic_bitset'. For non-const
924 * bitsets, an instance of the reference proxy class.
925 * @note These operators do no range checking and throw no
926 * exceptions, as required by DR 11 to the standard.
929 operator[](size_type __pos)
930 { return reference(*this,__pos); }
933 operator[](size_type __pos) const
934 { return _M_unchecked_test(__pos); }
938 * @brief Returns a numerical interpretation of the %dynamic_bitset.
939 * @return The integral equivalent of the bits.
940 * @throw std::overflow_error If there are too many bits to be
941 * represented in an @c unsigned @c long.
945 { return this->_M_do_to_ulong(); }
948 * @brief Returns a numerical interpretation of the %dynamic_bitset.
949 * @return The integral equivalent of the bits.
950 * @throw std::overflow_error If there are too many bits to be
951 * represented in an @c unsigned @c long.
955 { return this->_M_do_to_ullong(); }
958 * @brief Returns a character interpretation of the %dynamic_bitset.
959 * @return The string equivalent of the bits.
961 * Note the ordering of the bits: decreasing character positions
962 * correspond to increasing bit positions (see the main class notes for
965 template<typename _CharT = char,
966 typename _Traits = std::char_traits<_CharT>,
967 typename _Alloc1 = std::allocator<_CharT>>
968 std::basic_string<_CharT, _Traits, _Alloc1>
969 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
971 std::basic_string<_CharT, _Traits, _Alloc1> __result;
972 _M_copy_to_string(__result, __zero, __one);
976 // Helper functions for string operations.
977 template<typename _CharT, typename _Traits>
979 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
982 template<typename _CharT, typename _Traits, typename _Alloc1>
984 _M_copy_from_string(const std::basic_string<_CharT,
985 _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
986 _CharT __zero = _CharT('0'),
987 _CharT __one = _CharT('1'))
988 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
989 __pos, __n, __zero, __one); }
991 template<typename _CharT, typename _Traits, typename _Alloc1>
993 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
994 _CharT __zero = _CharT('0'),
995 _CharT __one = _CharT('1')) const;
997 /// Returns the number of bits which are set.
999 count() const noexcept
1000 { return this->_M_do_count(); }
1002 /// Returns the total number of bits.
1004 size() const noexcept
1005 { return this->_M_Nb; }
1007 /// Returns the total number of blocks.
1009 num_blocks() const noexcept
1010 { return this->_M_size(); }
1012 /// Returns true if the dynamic_bitset is empty.
1014 empty() const noexcept
1015 { return (this->_M_Nb == 0); }
1017 /// Returns the maximum size of a dynamic_bitset object having the same
1019 /// The real answer is max() * bits_per_block but is likely to overflow.
1022 { return std::numeric_limits<block_type>::max(); }
1025 * @brief Tests the value of a bit.
1026 * @param __pos The index of a bit.
1027 * @return The value at @a __pos.
1028 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1031 test(size_type __pos) const
1034 __throw_out_of_range(__N("dynamic_bitset::test"));
1035 return _M_unchecked_test(__pos);
1039 * @brief Tests whether all the bits are on.
1040 * @return True if all the bits are set.
1044 { return this->_M_are_all_aux() == _M_Nb; }
1047 * @brief Tests whether any of the bits are on.
1048 * @return True if at least one bit is set.
1052 { return this->_M_is_any(); }
1055 * @brief Tests whether any of the bits are on.
1056 * @return True if none of the bits are set.
1060 { return !this->_M_is_any(); }
1063 /// Self-explanatory.
1064 dynamic_bitset<_WordT, _Alloc>
1065 operator<<(size_type __pos) const
1066 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1068 dynamic_bitset<_WordT, _Alloc>
1069 operator>>(size_type __pos) const
1070 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1074 * @brief Finds the index of the first "on" bit.
1075 * @return The index of the first bit set, or size() if not found.
1080 { return this->_M_do_find_first(this->_M_Nb); }
1083 * @brief Finds the index of the next "on" bit after prev.
1084 * @return The index of the next bit set, or size() if not found.
1085 * @param __prev Where to start searching.
1089 find_next(size_t __prev) const
1090 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1093 is_subset_of(const dynamic_bitset& __b) const
1094 { return this->_M_is_subset_of(__b); }
1097 is_proper_subset_of(const dynamic_bitset& __b) const
1098 { return this->_M_is_proper_subset_of(__b); }
1101 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1102 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1103 { return __lhs._M_is_equal(__rhs); }
1106 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1107 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1108 { return __lhs._M_is_less(__rhs); }
1111 template<typename _WordT, typename _Alloc>
1112 template<typename _CharT, typename _Traits, typename _Alloc1>
1114 dynamic_bitset<_WordT, _Alloc>::
1115 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1116 _CharT __zero, _CharT __one) const
1118 __str.assign(_M_Nb, __zero);
1119 for (size_t __i = _M_Nb; __i > 0; --__i)
1120 if (_M_unchecked_test(__i - 1))
1121 _Traits::assign(__str[_M_Nb - __i], __one);
1126 /// These comparisons for equality/inequality are, well, @e bitwise.
1128 template<typename _WordT, typename _Alloc>
1130 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1131 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1132 { return !(__lhs == __rhs); }
1134 template<typename _WordT, typename _Alloc>
1136 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1137 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1138 { return !(__lhs > __rhs); }
1140 template<typename _WordT, typename _Alloc>
1142 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1143 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1144 { return __rhs < __lhs; }
1146 template<typename _WordT, typename _Alloc>
1148 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1149 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1150 { return !(__lhs < __rhs); }
1153 // 23.3.5.3 bitset operations:
1156 * @brief Global bitwise operations on bitsets.
1157 * @param __x A bitset.
1158 * @param __y A bitset of the same size as @a __x.
1159 * @return A new bitset.
1161 * These should be self-explanatory.
1163 template<typename _WordT, typename _Alloc>
1164 inline dynamic_bitset<_WordT, _Alloc>
1165 operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1166 const dynamic_bitset<_WordT, _Alloc>& __y)
1168 dynamic_bitset<_WordT, _Alloc> __result(__x);
1173 template<typename _WordT, typename _Alloc>
1174 inline dynamic_bitset<_WordT, _Alloc>
1175 operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1176 const dynamic_bitset<_WordT, _Alloc>& __y)
1178 dynamic_bitset<_WordT, _Alloc> __result(__x);
1183 template <typename _WordT, typename _Alloc>
1184 inline dynamic_bitset<_WordT, _Alloc>
1185 operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1186 const dynamic_bitset<_WordT, _Alloc>& __y)
1188 dynamic_bitset<_WordT, _Alloc> __result(__x);
1193 template <typename _WordT, typename _Alloc>
1194 inline dynamic_bitset<_WordT, _Alloc>
1195 operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1196 const dynamic_bitset<_WordT, _Alloc>& __y)
1198 dynamic_bitset<_WordT, _Alloc> __result(__x);
1204 /// Stream output operator for dynamic_bitset.
1205 template <typename _CharT, typename _Traits,
1206 typename _WordT, typename _Alloc>
1207 inline std::basic_ostream<_CharT, _Traits>&
1208 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1209 const dynamic_bitset<_WordT, _Alloc>& __x)
1211 std::basic_string<_CharT, _Traits> __tmp;
1213 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1214 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1215 return __os << __tmp;
1221 _GLIBCXX_END_NAMESPACE_VERSION
1225 #include <tr2/dynamic_bitset.tcc>
1227 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */