関数型プログラミング言語は、不変のデータ構造で機能することがよくありますが、構造を共有することで効率を維持します。たとえば、情報のマップで作業している場合、要素を挿入すると、既存のマップを変更せずに、新しい更新バージョンを作成します。大量のコピーとメモリ使用量を回避するために、マップは両方のインスタンス間で変更されていないデータを（可能な限り）共有します。
C++のデータ構造のようなマップを提供するテンプレートライブラリが存在するかどうか興味があります。少し検索しても、LLVMの内部クラス以外には何も見つかりませんでした。
Copy On Write b+tree は、探しているもののように聞こえます。基本的に、変更されるたびに自身の新しいスナップショットを作成しますが、変更されていないリーフ ノードをバージョン間で共有します。私が見た実装のほとんどは、追加専用のデータベース ログ ファイルに組み込まれている傾向があります。CouchDB には、それらについて非常に優れた記事があります。ただし、マップのデータ構造に関する限り、実装は「比較的簡単」です。
通常のマップを使用できますが、すべての要素にタイムスタンプまたは「マップ バージョン番号」を付けます。要素も削除する場合は、2 つのマークを使用します。削除された要素を再挿入する可能性がある場合は、要素ごとに値のリストとマークのペアが必要です。
たとえば、キー「foo」を検索すると、バージョン 0 から 3 (含まれている) では値が 5 で、その後「削除」され、バージョン 9 から現在までで値が -8 であることがわかります。 .
ただし、これは多くのメモリと時間を消費します。