4

我正在尝试使用位过滤器存储一个非常大的搜索掩码。

两者都std::vector<bool>将std::bitset<n>它们的 bool 表示形式存储为位，这与通常为 achar或大小的普通 bool 不同int32_t。

问题是这两种数据结构都将它们的元素存储在一个巨大的块中。操作系统因为我请求太大的块而生我的气。要做的一件事std::deque<bool>是将其元素存储在我认为的链表之类的东西中。

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

所以告诉我这种类型的结构是否存在于某个地方，或者甚至是可能的。

4

3 回答 3

4

我不知道您的问题有任何直接解决方案，但可以通过自定义容器轻松解决。

一种解决方案将简单地涉及 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-27T00:23:05.633 回答
1

具有所需“块”类（例如，为方便起见，无符号字符[N]，或包装类（甚至位集））的专用双端队列/队列具有自定义相等性和对相应块进行操作的按位运算符可以实现此目的。

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

一般的想法是将位掩码拆分为块并对这些块序列进行操作，因为根据内存碎片，您可能无法在运行时分配 2GB 或更多的连续内存。当然，块大小越小，处理开销、缓存一致性降低和内存碎片就越多，但是，在您的客户端应用程序中，您可能能够从内存中挤出更多内存。

正如@Crog 提到的那样，似乎已经有一个实现：boost::dynamic_bitset

于 2013-02-27T00:10:34.307 回答
1

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

于 2013-02-27T00:11:23.147 回答