我想使用 stxxl 作为库来创建一个数据位于外部存储器中的外部存储器二进制搜索树数据结构。

为此,STXXL中的哪种数据类型适合用作树中的节点。如果我们将stxxl:Vector用作树的节点,则如何保存指向它们的指针。

我在STXXL:Vector文档中已经读到,显然不能使用Pointers,这很容易理解。



那么问题是使用'stxxl'数据类型保存二进制搜索树数据结构的替代方法是什么?

最佳答案

存储指向元素的迭代器,而不是指向元素的指针/引用。指针/引用将因与磁盘之间的分页而无效,但迭代器不会无效。

例如:

// Safe to store this, not safe to store &nodes[node_index].
stxxl::vector<Node>::iterator node_it = nodes.begin() + node_index;

...和const_iterator用于只读目的。

除非删除元素,否则node_it不会无效。与STL不同,如果您执行push_back之类的操作,它甚至不会失效。取消引用它将向磁盘写入页面/从磁盘读取页面(仅读取const_iterator),因此您可以将其视为不会失效的指针。

10-06 01:27