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

vector<bool>以压缩形式包含布尔值，只使用一位作为值(而不是布尔[]数组的8位)。在 c + + 中不可能返回对位的引用，因此有一个特殊的辅助类型“ bit reference”，它为您提供了一个内存中某个位的接口，并允许您使用标准运算符和强制转换。

这来自 http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool 这是一个特殊版本的 Vector，它使用 类型 bool 的元素，并优化空间。

它的行为类似于向量的非专门化版本 以下改动:

• 存储不一定是 bool 值的数组，但是库实现可以优化存储，以便每个值都是
  存储在一个位中。
• 元素不使用分配器对象构造，但是它们的值直接设置在内部存储中的适当位上。
• 成员函数翻转和一个新的成员交换签名。
• 一个特殊的成员类型，引用，一个类，通过一个接口访问容器内部存储中的单个位
  模拟 bool 引用。相反，成员类型 const _ reference 是 普通的布。
• 容器使用的指针和迭代器类型不一定既不是指针也不是一致的迭代器，尽管它们
  将模拟他们的大部分预期行为。

这些更改为这种专门化提供了一个古怪的界面，并且 有利于内存优化而不是处理(这可能适合也可能不适合) 在任何情况下，都不可能实例化 直接用于 bool 的非专用向量模板 避免使用不同的类型(char、无符号 char)或 容器(如 deque)使用包装器类型或进一步专门用于 特定的分配程序类型。

位集是一个为固定大小提供类似功能的类 比特数组。

出于空间优化的原因，C + + 标准(最早可以追溯到 C + + 98)明确地将 vector<bool>调用为一个特殊的标准容器，其中每个 bool 只使用一个位空间，而不是像普通 bool 那样使用一个字节(实现了一种“动态位集”)。作为这种优化的交换，它不提供普通标准容器的所有功能和接口。

在这种情况下，由于您不能获取一个字节内的一个位的地址，所以像 operator[]这样的对象不能返回 bool&，而是返回一个代理对象，该代理对象允许操作所涉及的特定位。因为这个代理对象不是 bool&，所以您不能像在“普通”容器上对这样的操作员调用所得到的结果那样，将它的地址分配给 bool*。反过来，这意味着 bool *pb =&v[0];不是有效代码。

另一方面，deque没有调用任何这样的专门化，因此每个 bool 取一个字节，您可以从 operator[]获取返回值的地址。

最后请注意，MS 标准库实现(可以说)是次优的，因为它使用了小块大小的 deque，这意味着使用 deque 作为替代并不总是正确的答案。

看看它是如何实现的。STL 大量地建立在模板之上，因此头部确实包含了它们的代码。

例如，看看 Stdc + + 实现 给你。

同样有趣的是，即使 给你中的 BitVector不是一个符合 stl 的位向量。

llvm::BitVector的本质是一个称为 reference的嵌套类，并且适当的运算符重载使得 BitVector的行为类似于 vector，但有一些局限性。下面的代码是一个简化的接口，展示了 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;
};

这里的代码有很好的属性:

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 版本。 因此，调用 for(auto i = b.begin(), e = b.end(); i != e; ++i)将工作。也是 std::vector<bool>::const_iterator。

然而，在 std::vector<bool>仍然有限制，使其行为不同的情况下，一些。

问题是，vector<bool>返回的是 代理引用对象代理引用对象而不是真正的引用，因此 C + + 98样式代码 bool * p = &v[0];无法编译。但是，如果 operator&也是 返回一个代理指针对象 ，那么现代 C + + 11和 auto p = &v[0];就可以编译了。Howard Hinant 编写了 一篇博客文章，详细介绍了使用这种代理引用和指针时的算法改进。

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 + + 中是不允许的(尽管在 BoostCon 2013上使用 Sebastian Redl 提出了这样的建议)。你可以在引用代理中做一个详细的解决方案，比如 .get()成员，或者在引用中实现 T的所有接口(这就是为 vector<bool>::bit_reference所做的) ，但是这要么会丢失内建语法，要么会引入没有内建语义的用户定义转换(每个参数最多可以有一个用户定义转换)。

DR : 没有 vector<bool>不是一个容器，因为标准需要一个真正的引用，但是它可以表现得像一个容器，至少在 C + + 11(auto)中比在 C + + 98中更接近。

许多人认为 vector<bool>专门化是一个错误。

在 “在 C + + 17中弃用残留库部件”的论文里
有人提议 重新考虑向量部分专门化。