USet 和 UMap

以无符号整数作为键的集合和映射实现。

前提

我相信对于一项工作，使用合适的工具很重要。在某些情况下，通用数据结构和为任何类型的元素以及任何类型的用法设计的特实现，会导致性能不佳和代码不清晰。

这个项目试图为像视频游戏或真实场景模拟这样的场景提供更适合的替代方案 HashSet 和 HashMap。我设想了一个场景，当用户需要处理几百或几千（但不是数十亿）描述场景中对象的复杂数据结构。它们可以创建、修改和删除相当快。它们不持有引用，而是持有指向其他映射中数据结构的标识符。标识符可以是简单的整数，因此数据结构在任何时间点都是已知的尺寸。这允许用户将它们存储在一个或多个映射中，其中无符号整数用作键，检索这些键作为无符号整数集合，操作它们，并最终使用它们来访问数据结构。一组标识符 USet，非常轻量级，如果无法移动所有权，可以轻松地克隆。映射 UMap 可以存储在一个地方，可以从许多其他地方访问，作为原始（ECS）https://en.wikipedia.org/wiki/Entity_component_system 的形式。

实现

实现非常简单：USet 是围绕布尔向量的。它还有一个偏移量，有助于节省内存，还有冗余的最小和最大值，这大大加快了集合上的操作。如果向量的第 n 个元素是 true，从 API 视角来看，这意味着集合包含值 n - 偏移量。

因此，UMap<T> 是围绕一个类型为 Option<T> 的元素向量构建的。如果向量中的第 n 个元素是 Some(t)，从 API 观点来看，这意味着映射包含在标识符 n - 偏移量 下的值 t。

所有这些都意味着 USet 和 UMap 以内存换取 CPU。它们不适合在内存中存储大量条目，但对于较少的条目，基准测试显示与类似功能相比，性能提升了 3.5-4.0 倍。

用法

与 HashSet 和 HashMap 不同，USet 不是 UMap 的子类。这两个紧密合作，但它们的作用略有不同。使用 UMap 的习惯用法是填充它，然后使用 query 或 keys 方法构建满足某些条件的标识符的 USet。然后可以将 USet 遍历并操作（实现的方法有：put、remove、union、交集、差集和异或），然后可以使用结果 USet 或单个标识符再次访问 UMap，以读取、修改或删除数据。

计划改进

这是一个项目的初始 0.1 版本，所以当然还有许多事情要做！ :)

1. 尽量减少代码中的克隆使用。这主要适用于 UMap。对于 0.1 版本，我决定通过在其他解决方案似乎不可能时克隆数据结构来平息借用检查器，但我一直在学习。我希望优化一下代码。
2. 考虑使用 bitvec 而不是 Vec<boolean> 实现 USet。如果它对性能影响太大，我可能决定创建另一个 USet 的实现（例如 UBitSet？），以少量 CPU 功率换取更好的内存使用。
3. 将 UMap 转换成完整的 ECS。再次，这可能意味着我将保留实际的 UMap 如其所示，只有一些小的变化，而我会创建另一个具有更强大功能的实体，它将与 USet 和 UMap 紧密交互。