How to check if the <bool> vector is actually a bit vector, not a byte?

Question

I need to keep a dynamic array of bits.
The C ++ link page for the <bool> vector has the following information:

The storage is not necessarily an array of bool values, but the library implementation can optimize the storage so that each value is stored in one bit.

How to make sure that my program that uses vector<bool> actually stores bits in a vector instead of booleans (bytes)?

Answer 1

Do not try to do this. Use boost::dynamic_bitset instead, which clearly states what you really want. The optimization of vector<bool> actually creates many opportunities for errors, for example, when using iterators (since it usually returns a proxy object).

Answer 2

Well, you can always look at the header files that come with your compiler. Because STL containers are almost exclusively template classes, most, if not all parts of the implementation will be visible in the headers.

Perhaps searching for the vector object in the debugger can also be useful.

Note. You should also know that vector<bool> meanwhile, is frowning with the C ++ community, and that this optimization is for size, not speed:

https://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=98

Answer 3

There really is nothing to check here. The specialization of vector<bool> for storing bits instead of large objects is required by the standard. §23.2.5: "To optimize the distribution of space, specialization of the vector for bool elements is provided:".

I suppose, from a certain point of view, that you quoted, at least, is correct. Since virtually no one certifies compiler compliance and, in fact, there is no compiler that even tries to fulfill all compliance requirements, the compiler could also ignore this requirement.

I don’t know of any compiler that does this, though, and if someone did, I would suggest that this would probably be well known. From time to time, there were rather heated discussions about eliminating the vector<bool> specialization, so if someone had real examples of how much better (or worse) this created something, I suspect that we heard about it.

Edit: in C ++ 11, the requirements for std::vector<bool> were moved to §23.3.7. More importantly, the wording has been changed to indicate that a packaged view in which each bool is stored as one bit instead of the adjacent distribution of bool values ​​is now only a recommendation.

IMO at least, it doesn't really matter. As far as I know, all real implementations still use the packaged view, so even if the packaged storage is no longer theoretically guaranteed, it’s all the same in practice.

Answer 4

This program projects it.

 #include <vector> #include <iostream> template <typename T> void showSize() { std::vector<T> myvec; size_t capacity = myvec.capacity(); std::cout << "capacity: " << myvec.capacity() << std::endl; std::cout << "size: " << myvec.size() << std::endl; while (myvec.capacity() < 1024) { while (myvec.capacity() == capacity) { myvec.push_back(T()); } capacity = myvec.capacity(); std::cout << "capacity: " << myvec.capacity() << std::endl; std::cout << "size: " << myvec.size() << std::endl; } } int main(int, char**) { std::cout << std::endl << std::endl; std::cout << "*********************" << std::endl << std::endl; std::cout << "Booleans: " << std::endl << std::endl; showSize<bool>(); std::cout << std::endl << std::endl; std::cout << "*********************" << std::endl << std::endl; std::cout << "Chars: " << std::endl << std::endl; showSize<char>(); } 

exit:

 ********************* Booleans: capacity: 0 size: 0 capacity: 64 size: 1 capacity: 128 size: 65 capacity: 256 size: 129 capacity: 512 size: 257 capacity: 1024 size: 513 ********************* Chars: capacity: 0 size: 0 capacity: 1 size: 1 capacity: 2 size: 2 capacity: 4 size: 3 capacity: 8 size: 5 capacity: 16 size: 9 capacity: 32 size: 17 capacity: 64 size: 33 capacity: 128 size: 65 capacity: 256 size: 129 capacity: 512 size: 257 capacity: 1024 size: 513 

So the key is that the capacity for bools increases by 64 positions at a time (the size of int or my machine). This means that it simply reserves only 8 bytes at a time.

Answer 5

At compile time, you can verify this by checking the return type of the non-envelope version of vector<bool>::operator[] : an implementation that saves its values ​​as bits should return the proxy reference class, not bool& .

Answer 6

Create a huge vector<bool> and look at the memory usage in the program.

Or just check the source code - you can look into the vector header.