Bit Array in C++

Question

When working with Project Euler problems I often need large (> 10**7) bit array's.

My normal approach is one of:

bool* sieve = new bool[N];  bool sieve[N]; 

When N = 1,000,000 my program uses 1 MegaByte (8 * 1,000,000 bits).

Is there a more efficient way to use store bit arrays than bool in c++?

Answer 1

Use std::bitset (if N is a constant) otherwise use std::vector<bool> as others have mentioned (but dont forget reading this excellent article by Herb Sutter)

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).

The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

EDIT:

Herb Sutter (in that article) mentions that

The reason std::vector< bool > is nonconforming is that it pulls tricks under the covers in an attempt to optimize for space: Instead of storing a full char or int for every bool[1] (taking up at least 8 times the space, on platforms with 8-bit chars), it packs the bools and stores them as individual bits(inside, say, chars) in its internal representation.

std::vector < bool > forces a specific optimization on all users by enshrining it in the standard. That's not a good idea; different users have different requirements, and now all users of vector must pay the performance penalty even if they don't want or need the space savings.

EDIT 2:

And if you have used Boost you can use boost::dynamic_bitset(if N is known at runtime)

Answer 2

For better or for worse, std::vector<bool> will use bits instead of bool's, to save space. So just use std::vector like you should have been in the first place.

If N is a constant, you can use std::bitset.