Chuck Allison is a regular columnist with CUJ and a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, the ANSI C++ Standards Committee. Chuck can be reached on the Internet at allison@decus.org, or at (801)240-4510.## The Standard C++ Library

When ANSI Committee X3J16 convened in 1989, it planned to at least standardize the C++ library stream classes. At the close of the third meeting in July 1990 the Library Working Group emerged with more specific direction: 1) standardize the stream classes, 2) define mechanisms to support language features such as thenewanddeleteoperators and exceptions, 3) define the relationship between the standard C library and the C++ library, and 4) define a standard string class. Working group members sometimes call this list the "Blood in the Streets Manifesto" to indicate what might happen if we fail. I am happy to report that after three years of difficult work, our blood seems destined to stay where it is. We have completed the above four items, modulo some fine tuning.The overall charter of any standards committee is to standardize existing practice. It is not feasible, however, for the committee to design a comprehensive object-oriented library. A large group of volunteers cannot accomplish what a small, focused department can (plus the pay is not as good). It would be more reasonable to standardize a small number of popular, low-level classes as building blocks for a wide spectrum of applications. To determine the existing industry practice in development of libraries, in June 1991 I volunteered to review the libraries which a number of vendors had submitted to the committee. All submissions offered at least one string class and a number of container classes, such as lists, vectors, queues, stacks, and sets. Many vendors' libraries also supported bit sets. Now, two years later, the following classes are part of the standard C++ library (in addition to streams and language support):

TheClass Descriptionstring dynamic array of characters wstring dynamic array of wide characters dynarray dynamic array of anything (vector) bits fixed-length bitset bitstring dynamic-length bit stringstringclass, which started with contributions from Aron Insinga of Digital, and was completed through the efforts of Uwe Steinmueller of Siemens Nixdorf and Pete Becker at Borland, supports most of C'sstring.hfunctionality on dynamically-sized arrays of bytes. Beman Dawes adapted thestringclass to handle arrays of wide characters, of typewchar_t.(FYI: this is a keyword representing a distinct, overloadable type in C++). Uwe also designed thedynarrayclass. I was interested in improving on C's awkward bitwise support, and designed the last two classes. In this article I will discuss thebitstringclass.

## Bit Sets

C's bitwise operators allow you to process an integer as an ordered set of bits. This ability is useful for system interface operations, which often interpret individual bits as flags. If you want more bits than can fit in anunsigned long,however, you're out of luck. An extended version of such a bit array can come in handy, though. For example, I have developed a user interface library which provides picklists, scrollable popup menus that allow multiple choices. For efficiency, I like to track the choices with only one bit per entry. Bit arrays are also handy with sets. You can simulate a set of integers with a bit array: if the bit in positionnis set, then the integernis a member of the set. Pascal and Modula-2 both implement sets this way. (See last month'sCode Capsulefor a C implementation of bitsets.)The first bitset class proposal submitted to X3J16 tried to meet all of these needs with a single class. After much discussion and little agreement among working members, the committee realized that existing practice called for two distinct abstractions: fixed-length bit sets (for a collection of flags, say) and bit strings (i.e., dynamic bit arrays). One year and three committee meetings later, these abstractions became class

bitsandbitstring,respectively.

## Class

Thebitstringbitstringclass provides much of the same functionality as thestringclass (see the sidebar "A Simple String Class").bitstringsupports dynamically-sized bit strings with operations such as insert, remove, replace, and concatenate, as well as the basic bit operations — set, reset, test, and toggle (see Listing 4) . Since a bitstring is in fact a string, the bit numbering begins with bit0on the left, and increases as you move to the right (this is the reverse of numeric bitfields, which are numbered from right to left). I can now easily implement a picklist by embedding a bitstring:

class Picklist : public Popmenu { bitstring picks; // . . . public: Picklist(.., nitems,..) : picks(0,nitems), .. {} // . . . };When the user highlights thenthentry, I set bitnin the bitstring:

picks.set(n);## Member Function Descriptions

This section is a modified excerpt from the official proposal which describes the semantics of each member function. Since the library group is still deciding how to integrate exceptions into the standard library, I just mention them briefly here. The names and uses of exceptions are subject to change. I use assertions in place of exceptions in the implementation (see Listing 5 and Listing 6) . Throughout the rest of this article, the valueNPOS, which stands for "not a position," is the largest possible value of typesize_t, which is equivalent to(size_t)(-1). A bitstring can hold up toNPOS - 1bits.

## 1.0 Constructors

## Synopsis

bitstring() bitstring(unsigned long n, size_t nbits) bitstring(const string& s) bitstring(const bitstring& b)

1.1 Constructorbitstring()## Description

Creates a bit string of length zero.

1.2 Constructorbitstring(unsigned long n, size_t nbits)## Description

Creates a bit string at leastnbitslong, initialized with the contents ofn. The constructor drops no significant bits, i.e.,this->length == max(nbits, N+1), whereNis the bit position of the highest-orderonebit. The constructor pads the higher order bits with zeroes if necessary, to fill outnbitsbits. The common usage of this constructor would be to initialize a bitstring of a certain length with zeroes, e.g.,

bitstring x(0,16);Be aware when using a non-zero value initializer that the bits will be "reversed." For example, the bit pattern for the decimal number 21025 is 0101001000100001, but the output from the following code

bitstring x(21025,16); cout << x << endl;is 1000010001001010.

1.3 Constructorbitstring(const string& s)## Description

Reads bit characters ('1's and '0's) fromsand sets the corresponding bits in the new bitstring. The first bit read corresponds to bit0.

## Exceptions

Throwsinvalid_argumentif any character in the string is not a '1' or '0'.

1.4 Constructorbitstring(const bitstring& b)## Description

The usual copy constructor.

2.0 Destructorbitstring()## Description

Frees resources and destroys the object.

## 3.0 Other Member Functions

3.1 Functionstring to_string()## Description

Creates a string of '1's and '0's representing the contents of*this.The first (left-most) character is bit0.

## Returns

The temporary string of '1's and '0's.

3.2 Functionbitstring& operator=(const bitstring&)## Description

Standard assignment operator.

## Returns

A reference to*this.

3.3 Functionint operator==(const bitstring&b) const## Description

Compares*thistobfor equality. Two bitstrings are equal if and only if they have the same number of bits and their bit patterns are identical.

## Returns

Non-zero if the bitsets are equal, zero otherwise.

3.4 Functionint operator!=(const bitstring&b) const## Description

Compares*thistobfor inequality. Equivalent to!operator==(b);

## Returns

Zero if the bitsets are equal, non-zero otherwise.

3.5 Functionsset## Synopsis

bitstring& set(size_t n, int val = 1) bitstring& set()## Description

These functions set one or more bits. The functionset(size_t, intcan also reset a bit, depending on the contents ofval.

3.5.1 Functionbitstring& set (size_t n, int val = 1)## Description

Sets thenthbit ifvalis non-zero, otherwise resets the bit. Appends a bit ifn == length.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_range if n > length.

3.5.2 Functionbitstring& set()## Description

Sets all bits,

## Returns

A reference to*this.

3.6 Functionsreset## Synopsis

bitstring& reset(size_t n) bitstring& reset()## Description

These functions reset one or more bits.

3.6.1 Functionbitstring& reset(size_t n)## Description

Resets thenthbit. Appends the bit ifn == length.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_range if n > length.

3.6.2 Functionbitstring& reset()## Description

Resets all bits.

## Returns

A reference to*this.

3.7 Functionstoggle## Synopsis

bitstring& toggle(size_t n) bitstring& toggle()## Description

These functions toggle one or more bits.

3.7.1 Functionbitstring& toggle(size_t n)## Description

Toggles thenthbit.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifn >= length.

3.7.2 Functionbitstring& toggle()## Description

Toggles all bits.

## Returns

A reference to*this.

3.8 Functionint test(size_t n) const## Description

Tests if bitnis set.

## Returns

Non-zero if the bit is set, zero otherwise.

## Exceptions

Throwsout_of_range if n >= length.

3.9 Functionint any() const## Description

Tests if any bits at all are set.

## Returns

Zero if all bits are0, non-zero otherwise.

3.10 Functionint none() const## Description

Tests if no bits at all are set. Equivalent to!any.

## Returns

One if all bits are0, non-zero otherwise.

3.11 Functionbits operator~() const## Description

Toggles all the bits of a copy of*this.

## Returns

A toggled copy of *this.

3.12 Functionsize_t count() const## Description

Counts the number of bits that are set.

## Returns

The number of1bits in the string.

3.13 Functionbitstring& operator&=(const bitstring&b)## Description

Replaces the current object with the bitwise-AND ofband*this.This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the AND operation will be of equal length. The new length of the object is the maximum of the lengths of the old object andb.

## Returns

A reference to*this.

3.14 Functionbitstring& operator|=(const bitstring& b)## Description

Replaces the current object with the bitwise-OR ofband*this.This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the XOR operation will be of equal length. The new length of the object is the maximum of the lengths of the old object andb.

## Returns

A reference to*this.

3.15 Functionbitstring&operator^=(const bitstring& b)## Description

Replaces the current object with the bitwise-XOR ofband*this.This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the XOR operation will be of equal length. The new length of the object is the maximum of the lengths of the old object andb.

## Returns

A reference to*this.

3.16 Functionbitstring& operator>>=(size_t n)## Description

Modifies the current object by shifting*thisright, bynbit positions. Ifn > length, then this function resets all bits. Shifting "right" bynmeans that bitngets the value of bit0, bit(n+1)gets bit1, etc. This function resets any vacated bits.

## Returns

A reference to*this.

3.17 Functionbitstring& operator<<=(size_t n)## Description

Modifies the current object by shifting*thisleft bynbit positions. ifn > length, then this function resets all bits. Shifting "left" bynmeans that bit0receives the value of bitn, bit1receives bit(n+1), etc.

## Returns

A reference to*this.

3.18 Functionbitstring operator>>(const bitstring& b, size_t n) const## Description

Shiftsbright bynbit positions. Does not modifyb.(See 3.16).

## Returns

The shifted result in a temporary bitstring.

3.19 Functionbitstring operator<<(const bitstring& b, size_t n) const## Description

Shiftsbleft bynbit positions. Does not modifyb, (See 3.17).

## Returns

The shifted result in a temporary bitstring.

3.20 Functionbitstring& operator+= (constbitstring& b)## Description

Appendsbdestructively to*this.

## Returns

A reference to*this.

## Exceptions

Throwslength_error if length >= NPOS - b. length.

3.21 Functionbitstring& insert (size_t pos, const bitstring& b)## Description

Insertsbinto*thisstarting at bit positionpos. The bits of*thisstarting atposfollow the inserted copy ofb. Appendsbifpos == length.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifpos > length. Throwslength_erroriflength >= NPOS - b.length.

3.22 Functionbitstring& remove(size_t pos, size_t n = NPOS)## Description

Removes up to n bits from*thisstarting at bit positionpos. Truncates, starting at positionpos, iflength - pos < n.## Returns

A reference to *this.

## Exceptions

Throwsout_of_rangeifpos > length.

3.24 Functionbitstring&replace(size_t pos, size_t n, const bitstring& b)## Description

Equivalent to a remove followed by a replace in the obvious way. Included for convenience and efficiency.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifpos >= length. Throwslength_errorif the new length would be >=NPOS.

3.25 Functionsize_t find(int val, size_t pos = 0) const## Description

Searches forward, starting from positionpos, for the first occurrence of a0bit (ifvalis zero) or a1bit (ifvalis non-zero).

## Returns

The found bit position, if the search was successful,NPOSotherwise.

## Exceptions

Throwsout_of_rangeifpos > length.

3.26 Functionsize_t rfind(int val, size_t pos = NPOS) const## Description

Searches backwards from positionpos(or from positionlength-1ifpos == NPOS) for the first occurrence of a0bit (ifvalis zero) or a1bit (if val is nonzero).

## Returns

The found bit position, if the search was successful,NPOSotherwise.

## Exceptions

Throwsout_of_rangeifpos > length.

3.27 Functionbitstring substr(size_t pos, size_t n = NPOS) const## Description

Creates a new bitstring consisting of the bit pattern starting at positionpos. This function copies up tonbits or all bits to the end of the string, whichever number is smaller. Ifpos == length, this function creates an empty bitstring.

## Returns

The new bitstring.

## Exceptions

Throwsout_of_rangeifpos > length.

3.28 Functionslength()## Synopsis

size_t length() size_t length(size_t n, int val = 0)## Description

These functions determine and/or modify the length of a bit-string.

3.28.1 Functionsize_t length() const## Description

Determines the number of bits in the string.

## Returns

The number of bits.

3.28.2 Functionsize_t length(size_t n, int val = 0)## Description

Resizes (i.e., truncates or expands) the object so thatthis->length == n. If the length increases, this function extends the object on the right with0s ifval == 0, or with1sotherwise.

## Returns

The oldlength.

3.29 Functionbitstring& trim()## Description

Truncates high-order0bits. IfNis the highest-numbered1bit, thenthis->lengthbecomesN+1.

## Returns

A reference to*this.

## 4.0 Global Functions

4.1 Functionostream& operator<<(ostream& os, const bitstring& b)## Description

Sends the sequence of '1's and '0's corresponding tobto the output streamos.

## Returns

A reference to the streamos.

4.2 Functionistream& operator>>(istream& is, bitstring& b)## Description

Reads a contiguous sequence of '1's and '0's from a stream intob. Skips whitespace according tois.skipws. The first bit read is bit0. The first non-whitespace, nonbit character terminates the read and remains in the stream. This function setsis.failbitif the first non-whitespace character is not a '1' or '0'.

## Returns

A reference to the streamis.

4.3 Functionbitstring operator&(const bitstring& b1, const bitstring& b2)## Description

Computes the bitwise-AND of operandsb1andb2. The length of the result equals the length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order 0 bits until its length equaled that of the longer operand.

## Returns

The result of the bitwise-AND in a temporary bitstring.

4.4 Functionbitstring operator|(const bitstring& b1, const bitstring& b2)## Description

Computes the bitwise-OR of operandsb1andb2. The length of the result equals the length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order0bits until its length equaled that of the longer operand.

## Returns

The result of the bitwise-OR in a temporary bitstring.

4.5 Functionbitstring operator^(const bitstring& b1, const bitstring& b2)## Des cription

Computes the exclusive-OR of operandsb1andb2. The length of the result equals length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order zero bits until its length equaled that of the longer operand.

## Returns

The result of the exclusive-OR in a temporary bitstring.

4.6 Functionbitstring operator+(const bitstring& b1, const bitstring& b2)## Description

Appendsbnon-destructively to*this.

## Returns

The result of the concatenation in a temporary bitstring.

## Implementation Notes

Following what seems to be the most popular coding style, the class definition in Listing 4 specifies the public interface first, followed by the private artifacts of the implementation. Whenever possible, inline functions appear outside the class definition itself. This placement is not possible in the case of the functionsword, offset, mask1, andmask0, because they return objects of the private nested typeBlock. These functions appeared as macros in last month's C version. As private, static member functions, they are available only to otherbitstringmember functions.I pack the bits of a bitstring left-to-right into an array of integral blocks. You can substitute any unsigned type for

unsigned intin the line

typedef unsigned int Block;See last month's capsule for a detailed explanation of the packing and unpacking algorithms.Last month I developed bit handling functions in C; this month I have restated them in C++. In that regard, this column presents nothing new. What is new this month is memory management and operator overloading. A

bitstringexpands or shrinks automatically as needed, and always uses the minimum number of blocks required to hold its bits. For example, the statements

bitstring b1, b2; // . . . b1 += b2;appendb2tob1. Consider the implementation ofoperator+=from Listing 5:

bitstring& bitstring::operator+=(const bitstring& b) { assert(nbits_ + b.nbits_ < NPOS); int oldlen = nbits_; length(nbits_ + b.nbits_); for (int i = 0; i < b.nbits_; ++i) (void) set_(oldlen+i,b.test_(i)); return *this; }All this function has to do is resize the object and copyb's bits to the end of the object. If the number of bits inb2is less than or equal to the number of unused bits inb1's allocated memory, then no memory reallocation is necessary. Whether the array needs to be resized or not, the member functionlength(size_t)resizes the object; if the array must be resized, it handles that too.The implementation of the global

operator+is now trivial usingoperator+=:

bitstring operator+(const bitstring& b1, const bitstring& b2) { bitstring b(b1); return b.operator+=(b2); }We can do the same sort of thing for all the binary operators. Being small, the binary operators are good candidates for inlining, and therefore appear inbitstring.h.The program in Listing 6 illustrates many of the member functions of the

bitstringclass. Next month I'll cover classbits, a template class for fixed-length bitsets.