mirror of
https://github.com/boostorg/dynamic_bitset.git
synced 2026-01-19 04:12:09 +00:00
1380 lines
49 KiB
HTML
1380 lines
49 KiB
HTML
<HTML>
|
|
<!--
|
|
-- (C) Jeremy Siek 2001. Permission to copy, use, modify, sell and
|
|
-- distribute this software is granted provided this copyright notice
|
|
-- appears in all copies. This software is provided "as is" without
|
|
-- express or implied warranty, and with no claim as to its suitability
|
|
-- for any purpose.
|
|
-->
|
|
|
|
<!--
|
|
-- Copyright (c) 1996-1999
|
|
-- Silicon Graphics Computer Systems, Inc.
|
|
--
|
|
-- Permission to use, copy, modify, distribute and sell this software
|
|
-- and its documentation for any purpose is hereby granted without fee,
|
|
-- provided that the above copyright notice appears in all copies and
|
|
-- that both that copyright notice and this permission notice appear
|
|
-- in supporting documentation. Silicon Graphics makes no
|
|
-- representations about the suitability of this software for any
|
|
-- purpose. It is provided "as is" without express or implied warranty.
|
|
--
|
|
-- Copyright (c) 1994
|
|
-- Hewlett-Packard Company
|
|
--
|
|
-- Permission to use, copy, modify, distribute and sell this software
|
|
-- and its documentation for any purpose is hereby granted without fee,
|
|
-- provided that the above copyright notice appears in all copies and
|
|
-- that both that copyright notice and this permission notice appear
|
|
-- in supporting documentation. Hewlett-Packard Company makes no
|
|
-- representations about the suitability of this software for any
|
|
-- purpose. It is provided "as is" without express or implied warranty.
|
|
--
|
|
-->
|
|
<Head>
|
|
<Title>dynamic_bitset<Block, Allocator></Title>
|
|
</HEAD>
|
|
<BODY TEXT="#000000" LINK="#006600" ALINK="#003300" VLINK="#7C7F87" BGCOLOR="#FFFFFF">
|
|
|
|
<img src="../../c++boost.gif" alt="c++boost.gif (8819 bytes)" align=
|
|
"center" width="277" height="86">
|
|
<P>
|
|
<!--end header-->
|
|
<BR Clear>
|
|
<H1>dynamic_bitset<Block, Allocator></H1>
|
|
|
|
<h2>Contents</h2>
|
|
<dl class="index">
|
|
<dt><a href="#description">Description</a></dt>
|
|
<dt><a href="#synopsis">Synopsis</a></dt>
|
|
<dt><a href="#definitions">Definitions</a></dt>
|
|
<dt><a href="#examples">Examples</a></dt>
|
|
<dt><a href="#rationale">Rationale</a></dt>
|
|
<dt><a href="#header-files">Header Files</a></dt>
|
|
<dt><a href="#template-parameters">Template Parameters</a></dt>
|
|
<dt><a href="#concepts-modeled">Concepts modeled</a></dt>
|
|
<dt><a href="#type-requirements">Type requirements</a></dt>
|
|
<dt><a href="#public-base-classes">Public base classes</a></dt>
|
|
<dt><a href="#member-typedefs">Member typedefs</a></dt>
|
|
<dt><a href="#constructors">Constructors</a></dt>
|
|
<dt><a href="#destructor">Destructor</a></dt>
|
|
<dt><a href="#member-functions">Member functions</a></dt>
|
|
<dt><a href="#non-member-functions">Non-member functions</a></dt>
|
|
<dt><a href="#see-also">See also</a></dt>
|
|
<dt><a href="#acknowledgements">Acknowledgements</a></dt>
|
|
</dl>
|
|
|
|
<h3><a name="description">Description</a></h3>
|
|
|
|
<p>
|
|
The <tt>dynamic_bitset</tt> class represents a set of bits. It provides
|
|
accesses to the value of individual bits via an <tt>operator[]</tt>
|
|
and provides all of the bitwise operators that one can apply to
|
|
builtin integers, such as <tt>operator&</tt> and
|
|
<tt>operator<<</tt>. The number of bits in the set is specified
|
|
at runtime via a parameter to the constructor of the
|
|
<tt>dynamic_bitset</tt>.</p>
|
|
|
|
<p>
|
|
The <tt>dynamic_bitset</tt> class is nearly identical to the <a
|
|
href="http://www.sgi.com/tech/stl/bitset.html"><tt>std::bitset</tt></a>
|
|
class. The difference is that the size of the <tt>dynamic_bitset</tt>
|
|
(the number of bits) is specified at run-time during the construction
|
|
of a <tt>dynamic_bitset</tt> object, whereas the size of a
|
|
<tt>std::bitset</tt> is specified at compile-time through an integer
|
|
template parameter.</p>
|
|
|
|
<p>The main problem that <tt>dynamic_bitset</tt> is designed to solve is
|
|
that of representing a subset of a finite set. Each bit represents
|
|
whether an element of the finite set is in the subset or not. As such
|
|
the bitwise operations of <tt>dynamic_bitset</tt>, such as
|
|
<tt>operator&</tt> and <tt>operator|</tt>, correspond to set
|
|
operations, such as intersection and union. </p>
|
|
|
|
<h3><a name="synopsis">Synopsis</a></h3>
|
|
|
|
<pre>
|
|
namespace boost {
|
|
|
|
template <typename Block, typename Allocator>
|
|
class dynamic_bitset
|
|
{
|
|
public:
|
|
typedef Block <a href="#block_type">block_type</a>;
|
|
typedef <i>implementation-defined</i> <a href="#size_type">size_type</a>;
|
|
enum { <a href="#bits_per_block">bits_per_block</a> = CHAR_BIT * sizeof(Block) };
|
|
|
|
class <a href="#reference">reference</a>
|
|
{
|
|
public:
|
|
// An automatically generated copy constructor.
|
|
reference& operator=(bool value);
|
|
reference& operator|=(bool value);
|
|
reference& operator&=(bool value);
|
|
reference& operator^=(bool value);
|
|
reference& operator-=(bool value);
|
|
reference& operator=(const reference& j);
|
|
reference& operator|=(const reference& j);
|
|
reference& operator&=(const reference& j);
|
|
reference& operator^=(const reference& j);
|
|
reference& operator-=(const reference& j);
|
|
bool operator~() const;
|
|
operator bool() const;
|
|
reference& flip();
|
|
};
|
|
typedef bool <a href="#const_reference">const_reference</a>;
|
|
|
|
explicit <a href="#cons1">dynamic_bitset</a>(const Allocator& alloc = Allocator());
|
|
|
|
explicit <a href="#cons2">dynamic_bitset</a>(size_type num_bits, unsigned long value = 0,
|
|
const Allocator& alloc = Allocator());
|
|
|
|
template <typename CharT, typename Traits, typename Alloc>
|
|
explicit <a href="#cons3">dynamic_bitset</a>(const std::basic_string<CharT, Traits, Alloc>& s,
|
|
typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0,
|
|
typename std::basic_string<CharT, Traits, Alloc>::size_type n = std::basic_string<CharT, Traits, Alloc>::npos,
|
|
const Allocator& alloc = Allocator());
|
|
|
|
template <typename BlockInputIterator>
|
|
<a href="#cons4">dynamic_bitset</a>(BlockInputIterator first, BlockInputIterator last,
|
|
const Allocator& alloc = Allocator());
|
|
|
|
<a href="#cons5">dynamic_bitset</a>(const dynamic_bitset& b);
|
|
|
|
void <a href="#swap">swap</a>(dynamic_bitset& b);
|
|
|
|
dynamic_bitset& <a href="#assign">operator=</a>(const dynamic_bitset& b);
|
|
|
|
void <a href="#resize">resize</a>(size_type num_bits, bool value = false);
|
|
void <a href="#clear">clear</a>();
|
|
void <a href="#push_back">push_back</a>(bool bit);
|
|
void <a href="#append1">append</a>(Block block);
|
|
template <typename BlockInputIterator>
|
|
void <a href="#append2">append</a>(BlockInputIterator first, BlockInputIterator last);
|
|
|
|
dynamic_bitset& <a href="#op-and-assign">operator&=</a>(const dynamic_bitset& b);
|
|
dynamic_bitset& <a href="#op-or-assign">operator|=</a>(const dynamic_bitset& b);
|
|
dynamic_bitset& <a href="#op-xor-assign">operator^=</a>(const dynamic_bitset& b);
|
|
dynamic_bitset& <a href="#op-sub-assign">operator-=</a>(const dynamic_bitset& b);
|
|
dynamic_bitset& <a href="#op-sl-assign">operator<<=</a>(size_type n);
|
|
dynamic_bitset& <a href="#op-sr-assign">operator>>=</a>(size_type n);
|
|
dynamic_bitset <a href="#op-sl">operator<<</a>(size_type n) const;
|
|
dynamic_bitset <a href="#op-sr">operator>></a>(size_type n) const;
|
|
|
|
dynamic_bitset& <a href="#set2">set</a>(size_type n, bool val = true);
|
|
dynamic_bitset& <a href="#set1">set</a>();
|
|
dynamic_bitset& <a href="#reset2">reset</a>(size_type n);
|
|
dynamic_bitset& <a href="#reset1">reset</a>();
|
|
dynamic_bitset& <a href="#flip2">flip</a>(size_type n);
|
|
dynamic_bitset& <a href="#flip1">flip</a>();
|
|
bool <a href="#test">test</a>(size_type n) const;
|
|
bool <a href="#any">any</a>() const;
|
|
bool <a href="#none">none</a>() const;
|
|
dynamic_bitset <a href="#op-not">operator~</a>() const;
|
|
size_type <a href="#count">count</a>() const;
|
|
|
|
reference <a href="#bracket">operator[]</a>(size_type pos) { return reference(*this, pos); }
|
|
bool <a href="#const-bracket">operator[]</a>(size_type pos) const { return test(pos); }
|
|
|
|
unsigned long <a href="#to_ulong">to_ulong</a>() const;
|
|
|
|
size_type <a href="#size">size</a>() const;
|
|
size_type <a href="#num_blocks">num_blocks</a>() const;
|
|
|
|
bool <a href="#is_subset_of">is_subset_of</a>(const dynamic_bitset& a) const;
|
|
bool <a href="#is_proper_subset_of">is_proper_subset_of</a>(const dynamic_bitset& a) const;
|
|
};
|
|
|
|
template <typename B, typename A>
|
|
bool <a href="#op-equal">operator==</a>(const dynamic_bitset<B, A>& a, const dynamic_bitset<B, A>& b);
|
|
|
|
template <typename Block, typename Allocator>
|
|
bool <a href="#op-not-equal">operator!=</a>(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b);
|
|
|
|
template <typename B, typename A>
|
|
bool <a href="#op-less">operator<</a>(const dynamic_bitset<B, A>& a, const dynamic_bitset<B, A>& b);
|
|
|
|
template <typename Block, typename Allocator>
|
|
bool <a href="#op-less-equal">operator<=</a>(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b);
|
|
|
|
template <typename Block, typename Allocator>
|
|
bool <a href="#op-greater">operator></a>(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b);
|
|
|
|
template <typename Block, typename Allocator>
|
|
bool <a href="#op-greater-equal">operator>=</a>(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b);
|
|
|
|
template <typename Block, typename Allocator>
|
|
dynamic_bitset<Block, Allocator>
|
|
<a href="#op-and">operator&</a>(const dynamic_bitset<Block, Allocator>& b1, const dynamic_bitset<Block, Allocator>& b2);
|
|
|
|
template <typename Block, typename Allocator>
|
|
dynamic_bitset<Block, Allocator>
|
|
<a href="#op-or">operator|</a>(const dynamic_bitset<Block, Allocator>& b1, const dynamic_bitset<Block, Allocator>& b2);
|
|
|
|
template <typename Block, typename Allocator>
|
|
dynamic_bitset<Block, Allocator>
|
|
<a href="#op-xor">operator^</a>(const dynamic_bitset<Block, Allocator>& b1, const dynamic_bitset<Block, Allocator>& b2);
|
|
|
|
template <typename Block, typename Allocator>
|
|
dynamic_bitset<Block, Allocator>
|
|
<a href="#op-sub">operator-</a>(const dynamic_bitset<Block, Allocator>& b1, const dynamic_bitset<Block, Allocator>& b2);
|
|
|
|
template <typename Block, typename Allocator, typename CharT, typename Alloc>
|
|
void <a href="#to_string">to_string</a>(const dynamic_bitset<Block, Allocator>& b,
|
|
std::basic_string<CharT, Alloc>& s);
|
|
|
|
template <typename Block, typename Allocator, typename BlockOutputIterator>
|
|
void <a href="#to_block_range">to_block_range</a>(const dynamic_bitset<Block, Allocator>& b,
|
|
BlockOutputIterator result);
|
|
|
|
template <typename CharT, typename Traits, typename Block, typename Allocator>
|
|
std::basic_ostream<CharT, Traits>&
|
|
<a href="#op-out">operator<<</a>(std::basic_ostream<CharT, Traits>& os, const dynamic_bitset<Block, Allocator>& b);
|
|
|
|
template <typename CharT, typename Traits, typename Block, typename Allocator>
|
|
std::basic_istream<CharT, Traits>&
|
|
<a href="#op-in">operator>></a>(std::basic_istream<CharT, Traits>& is, dynamic_bitset<Block, Allocator>& b);
|
|
|
|
} // namespace boost
|
|
</pre>
|
|
|
|
<h3><a name="definitions">Definitions</a></h3>
|
|
<p>
|
|
Each bit represents either the Boolean value true or false (1 or 0).
|
|
To <i>set</i> a bit is to assign it 1. To <i>clear</i> or <i>reset</i>
|
|
a bit is to assign it 0. To <i>flip</i> a bit is to change the value
|
|
to 1 if it was 0 and to 0 if it was 1. Each bit has a non-negative
|
|
<i>position</i>. A bitset <tt>x</tt> contains <tt>x.size()</tt> bits,
|
|
with each bit assigned a unique position in the range
|
|
<tt>[0,x.size())</tt>. The bit at position 0 is called the <i>least
|
|
significant bit</i> and the bit at position <tt>size() - 1</tt> is the
|
|
<i>most significant bit</i>. When converting an instance of
|
|
<tt>dynamic_bitset</tt> to or from an unsigned long <tt>n</tt>, the bit at
|
|
position <tt>i</tt> of the bitset has the same value as <tt>(n >> i)
|
|
& 1</tt>.
|
|
</p>
|
|
|
|
<h3><a name="examples">Examples</a></h3>
|
|
|
|
<p>An example of setting and reading some bits. Note that
|
|
<tt>operator[]</tt> goes from the least-significant bit at <tt>0</tt>
|
|
to the most significant bit at <tt>size()-1</tt>. The
|
|
<tt>operator<<</tt> for <tt>dynamic_bitset</tt> prints the bitset from
|
|
most-significant to least-significant, since that is the format most
|
|
people are use to reading.</p>
|
|
<blockquote>
|
|
<pre>
|
|
#include <iostream>
|
|
#include <boost/dynamic_bitset.hpp>
|
|
int main(int, char*[]) {
|
|
boost::dynamic_bitset<> x(5); // all 0's by default
|
|
x[0] = 1;
|
|
x[1] = 1;
|
|
x[4] = 1;
|
|
for (boost::dynamic_bitset<>::size_type i = 0; i < x.size(); ++i)
|
|
std::cout << x[i];
|
|
std::cout << "\n";
|
|
std::cout << x << "\n";
|
|
return EXIT_SUCCESS;
|
|
}
|
|
</pre>
|
|
</blockquote>
|
|
<p>The output is</p>
|
|
<blockquote>
|
|
<pre>
|
|
11001
|
|
10011
|
|
</pre>
|
|
</blockquote>
|
|
|
|
<p>
|
|
An example of creating some bitsets from integers (unsigned longs).
|
|
|
|
<blockquote>
|
|
<pre>
|
|
#include <iostream>
|
|
#include <boost/dynamic_bitset.hpp>
|
|
int main(int, char*[])
|
|
{
|
|
const boost::dynamic_bitset<> b0(2, 0ul);
|
|
std::cout << "bits(0) = " << b0 << std::endl;
|
|
|
|
const boost::dynamic_bitset<> b1(2, 1ul);
|
|
std::cout << "bits(1) = " << b1 << std::endl;
|
|
|
|
const boost::dynamic_bitset<> b2(2, 2ul);
|
|
std::cout << "bits(2) = " << b2 << std::endl;
|
|
|
|
const boost::dynamic_bitset<> b3(2, 3ul);
|
|
std::cout << "bits(3) = " << b3 << std::endl;
|
|
|
|
return EXIT_SUCCESS;
|
|
}
|
|
</pre>
|
|
</blockquote>
|
|
<p>The output is</p>
|
|
<blockquote>
|
|
<pre>
|
|
bits(0) = 00
|
|
bits(1) = 01
|
|
bits(2) = 10
|
|
bits(3) = 11
|
|
</pre>
|
|
</blockquote>
|
|
|
|
<p>
|
|
An example of performing some bitwise operations.
|
|
</p>
|
|
|
|
<blockquote>
|
|
<pre>
|
|
#include <iostream>
|
|
#include <boost/dynamic_bitset.hpp>
|
|
int main(int, char*[]) {
|
|
const boost::dynamic_bitset<> mask(12, 2730ul);
|
|
std::cout << "mask = " << mask << std::endl;
|
|
|
|
boost::dynamic_bitset<> x(12);
|
|
|
|
std::cout << "Enter a 12-bit bitset in binary: " << std::flush;
|
|
if (std::cin >> x) {
|
|
std::cout << "input number: " << x << std::endl;
|
|
std::cout << "As unsigned long: " << x.to_ulong() << std::endl;
|
|
std::cout << "And with mask: " << (x & mask) << std::endl;
|
|
std::cout << "Or with mask: " << (x | mask) << std::endl;
|
|
std::cout << "Shifted left: " << (x << 1) << std::endl;
|
|
std::cout << "Shifted right: " << (x >> 1) << std::endl;
|
|
}
|
|
return EXIT_SUCCESS;
|
|
}
|
|
</pre>
|
|
</blockquote>
|
|
<p>The output is</p>
|
|
<blockquote>
|
|
<pre>
|
|
mask = 101010101010
|
|
Enter a 12-bit bitset in binary: 100110101101
|
|
input number = 100110101101
|
|
As unsigned long: 2477
|
|
And with mask: 100010101000
|
|
Or with mask: 101110101111
|
|
Shifted left: 001101011010
|
|
Shifted right: 010011010110
|
|
</pre>
|
|
</blockquote>
|
|
|
|
|
|
<h3><a name="rationale">Rationale</a></h3>
|
|
|
|
The <tt>dynamic_bitset</tt> does not provide iterators (and therefore is
|
|
not a <a href="http://www.sgi.com/tech/stl/Container.html">
|
|
Container</a>) for the following reasons:
|
|
<ol>
|
|
<li><tt>std::bitset</tt> does not have iterators, and
|
|
<tt>dynamic_bitset</tt> is meant to be a run-time sized version of
|
|
<tt>std::bitset</tt>.</il>
|
|
|
|
<li>The <tt>dynamic_bitset</tt> is not
|
|
designed to be a <a
|
|
href="http://www.sgi.com/tech/stl/Container.html">
|
|
Container</a>.</li>
|
|
|
|
<li>A container with a proxy <tt>reference</tt> type can not
|
|
fulfill the container requirements as specified in the C++
|
|
standard (unless one resorts to strange iterator
|
|
semantics). <tt>std::vector<bool></tt> has a proxy
|
|
<tt>reference</tt> type and does not fulfill the container
|
|
requirements and as a result has caused many problems. One common
|
|
problem is when people try to use iterators from
|
|
<tt>std::vector<bool></tt> with a Standard algorithm such as
|
|
<tt>std::search</tt>. The <tt>std::search</tt> requirements say
|
|
that the iterator must be a <a
|
|
href="http://www.sgi.com/tech/stl/ForwardIterator.html"> Forward
|
|
Iterator</a>, but the <tt>std::vector<bool>::iterator</tt>
|
|
does not meet this requirement because of the proxy reference.
|
|
Depending on the implementation, they may or not be a compile
|
|
error or even a run-time error due to this misuse. For further
|
|
discussion of the problem see <i>Effective STL</i> by Scott
|
|
Meyers). So <tt>dynamic_bitset</tt> tries to avoid these problems by
|
|
not pretending to be a container.</li>
|
|
</ol>
|
|
|
|
<p>
|
|
Some people prefer the name "toggle" to
|
|
"flip". The name "flip" was chosen because that
|
|
is the name used in <A
|
|
href="http://www.sgi.com/tech/stl/bitset.html"><tt>std::bitset</tt></a>.
|
|
In fact, most of the function names for <tt>dynamic_bitset</tt> were chosen for
|
|
this reason.</p>
|
|
|
|
<p>
|
|
<tt>dynamic_bitset</tt> does not throw exceptions when a precondition
|
|
is violated (as is done in <tt>std::bitset</tt>). Instead
|
|
<tt>assert</tt> is used. See the guidelines for <a
|
|
href="../../more/error_handling.html">Error and
|
|
Exception Handling</a> for the explanation.
|
|
</p>
|
|
|
|
|
|
<h3><a name="header-files">Header Files</a></h3>
|
|
|
|
<p>The class <tt>dynamic_bitset</tt> is defined in the header <A
|
|
href="../../boost/dynamic_bitset.hpp">
|
|
boost/dynamic_bitset.hpp</A>. Also, there is a forward declaration for
|
|
<tt>dynamic_bitset</tt> in the header <A
|
|
href="../../boost/dynamic_bitset_fwd.hpp">
|
|
boost/dynamic_bitset_fwd.hpp</A>.</p>
|
|
|
|
|
|
<h3><a name="template-parameters">Template parameters</a></h3>
|
|
<Table border>
|
|
<TR>
|
|
<TH>
|
|
Parameter
|
|
</TH>
|
|
<TH>
|
|
Description
|
|
</TH>
|
|
<TH>
|
|
Default
|
|
</TH>
|
|
</TR>
|
|
<TR>
|
|
<TD VAlign=top>
|
|
<tt>Block</tt>
|
|
</TD>
|
|
<TD VAlign=top>
|
|
The integer type in which the bits are stored.
|
|
</TD>
|
|
<TD VAlign=top>
|
|
<tt>unsigned long</tt>
|
|
</TD>
|
|
</tr>
|
|
<tr>
|
|
<td VAlign=top>
|
|
<tt>Allocator</tt>
|
|
</td>
|
|
<td VAlign=top>
|
|
The allocator type used for all internal memory management.
|
|
</td>
|
|
<td VAlign=top>
|
|
<tt>std::allocator<Block></tt>
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<h3><a name="concepts-modeled">Concepts Modeled</a></h3>
|
|
|
|
<A href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</A>,
|
|
<A href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</A>,
|
|
<A href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</A>,
|
|
<a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThan Comparable</a>.
|
|
|
|
<h3><a name="type-requirements">Type requirements</a></h3>
|
|
<tt>Block</tt> is an unsigned integer type. <tt>Allocator</tt> satisfies
|
|
the Standard requirements for an Allocator.
|
|
|
|
<h3><a name="public-base-classes">Public base classes</a></h3>
|
|
None.
|
|
|
|
<h3><a name="member-typedefs">Member typedefs</a></h3>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="reference">dynamic_bitset::reference</a>
|
|
</pre>
|
|
<p>A proxy class that acts as a reference to a single bit. It contains
|
|
an assignment operator, a conversion to <tt>bool</tt>, an
|
|
<tt>operator~</tt>, and a member function <tt>flip</tt>. It exists
|
|
only as a helper class for <tt>dynamic_bitset</tt>'s
|
|
<tt>operator[]</tt>. The following table describes the valid
|
|
operations on the <tt>reference</tt> type. Assume that <tt>b</tt> is
|
|
an instance of <tt>dynamic_bitset</tt>, <tt>i, j</tt> are of
|
|
<tt>size_type</tt> and in the range <tt>[0,b.size())</tt>. Also, note
|
|
that when we write <tt>b[i]</tt> we mean an object of type
|
|
<tt>reference</tt> that was initialized from <tt>b[i]</tt>. The
|
|
variable <tt>x</tt> is a <tt>bool</tt>.</p>
|
|
|
|
<table border=1>
|
|
<tr><th>Expression</th><th>Semantics</th></tr>
|
|
<tr><td><tt>x = b[i]</tt></td> <td>Assign the ith bit of <tt>b</tt> to <tt>x</tt>.</td></tr>
|
|
<tr><td><tt>(bool)b[i]</tt></td> <td>Return the ith bit of <tt>b</tt>.</td></tr>
|
|
|
|
<tr><td><tt>b[i] = x</tt></td> <td>Set the ith bit of <tt>b</tt> to the value of <tt>x</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] |= x</tt></td> <td>Or the ith bit of <tt>b</tt> with the value of <tt>x</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] &= x</tt></td> <td>And the ith bit of <tt>b</tt> with the value of <tt>x</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] ^= x</tt></td> <td>Exclusive-Or the ith bit of <tt>b</tt> with the value of <tt>x</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] -= x</tt></td> <td>If <tt>x==true</tt>, clear the ith bit of <tt>b</tt>. Returns <tt>b[i]</tt>.</td></tr>
|
|
|
|
<tr><td><tt>b[i] = b[j]</tt></td> <td>Set the ith bit of <tt>b</tt> to the value of the jth bit of <tt>b</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] |= b[j]</tt></td> <td>Or the ith bit of <tt>b</tt> with the
|
|
jth bit of <tt>b</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] &= b[j]</tt></td> <td>And the ith bit of <tt>b</tt> with the jth bit of <tt>b</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] ^= b[j]</tt></td> <td>Exclusive-Or the ith bit of <tt>b</tt> with the jth bit of <tt>b</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
<tr><td><tt>b[i] -= b[j]</tt></td> <td>If the jth bit of <tt>b</tt> is set, clear the ith bit of <tt>b</tt>. Returns <tt>b[i]</tt>.</td></tr>
|
|
|
|
|
|
<tr><td><tt>x = ~b[i]</tt></td> <td>Assign the opposite of the ith bit of <tt>b</tt> to <tt>x</tt>.</td></tr>
|
|
<tr><td><tt>(bool)~b[i]</tt></td> <td>Return the opposite of the ith bit of <tt>b</tt>.</td></tr>
|
|
<tr><td><tt>b[i].flip()</tt> <td>Flip the ith bit of <tt>b</tt> and return <tt>b[i]</tt>.</td></tr>
|
|
</table>
|
|
|
|
<hr>
|
|
<pre>
|
|
<a name="const_reference">dynamic_bitset::const_reference</a>
|
|
</pre>
|
|
The type <tt>bool</tt>.
|
|
|
|
<hr>
|
|
<pre>
|
|
<a name="size_type">dynamic_bitset::size_type</a>
|
|
</pre>
|
|
The unsigned integer for representing the size of the bit set.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="block_type">dynamic_bitset::block_type</a>
|
|
</pre>
|
|
The same type as the <tt>Block</tt> template parameter.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="bits_per_block">dynamic_bitset::bits_per_block</a>
|
|
</pre>
|
|
The number of bits in a <tt>Block</tt>.
|
|
|
|
<hr>
|
|
|
|
<h3><a name="constructors">Constructors</a></h3>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="cons1">dynamic_bitset</a>(const Allocator& alloc = Allocator())
|
|
</pre>
|
|
|
|
<b>Effects:</b> Constructs a bitset of size zero.
|
|
A copy of the <tt>alloc</tt> object will be used in subsequent
|
|
bitset operations such as <tt>resize</tt> to allocate memory.<br>
|
|
|
|
<b>Postconditions:</b> <tt>this->size() == 0</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
(Required by <a href="http://www.sgi.com/tech/stl/Defaultconstructible.html">
|
|
Default Constructible</a>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="cons2">dynamic_bitset</a>(size_type num_bits,
|
|
unsigned long value = 0,
|
|
const Allocator& alloc = Allocator())
|
|
</pre>
|
|
|
|
<b>Effects:</b> Constructs a bitset from an integer. The first
|
|
<tt>M</tt> bits are initialized to the corresponding bits in
|
|
<tt>val</tt> and all other bits, if any, to zero (where
|
|
<tt>M = min(num_bits, sizeof(unsigned long) * CHAR_BIT)</tt>). A copy
|
|
of the <tt>alloc</tt> object will be used in subsequent bitset
|
|
operations such as <tt>resize</tt> to allocate memory.<br>
|
|
|
|
<b>Postconditions:</b>
|
|
<ul>
|
|
<li><tt>this->size() == num_bits</tt></li>
|
|
<li> For all <tt>i</tt> in the range <tt>[0,M)</tt>, <tt>(*this)[i] == (value >> i) & 1</tt>.</li>
|
|
<li> For all <tt>i</tt> in the range <tt>[M+1,num_bits)</tt>,
|
|
<tt>(*this)[i] == false</tt>.</li>
|
|
</ul>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
<a name="cons5">dynamic_bitset</a>(const dynamic_bitset& x)
|
|
</pre>
|
|
|
|
<b>Effects:</b> Constructs a bitset that is a copy of the bitset
|
|
<tt>x</tt>. The allocator for this bitset is a copy of the
|
|
allocator in <tt>x</tt>. <br>
|
|
|
|
<b>Postconditions:</b> For all <tt>i</tt> in the range
|
|
<tt>[0,x.size())</tt>, <tt>(*this)[i] == x[i]</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
(Required by <A href="http://www.sgi.com/tech/stl/Assignable.html">
|
|
Assignable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
template <typename BlockInputIterator>
|
|
explicit
|
|
<a name="cons4">dynamic_bitset</a>(BlockInputIterator first, BlockInputIterator last,
|
|
const Allocator& alloc = Allocator());
|
|
</pre>
|
|
|
|
<b>Effects:</b> Constructs a bitset based on a range of blocks.
|
|
Let <tt>*first</tt> be block number 0, <tt>*++first</tt> block number
|
|
1, etc. Block number <tt>b</tt> is used to initialize the bits of the
|
|
dynamic_bitset in the position range <tt>[b*bits_per_block, (b+1)*bits_per_block)</tt>. For
|
|
each block number <tt>b</tt> with value <tt>bval</tt>, the bit
|
|
<tt>(bval >> i) & 1</tt> corresponds to the bit at position <tt>(b *
|
|
bits_per_block + i)</tt> in the bitset (where <tt>i</tt> goes through the
|
|
range <tt>[0, bits_per_block)</tt>).<br>
|
|
|
|
<b>Requires:</b> The type <tt>BlockInputIterator</tt> must be a model
|
|
of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input
|
|
Iterator</a> and its <tt>value_type</tt> must be the same type as
|
|
<tt>Block</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
template<typename Char, typename Traits, typename Alloc>
|
|
explicit
|
|
<a name="cons3">dynamic_bitset</a>(const <A href="http://www.sgi.com/tech/stl/basic_string.html">std::basic_string</A><Char,Traits,Alloc>& s,
|
|
typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0,
|
|
typename std::basic_string<CharT, Traits, Alloc>::size_type n = <A href="http://www.sgi.com/tech/stl/basic_string.html">std::basic_string</A><Char,Traits,Alloc>::npos,
|
|
const Allocator& alloc = Allocator())
|
|
</pre>
|
|
|
|
<b>Precondition:</b> <tt>pos <= s.size()</tt>
|
|
and the characters used to
|
|
initialize the bits must be <tt>0</tt> or <tt>1</tt>.<br>
|
|
|
|
<b>Effects:</b> Constructs a bitset from a string of 0's and 1's. The
|
|
first <tt>M</tt> bits are initialized to the corresponding characters
|
|
in <tt>s</tt>, where <tt>M = min(s.size() - pos, n)</tt>. Note that
|
|
the <i>highest</i> character position in <tt>s</tt>, not the lowest,
|
|
corresponds to the least significant bit. That is, character position
|
|
<tt>pos + M - 1 - i</tt> corresponds to bit <tt>i</tt>. So, for
|
|
example, <tt>dynamic_bitset(string("1101"))</tt> is the same as
|
|
<tt>dynamic_bitset(13ul)</tt>.<br>
|
|
|
|
<b>Throws:</b> an allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<h3><a name="destructor">Destructor</a></h3>
|
|
|
|
<hr>
|
|
<pre>
|
|
~dynamic_bitset()
|
|
</pre>
|
|
<b>Effects:</b> Releases the memory associated with this bitset
|
|
and destroys the bitset object itself.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
|
|
<hr>
|
|
|
|
<h3><a name="member-functions">Member Functions</a></h3>
|
|
|
|
<hr>
|
|
<pre>
|
|
void <a name="swap">swap</a>(dynamic_bitset& b);
|
|
</pre>
|
|
<b>Effects:</b> The contents of this bitset and bitset <tt>b</tt>
|
|
are exchanged.<br>
|
|
<b>Postconditions:</b> This bitset is equal to the original <tt>b</tt>,
|
|
and <tt>b</tt> is equal to the previous version of this bitset.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="assign">operator=</a>(const dynamic_bitset& x)
|
|
</pre>
|
|
|
|
<b>Effects:</b> This bitset becomes a copy of the bitset <tt>x</tt>.<br>
|
|
|
|
<b>Postconditions:</b> For all <tt>i</tt> in the range
|
|
<tt>[0,x.size())</tt>, <tt>(*this)[i] == x[i]</tt>.<br>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<br>
|
|
(Required by
|
|
<A href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</A>.)
|
|
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
void <a name="resize">resize</a>(size_type num_bits, bool value = false);
|
|
</pre>
|
|
|
|
<b>Effects:</b> Changes the number of bits of the bitset to
|
|
<tt>num_bits</tt>. If <tt>num_bits > size()</tt> then the bits in the
|
|
range <tt>[0,size())</tt> remain the same, and the bits in
|
|
<tt>[size(),num_bits)</tt> are all set to <tt>value</tt>. If
|
|
<tt>num_bits < size()</tt> then the bits in the range
|
|
<tt>[0,num_bits)</tt> stay the same (and the remaining bits are
|
|
discarded).<br>
|
|
|
|
<b>Postconditions:</b> <tt>this->size() == num_bits</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
void <a name="clear">clear</a>()
|
|
</pre>
|
|
<b>Effects:</b> The size of the bitset becomes zero.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
void <a name="push_back">push_back</a>(bool value);
|
|
</pre>
|
|
<b>Effects:</b> Increases the size of the bitset by one, and sets the value of
|
|
the new most-significant bit to <tt>value</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
void <a name="append1">append</a>(Block value);
|
|
</pre>
|
|
<b>Effects:</b> Appends the bits in <tt>value</tt> to the bitset
|
|
(appends to the most-significant end). This increases the size of the
|
|
bitset by <tt>bits_per_block</tt>. Let <tt>s</tt> be the old size of the
|
|
bitset, then for <tt>i</tt> in the range <tt>[0,bits_per_block)</tt>, the
|
|
bit at position <tt>(s + i)</tt> is set to <tt>((value >> i) &
|
|
1)</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
template <typename BlockInputIterator>
|
|
void <a name="append2">append</a>(BlockInputIterator first, BlockInputIterator last);
|
|
</pre>
|
|
<b>Effects:</b> This function provides the same end result as the following
|
|
code, but is typically more efficient.
|
|
<pre>
|
|
for (; first != last; ++first)
|
|
append(*first);
|
|
</pre>
|
|
|
|
<b>Requires:</b> The <tt>BlockInputIterator</tt> type must be a model
|
|
of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input
|
|
Iterator</a> and the <tt>value_type</tt> must be the same type as
|
|
<tt>Block</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).<br>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="op-and-assign">operator&=</a>(const dynamic_bitset& rhs)
|
|
</pre>
|
|
|
|
<b>Requires:</b> <tt>this->size() == rhs.size()</tt>.<br>
|
|
|
|
<b>Effects:</b> Bitwise-AND all the bits in <tt>rhs</tt> with the
|
|
bits in this bitset. This is equivalent to:
|
|
<pre>
|
|
for (size_type i = 0; i != this->size(); ++i)
|
|
(*this)[i] = (*this)[i] & rhs[i];
|
|
</pre>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>dynamic_bitset& <a name="op-or-assign">operator|=</a>(const dynamic_bitset& rhs)
|
|
</pre>
|
|
<b>Requires:</b> <tt>this->size() == rhs.size()</tt>.<br>
|
|
|
|
<b>Effects:</b> Bitwise-OR's all the bits in <tt>rhs</tt>
|
|
with the bits in this bitset. This is equivalent to:
|
|
<pre>
|
|
for (size_type i = 0; i != this->size(); ++i)
|
|
(*this)[i] = (*this)[i] | rhs[i];
|
|
</pre>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="op-xor-assign">operator^=</a>(const dynamic_bitset& rhs)
|
|
</pre>
|
|
<b>Requires:</b> <tt>this->size() == rhs.size()</tt>.<br>
|
|
|
|
<b>Effects:</b> Bitwise-XOR's all the bits in <tt>rhs</tt>
|
|
with the bits in this bitset. This is equivalent to:
|
|
<pre>
|
|
for (size_type i = 0; i != this->size(); ++i)
|
|
(*this)[i] = (*this)[i] ^ rhs[i];
|
|
</pre>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="op-sub-assign">operator-=</a>(const dynamic_bitset& rhs)
|
|
</pre>
|
|
<b>Requires:</b> <tt>this->size() == rhs.size()</tt>.<br>
|
|
|
|
<b>Effects:</b> Computes the set difference of
|
|
this bitset and the <tt>rhs</tt> bitset. This is equivalent to:
|
|
<pre>
|
|
for (size_type i = 0; i != this->size(); ++i)
|
|
(*this)[i] = (*this)[i] && !rhs[i];
|
|
</pre>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="op-sl-assign">operator<<=</a>(size_type n)
|
|
</pre>
|
|
<b>Effects:</b> Shifts the bits in this bitset to the left by
|
|
<tt>n</tt> bits. For each bit in the bitset, the bit at position pos
|
|
takes on the previous value of the bit at position <tt>pos - n</tt>,
|
|
or zero if no such bit exists.<br>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="op-sr-assign">operator>>=</a>(size_type n)
|
|
</pre>
|
|
<b>Effects:</b> Shifts the bits in this bitset to the right by
|
|
<tt>n</tt> bits. For each bit in the bitset, the bit at position
|
|
<tt>pos</tt> takes on the previous value of bit <tt>pos + n</tt>, or
|
|
zero if no such bit exists.<br>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-sl">operator<<</a>(size_type n) const
|
|
</pre>
|
|
<b>Returns:</b> a copy of <tt>*this</tt> shifted to the left by <tt>n</tt>
|
|
bits. For each bit in the returned bitset, the bit at position pos
|
|
takes on the value of the bit at position <tt>pos - n</tt> of this
|
|
bitset, or zero if no such bit exists.
|
|
Note that the expression <tt>b << n</tt> is equivalent to
|
|
constructing a temporary copy of <tt>b</tt> and then using
|
|
<tt>operator<<=</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-sr">operator>></a>(size_type n) const
|
|
</pre>
|
|
|
|
<b>Returns:</b> a copy of <tt>*this</tt> shifted to the right by
|
|
<tt>n</tt> bits. For each bit in the returned bitset, the bit at
|
|
position pos takes on the value of the bit at position <tt>pos +
|
|
n</tt> of this bitset, or zero if no such bit exists. Note that the
|
|
expression <tt>b >> n</tt> is equivalent to constructing a
|
|
temporary copy of <tt>b</tt> and then using
|
|
<tt>operator>>=</tt>.<br>
|
|
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="set1">set</a>()
|
|
</pre>
|
|
<b>Effects:</b> Sets every bit in this bitset to 1.<br>
|
|
<b>Returns:</b> <tt>*this</tt><br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="flip1">flip</a>()
|
|
</pre>
|
|
<b>Effects:</b> Flips the value of every bit in this bitset.<br>
|
|
<b>Returns:</b> <tt>*this</tt><br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-not">operator~</a>() const
|
|
</pre>
|
|
<b>Returns:</b> a copy of <tt>*this</tt> with all of its bits flipped.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="reset1">reset</a>()
|
|
</pre>
|
|
<b>Effects:</b> Clears every bit in this bitset.<br>
|
|
<b>Returns:</b> <tt>*this</tt><br>
|
|
<b>Throws:</b> nothing.
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="set2">set</a>(size_type n, bool val = true)
|
|
</pre>
|
|
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
|
|
<b>Effects:</b> Sets bit <tt>n</tt> if <tt>val</tt> is <tt>true</tt>,
|
|
and clears bit <tt>n</tt> if <tt>val</tt> is <tt>false</tt>. <br>
|
|
|
|
<b>Returns:</b> <tt>*this</tt>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="reset2">reset</a>(size_type n)
|
|
</pre>
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
<b>Effects:</b> Clears bit <tt>n</tt>.<br>
|
|
<b>Returns:</b> <tt>*this</tt>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset& <a name="flip2">flip</a>(size_type n)
|
|
</pre>
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
<b>Effects:</b> Flips bit <tt>n</tt>.<br>
|
|
<b>Returns:</b> <tt>*this</tt>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
size_type <a name="size">size</a>() const
|
|
</pre>
|
|
<b>Returns:</b> the number of bits in this bitset.<br>
|
|
<b>Throws:</b> nothing.
|
|
<hr>
|
|
|
|
<pre>
|
|
size_type <a name="num_blocks">num_blocks</a>() const
|
|
</pre>
|
|
<b>Returns:</b> the number of blocks in this bitset.<br>
|
|
<b>Throws:</b> nothing.
|
|
<hr>
|
|
|
|
<pre>
|
|
size_type <a name="count">count</a>() const
|
|
</pre>
|
|
<b>Returns:</b> the number of bits in this bitset that are set.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="any">any</a>() const
|
|
</pre>
|
|
<b>Returns:</b> <tt>true</tt> if any bits in this bitset are set,
|
|
and otherwise returns <tt>false</tt>.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="none">none</a>() const
|
|
</pre>
|
|
<b>Returns:</b> <tt>true</tt> if no bits are set, and otherwise
|
|
returns <tt>false</tt>.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="test">test</a>(size_type n) const
|
|
</pre>
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
|
|
<b>Returns:</b> <tt>true</tt> if bit <tt>n</tt> is set and
|
|
<tt>false</tt> is bit <tt>n</tt> is 0.
|
|
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
reference <a name="bracket">operator[]</a>(size_type n)
|
|
</pre>
|
|
</TD>
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
|
|
<b>Returns:</b> a <tt>reference</tt> to bit <tt>n</tt>. Note that
|
|
<tt>reference</tt> is a proxy class with an assignment operator and a
|
|
conversion to <tt>bool</tt>, which allows you to use
|
|
<tt>operator[]</tt> for assignment. That is, you can write both <tt>x
|
|
= b[n]</tt> and <tt>b[n] = x</tt>. However, in many other respects the
|
|
proxy is not the same as the true reference type <tt>bool&</tt>.
|
|
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="const-bracket">operator[]</a>(size_type n) const
|
|
</pre>
|
|
<b>Precondition:</b> <tt>n < this->size()</tt>.<br>
|
|
<b>Returns:</b> <tt>true</tt> if bit <tt>n</tt> is set.
|
|
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
unsigned long <a name="to_ulong">to_ulong</a>() const
|
|
</pre>
|
|
<b>Returns:</b> An <tt>unsigned long</tt> integer whose bits
|
|
corresponds to the bits in this bitset, as long as there are no bits
|
|
in the bitset that are set to 1 at a position greater than
|
|
<tt>sizeof(unsigned long) * CHAR_BIT</tt>.
|
|
|
|
<b>Throws:</b> <tt>std::overflow_error</tt> if the value of the bitset
|
|
can not be represented in an <tt>unsigned long</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="is_subset_of">is_subset_of</a>(const dynamic_bitset& a) const
|
|
</pre>
|
|
<b>Requires:</b> <tt>this->size() == a.size()</tt><br>
|
|
<b>Returns:</b> true if this bitset is a subset of bitset <tt>a</tt>.
|
|
That is, it returns true if, for every bit that is set in this bitset, the
|
|
corresponding bit in bitset <tt>a</tt> is also set. Otherwise this
|
|
function returns false.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="is_proper_subset_of">is_proper_subset_of</a>(const dynamic_bitset& a) const
|
|
</pre>
|
|
<b>Requires:</b> <tt>this->size() == a.size()</tt><br>
|
|
<b>Returns:</b> true if this bitset is a proper subset of bitset <tt>a</tt>.
|
|
That is, it returns true if, for every bit that is set in this bitset, the
|
|
corresponding bit in bitset <tt>a</tt> is also set and if
|
|
<tt>this->count() < a.count()</tt>. Otherwise this
|
|
function returns false.<br>
|
|
<b>Throws:</b> nothing.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-equal">operator==</a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>true</tt> if <tt>this->size() ==
|
|
rhs.size()</tt> and if for all <tt>i</tt> in the range
|
|
<tt>[0,rhs.size())</tt>, <tt>(*this)[i] == rhs[i]</tt>. Otherwise
|
|
returns <tt>false</tt>.<br>
|
|
|
|
<b>Throws:</b> nothing.<br>
|
|
|
|
(Required by <A
|
|
href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality
|
|
Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-not-equal">operator!=</a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>!((*this) == rhs)</tt><br>
|
|
<b>Throws:</b> nothing.<br>
|
|
(Required by <A
|
|
href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality
|
|
Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-less">operator<</a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>true</tt> if this bitset is lexicographically less
|
|
than <tt>rhs</tt>, and returns <tt>false</tt> otherwise. (See the
|
|
description of <a
|
|
href="http://www.sgi.com/tech/stl/lexicographical_compare.html">
|
|
lexicographical_compare</a> for a definition of lexicographic
|
|
ordering). <br>
|
|
<b>Throws:</b> nothing.<br>
|
|
(Required by
|
|
<A href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-greater">operator></a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>!((*this) < rhs || (*this) == rhs)</tt><br>
|
|
<b>Throws:</b> nothing.<br>
|
|
(Required by <A
|
|
href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
|
|
Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-less-equal">operator<=</a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>(*this) < rhs || (*this) == rhs</tt><br>
|
|
<b>Throws:</b> nothing.<br>
|
|
(Required by
|
|
<A href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
bool <a name="op-greater-equal">operator>=</a>(const dynamic_bitset& rhs) const
|
|
</pre>
|
|
<b>Returns:</b> <tt>(*this) > rhs || (*this) == rhs</tt><br>
|
|
<b>Throws:</b> nothing.<br>
|
|
(Required by
|
|
<A href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than Comparable</A>.)
|
|
|
|
<hr>
|
|
|
|
<h3><a name="non-member-functions">Non-Member Functions</a></h3>
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-and">operator&</a>(const dynamic_bitset& a, const dynamic_bitset& b)
|
|
</pre>
|
|
<b>Requires:</b> <tt>a.size() == b.size()</tt><br>
|
|
<b>Returns:</b> A new bitset that is the bitwise-AND of the bitsets
|
|
<tt>a</tt> and <tt>b</tt>. Note that the expression <tt>b1 &
|
|
b2</tt> is equivalent to creating a temporary copy of <tt>b1</tt>,
|
|
using <tt>operator&=</tt>, and returning the temporary copy.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-or">operator|</a>(const dynamic_bitset& a, const dynamic_bitset& b)
|
|
</pre>
|
|
<b>Requires:</b> <tt>a.size() == b.size()</tt><br>
|
|
<b>Returns:</b> A new bitset that is the bitwise-OR of the bitsets
|
|
<tt>a</tt> and <tt>b</tt>. Note that the expression <tt>b1 &
|
|
b2</tt> is equivalent to creating a temporary copy of <tt>b1</tt>,
|
|
using <tt>operator&=</tt>, and returning the temporary copy.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-xor">operator^</a>(const dynamic_bitset& a, const dynamic_bitset& b)
|
|
</pre>
|
|
<b>Requires:</b> <tt>a.size() == b.size()</tt><br>
|
|
<b>Returns:</b> A new bitset that is the bitwise-XOR of the bitsets
|
|
<tt>a</tt> and <tt>b</tt>. Note that the expression <tt>b1 &
|
|
b2</tt> is equivalent to creating a temporary copy of <tt>b1</tt>,
|
|
using <tt>operator&=</tt>, and returning the temporary copy.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
dynamic_bitset <a name="op-sub">operator-</a>(const dynamic_bitset& a, const dynamic_bitset& b)
|
|
</pre>
|
|
<b>Requires:</b> <tt>a.size() == b.size()</tt><br>
|
|
<b>Returns:</b> A new bitset that is the set difference of the bitsets
|
|
<tt>a</tt> and <tt>b</tt>. Note that the expression <tt>b1 - b2</tt>
|
|
is equivalent to creating a temporary copy of <tt>b1</tt>,
|
|
using <tt>operator-=</tt>, and returning the temporary copy.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
template <typename CharT, typename Alloc>
|
|
void <a name="to_string">to_string</a>(const dynamic_bitset<Block, Allocator>& b,
|
|
<A href="http://www.sgi.com/tech/stl/basic_string.html">std::basic_string</A><Char,Traits,Alloc>& s)
|
|
</pre>
|
|
|
|
<b>Effects:</b> Copies a representation of <tt>b</tt> into the string
|
|
<tt>s</tt>. A character in the string is <tt>'1'</tt> if the
|
|
corresponding bit is set, and <tt>'0'</tt> if it is not. Character
|
|
position <tt>i</tt> in the string corresponds to bit position
|
|
<tt>b.size() - 1 - i</tt>. <br>
|
|
|
|
<b>Throws:</b> If memory is exhausted, the string will throw an
|
|
allocation error.<br>
|
|
|
|
<b>Rationale:</b> This function is not a member function taking zero
|
|
arguments and returning a string for a couple reasons. First, this
|
|
version can be slighly more efficient because the string is not
|
|
copied (due to being passed by value). Second, as a member function,
|
|
to allow for flexibility with regards to the template parameters of
|
|
<tt>basic_string</tt>, the member function would require explicit
|
|
template parameters. Few C++ programmers are familiar with explicit
|
|
template parameters, and some C++ compilers do not handle them
|
|
properly.
|
|
|
|
|
|
<hr>
|
|
<pre>
|
|
template <typename Block, typename Alloc, typename BlockOutputIterator>
|
|
void <a name="to_block_range">to_block_range</a>(const dynamic_bitset<Block, Alloc>& b, BlockOutputIterator result)
|
|
</pre>
|
|
<b>Effects:</b> Writes the bits of the bitset into the iterator
|
|
<tt>result</tt> a block at a time. The first block written represents
|
|
the bits in the position range <tt>[0,bits_per_block)</tt> in the
|
|
bitset, the second block written the bits in the range
|
|
<tt>[bits_pre_block,2*bits_per_block)</tt>, and so on. For each block
|
|
<tt>bval</tt> written, the bit <tt>(bval >> i) & 1</tt>
|
|
corresponds to the bit at position <tt>(b * bits_per_block + i)</tt>
|
|
in the bitset.<br>
|
|
|
|
<b>Requires:</b> The type <tt>BlockOutputIterator</tt> must be a model
|
|
of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output
|
|
Iterator</a> and its <tt>value_type</tt> must be the same type as
|
|
<tt>Block</tt>. Further, the size of the output range must be greater
|
|
or equal <tt>b.num_blocks()</tt>.
|
|
|
|
|
|
<hr>
|
|
<pre>
|
|
template <typename BlockIterator, typename Block, typename Alloc>
|
|
void <a name="from_block_range">from_block_range</a>(BlockIterator first,
|
|
BlockIterator last, const dynamic_bitset<Block, Alloc>& b)
|
|
</pre>
|
|
<b>Effects:</b> Reads blocks from the iterator range into the
|
|
bitset. <br>
|
|
|
|
<b>Requires:</b> The type <tt>BlockIterator</tt> must be a model of <a
|
|
href="http://www.sgi.com/tech/stl/InputIterator.html">Input
|
|
Iterator</a> and its <tt>value_type</tt> must be the same type as
|
|
<tt>Block</tt>. The size of the iterator range must be less or equal
|
|
to <tt>b.num_blocks()</tt>.
|
|
|
|
|
|
<hr>
|
|
<pre>
|
|
template <typename Char, typename Traits, typename Block, typename Alloc>
|
|
basic_ostream<Char, Traits>&
|
|
<a name="op-out">operator<<</a>(basic_ostream<Char, Traits>& os, const dynamic_bitset<Block, Alloc>& x)
|
|
</pre>
|
|
Output a <tt>dynamic_bitset</tt> to an output stream. This function
|
|
behaves as if it converts the <tt>dynamic_bitset</tt> to a string and then
|
|
writes that string to the output stream. That is, it is equivalent to
|
|
<pre>
|
|
std::basic_string<Char, Traits> s;
|
|
to_string(x, s):
|
|
os << s;
|
|
</pre>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
Also will throw <tt>std::ios_base::failure</tt> if there is a problem
|
|
writing to the stream.
|
|
|
|
|
|
|
|
<hr>
|
|
<pre>
|
|
template <typename Char, typename Traits, typename Block, typename Alloc>
|
|
basic_istream<Char,Traits>&
|
|
<a name="op-in">operator>></a>(basic_istream<Char,Traits>& is, dynamic_bitset<Block, Alloc>& x)
|
|
</pre>
|
|
<b>Effects:</b> Extracts a <tt>dynamic_bitset</tt> from an input
|
|
stream. This function first skips whitespace, then extracts up to
|
|
<tt>x.size()</tt> characters from the input stream. It stops either
|
|
when it has successfully extracted <tt>x.size()</tt> characters, or
|
|
when extraction fails, or when it sees a character that is something
|
|
other than <tt>1</tt> (in which case it does not extract that
|
|
character). If extraction is successful, the function then assigns a
|
|
value to the bitset in the same way as if it were initializing the
|
|
bitset from a string. So, for example, if the input stream contains
|
|
the characters <tt>"1100abc"</tt>, it will assign the value
|
|
<tt>12ul</tt> to the bitset, and the next character read from the
|
|
input stream will be <tt>a</tt>.<br>
|
|
<b>Throws:</b> An allocation error if memory is exhausted
|
|
(<tt>std::bad_alloc</tt> if <tt>Allocator=std::allocator</tt>).
|
|
Also will throw <tt>std::ios_base::failure</tt> if there is a problem
|
|
reading from the stream.
|
|
|
|
<hr>
|
|
|
|
<h3><a name="see-also">See also</a></h3>
|
|
<tt><A href="http://www.sgi.com/tech/stl/bitset.html">std::bitset</A></tt>,
|
|
<tt><A href="http://www.sgi.com/tech/stl/Vector.html">std::vector</A></tt>,
|
|
|
|
<h3><a name="acknowledgements">Acknowledgements</a></h3>
|
|
|
|
<p>
|
|
We would like to thank the Boost community for putting in the time to
|
|
review and accept this library. This library is much better than it
|
|
ever would have been due to all the suggestions from Boost members. We
|
|
especially thank Matt Marcus for taking on the task of review
|
|
manager. Also, a special thanks goes to Gennaro Prota for work on
|
|
increasing efficiency for many of <tt>dynamic_bitset</tt>'s functions.
|
|
</p>
|
|
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2001</TD><TD>
|
|
<A HREF="../../people/jeremy_siek.htm">Jeremy Siek</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
|
|
<A HREF="http://freshsources.com">Chuck Allison</A>, Senior Editor, C/C++ Users Journal (<A HREF="mailto:cda@freshsources.com">cda@freshsources.com</A>)<br>
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|
|
<!-- LocalWords: dynamic bitset alt gif iostream hpp int bitsets const ul ulong
|
|
-->
|
|
<!-- LocalWords: STL LessThan alloc num typename BlockInputIterator html pos
|
|
-->
|
|
<!-- LocalWords: npos bool rhs OR's XOR's val CharT istream ostream os siek
|
|
-->
|
|
<!-- LocalWords: htm namespace enum sizeof BlockOutputIterator fwd ith jth
|
|
-->
|