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.

score 24 · Accepted Answer · answered Apr 25 '11 at 15:47

24

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.

answered Apr 25 '11 at 15:47

MTilsted

5,425
9
44
76

You can find an explanation to why here: http://stackoverflow.com/questions/4156538/how-can-stdbitset-be-faster-than-stdvectorbool – Laserallan Apr 25 '11 at 16:02

score 2 · Answer 2 · answered Apr 04 '20 at 11:38

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

taurus05 · Answer 3 · 2021-04-27T06:48:57.853

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.

score -1 · Answer 4 · answered Sep 28 '15 at 20:53

-1

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

answered Sep 28 '15 at 20:53

J.Kraftcheck

474
4
6

5

Use `vector` only if you know what you are doing! – Happy Green Kid Naps Dec 21 '15 at 21:57
1

std::vector is of poor performance compared to bitset, see: http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf – math Feb 26 '16 at 09:08
3

@math: An interesting bit of research, but it's a bit dated now. Despite the paper being only 7 years old, the researchers were using a version of MinGW that was roughly 3 years old at the time (10 years old now). I wonder if benchmarking of more modern implementations of the standard library would yield different results. Also, the code was not published as part of the research, so it's difficult to know for certain whether the benchmarking could have been improved. – dreamlax Nov 05 '17 at 11:34

Define a large bitset in C++

4 Answers4

Linked

Related