A type for storing fixed-size boolean arrays densely to optimize space

Inspired by C++'s std::vector implementation

Overview

compact_bitset adds a new container type, CompactBitset. A CompactBitset stores boolean variables so that one bit is used per bool. It is designed for cases where a boolean array is necessary, but Vec<bool> or a slice is undesired due to space requirements. The CompactBitset reduces size used per bool to an eighth of what it would otherwise be.

Details

CompactBitset uses the proxy types BitRef and BitRefMut for indexing operations.

These two types deref to bool and implement comparison to bool as well as each other.

Writing to a BitRefMut alters the bit that it symbolically references in the CompactBitset.

BitRef and BitRefMut contain references to their parent CompactBitset. Thus, any number of BitRefs can be borrowed from a CompactBitset, but only 1 BitRefMut may be active at a time. This allows BitRef and BitRefMut to take advantage of the safety guarantees of references.

BitIter allows the user to immutably iterate the CompactBitset via a wrapper around a BitRef with its index incremented. It contains all standard Iterator functionality.

BitIterMut may be on the roadmap, but a current implementation has not successfully been created without use of unsafe.