查找链接列表中的条目优于O（n）时间的索引

Question

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

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

删除似乎很直接;我需要传递要删除的项目的索引，但是如何知道索引？索引从零开始并且必须是连续的，但是我在插入时进行设置。所以我需要跟踪每件商品的指数。

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

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

一个可能的解决方案是跳过列表，其中子列表中的每个节点都知道它跳过的主列表中有多少个节点，并且由于搜索跳过列表是O（log N），所以我们可以继续跟踪找到O（log N）中的索引并删除O（log N）中的项目。

然而，实施跳过列表似乎有点矫枉过正......有没有更简单的解决方案？

编辑：

感谢所有为您的建议，但我想我已经说服自己跳跃列表是在这里解决这个问题的正确方法。

Answer 1

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

Answer 2

参见Hinze和Paterson的Finger Trees: A Simple General-purpose Data Structure。

另请参见MarkCC的blog post on finger trees中的漂亮插图。

Answer 3

编辑：我以前的解决方案有缺陷std :: vector :: erase（）在移动元素时是线性的。我的新建议将我先前的评论扩展到您的问题。

如果您只是使用列表中的指针，可以在对指针调用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指数仍然有效。这可能不是一个好的解决方案，如果你会看到经常删除，并有可能会用完内存。此外，你可以做到这一点，并有一个reindex（） - 方法，从链表中删除任何NULL项目，并为所有项目分配新的索引。

旁注1： 你不能传递指针的项目，你在做更新被删除？如果您这样做并使用double-linked list，则可以在O（1）中轻松执行删除操作。

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