What Happens When You Call Data() on a Std::Vector<Bool>

What happens when you call data() on a std::vector bool ?

This page documenting the class explicitely indicates that the specialization does not provide this method.

The specialization has the same member functions as the unspecialized vector, except data, emplace, and emplace_back, that are not present in this specialization.

This other page as well as §23.3.7 of the C++ specifications do confirm it.

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

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:

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.

std::vector bool - no data() function in specialization?

std::vector<bool> is specialized for space-efficiency. It doesn't provide data() function.

You cannot address its elements because each of them is of 1 bit size, and there is nothing on machine like pointer to single bit.

The manner in which std::vector 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.

You can access its elements using

std::vector<bool>::reference

This embedded class is the type returned by members of non-const
vector when directly accessing its elements. It accesses
individual bits with an interface that emulates a reference to a bool.

---

Normally data() returns a T* which here would be bool* but IS NOT because the reference and pointer types are not really references and pointers to bool. For example on my implementation bit type is a typedef for unsigned long

typedef unsigned long _Bit_type;

and this is what is used by a reference to bits called struct _Bit_reference. This struct is used by struct _Bit_iterator which is an iterator to elements. You can see here what it means to dereference this iterator and get element of std::vector<bool> on this implementation:

//  typedef unsigned long _Bit_type;
// struct _Bit_reference
// {
//   _Bit_type * _M_p;
// ...
// };
//  typedef _Bit_reference  reference;

reference
    _Bit_iterator::operator*() const
    { return reference(_M_p, 1UL << _M_offset); }

What does libstdc++'s std::vector bool ::data do?

My /usr/include/c++/4.8/bits/stl_bvector.h has:

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 464. Suggestion for new member functions in standard containers.
// N.B. DR 464 says nothing about vector<bool> but we need something
// here due to the way we are implementing DR 464 in the debug-mode
// vector class.
void
data() _GLIBCXX_NOEXCEPT { }

In /usr/include/c++/4.8/debug/vector I see the declaration:

using _Base::data;

So that seems to be the reason: the debug version of std::vector<bool> wouldn't compile unless std::vector<bool>::data existed.

vector bool raises an error on const data() method

vector<bool> is a specialization of a good old vector<T> and it may be implemented differently from ordinary vector (e.g. some space-saving optimizations may be employed). Side-effect of such design is that it does not always behave as ordinary vector (many consider vector<bool> to be broken because of that).

For example, the reference at http://en.cppreference.com/w/cpp/container/vector_bool does not mention vector<bool>::data() at all. Therefore - you should not use it when using vector with type bool. The fact that you don't get an error similar to method not found is - in your case - just a matter of how vector<bool> is implemented by your compiler.

std vector.data return void

vector<bool> is not a proper vector. As weird as that sounds, that's the way it is. It can't give you a pointer to its internal bool array, because it doesn't have one, since it stores the values packed into single bits.

Send a c++ std::vector bool via mpi

std::vector<bool> specialization does not have the data() member function. The underlying storage scheme is not specified by the standard:

There is no requirement that the data be stored as a contiguous allocation of bool values. A space-optimized representation of bits is recommended instead.

The only reasonable option to send std::vector<bool> is to copy it into a vector of char (or some similar type like std::int8_t), and then send that vector. A better option might be to avoid std::vector<bool> in your code from the very beginning.

If std::vector bool was rewritten to use the standard vector implementation, how would that break old software?

Firstly, that would be an ABI break. A major reason why changing anything from the standard library is difficult.

Secondly, anything using flip would break:

#include <vector>

int main() {
  std::vector<bool> vec { true };
  vec[0].flip(); // can't be done with regular bool
}

Thirdly, there would probably be other problems due to overload resolution someone probably relies on.

---

Side note: You can always use boost::container::vector instead, which is not specialized for bool.

Indexing std::vector bool works with true values, but does not work with false values

The line vector<bool> b(true, arr.size()); will create a vector, with 1 element, of value arr.size(). Thus, the loop will get out of bounds.

It's crucial to remember that when we construct a container this way, we say: "How much of what".

In this case: "We need arr.size() elements with value true":

vector<bool> b(arr.size(), true);

For more information, you may want to check the documentation on vector constructors, the third one in particular, "fill constructor".

---

Related Topics