我正在寻找一个带有红黑树和链接列表实现的库,它提供了不能快速失败的迭代器。我希望拥有与使用 STL 在 C++ 中相同的功能,即:
- 在树/列表中的插入不会使任何迭代器无效
- 删除仅使指向被删除元素的迭代器无效
- 可以以某种方式存储迭代器的“位置”并引用它指向的值
这个实现会很好,因为它可以在使用列表/树的一部分时提供修改列表/树的能力。这里有些例子:
- 将链表/红黑树中的相邻元素获取到 O(1) 中的某个存储值
- 批量插入/删除(没有限制,例如每个位置增量一个删除)
- 通过迭代器的位置在 O(1) 中拆分链表
- 存储迭代器位置时更有效的删除(例如,通过将迭代器保持在链表中的某个位置,删除是 O(1),而不是 O(N))
我还希望该库/源代码/实现具有一些 Apache/GPL 友好的许可证并且具有相当的可扩展性(因此我可以进行自己的修改以实现一些操作,例如上面示例中的操作)。
如果不存在这样的库,是否有其他库可以帮助我自己实现这两个数据结构?