libstdc++
|
The dynamic_bitset class represents a sequence of bits.
(Note that dynamic_bitset does not meet the formal requirements of a container. Mainly, it lacks iterators.)
The template argument, Nb, may be any non-negative number, specifying the number of bits (e.g., "0", "12", "1024*1024").
In the general unoptimized case, storage is allocated in word-sized blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B words will be used for storage. B - NbB bits are unused. (They are the high-order bits in the highest word.) It is a class invariant that those unused bits are always zero.
If you think of dynamic_bitset as "a simple array of bits," be aware that your mental picture is reversed: a dynamic_bitset behaves the same way as bits in integers do, with the bit at index 0 in the "least significant / right-hand" position, and the bit at index Nb-1 in the "most significant / left-hand" position. Thus, unlike other containers, a dynamic_bitset's index "counts from right to left," to put it very loosely.
This behavior is preserved when translating to and from strings. For example, the first line of the following program probably prints "b('a') is 0001100001" on a modern ASCII system.
#include <dynamic_bitset> #include <iostream> #include <sstream> using namespace std; int main() { long a = 'a'; dynamic_bitset b(a); cout << "b('a') is " << b << endl; ostringstream s; s << b; string str = s.str(); cout << "index 3 in the string is " << str[3] << " but\n" << "index 3 in the bitset is " << b[3] << endl; }
Also see: http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html for a description of extensions.
Most of the actual code isn't contained in dynamic_bitset<> itself, but in the base class __dynamic_bitset_base. The base class works with whole words, not with individual bits. This allows us to specialize __dynamic_bitset_base for the important special case where the dynamic_bitset is only a single word.
Extra confusion can result due to the fact that the storage for __dynamic_bitset_base is a vector, and is indexed as such. This is carefully encapsulated.
Definition at line 570 of file dynamic_bitset.
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | const allocator_type & | __alloc = allocator_type() | ) | [inline, explicit] |
All bits set to zero.
Definition at line 722 of file dynamic_bitset.
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | size_type | __nbits, |
unsigned long long | __val = 0ULL , |
||
const allocator_type & | __alloc = allocator_type() |
||
) | [inline, explicit] |
Initial bits bitwise-copied from a single word (others set to zero).
Definition at line 728 of file dynamic_bitset.
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | const std::basic_string< _CharT, _Traits, _Alloc1 > & | __str, |
typename basic_string< _CharT, _Traits, _Alloc1 >::size_type | __pos = 0 , |
||
typename basic_string< _CharT, _Traits, _Alloc1 >::size_type | __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos , |
||
_CharT | __zero = _CharT('0') , |
||
_CharT | __one = _CharT('1') , |
||
const allocator_type & | __alloc = allocator_type() |
||
) | [inline, explicit] |
Use a subset of a string.
__str | A string of '0' and '1' characters. |
__pos | Index of the first character in __str to use. |
__n | The number of characters to copy. |
std::out_of_range | If __pos is bigger the size of __str . |
std::invalid_argument | If a character appears in the string which is neither '0' nor '1'. |
Definition at line 750 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::resize(), and std::basic_string< _CharT, _Traits, _Alloc >::size().
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | const char * | __str, |
const allocator_type & | __alloc = allocator_type() |
||
) | [inline, explicit] |
Construct from a string.
__str | A string of '0' and '1' characters. |
std::invalid_argument | If a character appears in the string which is neither '0' nor '1'. |
Definition at line 778 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::resize().
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | const dynamic_bitset< _WordT, _Alloc > & | __b | ) | [inline] |
Copy constructor.
Definition at line 794 of file dynamic_bitset.
std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset | ( | dynamic_bitset< _WordT, _Alloc > && | __b | ) | [inline] |
Move constructor.
Definition at line 801 of file dynamic_bitset.
bool std::tr2::dynamic_bitset< _WordT, _Alloc >::all | ( | ) | const [inline] |
Tests whether all the bits are on.
Definition at line 1187 of file dynamic_bitset.
bool std::tr2::dynamic_bitset< _WordT, _Alloc >::any | ( | ) | const [inline] |
Tests whether any of the bits are on.
Definition at line 1195 of file dynamic_bitset.
void std::tr2::dynamic_bitset< _WordT, _Alloc >::append | ( | block_type | __block | ) | [inline] |
Append a block.
Definition at line 882 of file dynamic_bitset.
Referenced by std::tr2::dynamic_bitset< _WordT, _Alloc >::append().
void std::tr2::dynamic_bitset< _WordT, _Alloc >::append | ( | initializer_list< block_type > | __il | ) | [inline] |
Definition at line 892 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::append().
Referenced by std::tr2::dynamic_bitset< _WordT, _Alloc >::append().
void std::tr2::dynamic_bitset< _WordT, _Alloc >::append | ( | _BlockInputIterator | __first, |
_BlockInputIterator | __last | ||
) | [inline] |
Append an iterator range of blocks.
Definition at line 900 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::append().
void std::tr2::dynamic_bitset< _WordT, _Alloc >::clear | ( | ) | [inline] |
Clear the bitset.
Definition at line 860 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::count | ( | ) | const [inline] |
Returns the number of bits which are set.
Definition at line 1144 of file dynamic_bitset.
bool std::tr2::dynamic_bitset< _WordT, _Alloc >::empty | ( | ) | const [inline] |
Returns true if the dynamic_bitset is empty.
Definition at line 1158 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::find_first | ( | ) | const [inline] |
Finds the index of the first "on" bit.
Definition at line 1223 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::find_next | ( | size_t | __prev | ) | const [inline] |
Finds the index of the next "on" bit after prev.
__prev | Where to start searching. |
Definition at line 1233 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::flip | ( | ) | [inline] |
Toggles every bit to its opposite value.
Definition at line 1039 of file dynamic_bitset.
Referenced by std::tr2::dynamic_bitset< _WordT, _Alloc >::operator~().
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::flip | ( | size_type | __pos | ) | [inline] |
Toggles a given bit to its opposite value.
__pos | The index of the bit. |
std::out_of_range | If __pos is bigger the size of the set. |
Definition at line 1052 of file dynamic_bitset.
allocator_type std::tr2::dynamic_bitset< _WordT, _Alloc >::get_allocator | ( | ) | const [inline] |
Return the allocator for the bitset.
Definition at line 842 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::max_size | ( | ) | const [inline] |
Returns the maximum size of a dynamic_bitset object having the same type as *this. The real answer is max() * bits_per_block but is likely to overflow.
Definition at line 1165 of file dynamic_bitset.
References std::max().
bool std::tr2::dynamic_bitset< _WordT, _Alloc >::none | ( | ) | const [inline] |
Tests whether any of the bits are on.
Definition at line 1203 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::num_blocks | ( | ) | const [inline] |
Returns the total number of blocks.
Definition at line 1153 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator&= | ( | const dynamic_bitset< _WordT, _Alloc > & | __rhs | ) | [inline] |
Operations on dynamic_bitsets.
__rhs | A same-sized dynamic_bitset. |
These should be self-explanatory.
Definition at line 915 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator&= | ( | dynamic_bitset< _WordT, _Alloc > && | __rhs | ) | [inline] |
Operations on dynamic_bitsets.
__rhs | A same-sized dynamic_bitset. |
These should be self-explanatory.
Definition at line 922 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator-= | ( | const dynamic_bitset< _WordT, _Alloc > & | __rhs | ) | [inline] |
Operations on dynamic_bitsets.
__rhs | A same-sized dynamic_bitset. |
These should be self-explanatory.
Definition at line 943 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc> std::tr2::dynamic_bitset< _WordT, _Alloc >::operator<< | ( | size_type | __pos | ) | const [inline] |
Self-explanatory.
Definition at line 1209 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator<<= | ( | size_type | __pos | ) | [inline] |
Operations on dynamic_bitsets.
__pos | The number of places to shift. |
These should be self-explanatory.
Definition at line 958 of file dynamic_bitset.
dynamic_bitset& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator= | ( | const dynamic_bitset< _WordT, _Alloc > & | __b | ) | [inline] |
Assignment.
Definition at line 819 of file dynamic_bitset.
dynamic_bitset& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator= | ( | dynamic_bitset< _WordT, _Alloc > && | __b | ) | [inline] |
Move assignment.
Definition at line 832 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::swap().
dynamic_bitset<_WordT, _Alloc> std::tr2::dynamic_bitset< _WordT, _Alloc >::operator>> | ( | size_type | __pos | ) | const [inline] |
Self-explanatory.
Definition at line 1213 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator>>= | ( | size_type | __pos | ) | [inline] |
Operations on dynamic_bitsets.
__pos | The number of places to shift. |
These should be self-explanatory.
Definition at line 971 of file dynamic_bitset.
reference std::tr2::dynamic_bitset< _WordT, _Alloc >::operator[] | ( | size_type | __pos | ) | [inline] |
Array-indexing support.
__pos | Index into the dynamic_bitset. |
Definition at line 1074 of file dynamic_bitset.
const_reference std::tr2::dynamic_bitset< _WordT, _Alloc >::operator[] | ( | size_type | __pos | ) | const [inline] |
Array-indexing support.
__pos | Index into the dynamic_bitset. |
Definition at line 1078 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator^= | ( | const dynamic_bitset< _WordT, _Alloc > & | __rhs | ) | [inline] |
Operations on dynamic_bitsets.
__rhs | A same-sized dynamic_bitset. |
These should be self-explanatory.
Definition at line 936 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::operator|= | ( | const dynamic_bitset< _WordT, _Alloc > & | __rhs | ) | [inline] |
Operations on dynamic_bitsets.
__rhs | A same-sized dynamic_bitset. |
These should be self-explanatory.
Definition at line 929 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc> std::tr2::dynamic_bitset< _WordT, _Alloc >::operator~ | ( | ) | const [inline] |
See the no-argument flip().
Definition at line 1061 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::flip().
void std::tr2::dynamic_bitset< _WordT, _Alloc >::push_back | ( | bool | __bit | ) | [inline] |
Push a bit onto the high end of the bitset.
Definition at line 870 of file dynamic_bitset.
References std::tr2::dynamic_bitset< _WordT, _Alloc >::size().
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::reset | ( | ) | [inline] |
Sets every bit to false.
Definition at line 1014 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::reset | ( | size_type | __pos | ) | [inline] |
Sets a given bit to false.
__pos | The index of the bit. |
std::out_of_range | If __pos is bigger the size of the set. |
Same as writing set(__pos, false)
.
Definition at line 1028 of file dynamic_bitset.
void std::tr2::dynamic_bitset< _WordT, _Alloc >::resize | ( | size_type | __nbits, |
bool | __value = false |
||
) | [inline] |
Resize the bitset.
Definition at line 849 of file dynamic_bitset.
Referenced by std::tr2::dynamic_bitset< _WordT, _Alloc >::dynamic_bitset(), and std::tr2::operator>>().
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::set | ( | ) | [inline] |
Sets every bit to true.
Definition at line 989 of file dynamic_bitset.
dynamic_bitset<_WordT, _Alloc>& std::tr2::dynamic_bitset< _WordT, _Alloc >::set | ( | size_type | __pos, |
bool | __val = true |
||
) | [inline] |
Sets a given bit to a particular value.
__pos | The index of the bit. |
__val | Either true or false, defaults to true. |
std::out_of_range | If __pos is bigger the size of the set. |
Definition at line 1003 of file dynamic_bitset.
size_type std::tr2::dynamic_bitset< _WordT, _Alloc >::size | ( | ) | const [inline] |
Returns the total number of bits.
Definition at line 1149 of file dynamic_bitset.
Referenced by std::tr2::operator>>(), and std::tr2::dynamic_bitset< _WordT, _Alloc >::push_back().
void std::tr2::dynamic_bitset< _WordT, _Alloc >::swap | ( | dynamic_bitset< _WordT, _Alloc > & | __b | ) | [inline] |
Swap with another bitset.
Definition at line 809 of file dynamic_bitset.
Referenced by std::tr2::dynamic_bitset< _WordT, _Alloc >::operator=().
bool std::tr2::dynamic_bitset< _WordT, _Alloc >::test | ( | size_type | __pos | ) | const [inline] |
Tests the value of a bit.
__pos | The index of a bit. |
std::out_of_range | If __pos is bigger the size of the set. |
Definition at line 1175 of file dynamic_bitset.
std::basic_string<_CharT, _Traits, _Alloc1> std::tr2::dynamic_bitset< _WordT, _Alloc >::to_string | ( | _CharT | __zero = _CharT('0') , |
_CharT | __one = _CharT('1') |
||
) | const [inline] |
Returns a character interpretation of the dynamic_bitset.
Note the ordering of the bits: decreasing character positions correspond to increasing bit positions (see the main class notes for an example).
Definition at line 1114 of file dynamic_bitset.
unsigned long long std::tr2::dynamic_bitset< _WordT, _Alloc >::to_ullong | ( | ) | const [inline] |
Returns a numerical interpretation of the dynamic_bitset.
std::overflow_error | If there are too many bits to be represented in an unsigned long . |
Definition at line 1099 of file dynamic_bitset.
unsigned long std::tr2::dynamic_bitset< _WordT, _Alloc >::to_ulong | ( | ) | const [inline] |
Returns a numerical interpretation of the dynamic_bitset.
std::overflow_error | If there are too many bits to be represented in an unsigned long . |
Definition at line 1089 of file dynamic_bitset.