次の機能を持つペア (Key,T) を格納するためのマップのようなデータ構造 (C++) が必要です。
- 新しい要素 (Key,T) を現在の構造に挿入できます
- 現在の構造のキーに基づいて要素を検索できます
- 構造の現在のバージョンの「スナップショット」を作成できます
- スナップショットを作成した構造のバージョンの 1 つに切り替えて、そこからすべての操作を続行できます。
- バージョンの 1 つを完全に削除する
必要ないもの
- 構造からの要素の削除
- 構造の異なるバージョンを 1 つにマージする
- 現在構造体に格納されているすべての (または一部の) 要素に対する反復
言い換えれば、構築できる検索構造がありますが、いつでも履歴をジャンプして、構造の以前の/別のバージョンを別の方法で拡張できます。後で、これらの異なるバージョン間をジャンプできます。
私のプロジェクトでは、Key と T は整数またはポインター値である可能性が高く、文字列ではありません。
主な目的は、時間の複雑さを軽減することです。スペースの消費は二次的なものです (しかし、同様に妥当なはずです)。明確にするために、私にとっては log(N)+log(S) (N個の要素、S個のスナップショット)で十分ですが、速いほど良いです:)
実装方法の大まかなアイデアがあります---たとえば、構造が二分探索ツリーであるため、新しい要素を挿入すると、ルートから挿入場所までのパスを複製できますが、ツリーの残りの部分はそのままです。ツリー バージョンを切り替えることは、ルート ノードの別のバージョンを選択することと同じであり、一部の変更は単に表示されません。
ただし、このカスタム ツリーを効率的にする (自己均衡など) には、追加の作業と注意深いコーディングが必要です。もちろん、私はそれを自分で行うことができますが、おそらくそれを行うための既存のライブラリがすでに存在しますか?
また、おそらく私が知らないこの種のデータ構造には適切な名前があり、Google検索（またはSO検索）が完全に失敗します...
ご協力ありがとうございました！