在C++中使用std::vector<bool>对象是否可接受，或者我应该使用其他替代方案？

Question

我正在处理用户定义数量的位（我正在持有一个三维位数组，因此大小呈立方形增长 - 假设不少于512位），并且需要单独翻转它们。现在，仅在计算机上，我使用bool类型，因为内存不是问题。我计划将代码移动到微控制器中，因此处理能力和内存要求可能成为问题。但现在，我只想要速度。

然后我发现了C++ STL中的std::bitset对象，但我无法在运行时定义位集的大小。然后我发现std::vector<bool>具有特殊的初始化程序，以将它们存储为位（而不是整个字节或4个字节），但在维基百科的this section中找到了以下内容：

标准库为bool定义了vector模板的专门化版本。这种专门化版本的描述表明，实现应该打包元素，以便每个bool只使用一个位的内存。这被广泛认为是一个错误。[...] C++标准委员会和库工作组普遍认为，vector<bool>应该被弃用，并随后从标准库中删除，而功能将在不同的名称下重新引入。

现在，你可能看到了我使用 vector<bool> 对象的想法，但是在阅读之后，我正在考虑使用其他东西。唯一的问题是我不确定要使用什么。但我很好奇为什么他们说应该重新引入这个功能（尽管使用不同的名称）。

那么，我的问题是，使用vector<bool>对象是否可行（因为它们是STL的一部分）？ 它们是C++标准的一部分吗？

如果它们的使用不可行，则是否有可接受的替代方案（除了我自己定义一个特殊容器）？ 我自己有一些想法，但我只是好奇是否有更好的解决方案。 另外，我想避免使用大型库（再次，我希望最终将此代码移植到微控制器上）。

- Breakthrough

---

仅使用 vec[bit>>3] |= (1<<(bit&7)); 与 std::vector<unsigned char> 有哪些问题？ - 6502

相关：Howard Hinnant的博客文章关于vector<bool> - 这是一个有用的数据结构，但名字很糟糕。通过适当的std::find、std::count等特化，标准库甚至可以暴露快速的系统特定优化。 - Peter Cordes

Answer 1

在《Effective STL》的第18项中, Scott Meyers建议："避免使用vector< bool >。":

作为一个STL容器，vector< bool >实际上只有两个问题。 首先，它不是一个STL容器。其次，它不能保存bool值。除此之外，没有什么好反对的了。

- Gnawme

Answer 2

< p >使用 vector<bool> 没有任何问题，但它与一个 T 类型等同于 bool 的 vector<T> 不同。这只会在性能（CPU 只能一次访问一个字节，在 vector<bool> 中每个元素都存储在一个位中）和内存访问上表现出来（对于 vector<bool> 的第一个元素的引用不等同于像其他 vector<T> 一样的数组）。

不幸地，这是标准的一部分：请参阅第 23.3.7 节（C++0x FDIS）。

- rubenvb

---

vector<bool> 的优化目标是空间而非速度，但它的容器语义与 vector<T> 不完全相同。 - Martin York

Answer 3

批评的是vector<bool>是唯一一个不完全符合标准容器要求的标准容器。这有点令人惊讶。

另外一点是，vector<bool>强制对每个人进行空间优化(通过存储位)，而有些用户可能更喜欢速度优化。

除此之外，主要的偏差在于该容器不能返回对其成员的引用，因为它不存储任何bool值。这将使得某些标准库算法无法编译vector<bool>。

如果你可以接受这一点，并且它适合你的其他需求，那么使用它是完全可以的。

- Bo Persson

Answer 4

有一个boost.dynamic_bitset与std::bitset几乎相同，唯一的区别是它的大小在运行时给定。如果您不想依赖boost，则其源代码（完全包含在其头文件中）可以提供更多有关如何编写这种容器的想法。

- Cubbi

---

谢谢您的回复，我修改了我的问题以更准确地反映为什么我选择了512（我正在使用的网格是8x8x8，但它可以定义为任何大小，因此元素数量[及其内存要求]呈立方增加）。 - Breakthrough

@Breakthrough 刚才我提到的512请不用在意，但是这个可能很大的三维数组内部是否有结构？也许有其他数据结构可以利用它，比如 http://en.wikipedia.org/wiki/K-d_tree 和 http://en.wikipedia.org/wiki/Octree 等等？ - Cubbi

+1，你的答案没有问题，我真的很感激那些替代数据类型，但是@rubenvb发布了一个更适合我所寻找的答案。在这种情况下，我不认为树是正确的选择，因为我根本没有进行任何二进制搜索。然而，我确实需要以无特定顺序几乎立即访问此数组中的任何元素... - Breakthrough

Answer 5

正确使用vector<bool>是没有问题的，就像正确使用auto_ptr一样-只要你在继续之前了解它们的缺点和惊喜。

- Puppy

---

确实。如果vector<bool>适合您的需求，请使用它。它是标准库的一部分。如果安全地使用，将来当这个特化被移除时，最糟糕的情况不是您的代码会出错，而是它会突然使用更多的内存。 - Cory Nelson

不要使用 auto_ptr。它在 C++11 中被弃用，在 C++17 中被移除了。 - John McFarlane

Answer 6

另一种选择可能是BitMagic，尽管我不确定它是否适用于除x86之外的任何其他架构（它使用SIMD进行了大量优化）。

- celavek