OrderedDict ordered by most recently used element

I've written a small cache class. It is based around a standard dict and also persists to disk. Since the size of the working system cache has now exceeded the system memory, I'd like to implement a mechanism to throw out results. To do so, I'd like to keep a score and throw out the least important elements. One way to do this is to use an OrderedDict and move all recently used element to the end and then I can throw out the elements from the front when cache exceeds a size.

To achieve this, I first need a dictionary that will keep recently used elements at one end and least recently used elements at the other. The Python docs have a couple of examples that are useful. I've created the class below. It immediately fails on the most basic operation - popitem().

class LastUpdatedOrderedDict(OrderedDict): def __setitem__(self, key, value): super().__setitem__(key, value) self.move_to_end(key) def popitem(self, last = True): return super().popitem(last=last) def __getitem__(self, key): value = super().__getitem__(key) self.move_to_end(key) return value

If one used the class above to execute the following code:

d = LastUpdatedOrderedDict({1: 'a', 2: 'b', 3: 'c'}) x = d.popitem() # Throws exception

it throws an exception:

File "/infra/test/test_caching.py", line 105, in test_LastUpdatedOrderedDict x = d.popitem() File "/home/infra/infra/caching.py", line 22, in popitem return super().popitem(last=last) File "/infra/infra/caching.py", line 26, in __getitem__ self.move_to_end(key) KeyError: 3

In particular, if one breaks in the __getitem__() method at like self.move_to_end(key), then the following behaviour can be observed:

key in self Out[4]: True key in self.keys() Out[5]: True self.keys() Out[6]: odict_keys([1, 2]) key in set(self.keys()) Out[7]: False

What is the best solution to resolve this? Clearly,popitem() calls dict.__getitem__() but it appears to be in some sort of half-way state when it comes to the keys.