cbitset

能够在一个整型数组中保持一定数量的布尔值。

替代方案

已经有了很多位集库，但我似乎找不到一个能够与固定大小数组一起工作的 #![no_std] 库。它们中的大多数似乎都想要动态的。

cbitset 还也是 repr(transparent)，这意味着结构的表示形式保证与内部数组相同，使其可以在结构表示形式很重要的地方使用，例如 relibc。

灵感来源

我认为这在 C 中相对常见，因为我偶然在 MUSL 标准库中发现了这个概念。一个例子是在 strspn 中的使用。

虽然这是一个相对简单的概念，但实现可能相当难以阅读。所以也许应该使用某种……零成本抽象来将其抽象化？

示例

位集非常便宜。你可以在一个 4x 64 位数字的数组中存储从 0 到 255 的任何数字。理论上查找应该是 O(1)。这里有一个使用这个库的 strspn 示例。这是在 Rust 中使用此库的方式

/// The C standard library function strspn, reimplemented in rust. It works by
/// placing all allowed values in a bit set, and returning on the first
/// character not on the list. A BitSet256 uses no heap allocations and only 4
/// 64-bit integers in stack memory.
fn strspn(s: &[u8], accept: &[u8]) -> usize {
    let mut allow = BitSet256::new();

    for &c in accept {
        allow.insert(c as usize);
    }

    for (i, &c) in s.iter().enumerate() {
        if !allow.contains(c as usize) {
            return i;
        }
    }
    s.len()
}