.NET库中是否存在稀疏数组实现？

Question

是否已经在.NET库中实现了像稀疏数组(大多数索引为空)的数据结构,其中O(1)通过索引访问,O(1)访问下一个(和前一个)元素？

Answer 1

几年前，我基于我的“AList”概念实现了一个稀疏集合。它称为SparseAList，它可能比您自己推出的任何“简单”解决方案都要好。例如，@NathanPhilips 的解决方案Insert具有RemoveAt调用ToDictionary. Enumerable.ToDictionary是一个 O(N) 方法 - 它“从头开始”重新生成整个字典 - 所以效率不高。

相比之下， SparseAList基于B+ 树，因此它具有高效的 O(log N) 插入、查找和删除，并且还可以高效地使用内存。它包含在LoycCore的 Loyc.Collections.dll 中，可以在 NuGet 上找到（搜索 Loyc.Collections）。