C++中布尔值true和false的高效使用？

Question

有编译器专家能够对布尔值的有效使用发表评论吗？ 具体来说，编译器是否能够优化

std::vector<boolean>

以使用最少的内存？ 是否有等效的数据结构？

过去，有些语言的编译器可以将布尔值数组压缩为每个布尔值仅一位的表示形式。 也许对 C++ 来说最好的办法就是使用

std::vector<char>

来存储布尔值以最小化内存使用？

这里的用例将存储数亿个布尔值，其中单个字节将节省每个值 4 个或更多字节以及单个位的大量空间，甚至更多。

Answer 1

参见

std::vector

专业

标准库为 bool 类型提供了 std::vector 的特化，它针对空间效率进行了优化。
矢量 节省空间的动态位集 （类模板专业化）

以及来自“C++ 工作草案，2012-11-02”

23.3.7 类向量 [vector.bool]
1 为了优化空间分配，提供了 bool 元素向量的特化：
模板 类向量 {
...
}

3 不要求将数据存储为布尔值的连续分配。建议使用空间优化的位表示。

因此，没有要求，只是建议将

bool

值存储为位。

Answer 2

std::vector for bool 是一个模板专业化，可以满足您的要求。

您可以在这里阅读更多内容。

您可能还想探索标准 bitset。

Answer 3

注意，

vector<bool>

不是一个容器，但它假装是一个容器并提供迭代器。 有一天，如果您将其视为普通容器，例如，可能会导致混乱和错误。试图获取元素的地址。

如果您需要为每个布尔值存储 1 位，您可以考虑

std::bitset

或 boost::dynamic_bitset。这些数据结构不会伪装成容器，因此在使用它们中的任何一个时都不太可能犯任何错误，尤其是在模板代码中。

Answer 4

在被广泛认为是标准缺陷的地方，std::vector专门使用单个位来表示每个

bool

值。

如果这恰好是您正在寻找的，那就使用它吧。

Answer 5

作为保证高效存储的与标准无关的方法，您可以创建自己的

Bitvector

类。本质上，对于每 8 个

bool

值，您只需要分配一个

char

，然后您可以将每个

bool

存储在单个位中。然后，您可以在访问器/修改器中使用位移技术来存储/检索您的各个位。

Ron Penton 和 André LaMothe 的《游戏程序员的数据结构》中概述了一个这样的示例（我也推荐将其作为通用数据结构参考）。不过，编写自己的代码并不太难，而且，尽管我没有进行大量搜索，但互联网上可能还有一些进一步的示例。