Automatic dictionary key?

Question

I kept googling for some time, and I found that the best way that enables you to have a list containing variables with a corresponding unique key is a HashTable or a Dictionary, but I didn't find anything that enables you to have automatic keys(of type integer). I want to call a function that adds an object(passed as a parameter) to the dictionary and returns the automatically generated key(int), and without any key duplicates. How could I accomplish this? I am completely struggling!

EDIT: To clarify things up. This is a server, and I want to assign a unique key for each client. If I use the maximum key value, this value will soon get to the int maximum value on large servers. Because if a client connects then disconnects he leaves behind an unused value which should be reused in order to avoid reaching a very high key maximum value.

Answer 1

The following should do and it reuses freed up keys:

internal class AutoKeyDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
    private readonly Dictionary<TKey, TValue> inner;
    private readonly Func<TKey, TKey> incrementor;
    private readonly Stack<TKey> freeKeys;
    private readonly TKey keySeed;
    private TKey currentKey;

    public AutoKeyDictionary(TKey keySeed, Func<TKey, TKey> incrementor) 
    {
        if (keySeed == null)
            throw new ArgumentNullException("keySeed");

        if (incrementor == null)
            throw new ArgumentNullException("incrementor");

        inner = new Dictionary<TKey, TValue>();
        freeKeys = new Stack<TKey>();
        currentKey = keySeed;
    }

    public TKey Add(TValue value) //returns the used key
    {
        TKey usedKey;

        if (freeKeys.Count > 0)
        {
            usedKey = freeKeys.Pop();
            inner.Add(usedKey, value);
        }
        else
        {
            usedKey = currentKey;
            inner.Add(usedKey, value);
            currentKey = incrementor(currentKey);
        }

        return usedKey;
    }

    public void Clear()
    {
        inner.Clear();
        freeKeys.Clear();
        currentKey = keySeed;
    }

    public bool Remove(TKey key)
    {
        if (inner.Remove(key))
        {
            if (inner.Count > 0)
            {
                freeKeys.Push(key);
            }
            else
            {
                freeKeys.Clear();
                currentKey = keySeed;
            }

            return true;
        }

        return false;
    }

    public bool TryGetValue(TKey key, out TValue value) { return inner.TryGetValue(key, out value); }
    public TValue this[TKey key] { get {return inner[key];} set{inner[key] = value;} }
    public bool ContainsKey(TKey key) { return inner.ContainsKey(key); }
    public bool ContainsValue(TValue value) { return inner.ContainsValue (value); }
    public int Count { get{ return inner.Count; } }
    public Dictionary<TKey,TValue>.KeyCollection Keys { get { return inner.Keys; } }
    public Dictionary<TKey, TValue>.ValueCollection Values { get { return inner.Values; } }
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { return inner.GetEnumerator(); }
    IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)inner).GetEnumerator(); }
}

Disclaimer: I haven't tested this code, it could have a few pesty bugs of little importance, the general approach is sound.

Answer 2

I like Stefan Steinegger's solution. Here is an alternative that uses a List<> behind the scenes, but ensures the List<> is never removed from:

class AutoKeyDictionary<TValue> : IEnumerable<TValue> where TValue : class
{
  readonly List<TValue> list = new List<TValue>();

  public int Add(TValue val)
  {
    if (val == null)
      throw new ArgumentNullException(nameof(val), "This collection will not allow null values.");
    list.Add(val);
    return list.Count - 1;
  }

  public void RemoveAt(int key)
  {
    // do not remove ('list.Count' must never decrease), overwrite with null
    // (consider throwing if key was already removed)
    list[key] = null;
  }

  public TValue this[int key]
  {
    get
    {
      var val = list[key];
      if (val == null)
        throw new ArgumentOutOfRangeException(nameof(key), "The value with that key is no longer in this collection.");
      return val;
    }
  }

  public int NextKey => list.Count;

  public int Count => list.Count(v => v != null); // expensive O(n), Linq

  public bool ContainsKey(int key) => key >= 0 && key < list.Count && list[key] != null;

  public TValue TryGetValue(int key) => (key >= 0 && key < list.Count) ? list[key] : null;

  public void Clear()
  {
    for (var i = 0; i < list.Count; ++i)
      list[i] = null;
  }

  public IEnumerator<TValue> GetEnumerator() => list.Where(v => v != null).GetEnumerator(); // Linq

  IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

  public int FirstKeyOf(TValue val) => list.IndexOf(val);

  public IDictionary<int, TValue> ToDictionary()
  {
    var retColl = new SortedList<int, TValue>(list.Count);
    for (var i = 0; i < list.Count; ++i)
    {
      var val = list[i];
      if (val != null)
        retColl.Add(i, val);
    }
    return retColl;
  }

  // and so on...
}

Not thread-safe, obviously.

Be aware, the same value can be present several times in the collection, but with different keys.

Answer 3

Create a method that gets the max key value from the dictionary using LINQ, adds 1 to it and then uses that as the key for the value you would like to add, like this:

public void AddToMyDictionary(string value)
{
    int NextKey = MyDictionary.Keys.Max() + 1;
    MyDictionary.Add(NextKey, value);
}

Obviously, this assumes your dictionary is a Dictionary<int, string>, but you can obviously modify for your purposes.

If you want to re-use keys that have been removed, store the next index when something is added / removed.

private int NextKey = 0;

public int AddToMyDictionary(string value)
{
    int currentKey = NextKey;
    MyDictionary.Add(currentKey, value);
    NextKey = MyDictionary.Keys.Max() + 1;
    return currentKey;
}

public void RemoveFromMyDictionary(int key)
{
     MyDictionary.Remove(key);
     NextKey = key;
}

Answer 4

Given the additional information provided in your edit then i don't think int is the correct datatype for you, you shouldn't reuse ID's the way you are describing as if a client with an ID gets disconnected but don't realise then you could have 1 ID in use by 2 clients. change your datatype to Guid then when you get a new client give it a key of Guid.NewGuid() and the chance of duplicate keys drops as close as possible to 0

Answer 5

Wouldn't a List do what you say, without any additional overhead? You call it a "unique integer key", but in List terminology, that's simply called an "index".

If you really wanted a custom function to add a value and get a key all in one step, you could inherit from List<T>, like so:

class MyCustomList<T> : List<T>
{
    //Not thread-safe
    public int AddAndGetKey(T valueToAdd)
    {
        Add(valueToAdd);
        return LastIndexOf(valueToAdd);
    }
}

I use LastIndexOf() because the list may include duplicate values and adding to the list always adds to the end. So this should work unless you get into multithreaded situations where you'd have to add-and-get-index in one atomic operation. (Alternately maybe you could add an extension method to List<T>.)

The advantage of using a List is that there would be no gaps in keys. On the flipside, removing an item in the middle would change the key of every item after it. But I guess it depends what behavior you're looking for.

Answer 6

Write a class which does this. Something like this:

class AutoIndexDictionary : IEnumerable<Whatever>
{
  private readonly Dictionary<int, Whatever> myDict = new Dictionary<int, Whatever>();

  private int currentIndex = 0;

  public int Add(Whatever item)
  {
    var myIndex = currentIndex 
    myDict.Add(myIndex, item);
    currentIndex ++;
    return myIndex;
  }

  public void Remove(int index)
  {
    myDict.Remove(index);
  }

  // implement IEnumerable, indexer etc.
  // ...
}

Answer 7

This is what int Object.GetHashCode() is for.