在处理 Project Euler 问题时，我经常需要大 (> 10**7) 位数组。
我的正常方法是以下之一：
bool* sieve = new bool[N];
bool sieve[N];
当 N = 1,000,000 时，我的程序使用 1 兆字节（8 * 1,000,000 位）。
有没有比 c++ 中的 bool 更有效的方法来使用存储位数组？
问问题
58317 次
8 回答
33
使用std::bitset（如果N是常数），否则使用std::vector<bool>其他人提到的（但不要忘记阅读Herb Sutter 的这篇优秀文章）
位集是一种特殊的容器类，旨在存储位（只有两个可能值的元素：0 或 1，真或假，...）。
该类与常规数组非常相似，但优化了空间分配：每个元素仅占用一位（比 C++ 中最小的元素类型：char 少八倍）。
编辑：
Herb Sutter（在那篇文章中）提到
std::vector< bool > 不符合标准的原因是它隐藏了一些技巧以试图优化空间：而不是为每个 bool[1] 存储一个完整的 char 或 int （占用至少 8 倍的空间，在具有 8 位字符的平台上），它将布尔值打包并将它们作为单独的位（例如，字符内部）存储在其内部表示中。
std::vector < bool >通过将其写入标准来强制对所有用户进行特定优化。这不是一个好主意。不同的用户有不同的要求，现在所有的vector用户都必须付出性能代价，即使他们不想要或不需要空间节省。
编辑 2：
如果您使用过 Boost，则可以使用boost::dynamic_bitset（如果N在运行时已知）
于 2010-09-27T17:59:48.560 回答
15
无论好坏，std::vector<bool>都将使用位而不是布尔值，以节省空间。所以std::vector就像你应该首先使用的那样使用。
如果N是常数，则可以使用std::bitset.
于 2010-09-27T18:01:09.290 回答
5
你可以抬头std::bitset看std::vector<bool>。通常不推荐使用后者，因为尽管vector名称中有 ，但它实际上并不像任何其他类型的对象的向量，实际上也不符合一般容器的要求。尽管如此，它可能非常有用。
OTOH，没有什么会（至少可靠地）以不到 100 万位存储 100 万个布尔值。根本无法确定。如果您的位集包含一定程度的冗余，则有各种可能有效的压缩方案（例如，LZ*、霍夫曼、算术），但如果不了解内容，就不可能肯定地说它们是有效的。然而，这些中的任何一个通常只会将每个布尔/位存储在一个存储位中（加上一点簿记开销——但这通常是一个常数，并且最多字节到几十个字节的顺序）。
于 2010-09-27T18:01:54.787 回答
4
'bool' 类型不是仅使用 1 位存储的。从您对大小的评论来看，每个布尔似乎使用 1 个完整字节。
类似 AC 的做法是：
uint8_t sieve[N/8]; //array of N/8 bytes
然后逻辑或字节一起得到你所有的位：
sieve[0] = 0x01 | 0x02; //this would turn on the first two bits
在该示例中，0x01 和 0x02 是表示字节的十六进制数。
于 2010-09-27T18:04:07.793 回答
3
'bool' 类型不是仅使用 1 位存储的。从您对大小的评论来看，每个布尔似乎使用 1 个完整字节。
类似 AC 的做法是：
uint8_t sieve[N/8]; //array of N/8 bytes
数组元素是：
result = sieve[index / 8] || (1 << (index % 8));
或者
result = sieve[index >> 3] || (1 << (index & 7));
在数组中设置 1：
sieve[index >> 3] |= 1 << (index & 7);
于 2017-02-13T01:56:44.433 回答
2
您可能有兴趣尝试使用BITSCAN库作为替代方案。最近有人提出了稀疏性的扩展，我不确定你的情况，但可能是。
于 2014-07-30T07:19:45.933 回答
1
您可以使用字节数组并对其进行索引。索引n将在字节索引n/8，位 #n%8中。（如果 std::bitset 由于某种原因不可用）。
于 2010-09-27T17:59:59.270 回答
0
如果 N 在编译时已知，则使用std::bitset，否则使用boost::dynamic_bitset。
于 2010-09-27T18:08:19.947 回答