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 回答