1 // TR2 <dynamic_bitset> -*- C++ -*-
3 // Copyright (C) 2009-2025 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 #ifdef _GLIBCXX_SYSHDR
33 #pragma GCC system_header
40 #include <bits/functexcept.h>
41 #include <bits/stl_algo.h> // For fill
42 #include <bits/cxxabi_forced.h>
44 namespace std _GLIBCXX_VISIBILITY(default)
46 _GLIBCXX_BEGIN_NAMESPACE_VERSION
51 * @defgroup dynamic_bitset Dynamic Bitset.
58 * Base class, general case.
60 * See documentation for dynamic_bitset.
62 template<typename _WordT = unsigned long long,
63 typename _Alloc = std::allocator<_WordT>>
64 struct __dynamic_bitset_base
66 static_assert(std::is_unsigned<_WordT>::value, "template argument "
67 "_WordT not an unsigned integral type");
69 typedef _WordT block_type;
70 typedef _Alloc allocator_type;
71 typedef size_t size_type;
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);
76 /// 0 is the least significant word.
77 std::vector<block_type, allocator_type> _M_w;
80 __dynamic_bitset_base(const allocator_type& __alloc)
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;
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)
97 if (__nbits < std::numeric_limits<decltype(__val)>::digits)
98 __val &= ~(-1ULL << __nbits);
102 if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type))
107 = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type));
108 for (size_t __i = 0; __val && __i < __n; ++__i)
110 _M_w[__i] = static_cast<block_type>(__val);
111 __val >>= _S_bits_per_block;
117 _M_swap(__dynamic_bitset_base& __b) noexcept
118 { this->_M_w.swap(__b._M_w); }
122 { this->_M_w.clear(); }
125 _M_resize(size_t __nbits, bool __value)
127 size_t __sz = __nbits / _S_bits_per_block;
128 if (__nbits % _S_bits_per_block > 0)
130 if (__sz != this->_M_w.size())
132 block_type __val = 0;
134 __val = std::numeric_limits<block_type>::max();
135 this->_M_w.resize(__sz, __val);
140 _M_get_allocator() const noexcept
141 { return this->_M_w.get_allocator(); }
144 _S_whichword(size_type __pos) noexcept
145 { return __pos / _S_bits_per_block; }
148 _S_whichbyte(size_type __pos) noexcept
149 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
152 _S_whichbit(size_type __pos) noexcept
153 { return __pos % _S_bits_per_block; }
156 _S_maskbit(size_type __pos) noexcept
157 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
160 _M_getword(size_type __pos) noexcept
161 { return this->_M_w[_S_whichword(__pos)]; }
164 _M_getword(size_type __pos) const noexcept
165 { return this->_M_w[_S_whichword(__pos)]; }
169 { return this->_M_w[_M_w.size() - 1]; }
172 _M_hiword() const noexcept
173 { return this->_M_w[_M_w.size() - 1]; }
176 _M_do_and(const __dynamic_bitset_base& __x) noexcept
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];
186 _M_do_or(const __dynamic_bitset_base& __x) noexcept
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];
196 _M_do_xor(const __dynamic_bitset_base& __x) noexcept
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];
206 _M_do_dif(const __dynamic_bitset_base& __x) noexcept
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];
216 _M_do_left_shift(size_t __shift);
219 _M_do_right_shift(size_t __shift);
222 _M_do_flip() noexcept
224 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
225 this->_M_w[__i] = ~this->_M_w[__i];
231 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
232 this->_M_w[__i] = static_cast<block_type>(-1);
236 _M_do_reset() noexcept
238 std::fill(_M_w.begin(), _M_w.end(), static_cast<block_type>(0));
242 _M_is_equal(const __dynamic_bitset_base& __x) const noexcept
244 if (__x._M_w.size() == this->_M_w.size())
246 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
247 if (this->_M_w[__i] != __x._M_w[__i])
256 _M_is_less(const __dynamic_bitset_base& __x) const noexcept
258 if (__x._M_w.size() == this->_M_w.size())
260 for (size_t __i = this->_M_w.size(); __i > 0; --__i)
262 if (this->_M_w[__i-1] < __x._M_w[__i-1])
264 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
274 _M_are_all_aux() const noexcept
276 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
277 if (_M_w[__i] != static_cast<block_type>(-1))
279 return ((this->_M_w.size() - 1) * _S_bits_per_block
280 + __builtin_popcountll(this->_M_hiword()));
284 _M_is_any() const noexcept
286 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
287 if (this->_M_w[__i] != static_cast<block_type>(0))
293 _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept
295 if (__b._M_w.size() == this->_M_w.size())
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]))
307 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const noexcept
309 if (this->_M_is_subset_of(__b))
321 _M_do_count() const noexcept
324 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
325 __result += __builtin_popcountll(this->_M_w[__i]);
330 _M_size() const noexcept
331 { return this->_M_w.size(); }
334 _M_do_to_ulong() const;
337 _M_do_to_ullong() const;
339 // find first "on" bit
341 _M_do_find_first(size_t __not_found) const;
343 // find the next "on" bit that follows "prev"
345 _M_do_find_next(size_t __prev, size_t __not_found) const;
347 // do append of block
349 _M_do_append_block(block_type __block, size_type __pos)
351 size_t __offset = __pos % _S_bits_per_block;
353 this->_M_w.push_back(__block);
356 this->_M_hiword() |= (__block << __offset);
357 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
363 * @brief The %dynamic_bitset class represents a sequence of bits.
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
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.
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.
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.
388 * #include <dynamic_bitset>
389 * #include <iostream>
392 * using namespace std;
397 * dynamic_bitset<> b(a);
399 * cout << "b('a') is " << b << endl;
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;
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.
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.
419 template<typename _WordT = unsigned long long,
420 typename _Alloc = std::allocator<_WordT>>
422 : private __dynamic_bitset_base<_WordT, _Alloc>
424 static_assert(std::is_unsigned<_WordT>::value, "template argument "
425 "_WordT not an unsigned integral type");
429 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
430 typedef _WordT block_type;
431 typedef _Alloc allocator_type;
432 typedef size_t size_type;
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);
440 // Clear the unused bits in the uppermost word.
444 size_type __shift = this->_M_Nb % bits_per_block;
446 this->_M_hiword() &= block_type(~(block_type(-1) << __shift));
449 // Set the unused bits in the uppermost word.
453 size_type __shift = this->_M_Nb % bits_per_block;
455 this->_M_hiword() |= block_type(block_type(-1) << __shift);
459 * These versions of single-bit set, reset, flip, and test
460 * do no range checking.
463 _M_unchecked_set(size_type __pos) noexcept
465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
470 _M_unchecked_set(size_type __pos, int __val) noexcept
473 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
475 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
480 _M_unchecked_reset(size_type __pos) noexcept
482 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
487 _M_unchecked_flip(size_type __pos) noexcept
489 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
494 _M_unchecked_test(size_type __pos) const noexcept
495 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
496 != static_cast<_WordT>(0)); }
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.
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
512 * (On a typical system, this "bit %reference" is 64 times the
513 * size of an actual bit. Ha.)
517 friend class dynamic_bitset;
523 reference(dynamic_bitset& __b, size_type __pos) noexcept
525 this->_M_wp = &__b._M_getword(__pos);
526 this->_M_bpos = _Base::_S_whichbit(__pos);
531 operator=(bool __x) noexcept
534 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
536 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
540 // For b[i] = b[__j];
542 operator=(const reference& __j) noexcept
544 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
545 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
547 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
553 operator~() const noexcept
554 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
557 operator bool() const noexcept
558 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
564 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
569 friend class reference;
571 typedef bool const_reference;
573 // 23.3.5.1 constructors:
575 /// All bits set to zero.
576 dynamic_bitset() = default;
578 /// All bits set to zero.
580 dynamic_bitset(const allocator_type& __alloc)
584 /// Initial bits bitwise-copied from a single word (others set to zero).
586 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
587 const allocator_type& __alloc = allocator_type())
588 : _Base(__nbits, __val, __alloc),
592 dynamic_bitset(initializer_list<block_type> __il,
593 const allocator_type& __alloc = allocator_type())
595 { this->append(__il); }
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'.
609 template<typename _CharT, typename _Traits, typename _Alloc1>
611 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
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())
620 if (__pos > __str.size())
621 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
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);
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'.
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))
643 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
646 /// Copy constructor.
647 dynamic_bitset(const dynamic_bitset&) = default;
649 /// Move constructor.
650 dynamic_bitset(dynamic_bitset&& __b) noexcept
651 : _Base(std::move(__b)), _M_Nb(__b._M_Nb)
654 /// Swap with another bitset.
656 swap(dynamic_bitset& __b) noexcept
659 std::swap(this->_M_Nb, __b._M_Nb);
662 /// Copy assignment operator.
663 dynamic_bitset& operator=(const dynamic_bitset&) = default;
665 /// Move assignment operator.
667 operator=(dynamic_bitset&& __b)
668 noexcept(std::is_nothrow_move_assignable<_Base>::value)
670 static_cast<_Base&>(*this) = static_cast<_Base&&>(__b);
672 if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable<_Base>::value)
674 else if (get_allocator() == __b.get_allocator())
680 * @brief Return the allocator for the bitset.
683 get_allocator() const noexcept
684 { return this->_M_get_allocator(); }
687 * @brief Resize the bitset.
690 resize(size_type __nbits, bool __value = false)
694 this->_M_resize(__nbits, __value);
695 this->_M_Nb = __nbits;
696 this->_M_do_sanitize();
700 * @brief Clear the bitset.
710 * @brief Push a bit onto the high end of the bitset.
713 push_back(bool __bit)
715 if (this->size() % bits_per_block == 0)
716 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
718 this->_M_unchecked_set(this->_M_Nb, __bit);
722 // XXX why is there no pop_back() member in the proposal?
725 * @brief Append a block.
728 append(block_type __block)
730 this->_M_do_append_block(__block, this->_M_Nb);
731 this->_M_Nb += bits_per_block;
738 append(initializer_list<block_type> __il)
739 { this->append(__il.begin(), __il.end()); }
742 * @brief Append an iterator range of blocks.
744 template <typename _BlockInputIterator>
746 append(_BlockInputIterator __first, _BlockInputIterator __last)
748 for (; __first != __last; ++__first)
749 this->append(*__first);
752 // 23.3.5.2 dynamic_bitset operations:
755 * @brief Operations on dynamic_bitsets.
756 * @param __rhs A same-sized dynamic_bitset.
758 * These should be self-explanatory.
761 operator&=(const dynamic_bitset& __rhs)
763 this->_M_do_and(__rhs);
768 operator&=(dynamic_bitset&& __rhs)
770 this->_M_do_and(std::move(__rhs));
775 operator|=(const dynamic_bitset& __rhs)
777 this->_M_do_or(__rhs);
782 operator^=(const dynamic_bitset& __rhs)
784 this->_M_do_xor(__rhs);
789 operator-=(const dynamic_bitset& __rhs)
791 this->_M_do_dif(__rhs);
798 * @brief Operations on dynamic_bitsets.
799 * @param __pos The number of places to shift.
801 * These should be self-explanatory.
804 operator<<=(size_type __pos)
806 if (__builtin_expect(__pos < this->_M_Nb, 1))
808 this->_M_do_left_shift(__pos);
809 this->_M_do_sanitize();
817 operator>>=(size_type __pos)
819 if (__builtin_expect(__pos < this->_M_Nb, 1))
820 this->_M_do_right_shift(__pos);
827 // Set, reset, and flip.
829 * @brief Sets every bit to true.
835 this->_M_do_sanitize();
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.
846 set(size_type __pos, bool __val = true)
849 __throw_out_of_range(__N("dynamic_bitset::set"));
850 return this->_M_unchecked_set(__pos, __val);
854 * @brief Sets every bit to false.
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.
868 * Same as writing @c set(__pos, false).
871 reset(size_type __pos)
874 __throw_out_of_range(__N("dynamic_bitset::reset"));
875 return this->_M_unchecked_reset(__pos);
879 * @brief Toggles every bit to its opposite value.
885 this->_M_do_sanitize();
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.
895 flip(size_type __pos)
898 __throw_out_of_range(__N("dynamic_bitset::flip"));
899 return this->_M_unchecked_flip(__pos);
902 /// See the no-argument flip().
905 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
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.
917 operator[](size_type __pos)
918 { return reference(*this,__pos); }
921 operator[](size_type __pos) const
922 { return _M_unchecked_test(__pos); }
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.
933 { return this->_M_do_to_ulong(); }
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.
943 { return this->_M_do_to_ullong(); }
946 * @brief Returns a character interpretation of the %dynamic_bitset.
947 * @return The string equivalent of the bits.
949 * Note the ordering of the bits: decreasing character positions
950 * correspond to increasing bit positions (see the main class notes for
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
959 std::basic_string<_CharT, _Traits, _Alloc1> __result;
960 _M_copy_to_string(__result, __zero, __one);
964 // Helper functions for string operations.
965 template<typename _Traits = std::char_traits<char>,
966 typename _CharT = typename _Traits::char_type>
968 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
969 _CharT __zero = _CharT('0'),
970 _CharT __one = _CharT('1'));
972 template<typename _CharT, typename _Traits, typename _Alloc1>
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'))
979 _M_copy_from_ptr<_Traits>(__str.data(), __str.size(), __pos, __n,
983 template<typename _CharT, typename _Traits, typename _Alloc1>
985 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
986 _CharT __zero = _CharT('0'),
987 _CharT __one = _CharT('1')) const;
989 /// Returns the number of bits which are set.
991 count() const noexcept
992 { return this->_M_do_count(); }
994 /// Returns the total number of bits.
996 size() const noexcept
997 { return this->_M_Nb; }
999 /// Returns the total number of blocks.
1001 num_blocks() const noexcept
1002 { return this->_M_size(); }
1004 /// Returns true if the dynamic_bitset is empty.
1005 _GLIBCXX_NODISCARD bool
1006 empty() const noexcept
1007 { return (this->_M_Nb == 0); }
1009 /// Returns the maximum size of a dynamic_bitset object having the same
1011 /// The real answer is max() * bits_per_block but is likely to overflow.
1014 { return std::numeric_limits<block_type>::max(); }
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.
1023 test(size_type __pos) const
1026 __throw_out_of_range(__N("dynamic_bitset::test"));
1027 return _M_unchecked_test(__pos);
1031 * @brief Tests whether all the bits are on.
1032 * @return True if all the bits are set.
1036 { return this->_M_are_all_aux() == _M_Nb; }
1039 * @brief Tests whether any of the bits are on.
1040 * @return True if at least one bit is set.
1044 { return this->_M_is_any(); }
1047 * @brief Tests whether any of the bits are on.
1048 * @return True if none of the bits are set.
1052 { return !this->_M_is_any(); }
1055 /// Self-explanatory.
1057 operator<<(size_type __pos) const
1058 { return dynamic_bitset(*this) <<= __pos; }
1061 operator>>(size_type __pos) const
1062 { return dynamic_bitset(*this) >>= __pos; }
1066 * @brief Finds the index of the first "on" bit.
1067 * @return The index of the first bit set, or size() if not found.
1072 { return this->_M_do_find_first(this->_M_Nb); }
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.
1081 find_next(size_t __prev) const
1082 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1085 is_subset_of(const dynamic_bitset& __b) const
1086 { return this->_M_is_subset_of(__b); }
1089 is_proper_subset_of(const dynamic_bitset& __b) const
1090 { return this->_M_is_proper_subset_of(__b); }
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); }
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; }
1103 template<typename _WordT, typename _Alloc>
1104 template<typename _CharT, typename _Traits, typename _Alloc1>
1106 dynamic_bitset<_WordT, _Alloc>::
1107 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1108 _CharT __zero, _CharT __one) const
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);
1118 /// These comparisons for equality/inequality are, well, @e bitwise.
1120 template<typename _WordT, typename _Alloc>
1122 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1123 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1124 { return !(__lhs == __rhs); }
1126 template<typename _WordT, typename _Alloc>
1128 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1129 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1130 { return !(__lhs > __rhs); }
1132 template<typename _WordT, typename _Alloc>
1134 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1135 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1136 { return __rhs < __lhs; }
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); }
1145 // 23.3.5.3 bitset operations:
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.
1153 * These should be self-explanatory.
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)
1160 dynamic_bitset<_WordT, _Alloc> __result(__x);
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)
1170 dynamic_bitset<_WordT, _Alloc> __result(__x);
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)
1180 dynamic_bitset<_WordT, _Alloc> __result(__x);
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)
1190 dynamic_bitset<_WordT, _Alloc> __result(__x);
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)
1203 std::basic_string<_CharT, _Traits> __tmp;
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;
1214 _GLIBCXX_END_NAMESPACE_VERSION
1217 #include <tr2/dynamic_bitset.tcc>
1219 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */