Sorted Dictionary sorted on value in C# (LRU cache)

What you should do is keep two dictionaries, one sorted by time and one by keys.

Remember that dictionaries are only holding references to your actual objects, so which dictionary you use to update the object doesn't matter.

To update the object create a function that will update both the dictionaries

var oldObj = keyedObject[key];
timedObjects.Remove(oldObj.LastUpdateTime);
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject);
keyedObject[key] = myUpdatedObject;

Now you have track of the same object by both time and key.

I am keeping only one reference to an object in timedObjects. This helps while removing.

You can keep trimming your timedObjects dictionary as required.

Ofcource, while trimming you must bear in mind that there is another dictionary keyedObject that has reference to the same object. Merely calling Remove will not be enough.

Your remove code will have to be like this:

removeObject = timedObjects[timeToRemove];
timedObjects.Remove(timeToRemove);
keyedObject.Remove(removeObject.key);

timeToRemove will mostly come from a for loop, where you decide which object to remove