92

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?

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577

1 Answers1

100

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.

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • 1
    Question: could/would the recent [draft proposal](https://ericniebler.github.io/std/wg21/D0022.html) on proxy iterators by @EricNiebler somehow legitimize the libc++ extensions and put `vector` on a more first-class footing? – TemplateRex Aug 13 '15 at 06:07
  • Remark: I'd prefer to have a `vector_bool` and an `array_bool` to represent packed versions (including random-access proxy iterators iterating all bits) of `vector` and `array`. However, `bitset` (and it's cousin `boost::dynamic_bitset`) represent a different abstraction: namely packed versions of `std::set`. So I'd like to have, say, `bit_array` and `bit_vector` to be the successors to the bitset franchise, with appropriate *bidirectional* iterators (iterating over the 1-bits, rather than over all bits). What are your thoughts on this? – TemplateRex Aug 13 '15 at 06:14
  • 5
    My draft proposal on proxy iterators would make `vector` a std-conforming random-access container. It wouldn't make `vector` a good idea. :-) I agree with Howard. It should have been called something else. – Eric Niebler Aug 13 '15 at 18:57
  • 1
    Why isn't there a way to opt out of libc++ extensions and get strictly conforming behavior? (I'm not even asking for making conformance the default, just a way to disable libc++'s extensions to be able to write portable code). As you know I was bitten by libc++ tuple extensions in the past, and recently bitten by the bitset::const_reference extension. – gnzlbg Aug 14 '15 at 09:33
  • 5
    @gnzlbg: A finite amount of economic and temporal resources were available for the initial development of libc++. Subsequently the implementation was doomed to not make every single user happy. Given available resources, engineering tradeoffs were made in an attempt to maximize the number of happy users, maximize benefit to the overall C++ community. Sorry about your experience. I note that the tuple extensions that you ran afoul of are now in the current C++1z working paper. On that issue, you unknowingly sacrificed so that many could benefit, and those many owe you a debt of gratitude. – Howard Hinnant Aug 14 '15 at 13:31