C# - Dictionary with Behaviour of a Ring List?

Question

I need a ring list dictionary that can store key and item. Capacity = 50 and when I add #51 the first item must be removed. Basically it must be a dictionary that behaves like a ring list.

Is there something in .NET Framework that can do that ? Or do I have to write it by myself ?

You'll have to write this yourself. Just use a linked list and a dictionary underneath. — Lasse V. Karlsen, Aug 06 '13 at 10:37
Like Haris Hasan said, you could use OrderedDictionary. It's not sealed class, so you could inherit from it and write new `Insert` method definition (http://msdn.microsoft.com/en-us/library/435f1dw2.aspx). Unfortunately, it's not overriding but you could use your class explicity. — , Aug 06 '13 at 10:57

score 5 · Answer 1 · answered Aug 06 '13 at 10:39

5

You won't find anything built-in I think but you can easily implement one using OrderedDictionary

OrderedDictionary maintains items in order which they are inserted. Whenever you reach the limit/capacity you can remove the first item.

answered Aug 06 '13 at 10:39

Haris Hasan

29,856
10
92
122

Ashok Damani · Answer 2 · 2013-08-06T12:58:32.503

3

or use an extension method :

EDIT :

because

latest added entry ends up being returned first.

so u can remove the first item like :

dictionary.Remove(dictionary.Last().Key);

& so your extension method is :

addExtension(this Dictionary<string, object> dictionary, string key, object value)
   {
        if(dictionary.Count == 50)
                dictionary.Remove(dictionary.Last().Key);  

        dictionary.Add(key, value);   
   }

edited Aug 06 '13 at 12:58

answered Aug 06 '13 at 10:55

Ashok Damani

3,896
4
30
48

Parametrized version: `static void AddExtension(this IDictionary dictionary, T key, V value) { dictionary.Add(key, value); if (dictionary.Count == 50) dictionary.Remove(dictionary.First().Key); }` – Aug 06 '13 at 11:03
Aren't you removing a random item from the `Dictionary`? The order of the items in a `Dictionary` isn't defined. Perhaps you could even be deleting the item you just added :-) See for example http://stackoverflow.com/a/4007787/613130 – xanatos Aug 06 '13 at 12:12
@AshokDamani Now at least you are removing a random element but you are sure it isn't the newly added :-) – xanatos Aug 06 '13 at 13:01

Alex Filipovici · Accepted Answer · 2013-08-06T11:32:14.297

Try this:

class Program
{
    static void Main(string[] args)
    {
        var rD = new RingDictionary(50);
        for (int i = 0; i < 75; i++)
        {
            rD.Add(i, i);
        }
        foreach (var item in rD.Keys)
        {
            Console.WriteLine("{0} {1}", item, rD[item]);
        }
    }
}

class RingDictionary : OrderedDictionary
{
    int indexKey;

    int _capacity = 0;
    public int Capacity
    {
        get { return _capacity; }
        set
        {
            if (value <= 0)
            {
                var errorMessage = typeof(Environment)
                    .GetMethod(
                        "GetResourceString",
                        System.Reflection.BindingFlags.Static |
                        System.Reflection.BindingFlags.NonPublic,
                        null,
                        new Type[] { typeof(string) },
                        null)
                    .Invoke(null, new object[] { 
                        "ArgumentOutOfRange_NegativeCapacity" 
                    }).ToString();
                throw new ArgumentException(errorMessage);
            }
            _capacity = value;
        }
    }

    public RingDictionary(int capacity)
    {
        indexKey = -1;
        Capacity = capacity;
    }

    public new void Add(object key, object value)
    {
        indexKey++;

        if (base.Keys.Count > _capacity)
        {
            for (int i = base.Keys.Count-1; i >Capacity-1 ; i--)
            {
                base.RemoveAt(i);
            }
        }

        if (base.Keys.Count == _capacity)
        {
            base.RemoveAt(indexKey % _capacity);
            base.Insert(indexKey % _capacity, key, value);
        }
        else
        {
            base.Add(key, value);
        }
    }
}

For better performance you shouldn't remove and insert values but overwrite old ones. Besides that I'll go your way. — Bitterblue, Aug 06 '13 at 11:57

C# - Dictionary with Behaviour of a Ring List?

3 Answers3