c++ - C++ 中的可索引跳过列表实现

Question

到目前为止我发现的所有跳跃列表实现都使用键并将它们与值相关联。但我需要的是一个跳跃列表，我可以在其中的索引位置 i 插入一个值，以便所有跟随它的值索引 i 可以用一个递增的索引来查询。

这里有一个小例子来说明:

//pseudocode
//let skipList sk be a list of ints, containing 5 elements.

//insert 6 at index 3
sk.insert(3, 6);

//insert 5 at index 3
sk.insert(3, 5);

//get index 4
int value = sk.get(4);

现在 value 应该是 6，因为在索引 3 处插入了 5，所以值 6 向上移动了一个索引。

可以使用跳跃列表构建这样的数据结构，请参阅此处可索引的跳过列表: http://en.wikipedia.org/wiki/Skip_list

但我找不到实现。拥有这样的数据结构将非常有用，例如在大列表上有很多随机插入和访问的情况下。

Answer 1

您发布的维基百科页面中似乎有一个实现链接: http://code.activestate.com/recipes/576930/

虽然它是 python。

或者，采用现有的 C++ 实现并向其添加链接宽度并实现索引查找。