我有一个场景，我正在将更改列表推送到另一个系统。每个列表包含零个或多个插入、更新或删除的通知。
插入很容易；通知包含目标索引和指向项目的指针。更新很容易；我传递一个指向该项目的指针。
删除似乎很简单；我需要传递要删除的项目的索引，但是我怎么知道索引呢？索引从零开始并且必须是连续的，但我在插入时将它们组合起来。所以我需要跟踪我为每个项目编制的索引。
例如，我可以使用 map 来做到这一点:std::map<item*, int> ，但是当我删除一个项目时，我必须重新编号过去的所有内容，这是 O(N)。
这些项目列表将大到无法接受 O(N) 迭代的程度。我确信这个问题已经解决了，我只是不知道解决方案会被称为什么。搜索与“链表”相关的任何内容都会产生大量噪音。
一个可能的解决方案是跳表，其中子列表中的每个节点都知道它跳过了主列表中的多少个节点，并且由于搜索跳表的时间复杂度为 O(log N)，我们可以随时跟踪并找到O(log N) 中的索引并删除 O(log N) 中的项目。
然而，在这里实现跳过列表似乎有点矫枉过正……有没有更简单的解决方案？
编辑:
感谢大家的建议，但我想我已经说服自己跳过列表是解决这里问题的正确方法。
最佳答案
参见 Finger Trees: A Simple General-purpose Data Structure由 Hinze 和 Paterson 撰写。
另请参阅 MarkCC 的 blog post on finger trees 中的漂亮插图.
关于c++ - 在优于 O(n) 的时间内找到链表中条目的索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1794919/