类似 STL 的 Java 红黑树/TreeSet/Map 和带有非快速失败/安全迭代器的链表

Question

我正在寻找一个具有红黑树和链接列表实现的库，提供不快速失败的迭代器。我希望拥有与使用 STL 在 C++ 中所做的相同的功能，即：

• 在树/列表中插入不会使任何迭代器无效
• 删除只会使指向被删除元素的迭代器
• 无效可以以某种方式存储“迭代器的“位置”并引用它指向的值。

这个实现会很好，因为它提供了在使用列表/树的一部分时修改列表/树的能力。以下是一些示例：

• 将链表/红黑树中的相邻元素获取到 O(1) 中的某个存储值
• 批量插入/删除（没有限制，例如每个位置增量删除一个）
• 通过位置在 O(1) 中拆分链表 当存储了迭代器的位置时，迭代器的
• 更有效的删除（例如，通过将迭代器保持在链表中的某个位置，删除是 O(1)，而不是 O(N)）

我还希望该库/源代码/实现拥有一些 Apache/GPL 友好的许可证并且具有相当的可扩展性（因此我可以进行自己的修改来实现一些操作，例如上面示例中的操作）。

如果不存在这样的库，是否有其他库可以帮助我自己实现这两个数据结构？

Answer 1

这些都很容易自己实现。迭代器必须做三件事：

1. 仅存储两个引用，一个到“当前”元素，一个到外部容器对象（存储根引用（树）或头的 blob） /tail 引用（列表））。

2. 能够确定引用的元素是否有效（简单，如果父指针为空（树）或上一个/下一个指针为空（列表），那么这最好是树根或头/尾）列表）。当对无效迭代器尝试任何操作时抛出一些东西。

3. 能够找到上一个/下一个元素。

有几个问题：对于列表，高效支持 java.util.ListIterator 的 nextIndex() 和 prevIndex() 会很痛苦，当然，现在您还面临处理并发修改的问题！下面是一个事情可能会变得糟糕的例子：

while (it.hasNext()) {
    potentially_delete_the_last_element()
    it.next() // oops, may throw NoSuchElementException.
}

避免这种情况的方法是永远不要在检查列表是否有下一个/上一个和实际检索下一个/上一个之间修改列表。