我想创建一个外部内存二进制搜索树数据结构，其数据位于外部内存中，使用 stxxl 作为库。
为此，STXXL 中的哪种数据类型适合用作树中的节点。如果我们使用 stxxl:Vector 作为树的节点，我们如何保存指向它们的指针。
我在 STXXL:Vector 文档中读到，显然不可能使用指针，这是非常合乎逻辑的理解。
Warning : Do not store references to the elements of an external vector. Such references might be invalidated during any following access to elements of the vector .
那么问题是使用“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)，因此您可以将其视为不会失效的指针。
关于C++:STXXL 中的哪种数据类型适合创建外部存储器二叉搜索树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30636076/