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.
Efficient datastructure to create size-limited dictionary
algorithms;python;data structures