Define a large bitset in C++

In my program I need to check if I have already generated a value in a set of 2.5*10^9. I expect to generate about the half of the set and need to have a fast way to check and update it. The bitset seemed to me as a good idea as it takes not too much memory (1 bit per value) and is fast.

The problem is that when I define my set in my class, I got a segmentation fault as the size is too big (it works with smaller sizes).

private:
  std::bitset<2500000000UL> cover; // not working
  std::bitset<25000UL> cover; // working

Any idea ?

Thank you

开发者_JAVA百科PS: I'd rather not use external library if possible. I'm already using GMP but I don't think they have a bit set implementation for large numbers.

This may not be your problem, but try to allocate the bitset on the heap with new, instead of using the stack.

Some systems limit the size of the stack, which might be what causes problems for you.

I think the following solution is better than using new

    std::vector<std::bitset<2500000000UL>> wrapper(1);
    auto & cover = wrapper[0];//To avoide unnecessary indirection by wrapper[0]

To demonstrate

int main(){
    std::vector<std::bitset<2500000000UL>> wrapper(1);
    auto & cover = wrapper[0];
    cover[0] = 1;
    std::cout << cover[0] << " " << cover[2500000000UL - 1];
}

It will cause segmentation fault because memory here is being allocated on stack rather than heap. Memory allocation on stack is very limited and hence it fails to do so. This is when dynamic memory allocation comes to the rescue. If you're aware of how malloc works, you can modify your code as follows.

bitset<1000000000> *b;
b = (bitset<1000000000> *)malloc(sizeof(bitset<1000000000>));
b->set(0,1);

Once you're done with the bitset, delete it using delete keyword.

Use std::vector instead of std::bitset for large sizes.