位操作容器選型指南
| 特性 | std::bitset<N> | std::vector<bool> |
|---|
| 大小確定性 | 編譯期常量 N | 運行期動態調整 |
| 內存佈局 | 連續位數組 (壓縮存儲) | 專用代理引用 (壓縮存儲) |
| 隨機訪問 | `operator[]` 返回 `bool`/`reference` | `operator[]` 返回代理引用 |
| 位運算 | 內置 `&` `|` `^` `~` `<<` `>>` | 無內置，需手動實現 |
| 計數/查找 | `count()` `any()` `none()` `all()` `_Find_first/next` | 需算法實現 |
| 轉換 | `to_string()` `to_ulong()` `to_ullong()` | 需手動轉換 |
| 適用場景 | 固定大小標誌集、權限掩碼、狀態機 | 動態位集合、稀疏位陣列、運行期大小 |
std::bitset 完整實戰
基本操作
b4(std::string("1010")); // 從 string 對象
// 訪問
bool bit3 = b2[3]; // 第 3 位 (最低位為 0)
b2[5] = 1; // 設置第 5 位
b2.set(2); // 設置第 2 位
b2.reset(1); // 清除第 1 位
b2.flip(0); // 翻轉第 0 位
// 批量操作
b2.set(); // 全置 1
b2.reset(); // 全清 0
b2.flip(); // 全翻轉
// 查詢
size_t cnt = b2.count(); // 1 的個數
bool any = b2.any(); // 是否有 1
bool none = b2.none(); // 是否全 0
bool all = b2.all(); // 是否全 1
// 位運算
std::bitset<8> a("11110000");
std::bitset<8> b("10101010");
auto c = a & b; // 10100000
auto d = a | b; // 11111010
auto e = a ^ b; // 01011010
auto f = ~a; // 00001111
auto g = a << 2; // 11000000
auto h = a >> 1; // 01111000
// 轉換
std::string str = a.to_string(); // "11110000"
unsigned long ul = a.to_ulong(); // 240
unsigned long long ull = a.to_ullong();
// 輸出
std::cout << a << '\n'; // 直接輸出二進制字符串
}
進階技巧：_Find_first/_Find_next (GCC/Clang 擴展)
實戰：權限掩碼系統
#include
#include
void vector_bool_demo() {
std::vector v1(10); // 10 個 false
std::vector v2(10, true); // 10 個 true
std::vector v3(v2); // 拷貝構造
v1[0] = true; v1[1] = false; v1[2] = true;
v1.push_back(true); // 動態增長
// 遍歷 (注意：不能取地址 &v1[0])
for (size_t i = 0; i < v1.size(); ++i) {
std::cout << v1[i] << ' ';
}
std::cout << '\n';
// 範圍 for (C++11)
for (bool b : v1) std::cout << b << ' ';
// 翻轉
v1.flip(); // 成員函數 (C++11)
// 交換
std::vector v4(5, true);
v1.swap(v4); // O(1) 交換內部指針
}
代理引用機制深度解析
class BloomFilter {
std::vector bits;
size_t hashCount;
public:
BloomFilter(size_t size, size_t k) : bits(size), hashCount(k) {}
// 簡單哈希函數族
size_t hash(const std::string& s, size_t seed) const {
size_t h = seed;
for (char c : s) h = h * 31 + c;
return h;
}
void add(const std::string& item) {
for (size_t i = 0; i < hashCount; ++i) {
size_t pos = hash(item, i) % bits.size();
bits[pos] = true;
}
}
bool mightContain(const std::string& item) const {
for (size_t i = 0; i < hashCount; ++i) {
size_t pos = hash(item, i) % bits.size();
if (!bits[pos]) return false;
}
return true; // 可能存在 (有偽陽性)
}
};
性能對比測試
: "
<< std::chrono::duration_cast(t2-t1).count() << "ms\n";
std::cout << "raw uint64_t: "
<< std::chrono::duration_cast(t3-t2).count() << "ms\n";
// 典型結果：手寫位運算快 2-5x，vector 代理引用有開銷
}
選型決策樹
需要位操作？
├─ 大小編譯期固定？
│ ├─ 是 → std::bitset
│ │ ├─ 需要高級查詢 (count/any/none/all) → bitset 完勝
│ │ ├─ 需要位運算 (& | ^ ~ << >>) → bitset 完勝
│ │ └─ 需要轉字符串/整數 → bitset 完勝
│ └─ 否 → 運行期動態大小
│ ├─ 需要頻繁增減/插入刪除 → vector
│ ├─ 需要 STL 算法兼容 (sort/find 等) → vector (有限支持)
│ └─ 純位操作、極致性能 → 手寫 uint64_t[] / boost::dynamic_bitset
└─ 只是存 bool 值？
├─ 固定大小 → std::array / std::vector (避免代理開銷)
└─ 動態大小 → std::vector / std::deque (非壓縮，訪問更快)
boost::dynamic_bitset：兩全其美
