2

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

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

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

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

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

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

4

1 回答 1

0

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

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

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

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

有几个陷阱：对于列表，有效地支持 java.util.ListIterator 的 nextIndex() 和 prevIndex() 会很痛苦，当然，现在您遇到了处理并发修改的问题！这是事情如何变糟的一个例子：

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

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

于 2011-02-06T22:50:36.647 回答