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?

0

1 Answer 1

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.

5
  • 1
    Question: could/would the recent draft proposal on proxy iterators by @EricNiebler somehow legitimize the libc++ extensions and put vector<bool> on a more first-class footing? Aug 13, 2015 at 6:07
  • Remark: I'd prefer to have a vector_bool<Alloc> and an array_bool<N> to represent packed versions (including random-access proxy iterators iterating all bits) of vector<bool, Alloc> and array<bool, N>. However, bitset<N> (and it's cousin boost::dynamic_bitset<Alloc>) represent a different abstraction: namely packed versions of std::set<int>. So I'd like to have, say, bit_array<N> and bit_vector<Alloc> 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? Aug 13, 2015 at 6:14
  • 5
    My draft proposal on proxy iterators would make vector<bool> a std-conforming random-access container. It wouldn't make vector<bool> a good idea. :-) I agree with Howard. It should have been called something else. Aug 13, 2015 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, 2015 at 9: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. Aug 14, 2015 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.