为什么vector <bool>不是STL容器？

Question

Scott Meyers的书第18项有效STL:50改进您对标准模板库的使用的具体方法说避免vector <bool>因为它不是STL容器而且它实际上并不存在bool.

以下代码:

vector <bool> v; 
bool *pb =&v[0];

不会编译,违反STL容器的要求.

错误:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

bool返回类型应该是T&,但为什么它是特殊情况vector<T>::operator []？

什么是T&真正组成的呢？

该项目进一步说:

deque<bool> v; // is a STL container and it really contains bools

这可以用作替代品vector<bool>吗？

有人可以解释一下吗？

Answer 1

出于空间优化的原因,C++标准(早在C++ 98中)显式地调用了vector<bool>一个特殊的标准容器,其中每个bool只使用一位空间而不是一个字节作为普通bool(实现一种"动态bitset").作为这种优化的交换,它不提供普通标准容器的所有功能和接口.

在这种情况下,由于你不能在一个字节内取一个位的地址,所以诸如operator[]不能返回一个bool&但却返回一个允许操纵有问题的特定位的代理对象.由于此代理对象不是a bool&,因此您无法将其地址分配给bool*"正常"容器上的此类操作员调用的结果.反过来,这意味着这bool *pb =&v[0];不是有效的代码.

另一方面deque,没有任何这样的专业化调用,所以每个bool取一个字节,你可以从值返回的地址operator[].

最后请注意,MS标准库的实现(可以说)是次优的,因为它使用一个小的块大小来表示deques,这意味着使用deque作为替代并不总是正确的答案.

Answer 2

vector<bool>包含压缩形式的布尔值,仅使用一位作为值(而不是8如何bool []数组).不可能在c ++中返回对某个位的引用,因此有一个特殊的帮助器类型"位引用",它为您提供内存中某些位的接口,并允许您使用标准运算符和强制转换.

Answer 3

问题是vector<bool>返回代理引用对象而不是真正的引用,因此C++ 98样式代码bool * p = &v[0];将无法编译.但是,auto p = &v[0];如果operator&还返回代理指针对象,则可以使现代C++ 11 编译.Howard Hinnant撰写了一篇博文,详细介绍了使用此类代理引用和指针时的算法改进.

Scott Meyers在关于代理类的更有效的C++中有很长的第30项.你可以走了很长的路,几乎模仿内建类型:对于任何给定类型T,一对代理(如reference_proxy<T>和iterator_proxy<T>)可制成在这个意义上相互一致reference_proxy<T>::operator&(),并iterator_proxy<T>::operator*()互为倒数.

但是,在某些时候,需要将代理对象映射回来,表现得像T*或T&.对于迭代器代理,可以重载operator->()并访问模板T的接口,而无需重新实现所有功能.但是,对于参考代理,您需要重载operator.(),这在当前C++中是不允许的(尽管Sebastian Redl 在BoostCon 2013上提出了这样的提议).你可以做一个详细的工作周围像一个.get()参考代理内部成员,或实现所有T的接口引用内(这是给毁了vector<bool>::bit_reference),但这要么失去内置的语法或引入用户定义的转换,这种转换没有用于类型转换的内置语义(每个参数最多只能有一个用户定义的转换).

TL; DR:没有vector<bool>不是一个容器,因为标准要求一个真正的参考,但它可以被制成表现几乎像一个容器中,用C++ 11(自动)比在C++ 98至少更接近.

Answer 4

许多人认为vector<bool>专业化是错误的。

在一篇论文《 C ++ 17中不赞成使用Vestigial库的部分》
中，提出了重新考虑矢量部分专业化的建议 。

长期以来，std :: vector的布尔部分专业化不满足容器要求，特别是其迭代器不满足随机访问迭代器的要求。C ++ 11 N2204拒绝了之前弃用此容器的尝试。

拒绝的原因之一是，不赞成废弃模板的特定专业化意味着什么。可以通过认真措辞解决这一问题。更大的问题是，向量的（打包）专业化提供了标准库的客户真正寻求的重要优化，但不再可用。在提议并接受替代设施（例如N2050）之前，我们不太可能会弃用标准的这一部分。不幸的是，目前没有这样的修订提案提供给图书馆发展工作组。

Answer 5

看一下它是如何实现的。STL很大程度上建立在模板上，因此标头确实包含它们所执行的代码。

例如，在这里查看stdc ++实现。

同样有趣的，即使不符合位向量的STL是LLVM ::位向量自这里。

的本质llvm::BitVector是称为的嵌套类，reference并进行了适当的运算符重载，以使BitVector行为类似但vector有一些限制。下面的代码是一个简化的接口，用于显示BitVector如何隐藏一个名为的类，reference以使真实实现几乎像布尔的真实数组一样工作，而每个值不使用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;      
};

此代码具有不错的属性：

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.

这段代码实际上有一个缺陷，请尝试运行：

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

将不起作用，因为assert( (&b[5] - &b[3]) == (5 - 3) );将失败（在内llvm::BitVector）

这是非常简单的llvm版本。std::vector<bool>也有有效的迭代器。因此该呼叫for(auto i = b.begin(), e = b.end(); i != e; ++i)将起作用。还有std::vector<bool>::const_iterator。

但是，仍然存在一些局限性std::vector<bool>，使其在某些情况下的行为有所不同。