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

Question

斯科特·迈尔斯（Scott Meyers）的书《Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library》中的第18条建议避免使用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

vector<T>::operator []的返回类型应该是T&，但为什么对于vector<bool>来说是一个特殊情况呢？

vector<bool>到底由什么组成？

该条目进一步说明：

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

这能作为vector<bool>的替代品吗？

有人能解释一下吗？

- P0W

---

这是C++98中的一个设计错误，现在为了兼容性而保留。 - Oktalist

@g-makulik，不是说它的使用不能编译，而是你不能将一个元素的地址存储在指向bool的指针中，因为该元素没有自己的地址。 - chris

也许这个能帮到你：https://dev59.com/33RB5IYBdhLWcg3wSVe1 - chris

@g-makulik std::vector<bool> v; 可以编译通过。但是 &v[0] 不行（取临时变量的地址）。 - Oktalist

vector<bool> 的声誉不好，但并非完全无理可言：http://isocpp.org/blog/2012/11/on-vectorbool - TemplateRex

Answer 1

为优化空间，C++标准（从C++98开始）明确指出vector<bool>作为特殊的标准容器，其中每个bool只使用一个比特位而不是一个字节，实现了一种“动态位集”。为此优化，它不提供普通标准容器的所有功能和接口。

在这种情况下，由于无法获取字节内部的比特位地址，因此像operator[]这样的操作符不能返回bool&，而是返回一个代理对象来操作特定的位。由于该代理对象不是bool&，因此无法将其地址赋给bool*，就像你可以对“正常”容器的这种操作符调用结果所做的那样。反过来，这意味着bool *pb =&v[0];不是有效的代码。

另一方面，deque没有任何这样的特殊处理，所以每个bool都占用一个字节，并且可以获取从operator[]返回的值的地址。

最后注意，MS标准库实现在使用deque时使用了较小的块大小，这可能不是始终正确的解决方法（有人认为该实现是亚优化的）。

- Mark B

---

还有哪些数据类型是为其他STL容器专门化或显式调用的？ - P0W

这适用于 C++11 的 std::array<bool> 吗？ - Sergio Basurco

@chuckleplant 不，std::array 仅仅是一个模板包装器，用于封装原始数组 T[n] 并添加了一些辅助函数，例如 size()、复制/移动语义和迭代器，使其与 STL 兼容。（令人欣慰的是）它不违反自己的原则来为 bool 进行“专门化”的操作。（请注意我对这些操作的怀疑：） - underscore_d

只是一个小问题 - sizeof(bool)不一定是一个字节。https://dev59.com/eG445IYBdhLWcg3wXZIy - Uri Raz

vector<uint8_t>和vector<uint32_t>使用相同的空间吗？在使用uint8_t时，向量中是否存在内存填充？ - YuZ

Answer 2

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

Scott Meyers在More Effective C++中有一篇长长的第30条目关于代理类。你可以通过一对代理（例如reference_proxy<T>和iterator_proxy<T>）来实现几乎模拟内置类型：对于任何给定的类型T，可以使它们相互一致，即reference_proxy<T>::operator&()和iterator_proxy<T>::operator*()是彼此的反函数。

然而，在某些时候，需要将代理对象映射回T*或T&的行为。对于迭代器代理，可以重载operator->()并访问模板T的接口，而不必重新实现所有功能。然而，对于引用代理，你需要重载operator.()，但这在当前的C++中是不允许的（尽管Sebastian Redl在BoostCon 2013上提出了这样的建议）。你可以像在vector<bool>::bit_reference中所做的那样，在引用代理内部实现T的整个接口，但这样会失去内置语法，或者引入用户定义的转换，这些转换没有类型转换的内置语义（每个参数最多只能有一个用户定义的转换）。

总之：vector<bool>不是一个容器，因为标准要求使用真正的引用，但它可以被制作成几乎像一个容器一样的行为，至少在C++11（auto）中比在C++98中更接近。

- TemplateRex

Answer 3

vector<bool> 是一个使用一位(bit)来表示布尔值的压缩容器，而不是像 bool[] 数组一样使用8位(byte)。在 C++ 中无法返回对一个 bit 的引用，因此有一种特殊的辅助类型“位引用(bit reference)”，它提供了访问内存中某个位(bit)的接口，并允许您使用标准运算符和转换。

- Ivan Smirnov

---

@PrashantSrivastava deque<bool>没有被特化，因此它只是一个包含bool值的deque。 - Konrad Rudolph

@PrashantSrivastava vector<bool> 有一个特定的模板实现。我猜其他STL容器，比如deque<bool>，没有这样的实现，所以它们像任何其他类型一样持有bool值。 - Ivan Smirnov

这里有一个类似的问题，询问 Rust 是否禁止单个位布尔值：https://dev59.com/banka4cB1Zd3GeqPKDAb - andy boot

Answer 4

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

在一篇论文《C++17中弃用残留库部分》中，提出了重新考虑向量部分特化的建议。

长期以来，标准库的bool部分特化未能满足容器要求，特别是它的迭代器未能满足随机访问迭代器的要求。之前曾试图将该容器弃用，但被拒绝用于C++11，N2204。

---

拒绝的原因之一是不清楚弃用模板的特定特化意味着什么。通过精心措辞可以解决这个问题。更大的问题是（压缩）向量的特殊化提供了客户端标准库真正寻求的重要优化，但将不再可用。除非有提出并接受了替换设施的建议，例如N2050，否则我们不可能弃用标准的这部分。不幸的是，目前没有这样的修订提案被提交给库进化工作组。

- Trevor Hickey

Answer 5

看看它是如何实现的。STL大量使用模板，因此头文件中包含了它们所需的代码。

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

还有一个有趣的东西，即使不符合stl标准的位向量也可以从这里找到llvm::BitVector。

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

由于在llvm::BitVector中，assert( (&b[5] - &b[3]) == (5 - 3) );将失败，因此不会起作用。

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

然而，std::vector<bool>仍然存在限制，使其在某些情况下表现不同。

- Alexander Oh

Answer 6

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

bool类型的向量是vector的一种特殊版本，它针对空间进行了优化。

它的行为类似于未经专门化的vector，但有以下几点不同：

- 存储并不一定是一个bool值的数组，库实现可能会优化存储，使得每个值只占用一个位。 - 元素不是使用分配器对象构造的，而是直接在内部存储中的正确位上设置其值。 - 成员函数flip和新签名的成员swap。 - 特殊的成员类型reference，一个访问容器内部存储中单个位的类，其接口模拟了bool引用。相反，成员类型const_reference是一个普通的bool。 - 容器使用的指针和迭代器类型不一定是指针或符合迭代器规范，尽管它们应该模拟大多数预期行为。

这些更改提供了一个古怪的界面，优先考虑内存优化而不是处理（这可能或可能不适合您的需求）。无论如何，不能直接实例化bool的未经专门化的vector模板。避免这种情况的解决方法包括使用不同类型（char、unsigned char）或容器（如deque），使用包装类型或进一步专门化特定的分配器类型。

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

- kvv

---

这并没有直接回答问题。最多，它要求读者推断在这个一般的概述中解释的哪些事情使其不是STL。 - underscore_d