1

私は数回前に C++ で一般的なメモリ内 B+Tree の実装を書きましたが、それをディスク上で永続化することを考えています (これが、最初に B+Tree が設計された理由です)。私の最初の考えは、mmap（私はLinuxを使用しています）を使用して、ファイルを通常のメモリとして操作し、新しいものを書き換えることでしたこれにより、マップされた部分にポインターが返され、RAMアドレスをファイルオフセットに変換してノードを他のノードにリンクできるスマートポインターが作成されます。しかし、ユーザーが int、std::string、または任意のカスタム クラスを B+tree に格納できるように、実装を汎用にしたいと考えています。ここで問題が発生します。プリミティブ型またはポインターを含まない集約型の場合はすべて問題ありませんが、オブジェクトにヒープ割り当てオブジェクトへのポインター/参照が含まれるとすぐに、このアプローチは機能しなくなります。

だから私の質問は: この困難を克服するための既知の方法はありますか? トピックに関する個人的な検索は失敗に終わりますが、何かを見逃している可能性があります。

4

3 に答える 3

4

私の知る限り、これを解決するには 3 つの (やや) 簡単な方法があります。

アプローチ 1 :std::streambuf事前に割り当てられたメモリを指す a を記述します。

このアプローチにより、operator<<既存のコードを使用して、必要なものの文字列表現を取得できます。

  • 長所: 大量の既存コードを再利用できます。
  • 短所:operator<<コンテンツを吐き出す方法を制御できません。
  • 短所: テキストベースの表現のみ。

アプローチ 2 : 独自の (何度もオーバーロードされた) 出力関数を作成します。

  • 長所: バイナリ表現を考え出すことができます。
  • 利点: すべての出力形式を正確に制御できます。
  • 短所：非常に多くの出力関数を書き直してください...クライアントが新しい型のオーバーロードを書くのは面倒です.ライブラリの名前空間に分類される関数を書くべきではないためです.Koenig（引数依存）ルックアップに頼らない限り！

アプローチ 3 :btree_traits<>テンプレートを作成します。

  • 長所: バイナリ表現を考え出すことができます。
  • 利点: すべての出力形式を正確に制御できます。
  • 利点: 関数にメタデータとすべてを含めることができる出力と形式をより詳細に制御できます。
  • 短所：あなた/あなたのライブラリのユーザーは、多くのカスタムオーバーロードを書く必要があります.
  • 長所:誰かが特性をオーバーライドしない限りbtree_traits<>、使用するデフォルトがありますか?operator<<
于 2010-11-25T21:30:09.553 に答える
0

ポインターと参照を一般的な方法で処理するということは、格納しようとしている構造体の型とそのフィールドを検査する必要があることを意味します。C++ は、そのリフレクション性で知られていない言語です。

しかし、強力なリフレクションを備えた言語であっても、この問題の一般的な解決策は困難です。Python、Ruby などの高水準言語の型のサブセットで動作させることができる場合があります。関連するより強力なパラダイムは、永続的なプログラミング言語です。

必要な関数は、通常、データ ブロックを書き込む責任をターゲット型自体に委任することによって実装されます。それはシリアライゼーションと呼ばれます。これは単に、データをダンプするメソッドとデータをロードするメソッドを備えたインターフェースを作成することを意味します。B ツリーに永続化したいクラスは、このインターフェイスを実装するだけです。

于 2010-11-25T21:32:19.873 に答える
0

自明でないアイテムのポインターが malloc (または new および new[]) で割り当てられた場合、それは既にヒープにあるため、真に汎用的で透過的なバージョンを作成することはできません。

非透過的なソリューションでは、クラスをシリアル化することがオプションである可能性があり、これは比較的簡単に実行できます。クラスを保存する前にシリアライゼーション関数を呼び出す必要があり、プルする前にデシリアライズを呼び出す必要があります。Boost には、B+Tree で機能する優れたシリアル化機能があります。

于 2010-11-25T21:30:50.650 に答える