dictionary that discards old items

[Raymond Hettinger]

[Will McGugan]
> I need a collection class that behaves like a dictionary but when it
> reaches 'n' items it discards the oldest item so that the length never
> goes above 'n'. (Its for caching search results)


import collections

class Cache(dict):
    def __init__(self, n, *args, **kwds):
        self.n = n
        self.queue = collections.deque()
        dict.__init__(self, *args, **kwds)
    def __setitem__(self, k, v):
        self.queue.append(k)
        dict.__setitem__(self, k, v)
        if len(self) > self.n:
            oldk = self.queue.popleft()
            del self[oldk]

    #  . . .
    # make similar modifications to setdefault, __delitem__, fromkeys
    # and other mutating methods as needed

# Example
c = Cache(3)
for w in 'the quick brown fox jumped over the lazy dog'.split():
    c[w] = w[:1].upper()
    print repr(c)