I need a class that acts like a dictionary but will constrain the total number of key/value pairs it contains. For instance, let's say the maximum number of entries is 1000 and the class already contains 1000 key/value pairs. If I add an additional key/value pair, the class should remove the key-value pair that was updated least recently.

Here's my current implementation in python:

class SizeLimitedDefaultDict(defaultdict):
    last_changed = []

    def __init__(self, default, max_size, *args, **kwargs):
        max_size = 0
        super(SizeLimitedDict, self).__init__(default, *args, **kwargs)

    def __setitem__(self, key, val):
        if len(self) >= self.max_size:
            remove_oldest_entry()
        super.__setitem__(self, key, val)
        update_newest_entry(key)

    def update_newest_entry(self, key):
        key_index = last_changed.index(key) #will slow it down
        last_changed.insert(0, last_changed.pop(key_index))

This clearly isn't a viable solution. All the performance gains of the dictionary are lost. I'm having trouble figuring out a better solution though. Is there a data structure that can easily maintain which keys have been most recently updated.