动态位集通过std::vector存储比特位，支持运行时指定大小和动态扩容。核心设计包括位索引到字索引的映射、按位操作及resize/push_back等动态行为，兼顾内存紧凑与访问效率。
在C++中，std::bitset 是一个非常高效的固定大小位容器，适用于编译时已知长度的场景。但当需要动态调整位数时（例如处理不确定长度的二进制数据、实现布隆过滤器或稀疏位图），std::bitset 就无法满足需求了。这时就需要一个动态位数组——即“动态 bitset”。
动态位集的基本设计思路
动态位集的核心目标是：像 std::vector
我们可以自己实现一个简易但高效的动态位集类，关键点包括：
- 使用 std::vector<unsigned long> 或类似整型数组存储实际比特位
- 提供按位访问、设置、清除、翻转等操作
- 支持 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; }};
立即学习“C++免费学习笔记（深入）”；
空间优化技巧与注意事项
动态位集的优势在于极致的空间利用率，每个布尔值仅占 1 bit，远优于 vector<bool> 的间接开销或 vector<char> 的 8 倍浪费。
- 选择合适的存储类型：使用 uint64_t 能更好控制跨平台一致性
- 延迟初始化：只在真正 set(true) 时分配内存，适合稀疏场景
- 分块压缩：对全0或全1的word做标记，可进一步压缩（如 Roaring Bitmap 思路）
- 避免频繁 push_back：提前 reserve 容量减少重分配
使用建议与替代方案
如果你不想从头实现，可以考虑以下成熟方案：
- Boost.DynamicBitset：功能完整，文档齐全，最推荐的选择
- std::vector<bool>：已有动态特性，但接口受限且性能不一
- 第三方库如 abseil、folly 提供了更高级的位集合结构
自定义实现适合对性能和内存有极致要求的场景，比如嵌入式系统或高频算法竞赛。
基本上就这些。掌握动态位集的设计，不仅能节省内存，还能提升位操作密集型任务的效率。关键是理解位索引到字索引的映射逻辑，以及如何安全地进行位运算。不复杂但容易忽略细节。
