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

Question

在我的程序中，我需要检查我是否已经在一组 2.5*10^9 中生成了一个值。我希望生成大约一半的集合，并且需要有一种快速的方法来检查和更新它。在我看来，bitset 是一个好主意，因为它不需要太多内存（每个值 1 位）并且速度很快。

问题是，当我在课堂上定义我的集合时，我得到了一个segmentation fault，因为尺寸太大（它适用于较小的尺寸）。

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

任何的想法 ？

谢谢

PS：如果可能的话，我宁愿不使用外部库。我已经在使用GMP，但我认为他们没有针对大量数字设置的实现。

Answer 1

这可能不是您的问题，但请尝试使用 new 分配堆上的位集，而不是使用堆栈。

一些系统限制了堆栈的大小，这可能是给您带来问题的原因。

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

Answer 3

这将导致分段错误，因为这里的内存是在堆栈而不是堆上分配的。堆栈上的内存分配非常有限，因此无法这样做。这时候动态内存分配就派上用场了。如果您了解 malloc 的工作原理，则可以按如下方式修改您的代码。

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

完成 bitset 后，使用 delete 关键字将其删除。

Answer 4

对于大尺寸，使用 std::vector 而不是 std::bitset。