在解 Project Euler 问题时,我经常需要处理大的(>10**7)位数组。
我的通常解决方案有:
bool* sieve = new bool[N];
bool sieve[N];
当 N = 1,000,000 时,我的程序使用了 1 兆字节 (8 * 1,000,000 位)。
在 C++ 中,是否有比 bool 更高效的存储位数组的方法?
在解 Project Euler 问题时,我经常需要处理大的(>10**7)位数组。
我的通常解决方案有:
bool* sieve = new bool[N];
bool sieve[N];
当 N = 1,000,000 时,我的程序使用了 1 兆字节 (8 * 1,000,000 位)。
在 C++ 中,是否有比 bool 更高效的存储位数组的方法?
如果 N
是一个常量,使用 std::bitset
,否则使用 std::vector<bool>
,就像其他人提到的一样(但不要忘记阅读 Herb Sutter 的这篇优秀文章)。
bitset 是一种特殊的容器类,专门用于存储位(元素只有两个可能值:0 或 1,true 或 false,...)。
该类非常类似于普通数组,但它优化了空间分配:每个元素仅占用一个位(比 C++ 中最小的基本类型 char 小八倍)。
编辑:
Herb Sutter(在那篇文章中)提到
std::vector < bool > 之所以不符合规范是因为它在幕后使用技巧来优化空间:它将 bools 装入单独的位 (例如 chars) 中以进行存储,而不是为每个 bool 存储一个完整的 char 或 int(在具有 8 位字符的平台上至少需要 8 倍的空间)。
std::vector < bool > 强制 所有用户使用特定的优化,将其奉为标准。这不是一个好主意;不同的用户具有不同的需求,现在所有 vector 的用户必须支付性能代价,即使他们不想或不需要节省空间。
编辑 2:
如果你使用了 Boost,你可以使用boost::dynamic_bitset
(如果 N
在运行时已知)。
无论好坏,std::vector<bool>
将使用位(bit)而不是布尔值(bool),以节省空间。因此,应该一开始就像使用 std::vector
一样使用它。
如果 N
是一个常量,则可以使用 std::bitset
。
std::bitset
和 std::vector<bool>
。后者通常不被推荐使用,因为尽管名字中有“vector”,但它实际上并不像任何其他类型的对象的向量,并且事实上不符合容器的要求。尽管如此,它仍然可以非常有用。'bool'类型并不仅使用1位进行存储。从您对大小的评论来看,每个bool似乎使用了整个字节。
一种类似C的处理方式是:
uint8_t sieve[N/8]; //array of N/8 bytes
然后将字节逻辑或在一起,以获取所有位:
sieve[0] = 0x01 | 0x02; //this would turn on the first two bits
'bool'类型并不仅使用1位进行存储。从您对大小的评论来看,每个bool似乎使用了整整1个字节。
C语言的一种方法是:
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);