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

Question

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

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

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

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

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

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

Answer 1

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

1. 仅 存储两个引用，一个指向“当前”元素，一个指向外部容器对象(存储根引用(树)的 blob 或头/尾引用(列表) )).

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

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

有几个陷阱:对于列表，有效地支持 java.util.ListIterator 的 nextIndex() 和 prevIndex() 会很痛苦，当然，现在你有处理并发修改的问题!以下是事情如何变坏的示例:

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

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