Dictionary with limited size that removes oldest elements?

Question

Is there an existing data structure usable for hashing data that will give ability to delete the oldest element?

The approach that I am thinking of right now is to have a Dictionary and a Queue having fast lookup using the Dictionary and being able to delete oldest element from the Dictionary using a Queue.

Answer 1

An OrderedDictionary is a good suggestion, but if you need types other than a string in your dictionary, try this;

public sealed class SizedDictionary<TKey, TValue> : Dictionary<TKey, TValue> {

private int maxSize;
private Queue<TKey> keys;

public SizedDictionary(int size) {
    maxSize = size;
    keys = new Queue<TKey>();
}

new public void Add (TKey key, TValue value) {
    if (key==null) throw new ArgumentNullException();
    base.Add(key, value);
    keys.Enqueue(key);
    if (keys.Count > maxSize) base.Remove(keys.Dequeue());
}

new public bool Remove (TKey key) {
    if (key==null) throw new ArgumentNullException();
    if (!keys.Contains(key)) return false;
    var newQueue = new Queue<TKey>();
    while (keys.Count>0) {
        var thisKey = keys.Dequeue();
        if (!thisKey.Equals(key)) newQueue.Enqueue(thisKey);
    }
    keys=newQueue;
    return base.Remove(key);
}
}

I'm using a sealed class because we are just hiding the add and remove methods, so if this class were to be inherited it wouldn't be clear which version was used. A more complete solution would use an internal dictionary and not inherit, but that would be a lot more long winded