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？

回答

相關問題