3

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

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

删除似乎很简单；我需要传递要删除的项目的索引，但我怎么知道索引？索引从零开始并且必须是连续的，但我在插入时将它们组成。所以我需要跟踪我为每个项目组成的索引。

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

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

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

然而，在这里实现一个跳过列表似乎有点过头了......有没有更简单的解决方案？

编辑：

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

4

5 回答 5

4

请参阅Hinze 和 Paterson的手指树：一种简单的通用数据结构。

另请参阅 MarkCC关于手指树的博客文章中的精美插图。

于 2009-11-25T06:13:39.203 回答
1

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

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

简而言之，由于索引的计算是 O(n)，所以延迟它直到你绝对必须这样做。

于 2009-11-25T06:42:01.893 回答
1

当您在 中进行查找时，您不能保留删除历史并对此进行补偿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;
}

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

/AB

于 2009-11-25T12:09:47.827 回答
1

删除多久会发生一次？我正在考虑使用 保留您的解决方案std::map<item*, int>，而不是在删除时更新地图，用“NULL”项目替换链接列表中的项目，以确保查找图中的索引保持有效。如果您会看到频繁的删除并且您可能会耗尽内存，这可能不是一个好的解决方案。此外，您可以执行此操作并使用 reindex() 方法从链表中删除任何 NULL 项并将新索引分配给所有项。

旁注1：您不能像在更新中那样将指针传递给被删除的项目吗？如果您这样做并使用双链表，则可以在 O(1) 中轻松执行删除操作。

旁注 2：考虑使用boost::unordered_mapover std::map。

于 2009-11-25T14:23:41.193 回答
0

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

于 2010-01-22T17:57:00.010 回答