c++ - C++：STXXL 中的哪种数据类型适合创建外部存储器二叉搜索树？

Question

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

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

我在 STXXL:Vector 文档中读到，它显然不可能使用非常合乎逻辑的指针。

警告： 不要存储对外部向量元素的引用。在对 vector 元素的任何后续访问期间，此类引用可能会失效。

那么问题是使用“stxxl”数据类型保存二叉搜索树数据结构的替代方法是什么？

score 1 · Accepted Answer

您可以直接将 stxxl::vector 保留在节点结构中。但是，在使用和遍历节点时，您需要返回向量的引用而不是向量本身。如果您直接返回向量，您将对其进行深度复制，这是不可行的。从现有节点返回引用是一种安全的使用方式：

const stxxl::vector<int> &Node::getVectorFromNode() const
{
   return _VectorNodeMember;
}

score 1 · Accepted Answer

存储指向元素的迭代器而不是指向元素的指针/引用。指针/引用将因磁盘分页而失效，但迭代器不会失效。

前任：

// 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），因此您可以将其视为不会失效的指针。

2 回答 2