1

我正在尝试创建一个数据结构，其中有一个平衡的 BST 和一个双向链表。链表将小于 BST，因此在任何时候都只会包含 BST 的元素子集。LL 的每个节点将指向指向其在 BST 中的对应节点，如果该节点存在于链表中，则 BST 节点将指向其 LL 节点，否则将存储 null。

为了创建这个数据结构，我计划将 std::set< data, std::list::iterator > 用于 BST，将 std::list< data,std::set::iterator > 用于双向链表。是吗很好，如果我存储对彼此元素迭代器的引用来执行此操作。该集合是否有可能进行平衡并反过来使链表持有的迭代器无效。方法是否还有其他问题？

如何在 C++ 中使用 STL 或任何其他库来执行此操作？

（我想创建这个数据结构来创建 LRU 缓存）

4

2 回答 2

2

std::set当您在集合中插入新元素时，迭代器仍然有效，因此当您将迭代器保留在列表中时，这不会导致问题。从集合中删除元素将使这些元素的迭代器无效（显然），但其他迭代器仍然有效。

于 2013-05-13T13:27:35.100 回答
0

C++中具有双向链表的平衡二叉搜索树

在这儿：

http://archive.gamedev.net/archive/reference/programming/features/TStorage/index.html

于 2013-07-26T03:12:57.377 回答