Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says to avoid vector <bool> as it's not an STL container and it doesn't really hold bools.
Scott Meyers的书《有效STL: 50种改进你使用标准模板库的具体方法》的第18条说，要避免vector
The following code:
下面的代码:
vector <bool> v;
bool *pb =&v[0];
will not compile, violating requirement of STL containers.
不会编译，违反STL容器的要求。
Error:
错误:
cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization
vector<T>::operator [] return type is supposed to be T&, but why it's a special case for vector<bool>?
向量
What does vector<bool> really consist of?
向量
The Item further says:
项目进一步说:
deque<bool> v; // is a STL container and it really contains bools
Can this be used as an alternative to vector<bool>?
这可以作为矢量
Can anyone please explain this?
有人能解释一下吗?
6 个解决方案
#1
62
For space-optimization reasons, the C++ standard (as far back as C++98) explicitly calls out vector<bool> as a special standard container where each bool uses only one bit of space rather than one byte as a normal bool would (implementing a kind of "dynamic bitset"). In exchange for this optimization it doesn't offer all the capabilities and interface of a normal standard container.
对于空间优化的原因，c++标准(早于c++ 98)显式地将vector
In this case, since you can't take the address of a bit within a byte, things such as operator[] can't return a bool& but instead return a proxy object that allows to manipulate the particular bit in question. Since this proxy object is not a bool&, you can't assign its address to a bool* like you could with the result of such an operator call on a "normal" container. In turn this means that bool *pb =&v[0]; isn't valid code.
在这种情况下，由于您不能在一个字节内取位的地址，所以诸如运算符[]之类的东西不能返回一个bool&，而是返回一个代理对象，该对象允许对特定的比特进行操作。由于这个代理对象不是一个bool&，您不能将其地址分配给bool*，就像这样一个操作符调用一个“正常”容器的结果一样。这意味着bool *pb =&v[0];不是有效的代码。
On the other hand deque doesn't have any such specialization called out so each bool takes a byte and you can take the address of the value return from operator[].
另一方面，deque没有任何这样的专门化，因此每个bool都需要一个字节，并且您可以从运算符[]中获取值返回的地址。
Finally note that the MS standard library implementation is (arguably) suboptimal in that it uses a small chunk size for deques, which means that using deque as a substitute isn't always the right answer.
最后要注意的是，MS标准库的实现是(可以说)次优的，因为它使用一个小块大小的deques，这意味着使用deque作为替代并不总是正确的答案。
#2
18
vector<bool> contains boolean values in compressed form using only one bit for value (and not 8 how bool[] arrays do). It is not possible to return a reference to a bit in c++, so there is a special helper type, "bit reference", which provides you a interface to some bit in memory and allows you to use standard operators and casts.
vector
#3
16
The problems is that vector<bool> returns a proxy reference object instead of a true reference, so that C++98 style code bool * p = &v[0]; won't compile. However, modern C++11 with auto p = &v[0]; can be made to compile if operator& also returns a proxy pointer object. Howard Hinnant has written a blog post detailing the algorithmic improvements when using such proxy references and pointers.
问题是，vector
Scott Meyers has a long Item 30 in More Effective C++ about proxy classes. You can come a long way to almost mimic the builtin types: for any given type T, a pair of proxies (e.g. reference_proxy<T> and iterator_proxy<T>) can be made mutually consistent in the sense that reference_proxy<T>::operator&() and iterator_proxy<T>::operator*() are each other's inverse.
Scott Meyers在关于代理类的更有效的c++中有一个很长的项目30。您可以很长一段时间来模拟构建类型:对于任何给定类型的T，可以将一对代理(例如reference_proxy
However, at some point one needs to map the proxy objects back to behave like T* or T&. For iterator proxies, one can overload operator->() and access the template T's interface without reimplementing all the functionality. However, for reference proxies, you would need to overload operator.(), and that is not allowed in current C++ (although Sebastian Redl presented such a proposal on BoostCon 2013). You can make a verbose work-around like a .get() member inside the reference proxy, or implement all of T's interface inside the reference (this is what is done for vector<bool>::bit_reference), but this will either lose the builtin syntax or introduce user-defined conversions that do not have builtin semantics for type conversions (you can have at most one user-defined conversion per argument).
但是，在某些时候，需要将代理对象映射回像T*或t&。对于迭代器代理，可以重载操作符->()并访问模板T的接口，而无需重新实现所有功能。但是，对于引用代理，您需要重载操作符。()，这在当前c++中是不允许的(尽管Sebastian Redl在2013年的BoostCon上提出了这样的建议)。你可以做一个详细的工作像一个. get()成员内部引用代理,或实现T的所有接口内部的引用(这就是为向量做< bool >::bit_reference),但这将失去了内装式语法或引入用户定义的转换,没有安装在内部的语义类型转换(您最多只能有一个用户定义的转换每个论点)。
TL;DR: no vector<bool> is not a container because the Standard requires a real reference, but it can be made to behave almost like a container, at least much closer with C++11 (auto) than in C++98.
DR:没有vector
#4
3
This comes from http://www.cplusplus.com/reference/vector/vector-bool/
这来自于http://www.cplusplus.com/reference/vector/vector-bool/
Vector of bool This is a specialized version of vector, which is used for elements of type bool and optimizes for space.
bool矢量是矢量的一个专门版本，用于bool类型的元素，并对空间进行优化。
It behaves like the unspecialized version of vector, with the following changes:
它的行为类似于非专门化的向量版本，其变化如下:
- The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
stored in a single bit.- 存储不一定是bool值的数组，但是库实现可以优化存储，使每个值都存储在一个比特中。
- Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage.
- 元素不是使用分配程序对象构造的，但是它们的值直接设置在内部存储的适当位上。
- Member function flip and a new signature for member swap.
- 成员函数翻转和成员交换的新签名。
- A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
emulates a bool reference. Conversely, member type const_reference is a plain bool.- 一个特殊的成员类型，引用，一个类，它访问容器内部存储中的单个位，并使用一个模拟bool引用的接口。相反，成员类型const_reference是一个普通的bool。
- The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
shall simulate most of their expected behavior.- 容器使用的指针和迭代器类型不一定既不是指针，也不是一致的迭代器，尽管它们应该模拟它们的大多数预期行为。
These changes provide a quirky interface to this specialization and favor memory optimization over processing (which may or may not suit your needs). In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types.
这些更改为这种专门化提供了一个古怪的接口，并支持内存优化而不是处理(这可能或不适合您的需要)。在任何情况下，都不可能直接实例化bool的非专门化向量模板。避免使用不同类型(char、unsigned char)或容器(比如deque)来使用包装器类型或进一步专门化特定的分配器类型的方法。
bitset is a class that provides a similar functionality for fixed-size arrays of bits.
bitset是一个为固定大小的位数组提供类似功能的类。
#5
3
Look at how it is implemented. the STL builds vastly on templates and therefore the headers do contain the code they do.
看看它是如何实现的。STL在模板上进行了大量的构建，因此header包含了它们所做的代码。
for instance look at the stdc++ implementation here.
例如，看看这里的stdc++实现。
also interesting even though not an stl conforming bit vector is the llvm::BitVector from here.
同样有趣的是，即使不是stl一致位向量也是llvm::位向量。
the essence of the llvm::BitVector is a nested class called reference and suitable operator overloading to make the BitVector behaves similar to vector with some limitations. The code below is a simplified interface to show how BitVector hides a class called reference to make the real implementation almost behave like a real array of bool without using 1 byte for each value.
llvm的本质::BitVector是一个被称为引用和合适的操作符重载的嵌套类，使位向量的行为类似于具有某些限制的向量。下面的代码是一个简化的接口，显示了BitVector如何隐藏一个名为reference的类，使实际实现几乎像一个真正的bool数组，而不需要为每个值使用1字节。
class BitVector {
public:
class reference {
reference &operator=(reference t);
reference& operator=(bool t);
operator bool() const;
};
reference operator[](unsigned Idx);
bool operator[](unsigned Idx) const;
};
this code here has the nice properties:
这里的代码有很好的属性:
BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.
This code actually has a flaw, try to run:
这段代码实际上有一个缺陷，试着运行:
std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator
will not work because assert( (&b[5] - &b[3]) == (5 - 3) ); will fail (within llvm::BitVector)
不能工作，因为断言((&b[5] - &b[3]) == (5 - 3));将失败(在llvm::BitVector)
this is the very simple llvm version. std::vector<bool> has also working iterators in it. thus the call for(auto i = b.begin(), e = b.end(); i != e; ++i) will work. and also std::vector<bool>::const_iterator.
这是非常简单的llvm版本。std::vector
However there are still limitations in std::vector<bool> that makes it behave differently in some cases.
然而，std中仍然存在一些限制:在某些情况下，向量
#6
2
Many consider the vector<bool> specialization to be a mistake.
许多人认为向量
In a paper "Deprecating Vestigial Library Parts in C++17"
There is a proposal to Reconsider vector Partial Specialization.
在一篇论文中，“在c++ 17”中，有一项建议重新考虑向量局部专门化。
There has been a long history of the bool partial specialization of std::vector not satisfying the container requirements, and in particular, its iterators not satisfying the requirements of a random access iterator. A previous attempt to deprecate this container was rejected for C++11, N2204.
std的bool部分专门化有很长的历史::向量不满足容器的要求，特别是它的迭代器不能满足随机访问迭代器的要求。之前试图反对此容器的尝试被拒绝为c++ 11, N2204。
One of the reasons for rejection is that it is not clear what it would mean to deprecate a particular specialization of a template. That could be addressed with careful wording. The larger issue is that the (packed) specialization of vector offers an important optimization that clients of the standard library genuinely seek, but would not longer be available. It is unlikely that we would be able to deprecate this part of the standard until a replacement facility is proposed and accepted, such as N2050. Unfortunately, there are no such revised proposals currently being offered to the Library Evolution Working Group.
被拒绝的原因之一是不清楚它将意味着什么来反对模板的特定专门化。这可以用谨慎的措辞加以解决。更大的问题是，向量的(打包)专门化提供了一个重要的优化，这是标准库的客户真正想要的，但是不能再提供了。在提议和接受替代设施(如2050年)之前，我们不太可能反对这部分标准。不幸的是，目前还没有向图书馆进化工作组提出的修订建议。
#1
62
For space-optimization reasons, the C++ standard (as far back as C++98) explicitly calls out vector<bool> as a special standard container where each bool uses only one bit of space rather than one byte as a normal bool would (implementing a kind of "dynamic bitset"). In exchange for this optimization it doesn't offer all the capabilities and interface of a normal standard container.
对于空间优化的原因，c++标准(早于c++ 98)显式地将vector
In this case, since you can't take the address of a bit within a byte, things such as operator[] can't return a bool& but instead return a proxy object that allows to manipulate the particular bit in question. Since this proxy object is not a bool&, you can't assign its address to a bool* like you could with the result of such an operator call on a "normal" container. In turn this means that bool *pb =&v[0]; isn't valid code.
在这种情况下，由于您不能在一个字节内取位的地址，所以诸如运算符[]之类的东西不能返回一个bool&，而是返回一个代理对象，该对象允许对特定的比特进行操作。由于这个代理对象不是一个bool&，您不能将其地址分配给bool*，就像这样一个操作符调用一个“正常”容器的结果一样。这意味着bool *pb =&v[0];不是有效的代码。
On the other hand deque doesn't have any such specialization called out so each bool takes a byte and you can take the address of the value return from operator[].
另一方面，deque没有任何这样的专门化，因此每个bool都需要一个字节，并且您可以从运算符[]中获取值返回的地址。
Finally note that the MS standard library implementation is (arguably) suboptimal in that it uses a small chunk size for deques, which means that using deque as a substitute isn't always the right answer.
最后要注意的是，MS标准库的实现是(可以说)次优的，因为它使用一个小块大小的deques，这意味着使用deque作为替代并不总是正确的答案。
#2
18
vector<bool> contains boolean values in compressed form using only one bit for value (and not 8 how bool[] arrays do). It is not possible to return a reference to a bit in c++, so there is a special helper type, "bit reference", which provides you a interface to some bit in memory and allows you to use standard operators and casts.
vector
#3
16
The problems is that vector<bool> returns a proxy reference object instead of a true reference, so that C++98 style code bool * p = &v[0]; won't compile. However, modern C++11 with auto p = &v[0]; can be made to compile if operator& also returns a proxy pointer object. Howard Hinnant has written a blog post detailing the algorithmic improvements when using such proxy references and pointers.
问题是，vector
Scott Meyers has a long Item 30 in More Effective C++ about proxy classes. You can come a long way to almost mimic the builtin types: for any given type T, a pair of proxies (e.g. reference_proxy<T> and iterator_proxy<T>) can be made mutually consistent in the sense that reference_proxy<T>::operator&() and iterator_proxy<T>::operator*() are each other's inverse.
Scott Meyers在关于代理类的更有效的c++中有一个很长的项目30。您可以很长一段时间来模拟构建类型:对于任何给定类型的T，可以将一对代理(例如reference_proxy
However, at some point one needs to map the proxy objects back to behave like T* or T&. For iterator proxies, one can overload operator->() and access the template T's interface without reimplementing all the functionality. However, for reference proxies, you would need to overload operator.(), and that is not allowed in current C++ (although Sebastian Redl presented such a proposal on BoostCon 2013). You can make a verbose work-around like a .get() member inside the reference proxy, or implement all of T's interface inside the reference (this is what is done for vector<bool>::bit_reference), but this will either lose the builtin syntax or introduce user-defined conversions that do not have builtin semantics for type conversions (you can have at most one user-defined conversion per argument).
但是，在某些时候，需要将代理对象映射回像T*或t&。对于迭代器代理，可以重载操作符->()并访问模板T的接口，而无需重新实现所有功能。但是，对于引用代理，您需要重载操作符。()，这在当前c++中是不允许的(尽管Sebastian Redl在2013年的BoostCon上提出了这样的建议)。你可以做一个详细的工作像一个. get()成员内部引用代理,或实现T的所有接口内部的引用(这就是为向量做< bool >::bit_reference),但这将失去了内装式语法或引入用户定义的转换,没有安装在内部的语义类型转换(您最多只能有一个用户定义的转换每个论点)。
TL;DR: no vector<bool> is not a container because the Standard requires a real reference, but it can be made to behave almost like a container, at least much closer with C++11 (auto) than in C++98.
DR:没有vector
#4
3
This comes from http://www.cplusplus.com/reference/vector/vector-bool/
这来自于http://www.cplusplus.com/reference/vector/vector-bool/
Vector of bool This is a specialized version of vector, which is used for elements of type bool and optimizes for space.
bool矢量是矢量的一个专门版本，用于bool类型的元素，并对空间进行优化。
It behaves like the unspecialized version of vector, with the following changes:
它的行为类似于非专门化的向量版本，其变化如下:
- The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
stored in a single bit.- 存储不一定是bool值的数组，但是库实现可以优化存储，使每个值都存储在一个比特中。
- Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage.
- 元素不是使用分配程序对象构造的，但是它们的值直接设置在内部存储的适当位上。
- Member function flip and a new signature for member swap.
- 成员函数翻转和成员交换的新签名。
- A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
emulates a bool reference. Conversely, member type const_reference is a plain bool.- 一个特殊的成员类型，引用，一个类，它访问容器内部存储中的单个位，并使用一个模拟bool引用的接口。相反，成员类型const_reference是一个普通的bool。
- The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
shall simulate most of their expected behavior.- 容器使用的指针和迭代器类型不一定既不是指针，也不是一致的迭代器，尽管它们应该模拟它们的大多数预期行为。
These changes provide a quirky interface to this specialization and favor memory optimization over processing (which may or may not suit your needs). In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types.
这些更改为这种专门化提供了一个古怪的接口，并支持内存优化而不是处理(这可能或不适合您的需要)。在任何情况下，都不可能直接实例化bool的非专门化向量模板。避免使用不同类型(char、unsigned char)或容器(比如deque)来使用包装器类型或进一步专门化特定的分配器类型的方法。
bitset is a class that provides a similar functionality for fixed-size arrays of bits.
bitset是一个为固定大小的位数组提供类似功能的类。
#5
3
Look at how it is implemented. the STL builds vastly on templates and therefore the headers do contain the code they do.
看看它是如何实现的。STL在模板上进行了大量的构建，因此header包含了它们所做的代码。
for instance look at the stdc++ implementation here.
例如，看看这里的stdc++实现。
also interesting even though not an stl conforming bit vector is the llvm::BitVector from here.
同样有趣的是，即使不是stl一致位向量也是llvm::位向量。
the essence of the llvm::BitVector is a nested class called reference and suitable operator overloading to make the BitVector behaves similar to vector with some limitations. The code below is a simplified interface to show how BitVector hides a class called reference to make the real implementation almost behave like a real array of bool without using 1 byte for each value.
llvm的本质::BitVector是一个被称为引用和合适的操作符重载的嵌套类，使位向量的行为类似于具有某些限制的向量。下面的代码是一个简化的接口，显示了BitVector如何隐藏一个名为reference的类，使实际实现几乎像一个真正的bool数组，而不需要为每个值使用1字节。
class BitVector {
public:
class reference {
reference &operator=(reference t);
reference& operator=(bool t);
operator bool() const;
};
reference operator[](unsigned Idx);
bool operator[](unsigned Idx) const;
};
this code here has the nice properties:
这里的代码有很好的属性:
BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.
This code actually has a flaw, try to run:
这段代码实际上有一个缺陷，试着运行:
std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator
will not work because assert( (&b[5] - &b[3]) == (5 - 3) ); will fail (within llvm::BitVector)
不能工作，因为断言((&b[5] - &b[3]) == (5 - 3));将失败(在llvm::BitVector)
this is the very simple llvm version. std::vector<bool> has also working iterators in it. thus the call for(auto i = b.begin(), e = b.end(); i != e; ++i) will work. and also std::vector<bool>::const_iterator.
这是非常简单的llvm版本。std::vector
However there are still limitations in std::vector<bool> that makes it behave differently in some cases.
然而，std中仍然存在一些限制:在某些情况下，向量
#6
2
Many consider the vector<bool> specialization to be a mistake.
许多人认为向量
In a paper "Deprecating Vestigial Library Parts in C++17"
There is a proposal to Reconsider vector Partial Specialization.
在一篇论文中，“在c++ 17”中，有一项建议重新考虑向量局部专门化。
There has been a long history of the bool partial specialization of std::vector not satisfying the container requirements, and in particular, its iterators not satisfying the requirements of a random access iterator. A previous attempt to deprecate this container was rejected for C++11, N2204.
std的bool部分专门化有很长的历史::向量不满足容器的要求，特别是它的迭代器不能满足随机访问迭代器的要求。之前试图反对此容器的尝试被拒绝为c++ 11, N2204。
One of the reasons for rejection is that it is not clear what it would mean to deprecate a particular specialization of a template. That could be addressed with careful wording. The larger issue is that the (packed) specialization of vector offers an important optimization that clients of the standard library genuinely seek, but would not longer be available. It is unlikely that we would be able to deprecate this part of the standard until a replacement facility is proposed and accepted, such as N2050. Unfortunately, there are no such revised proposals currently being offered to the Library Evolution Working Group.
被拒绝的原因之一是不清楚它将意味着什么来反对模板的特定专门化。这可以用谨慎的措辞加以解决。更大的问题是，向量的(打包)专门化提供了一个重要的优化，这是标准库的客户真正想要的，但是不能再提供了。在提议和接受替代设施(如2050年)之前，我们不太可能反对这部分标准。不幸的是，目前还没有向图书馆进化工作组提出的修订建议。