在 O(n) 时间内找到链表中条目的索引

Question

我有一个场景，我将更改列表推送到另一个系统。每个列表包含零个或多个插入、更新或删除的通知。

插入很容易；该通知包含目标索引和指向该项目的指针。更新很容易；我传递了一个指向该项目的指针。

删除看起来很简单；我需要传递要删除的项目的索引，但是我如何知道索引呢？索引从零开始并且必须是连续的，但我在插入时弥补它们。所以我需要跟踪我为每个项目建立的索引。

例如，我可以使用地图来做到这一点： std::map<item*, int>, ，但是当我删除一个项目时，我必须重新编号它后面的所有内容，这是 O(N)。

这些项目列表将大到 O(N) 迭代不可接受的程度。我确信这个问题已经解决了，我只是不知道解决方案会被称为什么。搜索与“链接列表”相关的任何内容都会产生大量噪音。

一种可能的解决方案是跳跃列表，其中子列表中的每个节点都知道它跳过主列表中的多少个节点，并且由于搜索跳跃列表的时间复杂度为 O(log N)，因此我们可以随时跟踪并找到索引O(log N) 并删除 O(log N) 中的项目。

然而，在这里实现跳过列表似乎有点矫枉过正......有更简单的解决方案吗？

编辑：

感谢大家的建议，但我想我已经说服自己跳过列表是解决此问题的正确方法。

Answer 1

跳过列表是正确的解决方案。

Answer 2

请参阅手指树：一个简单的通用数据结构

又见MarkCC的博客文章的很好的解释说明手指树木的。

Answer 3

编辑：我的先前的溶液中是有缺陷的std ::矢量::擦除（）是移动元件时是线性的。我的新建议我以前的评论延伸到你的问题。

如果您在列表指针只是工作，你可以将指针调用delete上的指针，保持指数/按键有效后设置为0。然后，你应该能够用越来越大的指数，直到下一个索引超出std::numeric_limits<int>::max()。 然后，当您的列表的较大部分包含设置为零未使用指针的元件，所述通信信道的两侧，接着索引的重新计算执行的零指针同步的清理。我不知道一个很好的启发这个即兴的，但你可以保持零个指针数的轨迹，并将其与整个列表的大小。

在更少的话，由于指数的计算是O（n），延迟，直到你绝对必须。

Answer 4

当您在中进行查找时，您不能保留删除历史记录并对此进行补偿吗？ std::map<item*, int>?

我的意思是，索引中 std::map 代表该项目的原始索引，然后你就有一个辅助地图 std::map<int, int> 它存储给定索引被删除的次数？

item* todelete; //from somewhere
std::map<int, int> history; //stored somewhere
std::map<item*, int> itemIndices; //stored somewhere
const int originalIndex = itemIndices[todelete]; //index of item at insert time
int index = originalIndex;
for (std::map<int, int>::const_iterator it = history.begin(); it != history.end() && it->first < originalIndex; ++it) {
    index -= it->second;
}
// index has now been compensated for previous deletes
// ... send the delete request with 'index'
// update the history with this delete request
std::map<int, int>::iterator it = history.find(index);
if (history.end() == it) {
    history[index] = 1;
} else {
    ++it->second;
}

当然，这个速度取决于历史记录的大小。

/A.B.

Answer 5

多久会删除发生？我想用std::map<item*, int>保持您的解决方案，但不是更新后删除该地图用“NULL”代替链表的项目-Item以确保您的lookupmap指数仍然有效。这可能不是一个很好的解决方案，如果你会看到频繁的缺失和有一个机会，你会遇到内存不足。此外，你可以这样做，有一个重新索引（） - 方法，可以消除链表并指派新的指标对所有项目的任何空项目

旁注1： 你不能传递指针项被删除，你的更新呢？如果你做到这一点，使用可以进行双向链表删除操作很容易地在O（1）。

旁注2： 考虑使用 boost::unordered_map 超过std::map。