20

The specialisation of std::vector<bool>, as specified in C++11 23.3.7/1, doesn't declare a data() member (e.g. mentioned here and here).

The question is: Why does a std::vector<bool> have no .data()? This is the very same question as why is a vector of bools not stored contiguously in memory. What are the benefits in not doing so?

Why can a pointer to an array of bools not be returned?

S.S. Anne
  • 15,171
  • 8
  • 38
  • 76
schorsch312
  • 5,553
  • 5
  • 28
  • 57
  • 2
    `vector` allow to have space optimization by packing several bool in one byte. `data()` would remove that benefit. – Jarod42 Sep 08 '17 at 11:41
  • 3
    The benefit is that you use 8 times less memory. The downside is that you mess with people's expectations. It has more or less been concluded that the downside outweighs the benefit. – nwp Sep 08 '17 at 11:41
  • 5
    `std::vector` is a bit like inviting your mother in law to live with you. It might seem like a good idea at the time, but you'll eventually regret the whole idea. Luckily I can only credit myself with one of these transgressions. – Bathsheba Sep 08 '17 at 11:48
  • 7
    @Bathsheba you designed and implemented std::vector ? You should be ashamed, and I'm reporting you to your mother in law. – Martin James Sep 08 '17 at 12:37

1 Answers1

33

Why does a std::vector have no .data()?

Because std::vector<bool> stores multiple values in 1 byte.

Think about it like a compressed storage system, where every boolean value needs 1 bit. So, instead of having one element per memory block (one element per array cell), the memory layout may look like this:

enter image description here

Assuming that you want to index a block to get a value, how would you use operator []? It can't return bool& (since it will return one byte, which stores more than one bools), thus you couldn't assign a bool* to it. In other words bool *bool_ptr =&v[0]; is not valid code, and would result in a compilation error.

Moreover, a correct implementation might not have that specialization and don't do the memory optimization (compression). So data() would have to copy to the expected return type depending of implementation (or standard should force optimization instead of just allowing it).

Why can a pointer to an array of bools not be returned?

Because std::vector<bool> is not stored as an array of bools, thus no pointer can be returned in a straightforward way. It could do that by copying the data to an array and return that array, but it's a design choice not to do that (if they did, I would think that this works as the data() for all containers, which would be misleading).

What are the benefits in not doing so?

Memory optimization.

Usually 8 times less memory usage, since it stores multiple bits in a single byte. To be exact, CHAR_BIT times less.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • 1
    BTW, correct implementation might don't have that specialization and don't do the memory optimization. so `data()` would have to copy to the expected return type depending of implementation. (or standard should force optimization instead of just allowing it). – Jarod42 Sep 08 '17 at 11:55
  • I'm ok with that.BTW, *"layout looks like this:"* -> **may** looks like. as it is implementation specific (in particular "endianess") – Jarod42 Sep 08 '17 at 12:59
  • @Bathsheba: I don't think the Standard guarantees maximum packing. It would be allowed to pack 8 bits per byte, regardless of CHAR_BIT. – MSalters Sep 08 '17 at 13:10
  • IMO, getting rid of bool in your abstract and converting true|false type to another is the most logical course of action if you use vectors with templates. otherwise the code quality becomes worse. Bool it is. – Kalen Mar 05 '22 at 22:28