I need to create a very large array of bits/boolean values. How would I do this in C/C++?

Question

Is it even possible to create an array of bits with more than 100000000 elements? If it is, how would I go about doing this? I know that for a char array I can do this:

char* array;

array = (char*)malloc(100000000 * sizeof(char));

If I was to declare the array by char array[100000000] then I would get a segmentation fault, since the maximum number of elements has been exceeded, which is why I use malloc.

Is there something similar I can do for an array of bits?

Answer 1

If you are using C++, std::vector<bool> is specialized to pack elements into a bit map. Of course, if you are using C++, you need to stop using malloc.

Answer 2

You could try looking at boost::dynamic_bitset. Then you could do something like the following (taken from Boost's example page):

boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;

The bitset will use a single bit for each element so you can store 32 items in the space of 4 bytes, decreasing the amount of memory required considerably.