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

Why is vector<bool> not a STL container?

提问by P0W

Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Librarysays to avoid vector <bool>as it's not an STL container and it doesn't really hold bools.

Scott Meyers 的书Effective STL: 50 Specific Ways to改善标准模板库的使用的第 18 条说要避免，vector <bool>因为它不是 STL 容器，它并不真正包含bools。

The following code:

以下代码：

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

will not compile, violating a 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 is it a special case for vector<bool>?

vector<T>::operator []返回类型应该是T&，但为什么它是 的特例vector<bool>？

What does vector<bool>really consist of?

vector<bool>真正由什么组成？

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>?

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

Can anyone please explain this?

任何人都可以解释一下吗？

回答by Mark B

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

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.

在这种情况下，由于您不能在一个字节中获取某个位的地址，operator[]因此不能返回 abool&而是返回一个代理对象，该对象允许操作有问题的特定位。由于此代理对象不是bool&，因此您无法将其地址分配给bool*类似操作员调用“正常”容器的结果。反过来，这意味着这bool *pb =&v[0];不是有效代码。

On the other hand dequedoesn'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 都需要一个字节，您可以从operator[].

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 标准库实现（可以说）是次优的，因为它对双端队列使用了较小的块大小，这意味着使用双端队列作为替代并不总是正确的答案。

回答by Ivan Smirnov

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

回答by TemplateRex

The problems is that vector<bool>returns a proxy reference objectinstead 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 postdetailing the algorithmic improvements when using such proxy references and pointers.

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

Scott Meyers has a long Item 30 in More Effective C++about proxy classes. You can come a long way to almostmimic 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 在More Effective C++ 中有很长的第 30 条关于代理类。您可以走很长的路来几乎模仿内置类型：对于任何给定的 type T，可以使一对代理（例如reference_proxy<T>和iterator_proxy<T>）相互一致，因为reference_proxy<T>::operator&()和iterator_proxy<T>::operator*()是彼此的倒数。

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 proposalon 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&。对于迭代器代理，可以重载operator->()和访问模板T的接口，而无需重新实现所有功能。但是，对于参考代理，您需要重载operator.()，这在当前的 C++ 中是不允许的（尽管 Sebastian Redl在 BoostCon 2013 上提出了这样的提议）。您可以像.get()引用代理中的成员一样进行详细的解决方法，或者在引用中实现所有T的接口（这是为vector<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.

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

回答by Trevor Hickey

Many consider the vector<bool>specialization to be a mistake.

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

In a paper "Deprecating Vestigial Library Parts in C++17"
There is a proposal to Reconsider vector Partial Specialization.

在一篇论文“Deprecating Vestigial Library Parts in 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::vector 的 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.

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

回答by Alex

Look at how it is implemented. the STL builds vastly on templates and therefore the headers do contain the code they do.

看看它是如何实现的。STL 大量构建在模板上，因此标头确实包含它们所做的代码。

for instance look at the stdc++implementation here.

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

also interesting even though not an stl conforming bit vector is the llvm::BitVectorfrom here.

同样有趣的是，即使不是符合 stl 的位向量是来自here的llvm::BitVector。

the essence of the llvm::BitVectoris a nested class called referenceand suitable operator overloading to make the BitVectorbehaves similar to vectorwith some limitations. The code below is a simplified interface to show how BitVector hides a class called referenceto make the real implementation almost behave like a real array of bool without using 1 byte for each value.

的本质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;      
};

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)

不会工作，因为assert( (&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<bool>也有工作迭代器。因此呼叫for(auto i = b.begin(), e = b.end(); i != e; ++i)将起作用。还有std::vector<bool>::const_iterator。

However there are still limitations in std::vector<bool>that makes it behave differently in somecases.

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

回答by kvv

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.

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.
• 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.
• 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.

bitset is a class that provides a similar functionality for fixed-size arrays of bits.

布尔向量 这是向量的特殊版本，用于 bool 类型的元素并优化空间。

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

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

这些更改为这种专业化提供了一个古怪的界面，并有利于内存优化而不是处理（这可能适合也可能不适合您的需求）。在任何情况下，都不可能直接为 bool 实例化 vector 的非特化模板。从使用不同类型（char、unsigned char）或容器（如 deque）到使用包装器类型或进一步专用于特定分配器类型的变通方法。

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