2

ライブラリとしてstxxlを使用して、データが外部メモリにある外部メモリ バイナリ検索ツリー データ構造を作成したいと考えています。

この目的のために、ツリーのノードとして使用するのに適した STXXL のデータ型。ツリーのノードとして stxxl:Vector を使用する場合、それらへのポインタをどのように保持しますか。

STXXL:Vector のドキュメントを読みましたが、理解するのが非常に論理的であるポインターを使用することは明らかに不可能です。

警告 : 外部ベクトルの要素への参照を保存しないでください。このような参照は、ベクターの要素への以降のアクセス中に無効になる可能性があります。

次に、「stxxl」データ型を使用してバイナリ サーチ ツリー データ構造を保持する代替手段は何ですか?

4

2 に答える 2

1

ノード構造に stxxl::vector を直接保持できます。ただし、ノードを使用してトラバースしている間は、ベクター自体ではなく、ベクターの参照を返す必要があります。ベクトルを直接返すと、それをディープコピーすることになりますが、これは実現不可能です。既存のノードから参照を返すことは、安全な使用方法です。

const stxxl::vector<int> &Node::getVectorFromNode() const
{
   return _VectorNodeMember;
}
于 2015-06-04T06:16:16.237 に答える
1

要素へのポインター/参照ではなく、要素を指す反復子を格納します。ディスクへの/からのページングのためにポインター/参照は無効になりますが、反復子は無効になりません。

元：

// 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)、無効にならないポインターのように扱うことができます。

于 2015-06-04T06:16:30.273 に答える