c++ - 哪种算法最适合具有索引分组的非连续数组？

Question

我需要一些帮助来用 C/C++ 编写算法(尽管任何语言示例都可以)。目的是一个容器/数组，它允许在任何索引处插入。但是，如果在不靠近现有索引的索引中插入元素，即会导致大量空桶空间。然后数组会最小化空桶。

假设您有一组元素需要插入到以下索引处:

14
54
56
57
12
8
6
5678

一个连续的数组会产生一个数据结构。像这样:

0
1
2
3
4
5
6 val
7
8 val
9
10
11
12 val
...

但是，我正在寻找一种解决方案，当索引不在其最近邻居的 x 个存储桶内时创建一个新数组。

像这样:

Array1
6 val
7 
8 val
10
11
12 val
13
14 val

Array2
54 val
56 val
57 val

Array 3
5678 val

然后在查找期间使用某种索引映射来查找索引所在的数组。我的问题是在插入过程中我应该使用哪种算法将索引组合在一起？ (同时仍然保持良好的空间/时间权衡)

---

编辑:感谢您到目前为止的回答。我要查看的数据将包含一个或两个非常大的索引范围，没有间隙，然后是一个或两个非常大的间隙，然后可能是几个“散乱的”单个值。还需要对数据进行排序，所以哈希表就出来了。

Answer 1

为什么不直接使用哈希表/字典呢？如果你真的需要这么具体的东西，我首先想到的是 B tree.但可能还有比这更好的解决方案。