rbitset

一个位集合，能够在整数数组中存储固定数量的布尔值。

这是一个基于 cbitset 的分支，使用 const generics 重新实现了 BitSet 类型

替代方案

已经有很多用于位集合的库，但我似乎找不到一个能够与固定大小数组一起工作的 #![no_std]。大多数库似乎都希望是动态的。

rbitset 也具有 repr(transparent) 功能，这意味着结构的表示形式将与内部数组相同，使其可用于结构表示很重要的地方，例如 relibc。

灵感

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

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

示例

位集合非常便宜。您可以在一个包含 4 个 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()
}