BitSet
Introduction
The C++ STL provides std::bitset
which emulates an array of bool
elements.
The BitSet
class template provides similar support for sets of strongly-typed elements.
For example:
enum class Fruit {
apple,
banana,
kiwi,
orange,
passion,
pear,
tomato,
};
using FruitBasket = BitSet<uint8_t, Fruit, unsigned(Fruit::tomato) + 1>;
static constexpr FruitBasket fixedBasket = Fruit::orange | Fruit::banana | Fruit::tomato;
A FruitBasket
uses one byte of storage, with each bit representing an item of Fruit
.
If the basket contains a piece of fruit, the corresponding bit is set.
If it does not, the bit is clear.
Without BitSet you implement this as follows:
using FruitBasket = uint8_t;
static constexpr FruitBasket fixedBasket = _BV(Fruit::orange) | _BV(Fruit::banana) | _BV(Fruit::tomato);
To test whether the set contains a value you’d do this:
if(fixedBasket & _BV(Fruit::orange)) {
Serial.println("I have an orange");
}
With a BitSet, you do this:
if(fixedBasket[Fruit::orange]) {
Serial.println("I have an orange");
}
And you can add an element like this:
basket[Fruit::kiwi] = true;
Bit manipulation operators are provided so you can do logical stuff like this:
FruitBasket basket1; // Create an empty basket
// Add a kiwi fruit
basket1 = fixedBasket + Fruit::kiwi;
// Create a second basket containing all fruit not in our first basket
FruitBasket basket2 = ~basket1;
// Remove some fruit
basket2 -= Fruit::orange | Fruit::tomato;
And so on.
To display the contents of a BitSet, do this:
Serial.print(_F("My basket contains: "));
Serial.println(basket1);
You will also need to provide an implementation of toString(Fruit)
or whatever type you are using for the set elements.
API
-
template<typename S, typename E, size_t size_ = sizeof(S) * 8>
class BitSet Manage a set of bit values using enumeration.
API is similar to a simplified std::bitset, but with added +/- operators.
Note
It is important to specify size correctly when using enumerated values. In the
FruitBasket
example, we use auint8_t
storage type so can have up to 8 possible values. However, theFruit
enum contains only 7 values. The set operations will therefore be restricted to ensure that the unused bit is never set.- Template Parameters:
S – Storage type (e.g. uint32_t). This determines how much space to use, and must be an unsigned integer. It is safe to use this class in structures, where it will occupy exactly the required space.
E – Element type e.g. enum class. You can use any enum or unsigned integer for the elements. These must have ordinal sequence starting at 0.
size_ – Number of possible values in the set. Defaults to maximum for given storage type. Number of possible values in the set. This must be at least 1, and cannot be more than the given Storage type may contain. For example, a :cpp:type:
uint8_t
may contain up to 8 values.
Public Functions
-
constexpr BitSet() = default
Construct empty set.
-
template<typename S2>
inline constexpr BitSet(const BitSet<S2, E> &bitset) Copy constructor.
- Parameters:
bitset – The set to copy
-
inline constexpr BitSet(S value)
Construct from a raw set of bits.
- Parameters:
value – Integral type whose bits will be interpreted as set{E}
-
inline constexpr BitSet(E e)
Construct set containing a single value.
- Parameters:
e – Value to place in our new BitSet object
-
inline size_t count() const
Get the number of elements in the set, i.e. bits set to 1.
-
inline BitSet &operator&=(const BitSet &rhs)
Intersection: Leave only elements common to both sets.
-
inline bool operator[](E e) const
Read-only [] operator.
- Parameters:
e – Element to test for
- Return values:
bool – true if given element is in the set
-
inline BitRef operator[](E e)
Read/write [] operator.
This returns a temporary BitRef object to support assignment operations such as
set[x] = value
- Parameters:
e – Element to read or write
- Return values:
BitRef – Temporary object used to do the read or write
-
inline bool any() const
Determine if set contains any values.
-
inline bool any(const BitSet &other) const
Determine if set contains any values from another set i.e. intersection != [].
-
inline bool all() const
Test if set contains all possible values.
-
inline bool none() const
Test if set is empty.
-
inline BitSet &set(E e, bool state = true)
Set the state of the given bit (i.e. add to or remove from the set)
- Parameters:
e – Element to change
state – true to add the element, false to remove it
Public Static Functions
-
static inline constexpr size_t size()
Get the number of possible elements in the set.
-
class BitRef