Compacting bools feature of std::vector in C++

Question

Does the std::vector in C++ compact bools? I mean I have read that std::vector can combine 8 booleans into 1 byte. However, when I tried this code in visual studio,

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<bool> array {true, false, false, true, true,false,false,true};
    cout << sizeof(array) << endl;
    cout << sizeof(array[0]) << endl;

    getchar();
    return 0;
}

it printed:

24
16

while in another IDE, such as codeblocks, it printed 20 and 8.

I don't quite get what it does with booleans here.

sizeof does not do what you think it does. Remember that sizeof() is a compile time constant. If you added a thousand bools you should get the same size. — drescherjm, Apr 25 '18 at 03:13

Drew Dormann · Accepted Answer · 2018-04-25T03:45:34.293

15

Does the std::vector in C++ compact bools?

Yes, it is allowed to do so, and typically does.

I don't quite get what it does with booleans here.

You actually don't get what array[0] evaluates to.

It does not evaluate to a bit. It evaluates to a proxy object that correctly handles both conversion to bool and assignment from bool.

the sizeof this proxy does not have much significance. It is not the size of a bit or a bool. It's the size of an object programmed to act on a specific bit.

edited Apr 25 '18 at 03:45

answered Apr 25 '18 at 03:32

Drew Dormann

59,987
13
123
180

How do they make a proxy object that's so small? – Mark Ransom Apr 25 '18 at 03:35
1

@MarkRansom I imagine it to be a pointer, plus a bit offset from that pointer. – Drew Dormann Apr 25 '18 at 03:37
So I wonder if I can check if a vector does compact booleans or not? – W.Joe Apr 25 '18 at 03:47
7

@W.Joe that's a new question, and could be a very interesting one! – Drew Dormann Apr 25 '18 at 03:49
@W.Joe I'll save you the trouble - [it's already been asked](https://stackoverflow.com/a/14331405/16287). It would appear that it was required to be compressed before C++11 and optional in C++11. Which effectively means that no implementation is _not_ compressing it. While not bulletproof, you could always test `sizeof(array[0]) == sizeof(bool)`. – Drew Dormann Apr 25 '18 at 03:56
1

Never mind my question, it was a brain fart - for a moment I thought it was the size in bits, not bytes. – Mark Ransom Apr 25 '18 at 04:02
2

@W.Joe if that condition evaluates to false, that's a sign your vector is indeed likely to compact booleans (so that's not surprising). The idea behing that test is that if `std::vector` doesn't "compress" booleans, `array[0]` is likely to be a `bool&` (as it can merely store, e.g., a dynamically allocated array of booleans and return a reference to the corresponding boolean in memory) making the condition true. Otherwise, `array[0]` must be a proxy object (that are usually bigger than a boolean) so the condition is likely to be false. – Caninonos Apr 25 '18 at 09:26

score 1 · Answer 2 · answered Apr 25 '18 at 10:37

std::vector usually uses dynamic allocation internally by default. If you define your own allocator that tracks actual allocation size, you'll see that the number of bytes allocated for vector<bool> implies values are stored as bits:

#include <vector>
#include <iostream>

template<typename T>
class my_allocator : public std::allocator<T> {
public:
    T * allocate(const size_t count) {
        std::cout << "Allocated " << count << " * " << typeid(T).name() << std::endl;
        std::cout << "Total size: " << count * sizeof(T) << std::endl;
        return std::allocator<T>::allocate(count);
    }

    T * allocate(const size_t count, const void *) {
        return allocate(count);
    }

    template<typename U>
    struct rebind {
        typedef my_allocator<U> other;
    };

    my_allocator() noexcept {};
    my_allocator(const my_allocator<T>&) noexcept = default;

    template<typename Other>
    my_allocator(const my_allocator<Other>&) noexcept {}
};

int main() {
    std::vector<int, my_allocator<int>> v1 { 0 };
    std::vector<bool, my_allocator<bool>> v2 { 0 };

    v1.reserve(100);
    v2.reserve(100);

    return 0;
}

Relevant output:

Allocated 100 * int
Total size: 400
Allocated 4 * unsigned int
Total size: 16

Demo: https://wandbox.org/permlink/WHTD0k3sMvd3E4ag

Compacting bools feature of std::vector in C++

2 Answers2