c++ - 位集或位数组的好库

Question

大家好，我正在寻找一些适用于位集或位数组的优秀库。任何人都知道比 boost::dynamic_bitset 更好（或在所有情况下都不是更糟）的事情吗？无论库是开源的还是商业的。

在我的项目中，存储和使用包含较少数量的大位掩码是一项常见任务。所以它们可以在内存中很好地压缩。

Answer 1

有几种可用的压缩位向量实现。它们通常具有运行长度编码以及适用于压缩形式的和/或/异或/非操作。

所以好处是：

• 较小的空间使用（对于稀疏位集，如您的用例）
• 非常快的位操作（因为它们在字上工作并且对 CPU 缓存更友好）

不利的一面是：

• 较慢的位访问（需要迭代才能在特定位置找到位）

我知道的一些实现（我确定还有其他实现）：

Fastbit 实际上是一个使用位向量索引的数据库。压缩后的位向量类可以直接使用（无需索引）

Lemur bitmapindex Fastbit 引入的 EWAH 编码的另一种实现

koen.vandamme 压缩的位向量 从未尝试过......但只有两个标题和一个 cpp 文件。所以没有太多努力尝试一下。

Bitmagic 完整的包，实现了几个压缩位向量，包括硬件支持（sse2，...）

希望这可以帮助，

罗兰

Answer 2

MiniSAT 图书馆怎么样？

http://minisat.se/

我记得这有一个简单的位数组实现。

Answer 3

如果您要寻找的只是空间优化，那么 std::vector 提供了针对空间进行优化的向量特化。

http://www.cplusplus.com/reference/stl/vector/

和 C++ 标准 23.2.5

不知道这是否比 boost:dynamic_bitset 更好，但是如果您还没有研究过它，那么值得研究一下。