Why vector::reference doesn't return reference to bool?

Question

#include <vector>

struct A
{
    void foo(){}
};

template< typename T >
void callIfToggled( bool v1, bool &v2, T & t )
{
    if ( v1 != v2 )
    {
        v2 = v1;
        t.foo();
    }
}

int main()
{
    std::vector< bool > v= { false, true, false };

    const bool f = false;
    A a;

    callIfToggled( f, v[0], a );
    callIfToggled( f, v[1], a );
    callIfToggled( f, v[2], a );
}

The compilation of the example above produces next error :

dk2.cpp: In function 'int main()':
dk2.cpp:29:28: error: no matching function for call to 'callIfToggled(const bool&, std::vector<bool>::reference, A&)'
dk2.cpp:29:28: note: candidate is:
dk2.cpp:13:6: note: template<class T> void callIfToggled(bool, bool&, T&)

I compiled using g++ (version 4.6.1) like this :

g++ -O3 -std=c++0x -Wall -Wextra -pedantic dk2.cpp

The question is why this happens? Is vector<bool>::reference not bool&? Or is it a compiler's bug?
Or, am I trying something stupid? :)

Unfortunately, despite its name, `std::vector` is not a `vector` of `bool`. — CB Bailey, Dec 06 '11 at 11:56
As a workaround, you could use `std::unique_ptr(new bool[3])`... — Kerrek SB, Dec 06 '11 at 12:17
Herb Sutter's [When Is a Container Not a Container?](http://www.gotw.ca/publications/mill09.htm) is just about this problem. — legends2k, Aug 16 '13 at 10:54
Howard Hinnant's article [On vector](http://isocpp.org/blog/2012/11/on-vectorbool) says that it's a good optimization only the name should've been changed to not denote the greater meaning of a standard container. — legends2k, Aug 16 '13 at 11:24

score 71 · Accepted Answer · edited Mar 21 '17 at 01:35

71

Vector is specialized for bool.

It is considered a mistake of the std. Use vector<char> instead:

template<typename t>
struct foo {
  using type = t;
};
template<>
struct foo<bool> {
  using type = char;
};

template<typename t, typename... p>
using fixed_vector = std::vector<typename foo<t>::type, p...>;

Occasionally you may need references to a bool contained inside the vector. Unfortunately, using vector<char> can only give you references to chars. If you really need bool&, check out the Boost Containers library. It has an unspecialized version of vector<bool>.

edited Mar 21 '17 at 01:35

Nubok

3,502
7
27
47

answered Dec 06 '11 at 11:53

Pubby

51,882
13
139
180

3

Nice workaround, and nice demo of the new `using` syntax for aliasing. – Matthieu M. Dec 06 '11 at 12:50
@Nawaz I swear to God that pun was intended. – Apr 04 '13 at 16:05

score 55 · Answer 2 · edited Jan 30 '13 at 12:35

55

Your expectations are normal, but the problem is that std::vector<bool> has been a kind of experiment by the C++ commitee. It is actually a template specialization that stores the bool values tightly packed in memory: one bit per value.

And since you cannot have a reference to a bit, there's your problem.

edited Jan 30 '13 at 12:35

David G

94,763
41
167
253

answered Dec 06 '11 at 11:54

rodrigo

94,151
12
143
190

8

+1. std::vector only supports a subset of the functionality provided by std::vector. It's ugly since you have to replace bool with a different type (char) to get a working vector. – josefx Dec 06 '11 at 13:25
2

An experiment most (if not all) committee members regretted! – curiousguy Jun 12 '16 at 16:04

Potatoswatter · Answer 3 · 2012-11-09T01:38:17.077

std::vector< bool > packs its contents so each Boolean value is stored in one bit, eight bits to a byte. This is memory-efficient but computationally intensive, since the processor must perform arithmetic to access the requested bit. And it doesn't work with bool reference or pointer semantics, since bits within a byte do not have addresses in the C++ object model.

You can still declare a variable of type std::vector<bool>::reference and use it as if it were bool&. This allows generic algorithms to be compatible.

std::vector< bool > bitvec( 22 );
std::vector< bool >::reference third = bitvec[ 2 ];
third = true; // assign value to referenced bit

In C++11, you can work around this using auto and the && specifier which automatically selects an lvalue reference bound to the vector element or an rvalue reference bound to a temporary.

std::vector< bool > bitvec( 22 );
auto &&third = bitvec[ 2 ]; // obtain a std::vector< bool >::reference
third = true; // assign value to referenced bit

Good answer, especially the mention of `&&`, which is crucial to generic code to let proxy types/iterators ever be useful. Of course, it works equally well in loops: `for (auto &&it: bizarreContainer)` — underscore_d, Jul 18 '16 at 10:00

score 15 · Answer 4 · edited Dec 06 '11 at 15:46

15

std::vector<bool> is a non conforming container. To optimize space, it packs bools and cannot provide reference.

Use boost::dynamic_bitset instead.

edited Dec 06 '11 at 15:46

Jon Purdy

53,300
8
96
166

answered Dec 06 '11 at 11:53

reder

1,098
7
9

To get a kind of reference you need to use operator [] (result is dynamic_bitset::reference). There are no iterator though. – reder Dec 06 '11 at 12:00
3

-1 for not mentioning how `dynamic_bitset` is different or better. Of course it can't return a `bool &` either. – Potatoswatter Jul 16 '13 at 11:41

jrok · Answer 5 · 2011-12-06T12:42:51.067

5

Just my 2 cents:

std::vector<bool>::reference is a typedef for struct _Bit_reference which is defined as

typedef unsigned long _Bit_type;

struct _Bit_reference
  {
    _Bit_type * _M_p;
    _Bit_type _M_mask;

    // constructors, operators, etc...

    operator bool() const
    { return !!(*_M_p & _M_mask); }
  };

Changing the function like this, it works (well, compiles at least, haven't tested):

template< typename T >
void callIfToggled( bool v1, std::vector<bool>::reference v2, T & t )
{
    bool b = v2;  
    if ( v1 != b )
    {
        v2 = v1;
        t.foo();
    }
}

EDIT: I changed the condition from (v1 != v2), which wasn't a good idea, to (v1 != b).

edited Dec 06 '11 at 12:42

answered Dec 06 '11 at 12:15

jrok

54,456
9
109
141

1

It's not an extension, it's just how GCC implements the vector specialization. I don't know what standard says about this. You can see it for yourself: std_bvector.h in lib/gcc/mingw32/4.6.1/include/c++/bits. (Your directory tree might be different, but probably similar) – jrok Dec 06 '11 at 12:32
Sure, it works, for this one specific case - further illustrating why `vector` is an awful misnomer - as it becomes incredibly difficult, tedious, or impossible to use in generic code situations that work for other, _actual_ containers. Still, I think a usable workaround here would be to use `template void callIfToggled(B &&v1, B &&v2, T &&t)` and rely on the conversion operator from `v2` - which I guess is another reason to be thankful for forwarding references. Doesn't excuse the wrong choice of name, though! – underscore_d Jul 18 '16 at 10:10

score 1 · Answer 6 · edited Jun 26 '15 at 08:22

1

Make a structure with a bool in it, and make the vector<> using that struct type.

Try:

vector<struct sb> where sb is struct {boolean b];

then you can say

push_back({true})

do

typedef struct sbool {bool b;} boolstruct; and then vector<boolstruct> bs;

edited Jun 26 '15 at 08:22

Steve Lillis

3,263
5
22
41

answered Jun 25 '15 at 20:48

Todd

97
1
6

You don't need `struct` or `typedef` in C++ – Yashas Apr 01 '18 at 17:51

Why vector::reference doesn't return reference to bool?

6 Answers6

Linked

Related