Coalesced "bit"-thread-safe vector<bool>

Question

As far as I know:

• vector<bool> involves coalescing vector elements, that is: V[i] occupies a single bit, instead of sizeof(bool) bytes.

• "Coalesced" vector<bool> is not "bit"-thread-safe, meaning that concurrent writes, even to different positions, do not guarantee the absence of data races (a nice discussion around the standardized "vector" vector<bool> is to be found here).

• It would be great, but no: vector<std::atomic_bool> does not involve low-level coalescing.

• Even using std::bitset is not bit-thread-safe (here).

Given all of that, here is my question: how would you implement a coalesced vector<bool> such that concurrent writes to different position/bits are thread-safe?

Answer 1

You can use general concurrency patterns with locks. Do take into consideration that the space saving are probably gained at the cost of runtime performance.

Example:

std::vector<bool> b(size);
std::mutex m;

//modify:
{
    std::lock_guard lock(m);
    b[0] = true;
}

// read
{
    std::lock_guard lock(m);
    std::cout << b[0];
}

You can use std::shared_mutex if you want shared read locking.