sparseset

Rust 中的稀疏集实现。

稀疏集是一种专门的数据结构，用于表示一组整数。在某些非常狭窄和特定的场景中非常有用，即当可能值的范围非常大但使用得非常少，并且集合经常迭代或经常清除时。

在这个实现中，SparseSet 可以为集合中的每个整数（键）存储任意值。

使用 Cargo 进行使用

[dependencies]
sparseset = "1.0.1"

示例

use sparseset::SparseSet;
let mut set = SparseSet::with_capacity(128);
set.insert(42, 3);
set.insert(77, 5);
set.insert(23, 8);

assert_eq!(*set.get(42).unwrap(), 3);

set.remove(42);
assert!(!set.get(42).is_some());

for entry in set {
    println!("- {} => {}", entry.key(), entry.value);
}

性能

请注意，SparseSet 在空间方面非常不高效。O(1) 插入时间假设元素的空间已经分配。否则，大键可能需要大量的重新分配，这与集合中的元素数量没有直接关系。SparseSet 应仅考虑用于小键。

运行时复杂度

查看 SparseSet 与 Hash 和 Btree maps 的运行时复杂度的比较

• 清除对于简单类型是 O(1)，对于实现了 Drop 的类型是 O(n)。
• 迭代非常高效，它是在密集数组上迭代。事实上，甚至可以获取集合条目的（甚至是可变的）切片。

有关更多详细信息，请参阅 http://research.swtch.com/sparse。