No class template specialization for array of bool?

Question

According to https://en.cppreference.com/, std::vector<bool> has a class template specialization, while std::array<bool, N> does not. Which are the reasons why it is not provided?

Lawgiver

Because this is already provided by std::bitset. – Unsocial

Answer 1

When std::vector was introduced, a specialization for bool was considered a good idea. Basically, at that time, the average computer had 4 MB of memory, so saving computer memory was quite important. Nowadays we just say "memory is cheap" (quote from Uncle Bob).

Later it turned out that this specialization creates more problems than it is worth.

The issue is that the address to one of the elements of such a vector is a complex object (it has to store information on which bit holds which value) compared to regular old-fashioned C-array bool a[].

Since compatibility must be retained, this specialization can't be dropped, but based on that lesson, the same approach was not applied to std::array.

Another reason is that std::array is supposed to be a C-array wrapper, so it must be as similar to bool a[N] as possible, and must produce the same machine code when used.

And the last thing, as Cody Gray points out in a comment under question, std::bitset is a constant size array of bits, so such functionality is already available (and can be used if needed).

Holinshed

Excellent answer, +1. However, please don’t use code formatting for non-code text: it can interfere with alternative browsing technology, e.g. screen readers for the blind, and so make the site less accessible. – Gateshead

Answer 2

This is a question about history of evolution of C++. In hindsight a possible explanation is:

std::vector<bool> was a mistake. It is a major annoyance that a std::vector<bool> is very different from std::vector<T>. Generic code that works with vectors often needs a special case for std::vector<bool>. And users often have to apply weird workarounds like using a std::vector<char> in place of std::vector<bool>. Now we cannot go back without breaking lots of existing code. With what we know now, maybe std::vector<bool> would never have made it into C++.

std::array was added only in C++11. There was no reason to make the same mistake again.

Trinee

Answer 3

The initial motivation to specialize std::vector for bool was to optimize memory usage.

However this was a bad idea as this specialization behaves differently than usual std::vector (see example below).

This error was not reproduced later with C++11's std::array

#include <array>
#include <vector>

int main()
{
  std::vector<int> i_v(4);
  int i_a = *&i_v[3]; // ok

  std::vector<bool> v(4);
  bool a = *&v[3]; // Compile-time error

  std::array<bool,4> w;
  bool b = *&w[3]; // ok
}

Meningitis

Answer 4

The std::vector<bool> specialization was introduced as early as 1994, as per lib.vector.bool of WG21/N0545⁽¹⁾ [emphasis mine]:

23.1.6 Class vector<bool> [lib.vector.bool]

To optimize space allocation, a specialization for bool is provided: [...]

with a motivation to optimize for space allocation, a resource that was sparse back then.

In retrospect, this turned out to be quite a bad idea, and the original motivation was made moot with the rapid growth of available space in computer hardware.

std::array, on the other hand, was introduced much later, in C++11, alongside e.g. auto type deduction, a mechanism which highlighted yet another problem with the std::vector<bool> specialization. Naturally the library spec writers did not repeat the same mistake of std::vector<bool> when designing std::array.

E.g., the following snippet

#include <type_traits>
#include <vector>

int main() {
    std::vector<bool> v{false, false, true, true};
    auto bool_value = v[1];
    static_assert(std::is_same_v<decltype(bool_value), bool>, "");  // Error!
}   

fails with the error message that bool_value is not of type bool, but of the cryptic type (implementation-defined)

error: static_assert failed due to requirement
'std::is_same_v<
    std::__1::__bit_reference<
        std::__1::vector<bool, std::__1::allocator<bool>>, true>, 
    bool>' ""

---

_{(1) Working Paper for Draft Proposed International Standard for Information Systems-- Programming Language C++.}

Nevlin