Is bitset guaranteed contiguity?

Question

Swift and easy question: is std::bitset guaranteed to be contiguous in memory?

I know it abides by CopyConstructible and CopyAssignable concepts, but is it also a ContiguousContainer (or something like that) like std::vector?

Apart from padding, I'd like to make bitwise operations on structures like this:

struct tmp
{
    std::bitset<32> b;
    unsigned int    c;
};

So the contiguity of b is quite important. Of course, this leads to knowing if std::bitset is a standard layout class, so that every bitwise operation works.

Vostok

Do you mean union { std::bitset<32> b; unsigned int c; };? – Wolfort

No, it is not. Why asking when you already know the answer? Hint - only something which is specified in standard is guaranteed. – Neogaea

No, struct. I want two fields in memory, a bitset and an integer. – Vostok

@Neogaea I know about those two guarantees, but I want to know if there is any guarantee that memory layout would be simple. – Vostok

Do you see this guarantee anywhere? I do not. Hence, no guarantee. VTC the question as unclear. – Neogaea

I don't think it would matter. For the bit wise operations you'll need to write your own overload and in turn use the overloads for int and the bit set. It will all work independent of what the underlying layout is. – Grazing

Could you elaborate on why you need this? – Baggage

Without going into details, which I am not allowed to disclose, I want to apply SSE functions to speed up some computations. One field is a bit array, another is an (unsigned) integer. – Vostok

What SSE instruction do you have in mind? – Baggage

As of now, I cannot predict. I will for sure use need masks, logical and arithmetic ops on integers. I think I won't need floats. – Vostok

Answer 1

There is no such guarantee. std::bitset has, in my experience, an awkward interface, so I don't see much of the point of using it in undefined ways either.

Just write your own bitset like class with the layout and storage guarantees you need.

Personally, I'd enjoy it. And I don't find the bitset interface (especially construction/serialization/deserialization) particularly good, so I wouldn't even feel guilty. (I guess writing an efficient count, any, all and none is a bit of work, but everything else is trivial. And if you are writing assembly instructions/using SSE intrinstics, you might be able to match/exceed your compiler's implementation anyhow)

Slowmoving

Answer 2

There is no requirement in the standard for std::bitset<> to have any particular layout or bit order.

However:

• The fact that the number of bits required is specified as the template argument does strongly imply that bits storage units are an array member of the class (no heap allocation is involved).

• As well as directly mapping the low bits of bit index to storage unit bit index, and the higher bits to storage unit index. So that it takes one binary shift native CPU instruction to extract storage unit index from bit index and one binary and native CPU instruction to extract storage unit bit index from that same bit index.

Such a storage layout and index mapping are as simple and as efficient as it ever gets, aligned with C++ motto of standard components being as effiecient as if written by hand. Anything else than that would require a formal written justification.

---

Nevertheless, I do not suggest or endorse accessing the internal representation of std::bitset<>.

In the past, some C standard fundamentalists reversed the order of memcpy in libc for no good reason, rather for the sole purpose of breaking perfectly working applications which mistakenly used memcpy for overlapping memory regions instead of memmove.

Baggage

Even though the memory may be allocated in one block, there is no good way to get a pointer to the first bit. The OP intends to directly apply bitwise operations to such an object, so he implicitly assumes that the object contains only those bits (or does not care if the object gets corrupted). – Salcido

@Salcido True and I do not suggest or endorse accessing the internal representation of std::bitset. – Baggage

Just making sure the OP doesn't try to do it :). – Salcido

Yes, I don't care about corruption. But if I cannot be sure that, for instance, a bitset is essentially an array of chars (or similar) then I have no choice other than write my own container. – Vostok

@Vostok "I don't care about corruption" -- then you don't understand. – Slowmoving

The noexcept prevents it from allocating memory in practice. But the bytes might not be all that there is in the bitset, and they might not be ordered the way you want them to be (imagine a system where there are instructions that make accessing them in another order more efficient). – Slowmoving

@Yakk I am investigating some speedups I could get, errors are not important now. They will be later. – Vostok