如果您有一个数据结构的想法,可以用于研究项目,并且想知道它是否已经有名称或STL等效物:
创建一个大小为n
的稀疏数组,作为sqrt(n)
指针的数组。
要在i
插入项,请转到i/sqrt(n)
处的指针。如果该指针为null
,则将其分配给大小为sqrt(n)
的新数组。在位置i mod sqrt(n)
中在新数组中插入您的项。
优点很简单:它允许您创建一个最初只占用O(sqrt(n))
空间的大数组。您可以在恒定时间内访问任何元素,并且它允许您填充数组的部分而无需为所有n
个位置分配空间。
这可能已经用于哈希表存储桶,并且我还有另一种应用方式(在非常大的DNA序列中进行contigs记忆化)。我的问题是:这个有没有名字?有什么常见的实现可以使用吗?