哪种算法最适合非连续索引分组的数组？

Question

我可以帮助您翻译关于IT技术的内容，以下是需要翻译的内容：

我需要一些帮助来编写一个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

然后使用某种索引映射来在查找期间找到索引所在的数组。我的问题是，在插入期间应该寻找什么样的算法来将索引分组？（同时保持良好的空间/时间平衡）

---

编辑： 感谢迄今为止提供的答案。我将要查看的数据将包含一个或两个非常大的索引范围，没有间隙，然后是一个或两个非常大的间隙，然后可能还有几个“散乱”的单个值。此外，数据需要排序，因此哈希表不适用。

- user75832

---

如果您不必专门使用数组，请取索引，将其包装在对象中，并将其用作哈希键。然后，您仍然只能拥有具有该索引的一个对象，并且您不必拥有太多任意大的桶。 - Kylar

FWIW，您可能会发现这里关于我的问题的一些讨论很有趣：https://dev59.com/TUvSa4cB1Zd3GeqPiv2- - Ben Zotto

Answer 1

我相信你正在寻找一个哈希映射表或更普遍的映射表。你可以使用STL提供的map类。

这听起来正是你所需要的内容：

http://www.cplusplus.com/reference/stl/map/

- avirtuos

---

我不知道是谁给我们点了踩，但我已经把你的赞回给你了。我认为没有解释就这样做是不公平的。 - Tesserex

谢谢，我也为你做了同样的事，因为我们似乎看到了相似的问题。 - avirtuos

我猜有些人把地图视为一种“反数组”，但这绝对是 C++ 的正确答案。 - Alexis Wilke

Answer 2

为什么不直接使用哈希表/字典？如果你确实需要这样一个特定的数据结构，我脑海中首先想到的是B树。但可能还有比这更好的解决方案。

- Tesserex

Answer 3

也许你需要的是稀疏向量？试试Boost的实现。

- Paul Mitchell

Answer 4

你要么使用稀疏数组，要么使用某种哈希表，具体取决于情况。一般而言：

1. 如果最终会出现由大量空隙分隔的填充桶的长时间运行，则最好使用稀疏数组，因为它们在这种情况下可以很好地优化内存使用。
2. 如果最终只会在巨大的空洞海中散布条目，则最好使用哈希表。

- swestrup