I want to create an External Memory Binary Search Tree Data Structure whose data sits in the external memory using stxxl as a library.
For this purpose, which Data Type in STXXL is suitable to use as nodes in the Tree. If we use stxxl:Vector as the Nodes of the tree, how do we hold the pointers to them.
I have read in STXXL:Vector documentation that its obviously not possible to use Pointers which is very logical to understand.
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 .
Then the Question is what is an alternative to hold a Binary Search Tree Data Structure using 'stxxl' data types ?
Store iterators pointing to elements instead of pointers/refs to elements. Pointers/refs will be invalidated because of paging to/from the disk, but the iterators will not be invalidated.
Ex:
// Safe to store this, not safe to store &nodes[node_index].
stxxl::vector<Node>::iterator node_it = nodes.begin() + node_index;
... and const_iterator for read-only purpose.
node_it will not be invalidated unless the element is removed. Unlike the STL, it doesn't even get invalidated if you do things like push_back. Dereferencing it will write/read pages to/from disk (only reading for const_iterator), and so you can treat it like a pointer that doesn't get invalidated.