126

Scott Meyers 的《Effective STL: 50 Specific Ways to Improvement Your Use of the Standard Template Library 》的第 18 项说要避免vector <bool>，因为它不是 STL 容器，而且它并不真正持有bools。

以下代码：

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>吗？

谁能解释一下？

4

6 回答 6

145

出于空间优化的原因，C++ 标准（早在 C++98）显式调用vector<bool>作为一个特殊的标准容器，其中每个 bool 只使用一位空间，而不是像普通 bool 那样使用一个字节（实现一种“动态位集”）。作为这种优化的交换，它不提供普通标准容器的所有功能和接口。

在这种情况下，由于您无法获取字节内的位地址，operator[]因此无法返回 abool&而是返回允许操作相关特定位的代理对象。由于此代理对象不是 a bool&，因此您无法将其地址分配给 a bool*，因为这样的操作员调用“普通”容器的结果。反过来，这意味着这bool *pb =&v[0];不是有效的代码。

另一方面deque，没有调用任何此类特殊化，因此每个 bool 都占用一个字节，您可以从operator[].

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

于 2013-07-22T18:39:42.390 回答
30

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

于 2013-07-22T18:21:30.220 回答
29

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

Scott Meyers 在更有效的 C++中关于代理类的第 30 条很长。您几乎可以模仿内置类型：对于任何给定的 type T，可以使一对代理（例如reference_proxy<T>和iterator_proxy<T>）相互一致，即reference_proxy<T>::operator&()和iterator_proxy<T>::operator*()是彼此的逆。

但是，在某些时候需要将代理对象映射回行为类似于T*or T&。对于迭代器代理，可以重载operator->()和访问模板T的接口，而无需重新实现所有功能。但是，对于参考代理，您需要重载operator.()，这在当前的 C++ 中是不允许的（尽管 Sebastian Redl在 BoostCon 2013 上提出了这样的提议）。.get()您可以像引用代理中的成员一样进行详细的解决方法，或者在引用中实现所有T的接口（这是为vector<bool>::bit_reference)，但这要么会丢失内置语法，要么会引入没有用于类型转换的内置语义的用户定义转换（每个参数最多可以有一个用户定义的转换）。

TL;DR : novector<bool>不是容器，因为标准需要一个真正的引用，但它可以表现得几乎像一个容器，至少在 C++11（自动）中比在 C++98 中更接近。

于 2013-07-22T21:14:58.453 回答
16

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

在一篇论文“Deprecating Vestigial Library Parts in C++17”
中，有一个 Reconsider vector Partial Specialization的提议。

长期以来，std::vector 的 bool 部分特化不满足容器要求，特别是其迭代器不满足随机访问迭代器的要求。先前对 C++11, N2204弃用此容器的尝试被拒绝。

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

于 2016-02-29T09:10:20.317 回答
6

看看它是如何实现的。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

将无法工作，因为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>这使得它在某些情况下表现不同。

于 2013-07-22T20:29:03.160 回答
3

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

bool 的向量 这是向量的特殊版本，用于 bool 类型的元素并针对空间进行优化。

它的行为类似于未专门化的 vector 版本，但有以下变化：

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

这些更改为这种专业化提供了一个古怪的接口，并且有利于内存优化而不是处理（这可能会或可能不会满足您的需求）。在任何情况下，都不可能直接为 bool 实例化向量的非特化模板。避免这种情况的解决方法包括使用不同的类型（char、unsigned char）或容器（如 deque）来使用包装器类型或进一步专门用于特定的分配器类型。

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

于 2013-07-22T18:25:58.220 回答