任何编译器专家都能够评论布尔值的有效使用吗?具体来说,编译器是否能够优化 astd::vector<boolean>
以使用最少的内存?是否有等效的数据结构?
过去,有些语言的编译器可以将布尔数组压缩为每个布尔值仅一位的表示形式。也许对 C++ 可以做的最好的事情是使用std::vector<char>
存储布尔值以最小化内存使用?
这里的用例将存储数亿个布尔值,其中单个字节将节省大量空间,超过每个值 4 个或更多字节和单个位,甚至更多。
任何编译器专家都能够评论布尔值的有效使用吗?具体来说,编译器是否能够优化 astd::vector<boolean>
以使用最少的内存?是否有等效的数据结构?
过去,有些语言的编译器可以将布尔数组压缩为每个布尔值仅一位的表示形式。也许对 C++ 可以做的最好的事情是使用std::vector<char>
存储布尔值以最小化内存使用?
这里的用例将存储数亿个布尔值,其中单个字节将节省大量空间,超过每个值 4 个或更多字节和单个位,甚至更多。
专长
标准库为 bool 类型提供了 std::vector 的专门化,它针对空间效率进行了优化。
vector<bool> 节省空间的动态位集(类模板特化)
并来自“C++ 工作草案,2012-11-02”
23.3.7 类向量 [vector.bool]
1 为了优化空间分配,提供了一个专门用于 bool 元素的向量:
template <class Allocator> class vector<bool, Allocator> {
...
}3 不要求将数据存储为布尔值的连续分配。建议使用空间优化的位表示。
所以没有要求,而只是建议,将bool
值存储为位。
请注意,这vector<bool>
不是一个容器,但是它假装是一个并提供了迭代器。如果您将其视为普通容器,例如尝试获取元素的地址,那么有一天可能会导致混乱和错误。
如果您需要为每个布尔值存储 1 位,您可以考虑std::bitset
或boost::dynamic_bitset 。这些数据结构并不伪装成容器,因此在使用它们时不太可能出错,尤其是在模板代码中。
在被广泛认为是标准中的一个缺陷中,std::vector专门用于使用单个位来表示每个bool
值。
如果这恰好是您正在寻找的东西,那么就使用它。
作为一种保证高效存储的与标准无关的方式,您可以创建自己的Bitvector
类。基本上对于每 8bool
个值,您只需要分配一个char
,然后您可以将每个值存储bool
在一个位中。然后,您可以在访问器/突变器中使用位移技术来存储/检索您的各个位。
Ron Penton 和 André LaMothe 的Data Structures for Game Programmers中概述了一个这样的示例(我也建议将其作为一般数据结构参考)。不过自己写也不是太难,而且,虽然我没有详细搜索,但互联网上可能还有一些更多的例子。