RampTable

本软件包形式化了一个我在很多情况下都遇到过的数据结构。我从未看到过这个数据结构以自己的形式被处理。相反，我只看到它在许多代码库中被隐式使用，从未被命名。也许它确实有一个名字并且广为人知，但我还没有找到任何关于它的讨论。（如果你知道它，请告诉我。）

梯形表是一个用于存储一系列列表的特定表示。这些集合是编号的，并且（非负）数字靠近零。理想情况下，集合编号是连续的，或者接近连续。每个集合映射到一个项的列表。

该表示使用两个向量：index 和 values。每个 index 数组条目对应一个集合编号（也称为 键）。在 index 数组的末尾还有一个额外的条目，它与任何集合都不相关，但用来结束 index 向量。

index[key] 返回该键值在 values 中的起始索引。 index[key + 1] 返回该键值在 values 中的结束索引（不包括）。因此，&values[index[key]..index[key + 1]] 给出了该键值的值切片。

现在你可能会说：“哦，那个数据结构？每个人都知道。” 没错！它非常常见，到处都在使用。然而，通常我看到的这个数据结构是直接在应用程序中编写的，所以一开始很难识别它。将数据结构形式化并给它命名也是很有用的。这也有助于提高可读性。

我曾在以下情况中看到这个数据结构被使用

* graphviz (SparseMatrix, lots of other things)
* Berkeley YACC (storing all kinds of things)
* and many more