新鮮なIDを確定的に取得する

Question

私はIImmutableDictionary<int, MyType>をC＃で持っています。私のプログラムの実行中に、私はいくつかのコマンドに基づいてMyTypeインスタンスを追加し、削除したいと思います：MyTypeが追加されると

public sealed class AddMyTypeCommand : ICommand 
{ 
    public readonly MyType myTypeToAdd; 

    // etc... 
} 

public sealed class RemoveMyTypeCommand : ICommand 
{ 
    public readonly int keyToRemove; 

    // etc... 
} 

、私は辞書にない新鮮なintキーを生成したいと思います。

キーが削除され、後で再利用される可能性があるので、私はintを使い果たしてしまわないと思います。

主なキャッチは、プロセスが確定的であることです。与えられたストリームICommandの場合、コードは異なるマシンで同じコードを実行し、同じキーを生成する必要があります。

鍵生成ステップを達成するための、堅牢で維持可能かつ効率的なアプローチは何ですか？例えば

---

、遅いアプローチは次のようになります。新鮮なIDが見つかるまで上向きに歩く、int.MinValueから始まります。

Answer 1

追加よりも多くを削除しないことがわかっている場合は、すべてのホールをキューに保存し、キューが空であるかどうかに基づいてキーを決定できます。したがって、穴がない場合は、あなたの辞書はキーを自動的にインクリメントし、穴がある場合は埋め戻します。

class ImmutableDictionary<T> 
{ 
    private readonly Dictionary<int, T> _dict = new Dictionary<int, T>(); 
    private readonly Queue<int> _holes = new Queue<int>(); 
    private int _nextInt = 0; //what is next integer to assign, I'm starting at 0, but can be int.MinValue 
    private int AssignKey() 
    { 
     //if we have a hole, use that as the next key. Otherwise use the largest value we haven't assigned yet, and then increment that value by 1 
     return _holes.Count != 0 ? _holes.Dequeue() : _nextInt++; 
    } 

    public void Add(T input) 
    { 
     _dict.Add(AssignKey(), input); 
    } 

    public void Remove(int key) 
    { 
     if (_dict.Remove(key)) //if a remove is successful, we should add a hole 
     //you can extend the logic here to not add a hole if you are removing something equal to _nextInt - 1. 
      _holes.Enqueue(key); 
    } 
}