A collection based on a bitset to store a set of unique integers from a given range (rev. 2)

Question

This is a continuation of this review. I applied most of the proposed changes. These changes were focused mostly on decoupling the class from the rest of the program and making its interface more like STL collections.

Description of the code:

This is an implementation of a set data structure. It is optimized to efficiently store a huge amount of unsigned integers (even billions) from a range specified at construction (it always starts at 0). It it used in very expensive computations so the main goal of this implementation (beside the memory efficiency) is performance.

The most important (for my goals) properties of this set are random read/write access in O(1) time, checking its size in O(1) time and an iterator that can continue iteration after changes in the set are made.

Additionally, the set is kept sorted because of how it is implemented.

This collection is not intended for storing small number of integers from a huge possible range. In such case the memory optimization is terrible and iteration takes too long. (This is not the case in my program where on average half of the integers from the range is in the set.)

The goal of the review:

The primary goal is still to make sure that I as a self learner don't follow some weird coding patterns that have well established alternatives. (Things that a professional C++ programmer would consider stupid, counter-productive or just weird.) E.g. naming a function getSize() instead of size() (an example from the previous review). I would like the code to not only work reliably but also be elegant in a way that makes it easy to read and use by other programmers.

I would also like to learn about any tricks or techniques which lack is not pointed out by a compiler but which can be useful in some way or other. The attribute [[nodiscard]] is example of such thing as it provides additional static analysis of the code. Another example is the keyword const that not only prevents mistakes in the code but also it may improve optimization.

I'll also gladly take hints on making the code faster. Actually, I'll take any sensible comments as long as they are not detrimental to the performance.

The code:

CompactSet.hh:

#pragma once

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <limits>
#include <vector>


// This container can store unique numbers in range 0..capacity-1 using only about capacity/CHAR_BIT bytes of memory.
// (The memory usage is the same regardles of how many numbers are stored.)
template<typename T>
class CompactSet
{
    static_assert(!std::numeric_limits<T>::is_signed);
    
    std::vector<bool> bitset;
    std::size_t count = 0;
    
public:
    class const_iterator
    {
        const CompactSet<T> &compactSet;
        std::uint_fast64_t i;
        const_iterator(const CompactSet &compactSet, const std::uint_fast64_t i) : compactSet(compactSet), i(i) { }
        friend class CompactSet<T>;
    public:
        [[nodiscard]] bool operator==(const const_iterator &other) const { return this->i == other.i; }
        [[nodiscard]] bool operator!=(const const_iterator &other) const { return this->i != other.i; }
        inline const_iterator& operator++();
        inline const_iterator& operator--();
        [[nodiscard]] T operator*() const { return static_cast<T>(i); }
    };
    
    explicit inline CompactSet(const std::size_t capacity);
    
    [[nodiscard]] bool operator==(const CompactSet &other) const { return this->bitset == other.bitset; }
    [[nodiscard]] bool operator!=(const CompactSet &other) const { return this->bitset != other.bitset; }
    
    [[nodiscard]] bool empty() const { return count == 0; }
    [[nodiscard]] bool full() const { return count == bitset.size(); }
    [[nodiscard]] std::size_t size() const { return count; }
    [[nodiscard]] std::size_t capacity() const { return bitset.size(); }
    [[nodiscard]] bool check(const T value) const { return bitset[value]; }
    inline bool add(const T value);
    inline void add(const CompactSet &other);
    inline void add(const CompactSet &other, const std::size_t overlappingCount);
    inline bool remove(const T value);
    
    [[nodiscard]] inline const_iterator begin() const;
    [[nodiscard]] const_iterator end() const { return {*this, bitset.size()}; }
    [[nodiscard]] const_iterator cbegin() const { return begin(); }
    [[nodiscard]] const_iterator cend() const { return end(); }
    
#ifndef NDEBUG
    void validate() const;
#endif
};


template<typename T>
typename CompactSet<T>::const_iterator& CompactSet<T>::const_iterator::operator++()
{
    for (++i; i != compactSet.bitset.size() && !compactSet.bitset[i]; ++i) { }
    return *this;
}

template<typename T>
typename CompactSet<T>::const_iterator& CompactSet<T>::const_iterator::operator--()
{
    for (--i; !compactSet.bitset[i]; --i) { }
    return *this;
}

template<typename T>
CompactSet<T>::CompactSet(const std::size_t capacity) :
    bitset(capacity, false)
{
    assert(capacity == 0 || capacity - 1 <= std::numeric_limits<T>::max());
    assert(capacity <= std::numeric_limits<std::uint_fast64_t>::max());  // Otherwise, iterators won't work.
}

template<typename T>
bool CompactSet<T>::add(const T value)
{
    const bool previous = check(value);
    if (!previous)
    {
        bitset[value] = true;
        ++count;
    }
    return !previous;
}

template<typename T>
void CompactSet<T>::add(const CompactSet &other)
{
    for (const T value : other)
        add(value);
}

template<typename T>
void CompactSet<T>::add(const CompactSet &other, const std::size_t overlappingCount)
{
    std::transform(
            other.bitset.cbegin(), other.bitset.cend(),
            this->bitset.begin(), this->bitset.begin(),
            std::logical_or<bool>());
    this->count += other.count - overlappingCount;
}

template<typename T>
bool CompactSet<T>::remove(const T value)
{
    const bool previous = check(value);
    if (previous)
    {
        bitset[value] = false;
        --count;
    }
    return previous;
}

template<typename T>
typename CompactSet<T>::const_iterator CompactSet<T>::begin() const
{
    const_iterator iter{*this, 0};
    if (!bitset.empty() && !bitset[0])
        ++iter;
    return iter;
}

CompactSet.cc:

#include "./CompactSet.hh"


#ifndef NDEBUG
template<typename T>
void CompactSet<T>::validate() const
{
    const std::size_t actualCount = std::ranges::count(bitset.cbegin(), bitset.cend(), true);
    assert(count == actualCount);
}
#endif


#include "Minterm.hh"

template class CompactSet<Minterm>;

The function validate() is called (in development build only) to make sure mostly that the 2-argument add() was correctly used and in lesser degree to also check if normal add() and remove() are working correctly.

Minterm (an alias for std::uint_fast32_t) is the only type for which this class is used in my code.

Answer 1

Instead of a static_assert, I'd prefer to use a constraint to ensure we have only unsigned integer types:

#include <concepts>

template<std::unsigned_integral T>
class CompactSet
{

---

It's somewhat confusing that bitset refers to a std::vector<bool> and not a std::bitset! Perhaps bits might be a better name?

---

Why is const_iterator::i not a std::size_t, given that it's being used to index the vector? std::uint_fast64_t might not be big enough, at least in theory. Actually, since it represents the value of type T it's pointing at, perhaps it's sufficient to declare T i;, if we make appropriate arrangements for the past-the-end iterator?

---

The iterator is missing some boilerplate to work properly as a BidirectionalIterator. It needs a default constructor, and also inner types with the following names:

    public:
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;

---

Whilst ++ operator is careful not to index the vector out of range, -- has no such check.

---

I think we can reduce the size of iterator by wrapping std::vector::iterator rather than needing a reference to the container. But perhaps not, given the need to terminate the search in ++ and -- operators. That can be dealt with by over-allocating the vector by 2 elements and providing sentinel values before and after the valid range. We might choose to have a private view of just the valid values, for more convenient indexing.

---

You should be able to write operator!=(…) = default. In fact, we should be able to use default equality too - alternatively, test count first, to give a faster result in some cases.

---

The add() overload that allows callers to break the class invariant is dangerous in my opinion, and I wouldn't allow it. (Why not use std::ranges::transform(), instead of passing iterator pairs?)

---

It would be good to look more like a std::set:

• capacity() should be called max_size() (like std::array, this is a fixed-size container).
• add(T) should be called insert() and return a pair. Implement the other insert() signatures, too.
• check() should be called count().
• Provide reverse iterator functions (use std::make_reverse_iterator() for this).
• Provide clear(), swap(), emplace(), emplace_hint(), find(), equal_range(), lower_bound() and upper_bound() (these should be mostly trivial).
• Provide erase().

---

We might be able to provide set intersection, union, difference and symmetric-difference operations that are more efficient than the generic <algorithm> ones. Consider adding them, as an enhancement.

---

I thought we might be able to implement add() more simply using std::exchange():

    const bool previous = std::exchange(bitset[value], true);
    count += !previous;
    return !previous;

Unfortunately, that gets broken because std::vector<bool> violates the Container contract.