如何实现一个支持实时过滤的集合？
How to implement a collection that supports real-time filtering?
我想实现一个可变顺序集合 FilteredList 来包装另一个集合 List 并根据谓词对其进行过滤。
包装的 List 和暴露的 FilteredList 都是可变的和可观察的，并且应该是同步的（例如，如果有人向 List 添加一个元素，该元素应该出现在 FilteredList 中的正确位置，反之亦然）。
不满足谓词的元素仍然可以添加到FilteredList，但它们将不可见（它们仍会出现在内部列表中）。
集合应支持：
Insert(index,value) 在位置 index 插入一个元素 value，向前推动元素。Remove(index) 删除位置 index 的元素，将所有后续元素移回。Update(index, value)，将位置 index 的元素更新为 value。
我在想出一个好的同步机制时遇到了麻烦。
我没有任何严格的复杂性界限，但现实世界的效率很重要。
避免同步困难的最好方法是创建一个不需要它们的数据结构：使用单个数据结构来呈现过滤和未过滤的数据。
你应该可以通过修改后的 skip list (actually, an indexable skip list) 来做到这一点，这将使你可以通过索引进行 O(log n) 访问。
你所做的是为每个节点维护两组独立的前向指针，而不是仅仅一组。一组用于未过滤列表，如普通跳过列表，另一组用于过滤列表。
添加到列表或从列表中删除对于已过滤和未过滤的列表是相同的。也就是说，您通过遵循适当的过滤或未过滤的 links 找到索引处的节点，然后添加或删除节点，更新两组 link 指针。
这应该比标准顺序列表更有效，因为插入和删除不会产生向上或向下移动项目以打洞或填补空白的成本；这一切都通过引用完成。
不过，每个节点需要多一点 space。平均而言，跳过列表每个节点需要两个额外的引用。由于您构建的实际上是两个跳跃列表合二为一，因此预计您的节点平均每个节点需要四个额外的引用。
评论后编辑
如果像您所说的那样，您无法控制 List，那么您仍然会保留我描述的这个双重跳过列表。但是跳跃列表中存储的数据只是 List 的索引。你说 List 是可观察的，所以你会得到所有插入和删除操作的通知，所以你应该能够通过对所有通知做出反应来维护索引。
当有人想对 FilteredList 进行操作时，您使用过滤索引 links 找到用户想要影响的 FilteredList 记录的 List 索引.然后使用转换后的索引将请求传递到 List。然后您对来自 List.
的可观察通知做出反应
基本上，您只是维护 List 的二级索引，以便您可以将 FilteredList 索引转换为 List 索引。
我想实现一个可变顺序集合 FilteredList 来包装另一个集合 List 并根据谓词对其进行过滤。
包装的 List 和暴露的 FilteredList 都是可变的和可观察的，并且应该是同步的（例如，如果有人向 List 添加一个元素，该元素应该出现在 FilteredList 中的正确位置，反之亦然）。
不满足谓词的元素仍然可以添加到FilteredList，但它们将不可见（它们仍会出现在内部列表中）。
集合应支持：
Insert(index,value)在位置index插入一个元素value，向前推动元素。Remove(index)删除位置index的元素，将所有后续元素移回。Update(index, value)，将位置index的元素更新为value。
我在想出一个好的同步机制时遇到了麻烦。
我没有任何严格的复杂性界限，但现实世界的效率很重要。
避免同步困难的最好方法是创建一个不需要它们的数据结构：使用单个数据结构来呈现过滤和未过滤的数据。
你应该可以通过修改后的 skip list (actually, an indexable skip list) 来做到这一点，这将使你可以通过索引进行 O(log n) 访问。
你所做的是为每个节点维护两组独立的前向指针，而不是仅仅一组。一组用于未过滤列表，如普通跳过列表，另一组用于过滤列表。
添加到列表或从列表中删除对于已过滤和未过滤的列表是相同的。也就是说，您通过遵循适当的过滤或未过滤的 links 找到索引处的节点，然后添加或删除节点，更新两组 link 指针。
这应该比标准顺序列表更有效，因为插入和删除不会产生向上或向下移动项目以打洞或填补空白的成本；这一切都通过引用完成。
不过，每个节点需要多一点 space。平均而言，跳过列表每个节点需要两个额外的引用。由于您构建的实际上是两个跳跃列表合二为一，因此预计您的节点平均每个节点需要四个额外的引用。
评论后编辑
如果像您所说的那样，您无法控制 List，那么您仍然会保留我描述的这个双重跳过列表。但是跳跃列表中存储的数据只是 List 的索引。你说 List 是可观察的，所以你会得到所有插入和删除操作的通知，所以你应该能够通过对所有通知做出反应来维护索引。
当有人想对 FilteredList 进行操作时，您使用过滤索引 links 找到用户想要影响的 FilteredList 记录的 List 索引.然后使用转换后的索引将请求传递到 List。然后您对来自 List.
基本上，您只是维护 List 的二级索引，以便您可以将 FilteredList 索引转换为 List 索引。