在比O(n)更好的时间内查找链表中条目的索引

Question

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

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

删除似乎很简单；我需要传递要删除的项的索引，但是如何知道索引呢？索引从零开始并且必须连续，但是我在插入时随意制定它们。因此，我需要跟踪为每个项目制定的索引。

例如，我可以使用映射：std::map，但是当我删除一个项时，我必须重新编号其后面的所有内容，这是O(N)的操作。

这些项目列表将变得非常大，以至于O(N)迭代不可接受。我确定这个问题已经解决了，只是我不知道这个解决方案应该称为什么。搜索任何与“linked list”相关的内容都会产生大量噪音。

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

但是，在这里实现跳表似乎有些杀鸡焉用牛刀...是否有更简单的解决方案？

编辑：

感谢大家的建议，但我认为我已经说服自己使用跳表是解决这个问题的正确方法。

- i_am_jorf

---

在你的地图示例中，为什么必须重复使用先前使用过的索引/键？为什么不能将先前使用的索引的清理推迟到达到std::numeric_limits<int>::max()时再进行？ - Mads Elvheim

@Mads：因为它们需要连续以便进行未来的更改通知。如果我在我的端上删除了某些内容，那么更改通知系统另一端的人也会删除他所代表的该项内容，我们希望在未来的更新和插入中保持同步。 - i_am_jorf

为什么不能使用唯一ID来简单地完成这个操作？如果你删除带有ID 17的项目，那么他也会删除相同ID的项目，而不管该项目在实际列表中的位置是哪里，它可能是列表中的第五项。 - Lasse V. Karlsen

@Lasse，项目已经有唯一的ID，但需要排序。 - i_am_jorf

你并没有真正解释为什么排序必须是连续的。我也不明白为什么跳表会过度。为了减少时间，你要用空间来交换。这就是算法处理的工作方式。 - jmucchiello

@jmucchiello：它必须是连续的，因为这是我面临的要求。实际上，它是在另一端的UI系统，所以，你知道，这通常是控件跟踪子控件的方式。时间与空间，没错，但如果有一个更简单的结构，我宁愿使用它。感谢您的理智检查。 - i_am_jorf

Answer 1

请查看Hinze和Paterson的《指尖树：一种简单的通用数据结构》。

同时，请查看MarkCC在指尖树上的博客文章中的漂亮插图。

- Greg Bacon

---

呵呵，我想在完全理解那篇论文之前，我可以在C ++中实现一个跳表。 :) 我会看一下的。 - i_am_jorf

Answer 2

你不能保留删除历史，并在查找 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.

- Andreas Brinck

Answer 3

编辑：我的先前解决方案存在缺陷，std::vector::erase() 在移动元素时是线性的。我的新建议扩展了我之前对你问题的评论。

如果你只是在列表中使用指针，在调用指针上的 delete 后，可以将指针设置为 0，保持索引/键有效。然后，您应该能够使用越来越大的索引，直到下一个索引超出 std::numeric_limits<int>::max()。 然后，当您的列表的较大部分包含未使用的指针元素设置为零时，在通信渠道的两端执行同步清理零指针，然后重新计算索引。我不知道这方面的好启发式方法，但您可以跟踪零指针的数量，并将其与整个列表大小进行比较。

简而言之，由于索引的计算是 O(n) 的，因此要尽可能地延迟它。

- Mads Elvheim

---

是的，可悲的是我无法真正控制另一方。但你说得有道理。 - i_am_jorf

Answer 4

删除操作频率有多高？我考虑使用std::map<item*, int>来保留您的解决方案，但是在删除时不是更新映射表，而是将链表中的项目替换为一个"NULL"-item，以确保您的查找映射表中的索引仍然有效。如果您经常进行删除操作，并且有可能耗尽内存，这可能不是一个好的解决方案。另外，您可以执行这个操作并创建一个reindex()方法，该方法会从链表中移除任何NULL项目，并为所有项目分配新的索引。

附注1： 你能不能像在更新操作中那样传递要删除的项目指针？如果您这样做，并且使用双向链表，删除操作可以轻松地以O(1)完成。

附注2： 考虑使用boost::unordered_map代替std::map。

- larsmoa

---

删除本身可以在常数时间内完成，但在列表中查找项目仍然是线性的。我传递的项目指针是列表另一端项目的值，而不是列表节点本身的指针。Boost已被禁止使用于该项目，无论好坏。在适当的情况下，我们使用hash_map（std / stdext）。 - i_am_jorf

这正是我所建议的 :-) - Mads Elvheim

Answer 5

跳表（Skip List）是正确的解决方案。

- i_am_jorf