c++ - 是否有对两位值的 std::bitset 的概括？

Question

假设我是一名基因组科学家，试图存储极长的字符串，每个字符串代表两位信息(即每个元素是 G、A、T 或 C)。因为字符串非常长，所以我需要能够以精确的 2N 位(或者更确切地说，N/4 字节)存储长度为 N 的字符串。

考虑到这种动机，我正在寻找 std::bitset 的概括(或 boost::dynamic_bitset<> )适用于两位值而不是一位值。我要存储N这样的两位值，每个值可以是 0、1、2 或 3。我需要在内存中尽可能紧密地打包数据，所以 vector<char>将不起作用(因为它浪费了 4 倍的内存)。

实现我的目标的最佳方式是什么？一种选择是用定制的 operator[] 包装现有的位集模板。 、迭代器等，但如果可能的话，我更愿意使用现有的库。

Answer 1

std::bitset<>是固定长度的，您可能不希望这样。

我认为你应该继续包装 std::vector<bool> .

请注意 std::vector<bool> 针对空间进行了优化，但具有大小动态的优势。据推测，您需要从某处读取任意长度的基因组。

考虑一下您是否需要大量的 API 来访问它；您可能只需要几种方法。

@Jeffrey 的回答已经涵盖了相关代码，if for bitset<> .

[我不熟悉boost::dynamic_bitset<>以及它可能放弃的东西vector .]

一个进一步的想法是，使用四边形字母是否方便，一个四边形很好地填充了空间中的一个字符。

class Genome
{
public:
    enum class Letter {A,C,G,T};
    Genome(const std::string& source)
    {
        code_.resize(source.size() * 2);
        for (unsigned index = 0; index != source.size(); ++index)
        {
            char text = source[index];
            Letter letter = textToLetter(text);
            set(index, letter);
        }
    }  
    static Letter textToLetter(char text)
    {
        // Or search through the array `letterText`.
        // Or come up with a neat but unintelligible one liner ...
        Letter letter = Letter::A;
        switch (text)
        {
        case 'A':
            letter = Letter::A;
            break;
        case 'C':
            letter = Letter::C;
            break;
        case 'G':
            letter = Letter::G;
            break;
        case 'T':
            letter = Letter::T;
            break;
        default:
            // Invalid - handle error.
            break;
        }
        return letter;
    }
    static char letterToText(Letter l) 
    {
        return letterText[(unsigned)l];
    }
    // Add bounds checking
    Letter get(unsigned index) const
    {
        unsigned distance = index * 2;
        char numeric = code_[distance] + code_[distance + 1] * 2;
        return Letter(numeric);
    }
    // Add bounds checking
    void set(unsigned index, Letter value)
    {
        unsigned distance = index * 2;
        bool low = (unsigned)value & 1;
        bool high = (bool)((unsigned)value & 2);
        code_[distance] = low;
        code_[distance + 1]  = high;
    }
    unsigned size()
    {
        return code_.size() / 2;
    }
    // Extend by numLetters, initially set to 'A'
    void extend(unsigned numLetters)
    {
        code_.resize(code_.size() + numLetters * 2);
    }
private:

    static char letterText[4];
    std::vector<bool> code_;
};

char Genome::letterText [4] = { 'A', 'C', 'G', 'T' };

int main()
{
    Genome g("GATT");
    g.extend(3);
    g.set(5, Genome::Letter::C);
    for (unsigned i = 0; i != g.size(); ++i)
        std::cout << Genome::letterToText(g.get(i));
    std::cout << std::endl;
    return 0;
}