Bit Array in C++ -

when working project euler problems need large (> 10**7) bit array's.

my normal approach 1 of:

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

when n = 1,000,000 program uses 1 megabyte (8 * 1,000,000 bits).

is there more efficient way use store bit arrays bool in c++?

use std::bitset (if n constant) otherwise use std::vector<bool> others have mentioned (but dont forget reading this excellent article herb sutter)

a bitset special container class designed store bits (elements 2 possible values: 0 or 1, true or false, ...).

the class similar regular array, but optimizing space allocation: each element occupies 1 bit (which 8 times less smallest elemental type in c++: char).

edit:

herb sutter (in article) mentions that

the reason std::vector< bool > nonconforming pulls tricks under covers in attempt optimize space: instead of storing full char or int every bool[1] (taking @ least 8 times space, on platforms 8-bit chars), it packs bools , stores them individual bits(inside, say, chars) in internal representation.

std::vector < bool > forces specific optimization on users enshrining in standard. that's not idea; different users have different requirements, , users of vector must pay performance penalty if don't want or need space savings.

edit 2:

and if have used boost can use boost::dynamic_bitset(if n known @ runtime)