C++中是否存在类似deque的bitset？

我试图存储一个非常大的搜索掩码与位过滤器。C++中是否存在类似deque的bitset？

两个std::vector<bool>和std::bitset<n>存储他们的布尔表示为位，这是从一个正常的布尔它通常是一个或char的int32_t大小不同。

问题是这些数据结构都将它们的元素存储在一个巨块中的内存中。操作系统因为要求太大的块而生气。 std::deque<bool>所做的一件事就是将它的元素存储在我想的链表中。

现在我知道你不能使用一个指针指向一个位而没有移位，并且使用链表类型结构会破坏内存保护的目的。但是您可以像char[]这样的2gig块存储，使用移位来设置单个位，然后指向另一个2gb块的链接指针，您会挖掘它吗？

那么告诉我，这种类型的结构是否存在或甚至是可能的。

来源

2013-02-26 y2k

面罩能否长出？或者你知道它在编译时的大小吗？ – 2013-02-26 23:55:16

直到运行时才知道大小，所以它在技术上必须是动态的bitset。 Boost在图书馆里有一个。 – y2k 2013-02-26 23:57:37

您可能也想尝试boost :: dynamic_bitset，但我认为这与长期运行的std :: vector 类似。 – Crog 2013-02-27 00:17:14

我不知道任何直接解决您的问题，但它可以很容易地通过自定义容器来解决。

一个解决方案woudl只涉及std :: bitset的std :: deque。凡bitset的大小是2，如256电源有了这个，你可以采取的指标，只是屏蔽掉deque的指数和单独的bitset指数：

std::deque< std::bitset<256> > ; 
unsigned long long = 1500; 

bool val = bigBitset[ index>>8 ][ index & 0xFF ];

这可能也是一类被封装为方便：

class DequeBitset : public std::deque< std::bitset<256> > 
{ 
public: 
    struct Index 
    { 
     unsigned long index; 

     unsigned long dequeIndex() const { return index>>8; }  
     unsigned long bitsetIndex() const { return index&0xFF; } 
     Index(unsigned long index) : index(index) {} 
    }; 
public: 

    bool operator[](const Index& index) 
    { return std::deque< std::bitset<256> >::operator [](index.dequeIndex())[ index.bitsetIndex() ]; } 
}; 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    DequeBitset test; 
    test.resize(10); 
    bool val = test[259]; 
    return 0; 
}

来源

2013-02-27 00:23:05 Crog

这很优雅。 – 2013-02-27 00:33:08

为了方便起见，用自定义相等和按位运算符对相应块进行操作的deque/queue专门用了所需的“块”类（例如unsigned char [N]或包装类（甚至是bitset））做到这一点。

那些自定义按位方法需要通过将操作的每个输入“全局”位索引转换为取决于修改操作的一组（块编号，块本地）索引来确定要操作的块/范围。非修改操作/查询可以作为遍历所有块的简单遍历来实现。

总体思路是将位掩码分割成块并对这些块序列进行操作，因为根据内存碎片，您可能无法在运行时上分配2GB或更多的连续内存。当然，块大小越小，处理开销越多，缓存一致性越低，内存碎片越少，但是，在客户端应用程序中，您可能会挤出更多的内存，也就是内存。

好像已经有一个这样的执行情况@Crog提到：boost::dynamic_bitset

来源

2013-02-27 00:10:34

我不知道你能有多少块2GB的使用。但是，假设您需要2048个2GB的块。那么为什么不把指向2GB块的指针存储在一个向量中，即std::vector<uint8_t*>，并将新的2GB块添加到这个向量中，因为需要扩展结构。

来源

2013-02-27 00:11:23 perreal

C++中是否存在类似deque的bitset？

回答

相关问题