c++ - 创建一个由链接平衡 bst 和双向链表组成的数据结构

Question

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

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

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

(我想创建这个数据结构来创建 LRU 缓存)

Answer 1

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