Why is libc++'s vector<bool>::const_reference not bool?

Question

Section 23.3.7 Class vector<bool> [vector.bool], paragraph 1 states:

template <class Allocator> class vector<bool, Allocator> {
public:
    // types:
    typedef bool              const_reference;
    ...

However this program fails to compile when using libc++:

#include <vector>
#include <type_traits>

int
main()
{
    static_assert(std::is_same<std::vector<bool>::const_reference, bool>{}, "?");
}

Furthermore I note that the C++ standard has been consistent in this specification all the way back to C++98. And I further note that libc++ has consistently not followed this specification since the first introduction of libc++.

What is the motivation for this non-conformance?

Answer 1

The motivation for this extension, which is detectable by a conforming program, and thus non-conforming, is to make vector<bool> behave more like vector<char> with respect to references (const and otherwise).

Introduction

Since 1998, vector<bool> has been derided as "not quite a container." LWG 96, one of the very first LWG issues, launched the debate. Today, 17 years later, vector<bool> remains largely unchanged.

This paper goes into some specific examples on how the behavior of vector<bool> differs from every other instantiation of vector, thus hurting generic code. However the same paper discusses at length the very nice performance properties vector<bool> can have if properly implemented.

Summary: vector<bool> isn't a bad container. It is actually quite useful. It just has a bad name.

Back to const_reference

As introduced above, and detailed here, what is bad about vector<bool> is that it behaves differently in generic code than other vector instantiations. Here is a concrete example:

#include <cassert>
#include <vector>

template <class T>
void
test(std::vector<T>& v)
{
    using const_ref = typename std::vector<T>::const_reference;
    const std::vector<T>& cv = v;
    const_ref cr = cv[0];
    assert(cr == cv[0]);
    v[0] = 1;
    assert(true == cv[0]);
    assert(cr == cv[0]);  // Fires!
}

int
main()
{
    std::vector<char> vc(1);
    test(vc);
    std::vector<bool> vb(1);
    test(vb);
}

The standard specification says that the assert marked // Fires! will trigger, but only when test is run with a vector<bool>. When run with a vector<char> (or any vector besides bool when an appropriate non-default T is assigned), the test passes.

The libc++ implementation sought to minimize the negative effects of having vector<bool> behave differently in generic code. One thing it did to achieve this is to make vector<T>::const_reference a proxy-reference, just like the specified vector<T>::reference, except that you can't assign through it. That is, on libc++, vector<T>::const_reference is essentially a pointer to the bit inside the vector, instead of a copy of that bit.

On libc++ the above test passes for both vector<char> and vector<bool>.

At what cost?

The downside is that this extension is detectible, as shown in the question. However, very few programs actually care about the exact type of this alias, and more programs care about the behavior.

What is the motivation for this non-conformance?

To give the libc++ client better behavior in generic code, and perhaps after sufficient field testing, propose this extension to a future C++ standard for the betterment of the entire C++ industry.

Such a proposal might come in the form of a new container (e.g. bit_vector) that has much the same API as today's vector<bool>, but with a few upgrades such as the const_reference discussed here. Followed by deprecation (and eventual removal) of the vector<bool> specialization. bitset could also use a little upgrading in this department, e.g. add const_reference, and a set of iterators.

That is, in hindsight bitset is to vector<bool> (which should be renamed to bit_vector -- or whatever), as array is to vector. And the analogy ought to hold true whether or not we are talking about bool as the value_type of vector and array.

There are multiple examples of C++11 and C++14 features that started out as extensions in libc++. This is how standards evolve. Actual demonstrated positive field experience carries strong influence. The standards folk are a conservative bunch when it comes to changing existing specifications (as they should be). Guessing, even when you are sure you are guessing correctly, is a risky strategy for evolving an internationally recognized standard.