Define a large bitset in C++

Question

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

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.

Answer 1

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.

Answer 2

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];
}