C# Sorted List by Value with Object

Question

I'm trying to create an "ordered" cache of objects in C#, where the order is determined by how many times that has been accessed.

I've looked into Dictionary, SortedList and SortedDictionary which were very close but don't quite have what I'm looking for.

I'd like to have a list which contains all the previously cached items, those items can have a getHits() method to determine what order the cached items should be in.

I can then access that cache by name and increase how many times an item has been viewed.

Simplified example (in Pseudo C#):

class Result {
  public int Hits = 0;
  public string Name = "";

  public void IncreaseHits() {
    this.hits++;
  }

  public Result(String name) {
    this.name = name;
  }
}

class Program {
  public MagicSortableType<string, Result> MyCache; //what structure to use?


  public main() {
    MyCache.Add(new Result("My result 1"));
    MyCache.Add(new Result("My result 2"));
    MyCache.Add(new Result("My result 3"));

    MyCache['My result 2'].IncreaseHits();
    MyCache['My result 2'].IncreaseHits();
    MyCache['My result 3'].IncreaseHits();

    MyCache.SortDesc(); //what is the real C# equivalent?

    foreach(Result result in MyCache) {
      Console.Write(result.Name + " - hits " + result.Hits);
    }
  }
}

Outputs:

My result 2 - hits 2
My result 3 - hits 1
My result 1 - hits 0

Answer 1

When I needed something like this, I created what I called an MruDictionary. It consisted of a LinkedList<T>, and a Dictionary<string, LinkedListNode<T>> (where T is the type of object, and the object key was type string).

Access is through the dictionary. When an item is accessed, it is moved to the head of the list. When an item is added, it's added to the head of the list. If the list size grows beyond the set maximum, the last node in the list is removed.

This worked very well. The items weren't kept in order by number of times used, but rather in strict MRU order. This typically kept the most often used items in the cache, but if there was a long period in which a popular item wasn't used, it would get flushed. For my purposes this worked very well.

I wrote an article about it. Full source with description is available at http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626.

It should be easy enough to add the hit count if you really need it.