私は STL を使用してアルゴリズムを開発することを楽しんでいますが、データ セットがヒープに対して大きすぎるという問題が繰り返し発生します。
私は、STL コンテナーと、ディスクに支えられたアルゴリズム、つまりヒープではなくディスクに格納されたデータ構造のドロップイン代替品を探していました。
最近、友人が私にstxxlを指摘しました。私がそれに関与する前に... 私が検討すべき他のディスクでバックアップされた STL の代替品はありますか?
注: 永続性や組み込みデータベースには興味がありません。boost::serialization、POST++、Relational Template Library、Berkeley DB、sqlite などについては言及しないでください。私はこれらのプロジェクトを認識しており、目的に適した場合に使用しています。
更新: 何人かの人々がメモリ マッピング ファイルとカスタム アロケータの使用について言及していますが、良い提案です。つまり、カスタム アロケーター アプローチは機能しない可能性があります。
私は非常によく似たものを実装しました。イテレータの実装は最も困難です。イテレータの実装には、boost::iterator_facadeを使用しました。これを使用boost::iterator_facadeすると、ディスクにキャッシュされたデータ構造を簡単に適応させて、STL コンテナー インターフェイスを持つことができます。
このようなことをする必要はありませんでしたが、メモリ マップ ファイルを使用してデータをバックアップするカスタム アロケータを作成することで、やりたいことを実行できる可能性があります。
メモリ マップド ファイルの使いやすい実装に関するドキュメントについてはboost::interprocessesを参照してください。アロケータの記述に関する詳細な議論については、この Dr. Dobbs の記事を参照してください。問題の説明とサンプル コードについては、この IEEE ソフトウェア コラムを参照してください。
（あなたが書いているように）永続性に興味がない場合、最も簡単な解決策は、ヒープサイズを増やしてオペレーティングシステムの仮想メモリ機能を使用することです。コンピュータの物理メモリに収まらないヒープの部分は、ディスク上でページングされることになり、ディスク上に保存されることが多いデータへの通常の STL アクセスなど、まさに必要なものが得られます。オペレーティング システムは、最も使用されているページを物理メモリにキャッシュし、あまり使用しないページをディスクに削除します。コードは同じままで、物理メモリを追加するだけでパフォーマンスを向上させることができます。
ヒープ サイズを増やすには、Unix システムの ulimit(1) や Windows XP のシステム プロパティ - 詳細 - パフォーマンス - 詳細 - 仮想メモリなど、オペレーティング システムのパラメータを確認してください。32 ビットの 4GB 制限に達した場合は、64 ビット アーキテクチャに移行するか、プログラムを 64 ビット用にコンパイルすることを検討してください。
この件についてはよくわかりませんが、STL のようなインターフェイスをメモリ マップド ファイルに書き込むことは可能でしょうか?
編集: このアプローチは、巨大なファイルの特定の部分を取得しようとしている場合に適している可能性があります。ファイル全体で何かを行おうとすると、ファイルのキャッシュされていない部分を読み取るときに、膨大な数のページ フォールトが発生する可能性があります。