How to remove the oldest element from a dictionary

Question

I would like to know the best way to remove the oldest element in a dictionary in order to control the maximum dictionary size.

example:

MAXSIZE = 4
dict = {}
def add(key,value):
  if len(dict) == MAXSIZE:
    old = get_oldest_key() # returns the key to the oldest item
    del dict[old]
  dict[key] = value

add('a','1') # {'a': '1'}
add('b','2') # {'a': '1', 'b': '2'}
add('c','3') # {'a': '1', 'c': '3', 'b': '2'}
add('d','4') # {'a': '1', 'c': '3', 'b': '2', 'd': '4'}
add('e','5') # {'c': '3', 'b': '2', 'e': '5', 'd': '4'}

Was this clear?

Edit: Forgot that len(dict) lags one item behind.

Answer 1

Without knowing what you're really trying to use this structure for, here's something that may work for you:

class DictCache:
    def __init__(self, maxcount=4):
        self.data = {}
        self.lru = []
        self.maxcount = maxcount
    def add(self, key, value):
        self.data[key] = value
        self.lru.append(key)
        if len(self.lru) > self.maxcount:
            dead = self.lru.pop(0)
            del(self.data[dead])

Combine this with a get method that rearranges self.lru when they are accessed, and you can change your caching strategy to suit your usecase.

Answer 2

Dictionaries don't preserve order, so you can't tell which element had been added first. You could combine the dictionary with a list of it's keys to preserve order.

Here's an activestate recipe for an ordered dict that does just this.

There's also PEP-0372 with this patch for an odict class.