Component of the Week #22: `bdlc_bitarray`

Summary:

A vector-like space-efficient container of boolean values.

Although a bool represents just 1 bit of information, it typically occupies a full byte of memory. The bdlc::BitArray class provides a convenient way to store 8 bits of information per byte for an arbitrary number of bytes. A bdlc::BitArray supports constant-time access to individual bits, dynamic growth of the array, and efficient bitwise operations between arrays.

As a usage example, consider a problem discussed by Jon Bentley in the first chapter of his classic book, Programming Pearls where he determines that a “bitmap” (his term for a bit array) is the appropriate approach to a colleague’s problem of sorting a largish set of unique, positive integer values.

Here’s how that can be done using bdlc::BitArray:

#include <bdlc_bitarray.h>

#include <bsl_cstddef.h>   // `bsl::size_t`
#include <bsl_iostream.h>

using namespace BloombergLP;

int main()
{
    // Define input.
    const int         intArray[]   = { 666, 13, 42 };  // unsorted input
    const bsl::size_t NUM_ELEMENTS = sizeof intArray / sizeof *intArray;

    // Create bit array.
    bdlc::BitArray bitArray(1000); // 1000 bits, all `0`.

    // Use input as index at which `1` bits are set.
    for (bsl::size_t i = 0; i < NUM_ELEMENTS; ++i) {
        bitArray.assign1(intArray[i]);
    }

    // Find the bits set to `1` from lowest index to highest.
    for (bsl::size_t index = 0; index < bitArray.length(); ++index) {

            index = bitArray.find1AtMinIndex(index);

            if (bdlc::BitArray::k_INVALID_INDEX == index) {
                break;
            }
            bsl::cout << index << bsl::endl;
    }
}

The output is:

13
42
666

By the way, that chapter is not only valuable for introducing this data structure, but also as a demonstration of the importance of problem analysis. The original question posed in the chapter is: How do I sort a disk file?. The journey from that question, to the solution using a bitmap is worthwhile.

For more details, see: * documentation for bdlc_bitarray.

Component of the Week #22: bdlc_bitarray

Component of the Week #22: `bdlc_bitarray`