快速std :: vector <bool>重置

debugcn 发表于 Dev

阿迪·沙维特（Adi Shavit）

我有一个很的，其大小仅在运行时（即没有已知位（以百万计的“存在”位10秒）的大载体std::bitset），但实际使用之前已知的，因此容器可预先分配。

该向量最初是全零，并且以单个，增量，稀疏和随机的方式设置。我对这个容器的唯一使用是直接随机访问-检查“状态”（没有STL）。在尝试了几种替代容器之后，这似乎std::vector<bool>很适合我的需求（尽管存在概念上的问题）。

偶尔我需要重置此向量中的所有位。
由于它是如此之大，所以我无法完全重置其所有元素。但是，我知道所有设置位的索引，因此可以单独重置它们。

由于std::vector<bool>将bools表示为位，因此每次此类重置都涉及额外的移位和其他此类调整操作。

是否有（便携式）方式进行“粗略”，低精度的重置？
一个将重置我请求的位所属的整个整数，从而避免任何额外的额外操作的方法？

丹维尔

方法1“密集”：

如果你需要一个“密”容器我会建议你使用的混合物vector和bitset。

我们将位存储为位组序列，因此可以bitset::reset在每个“块”上使用以将它们全部重置。DynamicBitset::resize可用于为正确的位数腾出空间。

class DynamicBitset
{
private:
    static const unsigned BITS_LEN = 64; // or 32, or more?
    typedef std::bitset<BITS_LEN> Bits;
    std::vector<Bits> data_;
public:
    DynamicBitset(size_t len=0) {
        resize(len);
    }
    // reset all bits to false
    void reset() {
        for(auto it=data_.begin(); it!=data_.end(); ++it) {
            it->reset(); // we can use the fast bitfield::reset :)
        }
    }
    // reset the whole bitset belonging to bit i
    void reset_approx(size_t i) {
        data_[i/BITS_LEN].reset();
    }
    // make room for len bits
    void resize(size_t len) {
        data_.resize(len/BITS_LEN + 1);
    }
    // access a bit
    Bits::reference operator[](size_t i) {
        size_t k = i/BITS_LEN;
        return data_[k][i-k*BITS_LEN];
    }
    bool operator[](size_t i) const {
        size_t k = i/BITS_LEN;
        return data_[k][i-k*BITS_LEN];
    }
};

方法2“稀疏”：

如果存储只有极少数的位，你也可以去用的混合物map和bitset。

在这里，我们仅在其中至少设置了位的情况下存储块。这需要访问位，因此需要额外的开销，因为我们需要查找std::map具有的O(log N)，但是占用的内存少得多。

此外，功能重置功能完全符合您在问题中所说的内容-它仅涉及您已设置的区域。

SparseDynamicBitset 当您有很长的位序列（始终为false）时，例如对于1000 ... 000100 ... 010，而不是0101000111010110，则是一个不错的选择。

class SparseDynamicBitset
{
private:
    static const unsigned BITS_LEN = 64; // ?
    typedef std::bitset<BITS_LEN> Bits;
    std::map<unsigned,Bits> data_;
public:
    // reset all "stored" bits to false
    void reset() {
        for(auto it=data_.begin(); it!=data_.end(); ++it) {
            it->second.reset(); // uses bitfield::reset :)
        }
    }
    // access a bit
    Bits::reference operator[](size_t i) {
        size_t k = i/BITS_LEN;
        return data_[k][i-k*BITS_LEN];
    }
    bool operator[](size_t i) const {
        size_t k = i/BITS_LEN;
        auto it = data_.find(k);
        if(it == it.end()) {
            return false; // the default
        }
        return it->second[i-k*BITS_LEN];
    }
};