10

In the documentation, I can see that std::vector<bool> may be optimized for space-efficiency by making every boolean occupy one single bit. From the documentation:

The manner in which std::vector is made space efficient (as well as whether it is optimized at all) is implementation defined.

Does this mean that it depends on the compiler's implementation? If it does, where can I check if my compiler supports it? Why wouldn't they want it supported? It seems like a really simple and efficient implementation.

If not, what does it mean and what does it imply if I want this optimization to take place?

I'm using TDM GCC toolset.

Improve this question
5
  • 1
    Yes, it means that the implementation of std::vector<bool> is largely up to the compiler. It might not be optimized at all, or it might be optimized in an implementation-specific way. Generally, you find this out by consulting the documentation for your compiler. With GCC and other open-source toolchains, I suppose you could also consult the source code. But that not only takes more work, it may not be a very good idea, since source code documents only implementation, not contract. Commented Jul 11, 2016 at 5:11
  • 1
    An easy way to check if such an optimization is provided is to check if std::vector<bool>::reference_type is bool & or something else. In the latter case, you have a proxy type, which should be allowed just for the "optimized" implementation. Commented Jul 11, 2016 at 5:48
  • 1
    @MatteoItalia std::vector<bool>::reference is required to be a proxy even if the implementation doesn't actually pack the bits. Commented Jul 11, 2016 at 5:57
  • The standardised specialisation of std::vector<bool> is widely considered to be an error in hindsight by the community. If you are looking for a standardised set of bits then I think it would be wise to consider std::bitset Commented Jul 11, 2016 at 7:03
  • 1
    A related question is stackoverflow.com/q/14326754/3235496 Commented Jul 11, 2016 at 7:49

4 Answers 4

Reset to default
3

Implementation defined means it depends on what constitutes the parameters of the abstract machine. (I.E., the algorithms which define your host operating system, their implementation specification, and system calls). An informative Q&A on what "implementation defined” means is here.

More than likely, if you have a modern machine with a modern compiler/IDE, it supports implementation definition.

If a compiler doesn't support it, it's not likely because they don't "want" it, but because either it is a very old compiler, or a very resource limited machine.

It boils down to it's machine dependent; so different operating systems will handle accomplishing it it their own way. (i.e., 32-bit vs 64-bit, etc.) It doesn't effect the portability, unless working with an (very much) older compiler. You can check the compiler version's specifications if it's a concern, which is easily found online by searching for your compiler and its version.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

The formal language definition doesn't want to exclude reasonable implementations, so they always have to be a bit careful.

For instance, a typical debug build is still Standards-conforming, but I could very well see a vector<bool> not being compressed in debug mode.

Now this is not unspecified but implementation defined. That means the fact whether it's compressed should be in the compilers documentation somewhere, but the Standard doesn't describe how the documentation should be organized.

If your compiler doesn't support it as you'd like, you can just use another library (Boost being the obvious candidate). vector<bool> typically isn't a class that depends on deep compiler magic, so alternatives are easy to write.

Improve this answer

Comments

0

It's implementation-dependent, and not portable. It seems have some design flaws, and you should avoid using vector<bool>. You can get more details from Meyers' "Effective STL, item 18".

If you really DO care about space-efficiency, you can use std::bitset instead.

Improve this answer

2 Comments

Sadly I can't use std::bitset because I need dynamic initialization.
FWIW, Boost has a dynamic_bitset, but sometimes Boost might be an overkill. If you know how to use it, std::vector<bool> isn't that bad, after all, as some point out.
0

To quote cppreference.com https://en.cppreference.com/w/cpp/container/vector_bool.html

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

The manner in which std::vector<bool> is made space efficient (as well as whether it is optimized at all) is implementation defined. One potential optimization involves coalescing vector elements such that each element occupies a single bit instead of sizeof(bool) bytes.

If this implementation is provided, then when you access an element, a reference is not provided as would be the case for other vector types. Instead, it provides the value in an object created and returned by value. This object acts a bit like a reference, allowing you to access or modify the bool you requested, but it is not a reference.

Because it is not a reference (formally, because it is not an l-value), you cannot apply the address operator to get a non-const pointer. This means the following code will give a compiler error.

 std::vector<bool> vectorBool(16); auto* ptr0 = &vectorBool[0]; //fails to compile auto* ptr1 = &(*vectorBool.begin()); //also fails to compile and is general to other conainers

You can use this to test at compile time whether your compiler is performing the operation. If you want something to do this check at runtime as well, then you can make use of concepts with something like the following

 #include<vector> template<typename T> concept unoptimisedContainer = requires(T t, T::value_type* ptr) { ptr = &(*t.begin()); }; template<class T> constexpr bool isOptimisedContainer() requires (unoptimisedContainer<T>) { return false; } template<class T> constexpr bool isOptimisedContainer() requires (!unoptimisedContainer<T>) { return true; } constexpr bool hasBoolOptimisedVector() { return isOptimisedContainer<std::vector<bool>>(); } void testJustGrid() { constexpr bool optimisedBool = hasBoolOptimisedVector(); //should be true if bool optimisation is used, false otherwise constexpr bool optimisedInt = isOptimisedContainer<std::vector<int>>(); //should always be false as there's no optimised std::vector<int> }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.