在C++中定义一个大的位集

Question

在我的程序中，我需要检查是否已经在一个大小为 2.5*10^9 的集合中生成了某个值。我预计会生成大约一半的这个集合，并且需要一种快速的方式来检查和更新它。对我来说，位集似乎是一个不错的选择，因为它不需要太多的内存（每个值只需要 1 位）并且速度较快。但是问题在于，当我在类中定义我的集合时，由于尺寸太大，我得到了一个“分段故障”的错误（如果使用较小的尺寸，则可正常工作）。

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

有什么想法吗？

谢谢

PS：如果可能的话，我宁愿不使用外部库。 我已经在使用GMP，但我不认为它们有用于大数的位设置实现。

- Martin Trigaux

Answer 1

这可能不是你的问题，但尝试使用new在堆上分配bitset，而不是使用栈。

一些系统限制堆栈的大小，这可能是导致问题的原因。

- MTilsted

---

你可以在这里找到为什么的解释：https://dev59.com/cW855IYBdhLWcg3ww3Wa - Laserallan

Answer 2

我认为以下解决方案比使用new更好。

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

展示示例：

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

- asmmo

Answer 3

这会导致分段错误，因为内存在此处是在堆栈上分配而不是在堆上。在堆栈上进行内存分配非常有限，因此无法完成。 这就是动态内存分配发挥作用的时候。如果您了解malloc的工作原理，可以按照以下方式修改代码。

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

当你完成了位集的使用，使用delete关键字将其删除。

- taurus05

Answer 4

使用std::vector代替std::bitset来处理大尺寸的数据。

- J.Kraftcheck

---

只有当你知道自己在做什么时，才使用vector<bool>！ - Happy Green Kid Naps

std::vector与bitset相比性能较差，详见：http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf - math

@math：一项有趣的研究，但现在有点过时了。尽管这篇论文只有7年的历史，但当时研究人员使用的MinGW版本大约是3年前的（现在已经10年了）。我想知道对更现代的标准库实现进行基准测试是否会产生不同的结果。此外，该代码未作为研究的一部分发布，因此很难确定基准测试是否可以改进。 - dreamlax