From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-05-13 19:51:51
At 08:43 AM 5/12/2001, Daryle Walker wrote:
>I'm not sure this counts as an example, but I'm curious about what
>bit_string is like. I have an (inactive) project for an
>arbitrary-precision
>integer type for Boost. It strings together many bits for the
value. I've
>had two choices for the bit container:
>
>1. vector<bool> since it stores the bits compactly
>2. deque<bool> to allow inserts from either end (for shifts)
>
>If bit_string could provide compact representation with efficient pushing
>(and popping) from either end, it would be great!
See below for the interface.
Please don't criticize this interface in light of modern STL practice - it
was designed before there was an STL.
--Beman
-----------
The header <bitstring> defines a class and several function signatures
for representing and manipulating varying-length sequences of bits.
class bit_string {
public:
bit_string();
bit_string(unsigned long val, size_t n);
bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);
bit_string(const string& str, size_t pos = 0, size_t n = NPOS);
bit_string& operator+=(const bit_string& rhs);
bit_string& operator&=(const bit_string& rhs);
bit_string& operator|=(const bit_string& rhs);
bit_string& operator^=(const bit_string& rhs);
bit_string& operator<<=(size_t pos);
bit_string& operator>>=(size_t pos);
bit_string& append(const bit_string& str, pos = 0, n = NPOS);
bit_string& assign(const bit_string& str, pos = 0, n = NPOS);
bit_string& insert(size_t pos1, const bit_string& str,
size_t pos2 = 0, size_t n = NPOS);
bit_string& remove(size_t pos = 0, size_t n = NPOS);
bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
size_t pos2 = 0, size_t n2 = NPOS);
bit_string& set();
bit_string& set(size_t pos, bool val = 1);
bit_string& reset();
bit_string& reset(size_t pos);
bit_string& toggle();
bit_string& toggle(size_t pos);
string to_string() const;
size_t count() const;
size_t length() const;
size_t resize(size_t n, bool val = 0);
size_t trim();
size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;
size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;
bit_string substr(size_t pos, size_t n = NPOS) const;
bool operator==(const bit_string& rhs) const;
bool operator!=(const bit_string& rhs) const;
bool test(size_t pos) const;
bool any() const;
bool none() const;
bit_string operator<<(size_t pos) const;
bit_string operator>>(size_t pos) const;
bit_string operator~() const;
private:
// char* ptr; exposition only
// size_t len; exposition only
};
2 The class bit_string describes an object that can store a sequence
consisting of a varying number of bits. Such a sequence is also
called a bit string (or simply a string if the type of the elements is
clear from context). Storage for the string is allocated and freed as
necessary by the member functions of class bit_string.
3 Each bit represents either the value zero (reset) or one (set). To
toggle a bit is to change the value zero to one, or the value one to
zero. Each bit has a non-negative position pos. When converting
between an object of class bit_string of length len and a value of
some integral type, bit position pos corresponds to the bit value 1 <<
(len - pos - 1).2) The integral value corresponding to two or more
_________________________
2) Note that bit position zero is the most-significant bit for an ob
bits is the sum of their bit values.
4 For the sake of exposition, the maintained data is presented here as:
--char* ptr, points to the sequence of bits, stored one bit per
element;3)
--size_t len, the length of the bit sequence.
5 The functions described in this subclause can report three kinds of
errors, each associated with a distinct exception:
--an invalid-argument error is associated with exceptions of type
invalid_argument;
--a length error is associated with exceptions of type length_error;
--an out-of-range error is associated with exceptions of type
out_of_range.
------ end ------