vector( ) member function returns the vector<T> by value, which might cause some overhead issues with complex values of the parameter type T.
Holding bits
Most of my computer education was in hardware-level design and programming, and I spent my first few years doing embedded systems development. Because C was a language that purported to be “close to the hardware,” I have always found it dismaying that there was no native binary representation for numbers. Decimal, of course, and hexadecimal (tolerable only because it’s easier to group the bits in your mind), but octal? Ugh. Whenever you read specs for chips you’re trying to program, they don’t describe the chip registers in octal, or even hexadecimal – they use binary. And yet C won’t let you say 0b0101101, which is the obvious solution for a language close to the hardware.
Although there’s still no native binary representation in C++, things have improved with the addition of two classes: bitset and vector<bool>, both of which are designed to manipulate a group of on-off values. The primary differences between these types are:
1.The bitset holds a fixed number of bits. You establish the quantity of bits in the bitset template argument. The vector<bool> can, like a regular vector, expand dynamically to hold any number of bool values.
2.The bitset is explicitly designed for performance when manipulating bits, and not as a “regular” container. As such, it has no iterators and it’s most storage-efficient when it contains an integral number of long values. The vector<bool>, on the other hand, is a specialization of a vector, and so has all the operations of a normal vector – the specialization is just designed to be space-efficient for bool.
There is no trivial conversion between a bitset and a vector<bool>, which implies that the two are for very different purposes.
bitset<n>
The template for bitset accepts an integral template argument which is the number of bits to represent. Thus, bitset<10> is a different type than bitset<20>, and you cannot perform comparisons, assignments, etc. between the two.
A bitset provides virtually any bit operation that you could ask for, in a very efficient form. However, each bitset is made up of an integral number of longs (typically 32 bits), so even though it uses no more space than it needs, it always uses at least the size of a long. This means you’ll use space most efficiently if you increase the size of your bitsets in chunks of the number of bits in a long. In addition, the only conversion from a bitset to a numerical value is to an unsigned long, which means that 32 bits (if your long is the typical size) is the most flexible form of a bitset.
Chapter 15: Multiple Inheritance
226
The following example tests almost all the functionality of the bitset (the missing operations are redundant or trivial). You’ll see the description of each of the bitset outputs to the right of the output so that the bits all line up and you can compare them to the source values. If you still don’t understand bitwise operations, running this program should help.
//: C04:BitSet.cpp
// Exercising the bitset class #include <iostream>
#include <bitset> #include <cstdlib> #include <ctime> #include <climits> #include <string> using namespace std; const int sz = 32; typedef bitset<sz> BS;
template<int bits> bitset<bits> randBitset() {
bitset<bits> r(rand());
for(int i = 0; i < bits/16 - 1; i++) { r <<= 16;
// "OR" together with a new lower 16 bits: r |= bitset<bits>(rand());
}
return r;
}
int main() { srand(time(0));
cout << "sizeof(bitset<16>) = "
<<sizeof(bitset<16>) << endl; cout << "sizeof(bitset<32>) = "
<<sizeof(bitset<32>) << endl; cout << "sizeof(bitset<48>) = "
<<sizeof(bitset<48>) << endl; cout << "sizeof(bitset<64>) = "
<<sizeof(bitset<64>) << endl; cout << "sizeof(bitset<65>) = "
<<sizeof(bitset<65>) << endl;
BS a(randBitset<sz>()), b(randBitset<sz>()); // Converting from a bitset:
unsigned long ul = a.to_ulong(); string s = b.to_string();
Chapter 15: Multiple Inheritance
227
// Converting a string to a bitset: char* cbits = "111011010110111";
cout << "char* cbits = " << cbits <<endl; cout << BS(cbits) << " [BS(cbits)]" << endl; cout << BS(cbits, 2)
<<" [BS(cbits, 2)]" << endl; cout << BS(cbits, 2, 11)
<<" [BS(cbits, 2, 11)]" << endl; cout << a << " [a]" << endl;
cout << b << " [b]"<< endl;
//Bitwise AND:
cout << (a & b) << " [a & b]" << endl;
cout << (BS(a) &= b) << " [a &= b]" << endl; // Bitwise OR:
cout << (a | b) << " [a | b]" << endl;
cout << (BS(a) |= b) << " [a |= b]" << endl; // Exclusive OR:
cout << (a ^ b) << " [a ^ b]" << endl;
cout << (BS(a) ^= b) << " [a ^= b]" << endl; cout << a << " [a]" << endl; // For reference // Logical left shift (fill with zeros):
cout << (BS(a) <<= sz/2)
<<" [a <<= (sz/2)]" << endl; cout << (a << sz/2) << endl;
cout << a << " [a]" << endl; // For reference
//Logical right shift (fill with zeros): cout << (BS(a) >>= sz/2)
<<" [a >>= (sz/2)]" << endl;
cout << (a >> sz/2) << endl;
cout << a << " [a]" << endl; // For reference cout << BS(a).set() << " [a.set()]" << endl; for(int i = 0; i < sz; i++)
if(!a.test(i)) {
cout << BS(a).set(i)
<< " [a.set(" << i <<")]" << endl; break; // Just do one example of this
}
cout << BS(a).reset() << " [a.reset()]"<< endl; for(int j = 0; j < sz; j++)
if(a.test(j)) {
cout << BS(a).reset(j)
<< " [a.reset(" << j <<")]" << endl; break; // Just do one example of this
Chapter 15: Multiple Inheritance
228
}
cout << BS(a).flip() << " [a.flip()]" << endl; cout << ~a << " [~a]" << endl;
cout << a << " [a]" << endl; // For reference cout << BS(a).flip(1) << " [a.flip(1)]"<< endl; BS c;
cout << c << " [c]" << endl;
cout << "c.count() = " << c.count() << endl; cout << "c.any() = "
<<(c.any() ? "true" : "false") << endl; cout << "c.none() = "
<<(c.none() ? "true" : "false") << endl; c[1].flip(); c[2].flip();
cout << c << " [c]" << endl;
cout << "c.count() = " << c.count() << endl; cout << "c.any() = "
<<(c.any() ? "true" : "false") << endl; cout << "c.none() = "
<<(c.none() ? "true" : "false") << endl;
//Array indexing operations:
c.reset();
for(int k = 0; k < c.size(); k++) if(k % 2 == 0)
c[k].flip();
cout << c << " [c]" << endl; c.reset();
// Assignment to bool:
for(int ii = 0; ii < c.size(); ii++) c[ii] = (rand() % 100) < 25;
cout << c << " [c]" << endl; // bool test:
if(c[1] == true)
cout << "c[1] == true"; else
cout << "c[1] == false" << endl; } ///:~
To generate interesting random bitsets, the randBitset( ) function is created. The Standard C rand( ) function only generates an int, so this function demonstrates operator<<= by shifting each 16 random bits to the left until the bitset (which is templatized in this function for size) is full. The generated number and each new 16 bits is combined using the operator|=.
The first thing demonstrated in main( ) is the unit size of a bitset. If it is less than 32 bits, sizeof produces 4 (4 bytes = 32 bits), which is the size of a single long on most
Chapter 15: Multiple Inheritance
229