I need a class that **acts like a dictionary but will constrain the total number of key/value pairs it contains.** For instants, 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.**