Dictionary<> always sorted on value, lookup index from key

I need a dictionary (or any other collection) that stays always sorted by value and can be indexed by key开发者_JS百科. My purpose is to implement a cache where objects have a unique key and a metric associated to them. When a cache replacement has to be done objects with the least metric are removed. It needs to be as fast as possible, so to make a full ordering each time a replacement is done is not a good option. Any ideas? Thx

---

Something like this should work fine (not tested very much):

http://pastebin.com/eYeE33F5

---

It seams that priority queue is what you are looking for. There are good implementations of this class using binary heap. Example : http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

---

You can combine any kind of fast priority queue (look here: Priority queue in .Net) with a standard Dictionary to a new collection. When inserting a new element, insert a reference to the element into both containers. When looking for an element by "key", use the dictionary. When you are going to delete the element with the lowest "metric", use the priority queue to find it, get the key from the element itself, then it is easy to delete the element references from both containers.

---

Why don't you just keep the regular Dictionary. Now, whenever you need to do that cache replacement, that's the moment you select the element with the "minimum" value and replace it.

Edit - here is how you get the KeyPair with the minimum value. Just use the Key and Value properties after that:

var minValuePair = myDictionary.OrderBy(p => p .Value).First();

---

You want a dictionary that is sorted by Value but also has indexing by Key. You can't have your data arranged in two ways at once, so you will have to have two collections, your base key-value dictionary, and a reverse lookup dictionary. Your first one is a standard dictionary, your second one is a SortedDictionary with the same data and the keys and values swapped. You will have to keep the two in sync.

You could also write your own Dictionary implementation to encapsulate these two collections into one.