C++怎么实现一个位集(bitset)的动态版本_C++动态位数组与空间优化

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个位集(bitset)的动态版本_C++动态位数组与空间优化

2025-11-20

浏览次数：次

返回列表

动态位集通过std::vector存储比特位，支持运行时指定大小和动态扩容。核心设计包括位索引到字索引的映射、按位操作及resize/push_back等动态行为，兼顾内存紧凑与访问效率。

c++怎么实现一个位集(bitset)的动态版本_c++动态位数组与空间优化

在C++中，std::bitset 是一个非常高效的固定大小位容器，适用于编译时已知长度的场景。但当需要动态调整位数时（例如处理不确定长度的二进制数据、实现布隆过滤器或稀疏位图），std::bitset 就无法满足需求了。这时就需要一个动态位数组——即“动态 bitset”。

动态位集的基本设计思路

动态位集的核心目标是：像 std::vector 一样支持运行时指定大小，并能动态扩容，同时保持内存紧凑和访问高效。

我们可以自己实现一个简易但高效的动态位集类，关键点包括：

使用 std::vector 或类似整型数组存储实际比特位
提供按位访问、设置、清除、翻转等操作
支持 push_back、resize 等动态操作
尽量复用 STL 接口风格，便于使用

一个轻量级动态位集实现示例

#include <vector>
#include <cstddef>
#include <stdexcept>
<p>class dynamic_bitset {
private:
std::vector<unsigned long> data;
size_t num_bits;</p><pre class='brush:php;toolbar:false;'>static constexpr size_t bits_per_word = sizeof(unsigned long) * 8;

size_t word_index(size_t pos) const { return pos / bits_per_word; }
size_t bit_offset(size_t pos) const { return pos % bits_per_word; }
unsigned long bit_mask(size_t pos) const { return 1UL << bit_offset(pos); }

public: explicit dynamic_bitset(size_t n = 0) : num_bits(n) { data.resize((n + bits_per_word - 1) / bits_per_word, 0); }

void resize(size_t new_size) {
    size_t old_words = (num_bits + bits_per_word - 1) / bits_per_word;
    num_bits = new_size;
    size_t new_words = (new_size + bits_per_word - 1) / bits_per_word;
    data.resize(new_words, 0);

    // 可选：如果缩小，清除多余位
    if (new_size < num_bits) {
        size_t last_bit = bit_offset(new_size);
        if (last_bit != 0) {
            data[new_words - 1] &= (1UL << last_bit) - 1;
        }
    }
}

bool operator[](size_t pos) const {
    return (data[word_index(pos)] & bit_mask(pos)) != 0;
}

void set(size_t pos, bool value = true) {
    if (value)
        data[word_index(pos)] |= bit_mask(pos);
    else
        data[word_index(pos)] &= ~bit_mask(pos);
}

void reset() {
    std::fill(data.begin(), data.end(), 0);
}

void push_back(bool value) {
    if (bit_offset(num_bits) == 0) { // 需要新 word
        data.push_back(0);
    }
    set(num_bits++, value);
}

size_t size() const { return num_bits; }
bool empty() const { return num_bits == 0; }

};