RE: [boost] Dynamic sized bitset

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-12-11 09:43:44

Hi Cliff,

On Tue, 11 Dec 2001, Cliff Green wrote:
cliffg>
cliffg> There are various construction and get / append interfaces to stream in /
cliffg> out the binary buffer. For example, assume the template class is named
cliffg> BitBuffer, and the binary buffer is of type BinBuf:
cliffg>
cliffg>    BitBuffer (BinBuf const& buf, size_t numBits) : mBits() {
cliffg> appendBinaryBuf(buf, numBits); }
cliffg>    void appendBinaryBuf( BinBuf const& buf, size_t numBits);
cliffg>    BinBuf const getBinaryBuf() const { return getBinaryBuf(0, size()); }
cliffg>    BinBuf const getBinaryBuf(size_t startBit, size_t numBits) const;
cliffg>
cliffg> For dyn_bitset, it probably doesn't make sense to have either template
cliffg> policy (as in my class design), but instead maybe provide binary buffer
cliffg> streaming in / out solely through template member functions. The storage
cliffg> policy could also be implicit in the dyn_bitset, or through the allocator as
cliffg> it appears to be in the proposed interface.

So the idea would be to replace the functions that convert to and from
std::basic_string with function templates? That sounds reasonable to me.

cliffg> The get / append for unsigned integral types are template member functions,
cliffg> such as:
cliffg>
cliffg>    template <typename T>
cliffg>      void appendVal (T val, size_t numBits);
cliffg>    template <typename T>
cliffg>     T getVal (size_t startBit, size_t numBits) const;
cliffg>
cliffg> Everything in the bit container is considered to be Most Significant Bit
cliffg> first, so the "appendVal" and "getVal" template member functions have
cliffg> corresponding logic.

The most-significant bit first, and the append function would be more
difficult.

Both the std::bitset and the dyn_bitset are least significant bit first,
which means the appending you want would be prepending to the storage,
which is not so easy with an array.

However, the underlying storage order is just an implementation detail. It
is merely an issue of which operations you want to be fast. So it would be
conceivable to store the bits in most-significant bit order, and to
provide an append funtion, but then to provide the same least-significant
bit *public* interface as std::bitset.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------