c++ - C++ 中是否有类似双端队列的位集？

Question

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

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

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

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

所以请告诉我这种类型的结构是否存在于某处或者是否可能。

Answer 1

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

一个解决方案将简单地涉及 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;
}