是否有一个deque类在C ++中的BitSet？ [英] Is there a deque-like bitset in C++?

问题描述

我试图来存储一个非常大的搜索屏蔽带位的过滤器。

I am trying to store a very large search mask with a filter of bits.

两者的std ::矢量＆lt;布尔＆GT; 和和std :: bitset＆LT; N＆GT; 存储他们的布尔重新presentations为位，这是一个正常的布尔不同通常是一个字符或的int32_t 的大小。

Both std::vector<bool> and std::bitset<n> store their bool representations as bits, which is different from a normal bool which is usually the size of a char or int32_t.

问题是这两个数据结构存储它们的元素在内存中一个巨大的块。该操作系统是为请求太大块让我生气。有一件事的std :: deque的＆LT;布尔方式＆gt; 做的是保存它的元素像一个链表我觉得

The problem is both of those data structures store their elements in memory in one giant block. The operating systems are getting mad at me for requesting blocks that are too big. One thing std::deque<bool> does is store its elements in something like a linked list I think.

现在我知道你不能用一个指向单个位不转移，并使用链表结构类型击败内存保护的目的。但是，你可以存储喜欢的2gig块的char [] ，利用转移来设置各个位，然后一个链接指向另一个2GB块，你挖？

Now I know you cannot use a pointer to a single bit without shifting, and using a linked list type structure defeats the purpose of memory conservation. But you could store like a 2gig block of char[], use shifts to set individual bits, and then a linked pointer to another 2gb block, you dig?

所以，如果这种类型的结构存在某处或者甚至可以告诉我。

So tell me if this type of structure exists somewhere or is even possible.

推荐答案

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

I don't know of any direct solution to your problem but it could easily be resolved by a custom container.

解决方案之一woudl只是涉及的std ::性病的双端队列::位集。凡位集合的大小是2，如256动力有了这个，你可以走索引，只是屏蔽掉的双端队列指数和单独的bitset指数：

One solution woudl simply involve std::deque of std::bitset. Where the size of the bitset is a power of 2 such as 256. With this you can take the index and just mask off the deque index and bitset index individually:

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

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

这也可以在类中被封装为方便：

This could also be encapsulated within a class for convenience:

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

这篇关于是否有一个deque类在C ++中的BitSet？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！