8

In the documentation, I can see that std::vector<bool> is 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.

Simon
  • 774
  • 4
  • 21
  • 1
    Yes, it means that the implementation of `std::vector` 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. – Cody Gray - on strike Jul 11 '16 at 05:11
  • 1
    An easy way to check if such an optimization is provided is to check if `std::vector::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. – Matteo Italia Jul 11 '16 at 05:48
  • 1
    @MatteoItalia `std::vector::reference` is required to be a proxy even if the implementation doesn't actually pack the bits. – T.C. Jul 11 '16 at 05:57
  • The standardised specialisation of std::vector 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 – Richard Hodges Jul 11 '16 at 07:03
  • 1
    A related question is http://stackoverflow.com/q/14326754/3235496 – manlio Jul 11 '16 at 07:49

3 Answers3

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.

NonCreature0714
  • 5,744
  • 10
  • 30
  • 52
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.

MSalters
  • 173,980
  • 10
  • 155
  • 350
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.

for_stack
  • 21,012
  • 4
  • 35
  • 48
  • Sadly I can't use `std::bitset` because I need dynamic initialization. – Simon Jul 11 '16 at 05:31
  • 5
    FWIW, Boost has a [dynamic_bitset](http://www.boost.org/doc/libs/1_61_0/libs/dynamic_bitset/dynamic_bitset.html), but sometimes Boost might be an overkill. If you know how to use it, `std::vector` isn't that bad, after all, as [some point out](https://isocpp.org/blog/2012/11/on-vectorbool). – legends2k Jul 11 '16 at 05:42