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.