logo标签列表

我需要创建一个非常大的位/布尔值数组。我该如何在C/C++中实现？

c++carraysbitset
4
有没有可能创建一个超过100000000个元素的位数组？如果可以，我该如何做呢？我知道对于char数组，我可以这样做：
char* array;
array = (char*)malloc(100000000 * sizeof(char));
如果我通过char array[100000000]来声明数组，那么会出现分段错误，因为已经超过了最大元素数，这就是为什么要使用malloc的原因。
是否有类似于位数组的方法呢？
在什么情况下，您实际上需要在单个位置使用那么多位？ - Dennis Zickefoose
1
精确副本 - 同一用户 - 昨天：https://dev59.com/9XE85IYBdhLWcg3w9ohJ - Paul R
抱歉如果问题看起来相似，但实际上并不完全相同。之前我问了如何一般性地定义一个位数组。现在我想问的是如何定义一个非常大的位数组（即比通常定义数组的标准方式允许的元素更多）。 - Eddy
你可能正在尝试在堆栈上创建它。如果你创建了一个这么大的全局变量，它可能会起作用。 如果你需要创建一个数据结构，其大小超过了目标的size_t，那么你需要研究将数据的部分存储在辅助存储器（文件）中。根据你的使用模式，有几种文件结构可能适合你。查找“B树”。 - nategoose
9个回答
12
如果您正在使用 C++，std::vector<bool> 会被专门用于将元素封装成位图。当然，如果您正在使用 C++，则需要停止使用 malloc。
2
使用 vector<bool> 时，请注意它不符合STL的容器概念，这可能会在使用STL算法时导致问题。请参阅http://www.sgi.com/tech/stl/bit_vector.html。 - Björn Pollex
我曾经忘记了 std::vector<bool> 这个特化的存在。很好的提醒。 - cpalmer
你所说的“专业化”是什么意思？ - Eddy
@Eddy：我得先解释一下什么是模板。你以前用过模板吗？ - Ben Voigt
@Eddy：在这种情况下，“Specialized”只是指对于布尔数据类型，vector不使用通用的向量实现。这将会在常见的架构和编译器上浪费每个条目7至63位的数据。vector<bool>的实现方式与我前几天告诉你如何在C中实现它的方式相同。 - nategoose
8

您可以尝试查看boost::dynamic_bitset。然后，您可以像以下示例（取自Boost的示例页面）中所示执行以下操作：

boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;

位集合将为每个元素使用一个位，因此您可以在4字节的空间中存储32个项目，大大减少所需的内存量。
这样会行吗？大多数C++编译器不会尝试在栈上分配x，因为栈没有足够的空间来容纳如此大的对象。栈通常只有1MB左右。我认为你可能需要使用new从堆中分配它。 - Charles E. Grant
3
@Charles：变量x将存在于栈中，但存储其位的内存不会。与vector相似，boost::dynamic_bitset接受一个分配器模板参数，默认使用new进行分配。在标准C++中，没有办法将大小在编译时未知的任何内容放入栈中。 - Steve Jessop
x在堆栈上，但这并不意味着x的成员也在堆栈上。 - Dennis Zickefoose
1
@Dennis：x的成员也在堆栈上...但这并不意味着一些成员不能是指向动态分配内存的指针。 - UncleBens
5

在C和C++中，char是最小的类型。您不能直接声明一个位数组。但是，由于任何基本类型的数组基本上都是由位组成的，您可以模拟它们，类似于以下方式（代码未经测试）：

unsigned *array;
array = (unsigned *) malloc(100000000 / sizeof(unsigned) + 1);

/* Retrieves the value in bit i */
#define GET_BIT(array, i) (array[i / sizeof(unsigned)] & (1 << (i % sizeof(unsigned))))

/* Sets bit i to true*/
#define SET_BIT(array, i) (array[i / sizeof(unsigned)] |= (1 << (i % sizeof(unsigned))))

/* Sets bit i to false */
#define CLEAR_BIT(array, i) (array[i / sizeof(unsigned)] &= ~(1 << (i % sizeof(unsigned))))
4
您遇到的段错误是由于堆栈空间不足引起的。当然，在具有大约4 MB堆栈的线程中声明一个大小为12.5 MB（1亿位）甚至100 MB（1亿字节）的本地变量都是不可能的。虽然可以作为全局变量工作，但这可能会导致12或100 MB的可执行文件 - 这仍然不是个好主意。对于像这样的大缓冲区，动态分配绝对是正确的做法。
3
如果允许使用STL，我会使用 std::bitset。对于100,000,000个位，它将使用100000000 / 32个unsigned int，每个存储32位。 std::vector<bool>，已经提到的另一个好解决方案。
1

有几种方法可以在C++中创建位图。

如果您已经在编译时知道位图的大小，则可以使用STL的std::bitset模板。

以下是使用bitset的方法：std::bitset<100000000> array

否则，如果位图的大小在运行时动态更改，则可以使用std::vector<bool>或boost::dynamic_bitset，如此处所建议http://en.cppreference.com/w/cpp/utility/bitset（请参见底部的注释）。

你的回答没有包含任何代码，链接也没有上下文。请参考http://stackoverflow.com/help/how-to-answer。 - A.L
0

是的，但它会变得有点更加复杂！

存储位的更好方法是将位用于字符本身！

因此，您可以在一个字符中存储8个位！

这将“仅”需要12,500,000个八位字节！

这里有一些关于二进制的文档：http://www.somacon.com/p125.php

你应该在谷歌上搜索 :)

6
对你来说，一切都是令人兴奋的！ :) - John Dibling
0

其他解决方案：

unsigned char * array;
array = (unsigned char *) malloc ( 100000000 / sizeof(unsigned char) + 1);
bool MapBit ( unsigned char arraybit[], DWORD position, bool set)
{
    //适用于4294967295位位置的0
    //计算位位置
    DWORD bytepos = ( position / 8 );
    //
    unsigned char bitpos =  ( position % 8);
 unsigned char bit = 0x01;
//获取位
    if ( bitpos )
    {
        bit = bit << bitpos;
    }
if ( set )
    {
        arraybit [ bytepos ] |= bit;
    }
    else
    {
        //获取
        if ( arraybit [ bytepos ] & bit )
            return true;
    }
return false;
}
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接